Encryption schemes that support operations on encrypted data (e.g., homomorphic encryption) are very useful for secure computation.
A homomorphic encryption scheme is one wherein one or more operations (e.g., addition, multiplication) performed on two or more ciphertexts translate to the decrypted plaintexts (i.e., the decryption of the ciphertexts). For example, an encryption scheme may be said to be additively homomorphic if the decryption of the sum of the ciphertexts (C1+C2) yields the sum of the corresponding plaintexts (B1+B2) (possibly modulo a value): dec(C1+C2)→B1+B2. Many public-key cryptosystems support either addition of multiplication of encrypted data, but obtaining both at the same time appears to be more difficult.
It is known that computing arbitrary functions on encrypted data can be implemented, e.g., using Yao's “garbled circuit” technique [16, 12], but the size of the ciphertext and complexity of decryption grow at least linearly with the number of gates in the circuit being computed. Also, Sander et al. [15] described a technique that permits evaluation of arbitrary circuits, but the ciphertext size grows exponentially with the circuit depth. Both of these methods can be implemented using only “general hardness assumptions” (e.g., the existence of two-flow Oblivious-Transfer protocols etc.).
Boneh, Goh, and Nissim described a cryptosystem that permitted arbitrary number of additions and one multiplication, without growing the ciphertext size [5]. This scheme is referred to herein as the BGN cryptosystem. Security of the BGN cryptosystem is based on the subgroup-membership problem in composite-order groups that admit bilinear maps. This cryptosystem immediately implies an efficient protocol for evaluating 2-disjunctive normal form (2DNF) formula (or more generally bilinear forms). Boneh et al. also described applications of the BGN cryptosystem to improving the efficiency of private information retrieval schemes (PIR) and for a voting protocol.
More recently, Aguilar Melchor, Gaborit, and Herranz described in [2] a “template” for converting some additively homomorphic encryption into a cryptosystem that permits both additions and multiplications. They show how to use this template to combine the BGN cryptosystem with the cryptosystem of Kawachi et al. [11], thus obtaining a cryptosystem that supports two multiplications and arbitrary additions, based on the hardness of both the subgroup membership problem and the unique-shortest vector problem in lattices. They also show how to use this template with the cryptosystem of Aguilar Melchor et al. [1] in order to obtain unlimited multiplication depth, where the ciphertext size grows exponentially with the multiplication depth but additions are supported without increasing the size. (Security of this last realization is based on a relatively unstudied hardness assumption, called the “Differential Knapsack Vector Problem.”)
It is known that one can construct additively homomorphic encryption schemes from lattices or linear codes. Ciphertexts implicitly contain an “error” that grows as ciphertexts are operated on together (e.g., added, multiplied). Thus, the resulting ciphertexts do not have the same distribution as the original ciphertexts (e.g., as decrypted individually), and at some point the error may become large enough to cause incorrect decryption. For this reason, in such cases the homomorphism is sometimes referred to as a “pseudohomomorphism” or a “bounded homomorphism.”
Very recently, Gentry described a fully homomorphic cryptosystem [9], supporting polynomially many additions and multiplications without increasing the ciphertext size, with security based on the hardness of finding short vectors in ideal lattices [8].
USPTO Backgrounds
USPTO Backgrounds