Posted by: jonkatz | December 1, 2009

(More) fully homomorphic encryption?

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.



  1. 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.

  2. 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!

  3. 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.

  4. van Dijk, Gentry, Halevi, and Vaikuntanathan’s eprint is now available:

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s


%d bloggers like this: