While homomorphic encryption does not protect against side-channel attacks that observe behavior, it can be used for privacy-preserving outsourced storage and computation.
For example, predictive analytics in healthcare can be hard to apply via a third-party service provider due to medical data privacy concerns.
But if the predictive-analytics service provider could operate on encrypted data instead, without having the decryption keys, these privacy concerns are diminished.
Specifically, fully homomorphic encryption schemes are often grouped into generations corresponding to the underlying approach.
[9] Gentry's scheme supports both addition and multiplication operations on ciphertexts, from which it is possible to construct circuits for performing arbitrary computation.
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.
The Gentry-Halevi implementation of Gentry's original cryptosystem reported a timing of about 30 minutes per basic bit operation.
In 2010, Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan presented a second fully homomorphic encryption scheme,[12] which uses many of the tools of Gentry's construction, but which does not require ideal lattices.
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.
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 include: 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[25] variant of the NTRU computational problem.
This NTRU variant was subsequently shown vulnerable to subfield lattice attacks,[26][25] which is why these two schemes are no longer used in practice.
A distinguishing characteristic of the second-generation cryptosystems is that they all feature a much slower growth of the noise during the homomorphic computations.
[17][18] 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.
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.
[31] 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.
[32] Jacob Alperin-Sheriff and Chris Peikert then described a very efficient bootstrapping technique based on this observation.
[33] These techniques were further improved to develop efficient ring variants of the GSW cryptosystem: FHEW (2014)[34] and TFHE (2016).
[35] 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.
In 2016, Cheon, Kim, Kim and Song (CKKS)[37] 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.
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.
[38] 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.
[39] 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.
Further information on the mitigation strategies implemented in the homomorphic encryption libraries has also been published.
Second-generation and fourth-generation FHE scheme 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 scheme implementations often bootstrap after each operation but have limited support for packing; they were initially used to compute Boolean circuits over encrypted bits, but have been extended to support integer arithmetics and univariate function evaluation.
The choice of using a second-generation vs. third-generation vs fourth-generation scheme depends on the input data types and the desired computation.
Supporting Boolean, integer operation and univariate function evaluation (via Programmable Bootstrapping[57]).