3
$\begingroup$

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?

  • 0
    +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... :-)2011-05-28

1 Answers 1

1

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.

  • 0
    @blunders: You keep the key secret and only send the outside computer the encrypted data. Because the encryption is respected by the computation the outside computer need not decode it, just perform the same computation you want done on the encrypted values. The solution comes back encrypted by the same key, so you decrypt it and get your answer.2011-05-28