Homomorphic encryption

Homomorphic encryption is a form of encryption that allows computations to be carried out on ciphertext, thus generating an encrypted result which, when decrypted, matches the result of operations performed on the plaintext.

This is sometimes a desirable feature in modern communication system architectures. Homomorphic encryption would allow the chaining together of different services without exposing the data to each of those services. For example, a chain of different services from different companies could calculate 1) the tax 2) the currency exchange rate 3) shipping, on a transaction without exposing the unencrypted data to each of those services.^[1] Homomorphic encryption schemes are malleable by design. This enables their use in cloud computing environment for ensuring the confidentiality of processed data. In addition the homomorphic property of various cryptosystems can be used to create many other secure systems, for example secure voting systems,^[2] collision-resistant hash functions, private information retrieval schemes, and many more.

There are several partially homomorphic crypto-systems, and also a number of fully homomorphic crypto-systems. Although a crypto-system which is unintentionally malleable can be subject to attacks on this basis, if treated carefully homomorphism can also be used to perform computations securely.

Partially homomorphic cryptosystems

In the following examples, the notation $\mathcal{E}(x)$ is used to denote the encryption of the message x.

Unpadded RSA

If the RSA public key is modulus $m$ and exponent $e$, then the encryption of a message $x$ is given by $\mathcal{E}(x) = x^e \;\bmod\; m$. The homomorphic property is then

$\mathcal{E}(x_1) \cdot \mathcal{E}(x_2) = x_1^e x_2^e \;\bmod\; m = (x_1x_2)^e \;\bmod\; m = \mathcal{E}(x_1 \cdot x_2)$

ElGamal

In the ElGamal cryptosystem, in a cyclic group $G$ of order $q$ with generator $g$, if the public key is $(G, q, g, h)$, where $h = g^x$, and $x$ is the secret key, then the encryption of a message $m$ is $\mathcal{E}(m) = (g^r,m\cdot h^r)$, for some random $r \in \{0, \ldots, q-1\}$. The homomorphic property is then

$\begin{align} & \mathcal{E}(m_1) \cdot \mathcal{E}(m_2) = (g^{r_1},m_1\cdot h^{r_1})(g^{r_2},m_2 \cdot h^{r_2}) \\[6pt] = {} & (g^{r_1+r_2},(m_1\cdot m_2) h^{r_1+r_2}) = \mathcal{E}(m_1 \cdot m_2). \end{align}$

Goldwasser–Micali

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 $\mathcal{E}(b) = x^b r^2 \;\bmod\; m$, for some random $r \in \{0, \ldots, m-1\}$. The homomorphic property is then

$\mathcal{E}(b_1)\cdot \mathcal{E}(b_2) = x^{b_1} r_1^2 x^{b_2} r_2^2 \;\bmod\; m = x^{b_1+b_2} (r_1r_2)^2 \;\bmod\; m = \mathcal{E}(b_1 \oplus b_2)$

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

Benaloh

In the Benaloh cryptosystem, if the public key is the modulus m and the base g with a blocksize of c, then the encryption of a message x is $\mathcal{E}(x) = g^x r^c \;\bmod\; m$, for some random $r \in \{0, \ldots, m-1\}$. The homomorphic property is then

$\mathcal{E}(x_1) \cdot \mathcal{E}(x_2) \;\bmod\; m = (g^{x_1} r_1^c)(g^{x_2} r_2^c) \;\bmod\; m = g^{x_1+x_2} (r_1r_2)^c = \mathcal{E}(x_1 + x_2 \;\bmod\; m )$

Paillier

In the Paillier cryptosystem, if the public key is the modulus m and the base g, then the encryption of a message x is $\mathcal{E}(x) = g^x r^m \;\bmod\; m^2$, for some random $r \in \{0, \ldots, m-1\}$. The homomorphic property is then

$\mathcal{E}(x_1) \cdot \mathcal{E}(x_2) = (g^{x_1} r_1^m)(g^{x_2} r_2^m) \;\bmod\; m^2 = g^{x_1+x_2} (r_1r_2)^m \;\bmod\; m^2 = \mathcal{E}( x_1 + x_2 \;\bmod\; m^2)$

Other partially homomorphic cryptosystems

