# Homomorphic encryption

*566*pages on

this wiki

**Homomorphic encryption** is a form of encryption where a specific algebraic operation is performed on the plaintext and another (possibly different) algebraic operation is performed on the ciphertext. Depending on one's viewpoint, this can be seen as either a positive or negative attribute of the cryptosystem. Homomorphic encryption schemes are malleable by design. The homomorphic property of various cryptosystems can be used to create secure voting systems,^{[1]} collision-resistant hash functions, and private information retrieval schemes.

There are several efficient, partially homomorphic cryptosystems, and two fully homomorphic, but less efficient cryptosystems.

## Partially homomorphic cryptosystemsEdit

In the following examples, the notation is used to denote the encryption of the message *x*.

### Unpadded RSAEdit

If the RSA public key is modulus and exponent , then the encryption of a message is given by . The homomorphic property is then

### ElGamalEdit

In the ElGamal cryptosystem, in a group , if the public key is , where , and is the secret key, then the encryption of a message is , for some . The homomorphic property is then

### Goldwasser-MicaliEdit

In the Goldwasser-Micali cryptosystem, if the public key is the modulus *m* and quadratic non-residue *x*, then the encryption of a bit *b* is . The homomorphic property is then

where denotes addition modulo 2, (i.e. exclusive-or).

### BenalohEdit

In the Benaloh cryptosystem, if the public key is the modulus *m* and the base *g* with a blocksize of *r*, then the encryption of a message *x* is . The homomorphic property is then

### PaillierEdit

In the Paillier cryptosystem, if the public key is the modulus *m* and the base *g*, then the encryption of a message *x* is . The homomorphic property is then

### Other partially homomorphic cryptosystemsEdit

- Okamoto-Uchiyama cryptosystem
- Naccache-Stern cryptosystem
- Damgård-Jurik cryptosystem
- Boneh-Goh-Nissim cryptosystem

## Fully homomorphic encryptionEdit

Each of the examples listed above allows homomorphic computation of only one operation (either addition or multiplication) on plaintexts. A cryptosystem which supports both addition and multiplication (thereby preserving the ring structure of the plaintexts) would be far more powerful. Using such a scheme, any circuit could be homomorphically evaluated, effectively allowing the construction of programs which may be run on encryptions of their inputs to produce an encryption of their output. Since such a program never decrypts its input, it could be run by an untrusted party without revealing its inputs and internal state. The existence of an efficient and fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing.^{[2]}

The "homomorphic" part of a fully homomorphic encryption scheme can also be described in terms of category theory. If *C* is the category whose objects are integers (i.e., finite streams of data) and whose morphisms are computable functions, then (ideally) a fully homomorphic encryption scheme elevates an encryption function to a functor from *C* to itself.

The utility of fully homomorphic encryption has been long recognized. The problem of constructing such a scheme was first proposed within a year of the development of RSA.^{[3]} A solution proved more elusive; for more than 30 years, it was unclear whether fully homomorphic encryption was even possible. During this period, the best result was the Boneh-Goh-Nissim cryptosystem which supports evaluation of an unlimited number of addition operations but at most one multiplication.

In 2009, Craig Gentry^{[4]} using lattice-based cryptography showed the first fully homomorphic encryption scheme as announced by IBM on June 25.^{[5]}^{[6]} His scheme supports evaluations of arbitrary depth circuits.
His construction starts from a *somewhat homomorphic* encryption scheme using ideal lattices that is limited to evaluating low-degree polynomials over encrypted data. (It is limited because each ciphertext is noisy in some sense, and this noise grows as one adds and multiplies ciphertexts, until ultimately the noise makes the resulting ciphertext indecipherable.) He then shows how to modify this scheme to make it *bootstrappable* -- in particular,
he shows that by modifying the somewhat homomorphic scheme slightly,
it can actually evaluate its own decryption circuit, a self-referential property.
Finally, he shows that any bootstrappable somewhat homomorphic encryption scheme can be converted into a fully homomorphic encryption through a recursive self-embedding.
In the particular case of Gentry's ideal-lattice-based somewhat homomorphic scheme,
the effect of this bootstrapping procedure is to "refresh" a ciphertext -- i.e., to reduce the noise associated to a ciphertext -- so that it can thereafter be used in more additions and multiplications without resulting in an indecipherable ciphertext.
Gentry based the security of his scheme on the assumed hardness of two problems -- certain worst-case problems over ideal lattices, and the sparse (or low-weight) subset sum problem.

Regarding performance, ciphertexts in Gentry's scheme remain compact -- that is, their length does not depend at all on the complexity of the function that is evaluated over the encrypted data. The computational time only depends linearly on the number of operations performed. However, the scheme is impractical for many applications, because ciphertext size and computation time increase sharply as one increases the security level. To obtain 2^{k} security against known attacks, the computation time and ciphertext size are high-degree polynomials in *k*. Recently, Stehle and Steinfeld reduced the dependence on *k* substantially.^{[7]}
They presented optimizations that permit the computation to be only quasi-*k*^{3.5} per boolean gate of the function being evaluated.

Gentry's Ph.D. thesis^{[8]}
provides additional details.
Gentry also published a high-level overview of the van Dijk et al. construction (described below) in the March 2010 issue of Communications of the ACM.^{[9]}

In 2009, Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan presented a second fully homomorphic encryption scheme,^{[10]}
which uses many of the tools of Gentry's construction,
but which does not require ideal lattices.
Instead, they show that the somewhat homomorphic component of Gentry's scheme (which uses ideal lattices) can be replaced with a very simple somewhat homomorphic scheme that uses integers.
The scheme is therefore conceptually simpler than Gentry's ideal lattice scheme, but has similar properties with regards to homomorphic operations and efficiency.
The somewhat homomorphic component in the work of van Dijk et al. is similar to an encryption scheme
proposed by Levieil and Naccache in 2008,^{[11]} and also to one that was proposed by Bram Cohen in 1998.^{[12]}
Cohen's method is not even additively homomorphic, however. The Levieil-Naccache scheme is additively homomorphic, and can be modified to support also a small number of multiplications.

In 2010, Nigel P. Smart and Frederik Vercauteren presented a refinement of Gentry's scheme giving smaller key and ciphertext sizes, but which is still not fully practical.^{[13]} At the rump session of Eurocrypt 2010, Craig Gentry and Shai Halevi presented a working implementation of fully homomorphic encryption -- that is, an implementation of the entire bootstrapping procedure -- together with performance numbers.^{[14]}

## ReferencesEdit

- ↑ Template:Cite web
- ↑ Template:Cite web
- ↑ R. L. Rivest, L. Adleman, and M. L. Dertouzos. On data banks and privacy homomorphisms. In
*Foundations of Secure Computation*, 1978. - ↑
Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In
*the 41st ACM Symposium on Theory of Computing (STOC)*, 2009. - ↑ http://www-03.ibm.com/press/us/en/pressrelease/27840.wss
- ↑ Template:Cite web
- ↑ Template:Cite web
- ↑ Template:Cite web
- ↑ Template:Cite web
- ↑ Template:Cite web
- ↑ Template:Cite web
- ↑ Template:Cite web
- ↑ News report paper pdf slides
- ↑ Template:Cite web