Homomorphic encryption schemes have been developed using different approaches. Specifically, fully homomorphic encryption schemes are often grouped into generations corresponding to the underlying approach.
Predecessors The problem of constructing a fully homomorphic encryption scheme was first proposed in 1978, within a year of publishing of the RSA scheme. For more than 30 years, it was unclear whether a solution existed. During that period, partial results included the following schemes: •
RSA cryptosystem (unbounded number of modular multiplications) •
ElGamal cryptosystem (unbounded number of modular multiplications) •
Goldwasser–Micali cryptosystem (unbounded number of
exclusive or operations) •
Benaloh cryptosystem (unbounded number of modular additions) •
Paillier cryptosystem (unbounded number of modular additions) • Sander-Young-Yung system (after more than 20 years solved the problem for logarithmic depth circuits) • Boneh–Goh–Nissim cryptosystem (unlimited number of addition operations but at most one multiplication) • Ishai-Paskin cryptosystem (polynomial-size
branching programs)
First generation Craig Gentry, using
lattice-based cryptography, described the first plausible construction for a fully homomorphic encryption scheme in 2009. 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 provides additional details. The Gentry-Halevi implementation of Gentry's original cryptosystem reported a timing of about 30 minutes per basic bit operation. 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, 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, and also to one that was proposed by
Bram Cohen in 1998.
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. Some of these works included also implementations of the resulting schemes.
Second generation The homomorphic cryptosystems of this generation 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, building on techniques of Brakerski-Vaikuntanathan; • The
NTRU-based scheme by Lopez-Alt, Tromer, and Vaikuntanathan (LTV, 2012); • The Brakerski/Fan-Vercauteren (BFV, 2012) scheme, building on Brakerski's cryptosystem; • The
NTRU-based scheme by Bos, Lauter, Loftus, and Naehrig (BLLN, 2013), building on LTV and Brakerski's scale-invariant cryptosystem; variant of the
NTRU computational problem. This NTRU variant was subsequently shown vulnerable to subfield lattice attacks, These optimizations build on the Smart-Vercauteren techniques that enable packing of many plaintext values in a single ciphertext and operating on all these plaintext values in a
SIMD fashion. Many of the advances in these second-generation cryptosystems were also ported to the cryptosystem over the integers. 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. Jacob Alperin-Sheriff and Chris Peikert then described a very efficient bootstrapping technique based on this observation. These techniques were further improved to develop efficient ring variants of the GSW cryptosystem: FHEW (2014) using a method similar to the one in FHEW.
Fourth generation In 2016,
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song (CKKS) proposed an approximate homomorphic encryption scheme that supports a special kind of
fixed-point arithmetic that is commonly referred to as
block floating point arithmetic. The CKKS scheme includes an efficient rescaling operation that scales down an encrypted message after a multiplication. For comparison, such rescaling requires bootstrapping in the BGV and BFV schemes. The rescaling operation makes CKKS scheme the most efficient method for evaluating polynomial approximations, and is the preferred approach for implementing privacy-preserving machine learning applications. The scheme introduces several approximation errors, both nondeterministic and deterministic, that require special handling in practice. A 2020 article by Baiyu Li and Daniele Micciancio discusses passive attacks against CKKS, suggesting that the standard IND-CPA definition may not be sufficient in scenarios where decryption results are shared. The authors apply the attack to four modern homomorphic encryption libraries (HEAAN, SEAL, HElib and PALISADE) and report that it is possible to recover the secret key from decryption results in several parameter configurations. The authors also propose mitigation strategies for these attacks, and include a Responsible Disclosure in the paper suggesting that the homomorphic encryption libraries already implemented mitigations for the attacks before the article became publicly available. Further information on the mitigation strategies implemented in the homomorphic encryption libraries has also been published. == Partially homomorphic cryptosystems ==