[Cryptography] A naive question about fully homomorphic encryption

[Charlie Kaufman]

"Fully Homomorphic Encryption" is all the rage in academic communities, and
there is general consensus that it's performance is unacceptable except in
certain special cases, but it's also true that lots of people are coming up
with new mechanisms to speed it up - both in general and in the form of
finding more special cases.

 

I'm trying to figure out what the performance penalty is in the most general
case, and in particular whether that performance penalty is bounded or
unbounded. In other words, could I do anything I wanted if I were willing to
pay - say - a 2^64 performance penalty, or are there some calculations whose
performance penalty would be larger than that.

 

I imagine the following as a "proof of principle" Turing-machine sort of
computational engine:

 

1)      Given the encryption key K, I can encrypt a single bit (0 or 1) and
get an encrypted quantity X bits long.

2)      Given the encryption key K and any value X bits long, I can decrypt
and get either 0, 1, or "invalid" (where if the value was generated by an
encrypt operation, I'll get back the value I encrypted).

3)      Without knowing the encryption key K, but given two validly
encrypted values A and B - each X bits long - I can compute a third value C
this is a validly encrypted representation of A NAND B.

 

If I had these primitives, I believe I could compute any computable quantity
without knowing the encryption key, and I could measure the performance of
the system according to how big X is, how long it takes to do the
computation of step 3, and to a lesser degree how long the encryption and
decryption operations take.

 

Is the state of the art in Homomorphic Encryption such that a simple system
like the above possible? If so, what is the required size of X and how long
do each of the operations take?

 

                --Charlie

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140819/1e655c67/attachment.html>