Homomorphic encryption

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Homomorphic encryption is a form of encryption that allows computation on ciphertexts, generating an encrypted result which, when decrypted, matches the result of the operations as if they had been performed on the plaintext.

Homomorphic encryption can be used for privacy-preserving outsourced storage and computation. This allows data to be encrypted and out-sourced to commercial cloud environments for processing, all while encrypted. In highly regulated industries, such as health care, homomorphic encryption can be used to enable new services by removing privacy barriers inhibiting data sharing. For example, predictive analytics in health care can be hard to apply due to medical data privacy concerns, but if the predictive analytics service provider can operate on encrypted data instead, these privacy concerns are diminished.

Description[edit]

Homomorphic encryption is a form of encryption with an additional evaluation capability for computing over encrypted data without access to the secret key. The result of such a computation remains encrypted. Homomorphic encryption can be viewed as an extension of either symmetric-key or public-key cryptography. Homomorphic refers to homomorphism in algebra: the encryption and decryption functions can be thought as homomorphisms between plaintext and ciphertext spaces.

Homomorphic encryption includes multiple types of encryption schemes that can perform different classes of computations over encrypted data.[1] Some common types of homomorphic encryption are partially homomorphic, somewhat homomorphic, leveled fully homomorphic, and fully homomorphic encryption. The computations are represented as either Boolean or arithmetic circuits. Partially homomorphic encryption encompasses schemes that support the evaluation of circuits consisting of only one type of gate, e.g., addition or multiplication. Somewhat homomorphic encryption schemes can evaluate two types of gates, but only for a subset of circuits. Leveled fully homomorphic encryption supports the evaluation of arbitrary circuits of bounded (pre-determined) depth. Fully homomorphic encryption (FHE) allows the evaluation of arbitrary circuits of unbounded depth, and is the strongest notion of homomorphic encryption. For the majority of homomorphic encryption schemes, the multiplicative depth of circuits is the main practical limitation in performing computations over encrypted data.

Homomorphic encryption schemes are inherently malleable. In terms of malleability, homomorphic encryption schemes have weaker security properties than non-homomorphic schemes.

History[edit]

Homomorphic encryption schemes have been developed using different approaches. Specifically, fully homomomorphic encryption schemes are often grouped into generations corresponding to the underlying approach.[2]

Pre-FHE[edit]

The problem of constructing a fully homomorphic encryption scheme was first proposed in 1978, within a year of publishing of the RSA scheme.[3] For more than 30 years, it was unclear whether a solution existed. During that period, partial results included the following schemes:

First-Generation FHE[edit]

Craig Gentry, using lattice-based cryptography, described the first plausible construction for a fully homomorphic encryption scheme.[7] 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 an 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. The Gentry-Halevi implementation of Gentry's original cryptosystem reported timing of about 30 minutes per basic bit operation.[9] Extensive design and implementation work in subsequent years have improved upon these early implementations by many orders of magnitude runtime performance.

