# What is the mathematical process behind fully homomorphic encryption?

I've often wondered about how to compute encrypted data, and appears that a "hack" to do so has been found: http://www.technologyreview.com/computing/37197/

Is anyone able to offer an better, yet still "simple" explanation of how Craig Gentry's approach is possible?

-
Do you mean doubly-homomorphic? Singly-homomorphic algorithms are well-known (e.g. RSA). – Dan Brumleve May 28 '11 at 2:02
@Dan Brumleve: Not 100% sure to be honest, but yes, I'd wondered the same thing. Believe this is the guy's thesis on the topic crypto.stanford.edu/craig/craig-thesis.pdf – blunders May 28 '11 at 2:11
This was suggested as a solution to one of my questions here on math.SE math.stackexchange.com/questions/2968/mental-card-game/… – Dan Brumleve May 28 '11 at 2:58
You should check Wikipedia's page Homomorphic_encryption#Fully_homomorphic_encryption and Section 1.1 in Gentry's thesis, titled "A Very Brief and Informal Overview of Our Construction." – user2468 May 28 '11 at 4:54
+1 @M.S.: Thanks, agree that info was of use, though still missing the "simple" answer, or at least I missed it if it was present... :-) – blunders May 28 '11 at 13:42

A simple explanation would be to imagine a bijective function $f_k: \mathbb{Z} \to \mathbb{Z}$ that depends upon a key $k$, such that $f_k(n)\pm f_k(m)=f_k(n\pm m)$ and similarly for multiplication and whatever other operations are embedded in the processor. Then I can send an insecure computer my program and encrypted data, it can do the computation and return the encrypted result, which I can decrypt. Each individual step along the way, it has the encrypted value of what I would get on my processor without encryption. I still need to convince myself that the computation was done correctly, but one can imagine embedding simple checks like $2+2=4$. Not that I have such a function-if so I would have Gentry's PhD.