Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Very possible I'm miss understanding your answer, but if the key gives the function the true values of the input, then the a the system running the function would know the values. Whole point I believe is for it to be possible to have calculations done on encrypted values. Am I missing something? Thanks! –  blunders May 28 '11 at 13:39
    
@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. –  Ross Millikan May 28 '11 at 15:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.