• Okamoto–Uchiyama cryptosystem
• Naccache–Stern cryptosystem
• Damgård–Jurik cryptosystem
• Boneh–Goh–Nissim cryptosystem
• Ishai-Paskin cryptosystem

Fully homomorphic encryption

The examples listed above allow homomorphic computation of some operations on ciphertexts (e.g., additions, multiplications, quadratic functions, etc.). A cryptosystem that supports arbitrary computation on ciphertexts is known as fully homomorphic encryption (FHE) and is far more powerful. Such a scheme enables the construction of programs for any desirable functionality, which can be run on encrypted inputs to produce an encryption of the result. Since such a program need never decrypt its inputs, it can 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.^[3]

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.^[4] A solution proved more elusive; for more than 30 years, it was unclear whether fully homomorphic encryption was even possible. During that period, partial results included the Boneh–Goh–Nissim cryptosystem that supports evaluation of an unlimited number of addition operations but at most one multiplication,^[5] and the Ishai-Paskin cryptosystem that supports evaluation of (polynomial-size) Branching program.^[6]

Early homomorphic cryptosystems

Gentry's cryptosystem

Craig Gentry described the first plausible construction for a fully homomorphic encryption scheme.

Craig Gentry^[7] using lattice-based cryptography, described the first plausible construction for a fully homomorphic encryption scheme. Gentry's scheme supports both addition and multiplication operations on ciphertexts, from which it is possible to construct circuits for performing arbitrary computation.

The construction starts from a somewhat homomorphic encryption scheme, which 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.) Gentry then shows how to slightly modify this scheme to make it bootstrappable, i.e., capable of evaluating its own decryption circuit and then at least one more operation. Finally, he shows that any bootstrappable somewhat homomorphic encryption scheme can be converted into a fully homomorphic encryption through a recursive self-embedding. For Gentry's "noisy" scheme, the bootstrapping procedure effectively "refreshes" the ciphertext by applying to it the decryption procedure homomorphically, thereby obtaining a new ciphertext that encrypts the same value as before but has lower noise. By "refreshing" the ciphertext periodically whenever the noise grows too large, it is possible to compute arbitrary number of additions and multiplications without increasing the noise too much. 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. Gentry's Ph.D. thesis^[8] provides additional details.

Regarding performance, ciphertexts in Gentry's scheme remain compact insofar as their lengths do not depend at all on the complexity of the function that is evaluated over the encrypted data, but the scheme is impractical, and its ciphertext size and computation time increase sharply as one increases the security level. Several optimizations and refinements were proposed by Damien Stehle and Ron Steinfeld,^[9] Nigel Smart and Frederik Vercauteren,^[10][11] and Craig Gentry and Shai Halevi,^[12][13] the latter obtaining the first working implementation of Gentry's fully homomorphic encryption.

Cryptosystem over the integers

In 2010, Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan presented a second fully homomorphic encryption scheme,^[14] 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 ideal lattice-based scheme 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^[15] , and also to one that was proposed by Bram Cohen in 1998.^[16] Cohen's method is not even additively homomorphic, however. The Levieil–Naccache scheme supports only additions, but it can be modified to also support a small number of multiplications. Many refinements and optimizations of the scheme of van Dijk et al. were proposed in a sequence of works by Jean-Sébastien Coron, Tancrède Lepoint, Avradip Mandal, David Naccache, and Mehdi Tibouchi.^{[17][18][19][20]} Some of these works included also implementations of the resulting schemes.

The 2nd generation of homomorphic cryptosystems

Several new techniques that were developed starting in 2011-2012 by Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan, and others, led to the development of much more efficient somewhat and fully homomorphic cryptosystems. These include:

• The Brakerski-Gentry-Vaikuntanathan cryptosystem (BGV),^[21] building on techniques of Brakerski-Vaikuntanathan.^[22]
• Brakerski's scale-invariant cryptosystem.^[23]
• The NTRU-based cryptosystem due to Lopez-Alt, Tromer, and Vaikuntanathan (LTV).^[24]
• The Gentry-Sahai-Waters cryptosystem (GSW).^[25]

