Fully Homomorphic Encryption
Fully homomorphic encryption allows to evaluate an arbitrary
circuit C (or a program) on an input x_1,..., x_n although one only
receives an encrypted input Enc(C, x_1,..., x_n). The evaluation
yields the encryption of C on input (x_1,..., x_n), i.e.,
c' = Enc(C(x_1,..., x_n)), where the size of c' does not depend on the size of the circuit C.
Depending on C, fully homomorphic encryption allows to
realize different functionalities like multiparty computation, private
information retrieval, search on encrypted data, web services and
obfuscation. These functionalities are useful in ubiquitous
computation scenarios where data from different
sources like sensors, mobile devices or PCs are processed on non-trusted servers in the cloud. Fully homomorphic encryption thereby ensures private processing of the data, which is often mandatory, e.g., for medical data.
In 2009, Gentry introduced the first realization of a fully homomorphic
public-key crypto system. Naturally, a scheme as powerful as fully homomorphic encryption requires strong complexity assumptions. For realizing the full functionality, Gentry had to assume the existence of circular encryption, where a secret key can securely be encrypted under its own public key, and the hardness of a very low weight subset sum problem, which allowed for the so-called squashing of the decryption circuit.
The main research challenges are now to find the minimal requirements under which fully homomorphic encryption schemes can be realized, which in turn would maximize the efficiency of the schemes. For instance, it is not clear whether circular encryption follows from standard notions as CPA security, or whether there exist (pathological) cryptosystems that are CPA secure, but do not offer circular security.
Moreover, is the complexity assumption on low weight subset sum really necessary? Or on the cryptanalytic side, do their exist efficient ways to solve subset sums of very low weight?
Publications
Jake Loftus, Alexander May, Nigel P. Smart, Frederik Vercauteren
"On CCA-Secure Fully Homomorphic Encryption", International Workshop on Selected Areas in Cryptography (SAC 2011)