Re:An open-source fully homomorphic encryption library
by Cyranix on Tuesday April 30, 2013 @11:33AM
(#5632725)
> can't be evaluated in any reasonable time
I gave the same statement to a coworker who inquired about fully homomorphic encryption, but I didn't have the data to back it up. Can someone help me find performance numbers relevant to this library, or at least a recent comparable implementation?
Re:An open-source fully homomorphic encryption library
by bradleyjg on Tuesday April 30, 2013 @12:03PM
(#5632981)
I don't see benchmarks for this particular implimentation yet, but the readme references the Gentry-Halevi-Smart optimizations as an inspiration. That paper Homomorphic Evaluation of the AES Circuit (http://eprint.iacr.org/2012/099.pdf), discusses three FHE methods of computing AES-128. The fastest disclosed implementation has an amortized run time (on a beast of a machine -- 18MB cache, 256GB RAM) of around 19 seconds per byte. In contrast some CPU have native instructions that can run AES-128 on the order of cycles per byte. So we are roughly talking a 10 billion fold slowdown.
Re:An open-source fully homomorphic encryption library
by bhitov on Tuesday April 30, 2013 @01:19PM
(#5633537)
I thought the Gentry method solved the problem of enormous cyphertexts (via 'bootstrapping') while still preserving addition and multiplication operations. Is that not true?
Re:An open-source fully homomorphic encryption library
by bradleyjg on Wednesday May 01, 2013 @01:24PM
(#5639324)
Sure but that method just trades time for space. Later work did reduce the overall complexity by substituting different "hard problems" as the cryptographic primitive, but it's still in the realm of unusable scaling characteristics.
On the other hand, so far as I know, no one has published any papers that suggest a fundamental barrier to improvement. Here's hoping!
As a practical matter conplext transforms tend to produce enormous cyphertexts that can't be evaluated in any reasonable time. Which is why a lot of the cutting edge work is in renormalizing, even at the cost of restricting operations (thus somewhat rather than fully homomorphic).