The security of most of these schemes is based on the hardness of the Learning with errors problem, except for the LTV scheme whose security is based on a variant of the NTRU computational problem. The distinguishing characteristic of these cryptosystems is that they all feature much slower growth of the noise during the homomorphic computations. Additional optimizations by Craig Gentry, Shai Halevi, and Nigel Smart resulted in cryptosystems with nearly optimal asymptotic complexity: Performing $T$ operations on data encrypted with security parameter $k$ has complexity of only $T\cdot\mathrm{polylog}(k)$.^[26][27][28] These optimizations build on the Smart-Vercauteren techniques that enables packing of many plaintext values in a single ciphertext and operating on all these plaintext values in a SIMD fashion.^[11] Many of the advances in these second-generation cryptosystems were also ported to the cryptosystem over the integers.^[19][20]

Zvika Brakerski and Vinod Vaikuntanathan observed that for certain types of circuits, the GSW cryptosystem features an even slower growth rate of noise, and hence better efficiency and stronger security.^[29] Jacob Alperin-Sheriff and Chris Peikert then described a very efficient bootstrapping technique that uses exactly this type of circuits^[30] This type of circuits, however, seems incompatible with the ciphertext-packing techniques, and hence the Gentry-Halevi-Smart optimizations^[26] cannot be applied here.

All the second-generation cryptosystems still follow the basic blueprint of Gentry's original construction, namely they first construct a somewhat-homomorphic cryptosystem that handles noisy ciphertexts, and then convert it to a fully homomorphic cryptosystem using bootstrapping.

Implementations

The first reported implementation of fully homomorphic encryption is the Gentry-Halevi implementation mentioned above of Gentry's original cryptosystem,^[13] they reported timing of about 30 minutes per basic bit operation. The second-generation schemes made this implementation obsolete, however.

Many implementations of second-generation somewhat-homomorphic cryptosystems were reported in the literature. An early implementation from 2012 due to Gentry, Halevi, and Smart (GHS)^[28] of a variant of the BGV cryptosystem,^[21] reported evaluation of a complex circuit (implementing the encryption procedure of the AES cipher) in 36 hours. Using the packed-ciphertext techniques, that implementation could evaluate the same circuit on 54 different inputs in the same 36 hours, yielding amortized time of roughly 40 minutes per input. This AES-encryption circuit was adopted as a benchmark in several follow-up works,^[19][31][32] gradually bringing the evaluation time down to about four hours and the per-input amortized time to just over 7 seconds.

Two implementations of second-generation homomorphic cryptosystems are available in open source libraries: The HElib library^[33] due to Shai Halevi and Victor Shoup that implements the BGV cryptosystem with the GHS optimizations, and the FHEW library^[34] due to Leo Ducas and Daniele Micciancio that implements a combination of Regev's LWE cryptosystem with the bootstrapping techniques of Alperin-Sheriff and Peikert.^[30] Both libraries implement fully homomorphic encryption including bootstrapping. HElib reports time of 5–10 minutes for bootstrapping a packed ciphertext with about 1000 plaintext values,^[35] and FHEW reports time of around 1/2 second for bootstrapping a non-packed ciphertext encrypting a single bit.^[36] In late-2014, a re-implementation of homomorphic evaluation of the AES-encryption circuit using HElib, reported evaluation time of just over four minutes on 120 inputs, bringing the amortized per-input time to about 2 seconds^[33]

See also

• Homomorphic signatures for network coding
• Verifiable computing using a fully homomorphic scheme
• Client-side encryption
• Secure multi-party computation

References

