Cryptography Research       


 Shai Halevi photoTal  Rabin photo

Cryptography Research - Homomorphic Encryption

What if you want to query a search engine, but don't want to tell the search engine what you are looking for?  You might consider encrypting your query, but if you use an ordinary encryption scheme, the search engine will not be able to manipulate your ciphertexts to construct a meaningful response.  What you would like is a cryptographic equivalent of a photograph developer's "dark room", where the search engine can process your query intelligently without ever seeing it.

Or, what if you want to store your data on the internet, so that you can access it at your convenience?  You want your data to remain private, even from the server that is storing them; so, you store your data in encrypt form.  But you would also like to be able to access your data intelligently -- e.g., you would like the server to be able to return exactly those files containing the word `homomorphic' within five words of `encryption'.  Again, you would like the server to be able to "process" your data while it remains encrypted.

A "fully homomorphic" encryption scheme creates exactly this cryptographic dark room.  Using it, anyone can manipulate ciphertexts that encrypt data under some public key pk to construct a ciphertext that encrypts *any desired function* of that data under pk.  Such a scheme is useful in the settings above (and many others).

In 2009, Gentry proposed the first efficient fully homomorphic encryption scheme.  It is efficient in the sense that all algorithms run in time polynomial in the security parameter and the size of the function f that you are computing, and the size output ciphertext grows only linearly with the size of f's output (which is the best you can hope for).  Although all algorithms run in polynomial time, there is still work to be done to make it truly practical.

Members of the group are very active in investigating new forms of homomorphic encryption and also in implementations to test its practical applicability.

C Gentry, S Halevi, Implementing Gentry’s Fully-Homomorphic Encryption Scheme , Advances in Cryptology--EUROCRYPT 2011, Springer.

C Gentry, S Halevi, V Vaikuntanathan, i-hop homomorphic encryption and rerandomizable Yao circuits, Advances in Cryptology--CRYPTO 2010, Springer.

C Gentry, Toward basing fully homomorphic encryption on worst-case hardness, Advances in Cryptology--CRYPTO 2010, Springer.

C.Gentry, S.Halevi, V.Vaikuntanathan Fully Homomorphic Encryption over the Integers. To appear at EUROCRYPT'10.

Craig Gentry. Fully homomorphic encryption using ideal lattices. STOC 2009: 169-178