In 2010, 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 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,[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 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.[13][14][15][16] Some of these works included also implementations of the resulting schemes.

Second-Generation FHE[edit]

The homomorphic cryptosystems in current use are derived from techniques that were developed starting in 2011-2012 by Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan, and others. These innovations led to the development of much more efficient somewhat and fully homomorphic cryptosystems. These include:

  • The Brakerski-Gentry-Vaikuntanathan (BGV, 2011) scheme,[17] building on techniques of Brakerski-Vaikuntanathan;[18]
  • The NTRU-based scheme by Lopez-Alt, Tromer, and Vaikuntanathan (LTV, 2012);[19]
  • The Brakerski/Fan-Vercauteren (BFV, 2012) scheme,[20] building on Brakerski's scale-invariant cryptosystem;[21]
  • The NTRU-based scheme by Bos, Lauter, Loftus, and Naehrig (BLLN, 2013),[22] building on LTV and Brakerski's scale-invariant cryptosystem;[21]
  • The Cheon-Kim-Kim-Song (CKKS, 2016) scheme.[23]

The security of most of these schemes is based on the hardness of the (Ring) Learning With Errors (RLWE) problem, except for the LTV and BLLN schemes that rely on an overstretched[24] variant of the NTRU computational problem. This NTRU variant was subsequently shown vulnerable to subfield lattice attacks,[25][24] which is why these two schemes are no longer used in practice.

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

A distinguishing characteristic of the second-generation cryptosystems is that they all feature a 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 operations on data encrypted with security parameter has complexity of only .[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.[29] Many of the advances in these second-generation cryptosystems were also ported to the cryptosystem over the integers.[15][16]

Another distinguishing feature of second-generation schemes is that they are efficient enough for many applications even without invoking bootstrapping, instead operating in the leveled FHE mode.

Third-Generation FHE[edit]

In 2013, Craig Gentry, Amit Sahai, and Brent Waters (GSW) proposed a new technique for building FHE schemes that avoids an expensive "relinearization" step in homomorphic multiplication.[30] 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.[31] Jacob Alperin-Sheriff and Chris Peikert then described a very efficient bootstrapping technique based on this observation.[32]

These techniques were further improved to develop efficient ring variants of the GSW cryptosystem: FHEW (2014)[33] and TFHE (2016).[34] The FHEW scheme was the first to show that by refreshing the ciphertexts after every single operation, it is possible to reduce the bootstrapping time to a fraction of a second. FHEW introduced a new method to compute Boolean gates on encrypted data that greatly simplifies bootstrapping, and implemented a variant of the bootstrapping procedure.[32] The efficiency of FHEW was further improved by the TFHE scheme, which implements a ring variant of the bootstrapping procedure[35] using a method similar to the one in FHEW.

Fully Homomorphic Encryption[edit]

A cryptosystem that supports arbitrary computation on ciphertexts is known as fully homomorphic encryption (FHE). 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. Fully homomorphic cryptosystems have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing.[36]

Implementations[edit]

There are no actively developed implementations of first-generation schemes. There are several open-source implementations of second- and third-generation fully homomorphic encryption schemes. Second-generation FHE implementations typically operate in the leveled FHE mode (though bootstrapping is still available in some libraries) and support efficient SIMD-like packing of data; they are typically used to compute on encrypted integers or real/complex numbers. Third-generation FHE implementations often bootstrap after each Boolean gate operation but have limited support for packing and efficient arithmetic computations; they are typically used to compute Boolean circuits over encrypted bits. The choice of using a second-generation vs. third-generation scheme depends on the input data types and the desired computation.

Second-generation FHE implementations[edit]

Third-generation FHE implementations[edit]

  • FHEW[33] by Leo Ducas and Daniele Micciancio implements the FHEW scheme.
  • TFHE[34] by Ilaria Chillotti, Nicolas Gama, Mariya Georgieva and Malika Izabachene implements the TFHE scheme.
  • FV-NFLlib by CryptoExperts.
  • NuFHE by NuCypher.
  • RHE by Ravel Technologies.

Standardization[edit]

A community standard for homomorphic encryption is maintained by the HomomorphicEncryption.org group, an open industry/government/academia consortium founded in 2017. The current standard document includes specifications of secure parameters for RLWE.

An up-to-date list of homomorphic encryption implementations is also maintained by the consortium.

Partially homomorphic cryptosystems[edit]

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

Unpadded RSA

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

ElGamal

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

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 , for some random . The homomorphic property is then

where 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 , for some random . The homomorphic property is then

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 , for some random . The homomorphic property is then

Other partially homomorphic cryptosystems


See also[edit]

References[edit]

  1. ^ Armknecht, Frederik; Boyd, Colin; Gjøsteen, Kristian; Jäschke, Angela; Reuter, Christian; Strand, Martin (2015). "A Guide to Fully Homomorphic Encryption".
  2. ^ Vinod Vaikuntanathan. "Homomorphic Encryption References" (HTML).
  3. ^ R. L. Rivest, L. Adleman, and M. L. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, 1978.
  4. ^ Sander, Tomas; Young, Adam L.; Yung, Moti (1999). Non-Interactive CryptoComputing For NC1. Focs1991. pp. 554–566. doi:10.1109/SFFCS.1999.814630. ISBN 978-0-7695-0409-4.
  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. ^ Gentry, Craig; Halevi, Shai (2010). "Implementing Gentry's fully-homomorphic encryption scheme". Eurocrypt 2011.
  10. ^ Marten, van Dijk; Gentry, Craig; Halevi, Shai; Vinod, Vaikuntanathan (2009). "Fully Homomorphic Encryption over the Integers". Eurocrypt 2010.
  11. ^ Levieil, Eric; Naccache, David. "Cryptographic Test Correction" (PDF).
  12. ^ Cohen, Bram. "Simple Public Key Encryption". Archived from the original on 2011-10-07.
  13. ^ Coron, Jean-Sébastien; Naccache, David; Tibouchi, Mehdi (2011). "Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers". Eurocrypt 2012.
  14. ^ Coron, Jean-Sébastien; Mandal, Avradip; Naccache, David; Tibouchi, Mehdi (2011). "Fully Homomorphic Encryption over the Integers with Shorter Public Keys". Crypto 2011.
  15. ^ a b Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi (2013). "Batch Fully Homomorphic Encryption over the Integers". Eurocrypt 2013.
  16. ^ a b Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi (2014). "Scale-Invariant Fully Homomorphic Encryption over the Integers". Pkc 2014.
  17. ^ Z. Brakerski, C. Gentry, and V. Vaikuntanathan. Fully Homomorphic Encryption without Bootstrapping, In ITCS 2012
  18. ^ Z. Brakerski and V. Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In FOCS 2011 (IEEE)
  19. ^ 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)
  20. ^ a b c Fan, Junfeng; Vercauteren, Frederik (2012). "Somewhat Practical Fully Homomorphic Encryption".
  21. ^ a b Z. Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP, In CRYPTO 2012 (Springer)
  22. ^ J. Bos, K. Lauter, J. Loftus, and M. Naehrig. Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme. In IMACC 2013 (Springer)
  23. ^ a b c Cheon, Jung Hee; Kim, Andrey; Kim, Miran; Song, Yongsoo (2017). "Homomorphic encryption for arithmetic of approximate numbers". Takagi T., Peyrin T. (eds) Advances in Cryptology – ASIACRYPT 2017. ASIACRYPT 2017. Springer, Cham. pp. 409–437. doi:10.1007/978-3-319-70694-8_15.
  24. ^ a b M. Albrecht, S. Bai, and L. Ducas. A subfield lattice attack on overstretched NTRU assumptions, In CRYPTO 2016 (Springer)
  25. ^ Cheon, J. H.; Jeong, J; Lee, C. (2016). "An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero". LMS Journal of Computation and Mathematics. 19 (1): 255–266.
  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. ^ Smart, Nigel P.; Vercauteren, Frederik (2014). "Fully Homomorphic SIMD Operations". Designs, Codes and Cryptography. 71 (1): 57–81.
  30. ^ C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO 2013 (Springer)
  31. ^ Z. Brakerski and V. Vaikuntanathan. Lattice-Based FHE as Secure as PKE. In ITCS 2014
  32. ^ a b J. Alperin-Sheriff and C. Peikert. Faster Bootstrapping with Polynomial Error. In CRYPTO 2014 (Springer)
  33. ^ a b Leo Ducas; Daniele Micciancio. "FHEW: A Fully Homomorphic Encryption library". Retrieved 31 December 2014.
  34. ^ a b Ilaria Chillotti; Nicolas Gama; Mariya Georgieva; Malika Izabachene. "Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds". Retrieved 31 December 2016.
  35. ^ N. Gama, M. Izabachène, P.Q. Nguyen, and X. Xie Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems. In EUROCRYPT 2016 (Springer)
  36. ^ Daniele Micciancio (2010-03-01). "A First Glimpse of Cryptography's Holy Grail". Association for Computing Machinery. p. 96. Retrieved 2010-03-17.
  37. ^ Shai Halevi; Victor Shoup. "HElib: An Implementation of homomorphic encryption". Retrieved 31 December 2014.
  38. ^ Microsoft Research. "Microsoft SEAL". Retrieved 20 February 2019.
  39. ^ "PALISADE Lattice Cryptography Library". Retrieved 1 January 2019.
  40. ^ Jung Hee Cheon; Kyoohyung Han; Andrey Kim; Miran Kim; Yongsoo Song. "Homomorphic Encryption for Arithmetic of Approximate Numbers". Retrieved 15 May 2016.
  41. ^ Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim and Yongsoo Song. Bootstrapping for Approximate Homomorphic Encryption. In EUROCRYPT 2018 (Springer).
  42. ^ Guilhem Castagnos and Fabien Laguillaumie. "Linearly Homomorphic Encryption from DDH" (PDF).

External links[edit]