1. Craig Stuntz (2010-03-18). "What is Homomorphic Encryption, and Why Should I Care?".
2. Ron Rivest (2002-10-29). "Lecture Notes 15: Voting, Homomorphic Encryption" (PDF).
3. Daniele Micciancio (2010-03-01). "A First Glimpse of Cryptography's Holy Grail". Association for Computing Machinery. p. 96. Retrieved 2010-03-17.
4. R. L. Rivest, L. Adleman, and M. L. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, 1978.
5. D. Boneh, E. Goh, and K. Nissim. Evaluating 2-DNF Formulas on Ciphertexts. In Theory of Cryptography Conference, 2005.
6. Y. Ishai and A. Paskin. Evaluating branching programs on encrypted data. In Theory of Cryptography Conference, 2007.
7. Craig Gentry. Fully Homomorphic Encryption Using Ideal Lattices. In the 41st ACM Symposium on Theory of Computing (STOC), 2009.
8. Craig Gentry. "A Fully Homomorphic Encryption Scheme (Ph.D. thesis)" (PDF).
9. Stehle, Damien; Steinfeld, Ron. "Faster Fully Homomorphic Encryption". Asiacrypt 2010 (Springer).
10. Smart, Nigel P.; Vercauteren, Frederik. "Fully homomorphic encryption with relatively small key and ciphertext sizes". PKC 2010 (Springer).
11. Smart, Nigel P.; Vercauteren, Frederik (2014). "Fully Homomorphic SIMD Operations". Designs, Codes and Cryptography (Springer) 71 (1): 57–81.
12. Gentry, Craig; Halevi, Shai. "Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits". FOCS 2011 (IEEE).
13. Gentry, Craig; Halevi, Shai. "Implementing Gentry's fully-homomorphic encryption scheme". EUROCRYPT 2011 (Springer).
14. Marten, van Dijk; Gentry, Craig; Halevi, Shai; Vinod, Vaikuntanathan. "Fully Homomorphic Encryption over the Integers". EUROCRYPT 2010 (Springer).
15. Levieil, Eric; Naccache, David. "Cryptographic Test Correction" (PDF).
16. Cohen, Bram. "Simple Public Key Encryption".
17. Coron, Jean-Sébastien; Naccache, David; Tibouchi, Mehdi. "Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers". EUROCRYPT 2012 (Springer).
18. Coron, Jean-Sébastien; Mandal, Avradip; Naccache, David; Tibouchi, Mehdi. "Fully Homomorphic Encryption over the Integers with Shorter Public Keys". CRYPTO 2011 (Springer).
19. Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi. "Batch Fully Homomorphic Encryption over the Integers". EUROCRYPT 2013 (Springer).
20. Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi. "Scale-Invariant Fully Homomorphic Encryption over the Integers". PKC 2014 (Springer).
21. Z. Brakerski, C. Gentry, and V. Vaikuntanathan. Fully Homomorphic Encryption without Bootstrapping. In ITCS 2012
22. Z. Brakerski and V. Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In FOCS 2011 (IEEE)
23. Z. Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In CRYPTO 2012 (Springer)
24. A. Lopez-Alt, E. Tromer, and V. Vaikuntanathan. On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption. In STOC 2012 (ACM)
25. C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO 2013 (Springer)
26. C. Gentry, S. Halevi, and N. P. Smart. Fully Homomorphic Encryption with Polylog Overhead. In EUROCRYPT 2012 (Springer)
27. C. Gentry, S. Halevi, and N. P. Smart. Better Bootstrapping in Fully Homomorphic Encryption. In PKC 2012 (SpringeR)
28. C. Gentry, S. Halevi, and N. P. Smart. Homomorphic Evaluation of the AES Circuit. In CRYPTO 2012 (Springer)
29. Z. Brakerski and V. Vaikuntanathan. Lattice-Based FHE as Secure as PKE. In ITCS 2014
30. J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer)
31. Y. Doroz, Y. Hu, and B. Sunar. Homomorphic AES Evaluation using NTRU. In Financial Cryptography 2014
32. Wei Dai; Yarkin Doroz; Berk Sunar. "Accelerating NTRU based Homomorphic Encryption using GPUs".
33. Shai Halevi; Victor Shoup. "HElib: An Implementation of homomorphic encryption". Retrieved 31 December 2014.
34. Leo Ducas; Daniele Micciancio. "FHEW: A Fully Homomorphic Encryption library". Retrieved 31 December 2014.
35. Halevi, Shai; Shoup, Victor. "Bootstrapping for HElib". Cryptology ePrint archive. Retrieved 2 January 2015.
36. Ducas, Léo; Micciancio, Daniele. "FHE Bootstrapping in less than a second". Cryptology ePrint archive. Retrieved 2 January 2015.

External links

• The Swiss Army Knife of Cryptography
• Homomorphic encryption in Cryptology Pointers
• American Scientist article, September 2012
• The Homomorphic Encryption Project
• The Open Source hcrypt Project
• HElib, open source homomorphic encryption library for C++
• FHEW, open source homomorphic encryption library for C and C++