We all know about Gentry’s breakthrough this past year where he showed the first construction of a fully homomorphic encryption scheme. Gentry’s scheme is hard to understand and seems challenging to implement, and was/is viewed as a feasibility result only.
More recently, two new fully homomorphic encryption schemes have been proposed, by van Dijk, Gentry, Halevi, and Vaikuntanathan and Smart and Vercauteren. No paper is available for the first one, but the abstract explicitly claims conceptual simplicity. As for the second, a paper (with implementation results!) is available; I have not yet read the paper, but they claim that their scheme can be viewed as a generalization of Gentry’s scheme to algebraic number fields.
I was asked recently whether fully homomorphic encryption would become remotely practical within the next 10 years. While it’s still too early to say for sure, the fact that there are (at least) two relatively quick improvements to the original scheme gives hope.
it is really exciting to see that arithmetic operations on ciphertexts are indeed doable.
Interesting to see that though the problem was actually very old, we are experiencing many improvements just recently and almost at the same time.
By: osmugus on December 1, 2009
at 2:57 pm
From scanning the Smart-Vercauteren paper, it looks like any realistic version of the scheme can handle depth-2 circuits before causing decryption error. (On larger security parameters, the keygen procedure never terminated with an output). The corresponding decryption circuits are depth 4 or 5 — I can’t tell if the final NAND gate is included in that count — which is oh-so-close-but-so-far from what’s needed for full homomorphism. Tantalizing!
By: Chris Peikert on December 1, 2009
at 4:00 pm
I will attend Vercauteren’s seminar in Tokyo Tech tomorrow.
Brief reading tells that it is a specialization of Gentry’s scheme and has very efficient operations except key generations and encryptions
On the latter problem, I think it will be improved by algorithmic algebra community.
By: xagawa on December 2, 2009
at 3:40 am
van Dijk, Gentry, Halevi, and Vaikuntanathan’s eprint is now available:
http://eprint.iacr.org/2009/616
By: Eleanor Rieffel on December 15, 2009
at 3:32 pm