Homomorphic encryption

{{morerefs|date=February 2025}}

{{short description|Form of encryption that allows computation on ciphertexts}}

{{Infobox encryption method

| name = Homomorphic encryption

| image =

| caption =

| designers =

| publish date =

| derived from = Various assumptions, including learning with errors, Ring learning with errors or even RSA (multiplicative) and others

| derived to =

| related to = Functional encryption

| key size =

| block size =

| structure =

| rounds =

| cryptanalysis =

}}

Homomorphic encryption is a form of encryption that allows computations to be performed on encrypted data without first having to decrypt it.{{Cite web |last=Technology |first=Massachusetts Institute of |title=Researchers develop innovative method for secure operations on encrypted data without decryption |url=https://techxplore.com/news/2025-03-method-encrypted-decryption.html |access-date=2025-04-01 |website=techxplore.com |language=en}} The resulting computations are left in an encrypted form which, when decrypted, result in an output that is identical to that of the operations performed on the unencrypted data. While homomorphic encryption does not protect against side-channel attacks that observe behavior, it can be used for privacy-preserving outsourced storage and computation. This allows data to be encrypted and outsourced to commercial cloud environments for processing, all while encrypted.

As an example of a practical application of homomorphic encryption: encrypted photographs can be scanned for points of interest, without revealing the contents of a photo. However, observation of side-channels can see a photograph being sent to a point-of-interest lookup service, revealing the fact that photographs were taken.

Thus, homomorphic encryption eliminates the need for processing data in the clear, thereby preventing attacks that would enable an attacker to access that data while it is being processed, using privilege escalation.{{Cite web |last=Sellers |first=Andrew |title=Council Post: Everything You Wanted To Know About Homomorphic Encryption (But Were Afraid To Ask) |url=https://www.forbes.com/sites/forbestechcouncil/2021/04/14/everything-you-wanted-to-know-about-homomorphic-encryption-but-were-afraid-to-ask/ |access-date=2023-08-18 |website=Forbes |language=en}}

For sensitive data, such as healthcare information, homomorphic encryption can be used to enable new services by removing privacy barriers inhibiting data sharing or increasing security to existing services. 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. Moreover, even if the service provider's system is compromised, the data would remain secure.{{cite journal |last1=Munjal |first1=Kundan |last2=Bhatia |first2=Rekha |title=A systematic review of homomorphic encryption and its contributions in healthcare industry |journal=Complex & Intelligent Systems |date=2022 |volume=9 |issue=4 |pages=3759–3786 |doi=10.1007/s40747-022-00756-z |pmid=35531323 |pmc=9062639 |doi-access=free}}

{{TOC limit|3}}

Description

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 public-key cryptography{{How|title=The connection to public-key cryptography is unclear. Please clarify.|date=December 2022}}. Homomorphic refers to homomorphism in algebra: the encryption and decryption functions can be thought of 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.

{{cite journal

|last1=Armknecht |first1=Frederik

|last2=Boyd |first2=Colin

|last3=Gjøsteen |first3=Kristian

|last4=Jäschke |first4=Angela

|last5=Reuter |first5=Christian

|last6=Strand |first6=Martin

|title=A Guide to Fully Homomorphic Encryption

|journal=Cryptology ePrint Archive

|url=https://eprint.iacr.org/2015/1192

|date=2015}}

The computations are represented as either Boolean or arithmetic circuits. Some common types of homomorphic encryption are partially homomorphic, somewhat homomorphic, leveled fully homomorphic, and fully homomorphic encryption:

  • 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 composed of multiple types of gates of bounded (pre-determined) depth.
  • Fully homomorphic encryption (FHE) allows the evaluation of arbitrary circuits composed of multiple types of gates 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

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

{{cite web

|title=Homomorphic Encryption References

|url=https://people.csail.mit.edu/vinodv/FHE/FHE-refs.html

|author=Vinod Vaikuntanathan

}}

=Pre-FHE=

The problem of constructing a fully homomorphic encryption scheme was first proposed in 1978, within a year of publishing of the RSA scheme.R. L. Rivest, L. Adleman, and M. L. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, 1978. For more than 30 years, it was unclear whether a solution existed. During that period, partial results included the following schemes:

{{cite book|last1=Sander|first1=Tomas |last2=Young|first2=Adam L.|last3=Yung|first3=Moti |title=40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) |chapter=Non-interactive cryptocomputing for NC/Sup 1/ |pages=554–566 |doi=10.1109/SFFCS.1999.814630 |year=1999 |isbn=978-0-7695-0409-4 |s2cid=1976588 }}

  • Boneh–Goh–Nissim cryptosystem (unlimited number of addition operations but at most one multiplication)D. Boneh, E. Goh, and K. Nissim. Evaluating 2-DNF Formulas on Ciphertexts. In Theory of Cryptography Conference, 2005.
  • Ishai-Paskin cryptosystem (polynomial-size branching programs)Y. Ishai and A. Paskin. Evaluating branching programs on encrypted data. In Theory of Cryptography Conference, 2007.

=First-generation FHE=

Craig Gentry, using lattice-based cryptography, described the first plausible construction for a fully homomorphic encryption scheme in 2009.{{cite book | doi=10.1145/1536414.1536440 | chapter=Fully homomorphic encryption using ideal lattices | title=Proceedings of the forty-first annual ACM symposium on Theory of computing | date=2009 | last1=Gentry | first1=Craig | pages=169–178 | isbn=978-1-60558-506-2 }} 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

{{cite thesis

|title=A Fully Homomorphic Encryption Scheme

|type=PhD Thesis

|publisher=Stanford University

|url=http://crypto.stanford.edu/craig/

|author=Craig Gentry

|format=PDF

}} provides additional details. The Gentry-Halevi implementation of Gentry's original cryptosystem reported a timing of about 30 minutes per basic bit operation.

{{cite book|doi=10.1007/978-3-642-20465-4_9|last1=Gentry|first1=Craig|last2=Halevi|first2=Shai|title=Advances in Cryptology – EUROCRYPT 2011 |chapter=Implementing Gentry's Fully-Homomorphic Encryption Scheme |series=Lecture Notes in Computer Science |chapter-url=http://eprint.iacr.org/2010/520|year=2010|volume=6632 |pages=129–148 |isbn=978-3-642-20464-7 }} 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,

{{cite book|last1=Van Dijk|first1=Marten|last2=Gentry|first2=Craig|last3=Halevi|first3=Shai

|last4=Vinod|first4=Vaikuntanathan |title=Advances in Cryptology – EUROCRYPT 2010 |chapter=Fully Homomorphic Encryption over the Integers |series=Lecture Notes in Computer Science |doi=10.1007/978-3-642-13190-5_2|chapter-url=http://eprint.iacr.org/2009/616|year=2009 |volume=6110 |pages=24–43 |isbn=978-3-642-13189-9 }} 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,

{{cite book

|chapter=Cryptographic Test Correction

|chapter-url=https://www.iacr.org/archive/pkc2008/49390088/49390088.pdf

|last1=Levieil |first1=Eric

|last2=Naccache |first2=David |title=Public Key Cryptography – PKC 2008

|series=Lecture Notes in Computer Science

|date=2008

|volume=4939

|pages=85–100

|author-link2=David Naccache

|doi=10.1007/978-3-540-78440-1_6

|isbn=978-3-540-78439-5

}} and also to one that was proposed by Bram Cohen in 1998.

{{cite web

|title=Simple Public Key Encryption

|url=http://bramcohen.com/simple_public_key.html

|last=Cohen

|first=Bram

|author-link=Bram Cohen

|url-status=dead

|archive-url=https://web.archive.org/web/20111007060226/http://bramcohen.com/simple_public_key.html

|archive-date=2011-10-07

}}

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.

{{cite book|last1=Coron|first1=Jean-Sébastien|last2=Naccache|first2=David|last3=Tibouchi|first3=Mehdi|title=Advances in Cryptology – EUROCRYPT 2012 |chapter=Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers |series=Lecture Notes in Computer Science |chapter-url=http://eprint.iacr.org/2011/440|year=2011|volume=7237 |pages=446–464 |doi=10.1007/978-3-642-29011-4_27|isbn=978-3-642-29010-7 }}

{{cite book|last1=Coron|first1=Jean-Sébastien|last2=Mandal|first2=Avradip|last3=Naccache|first3=David |last4=Tibouchi|first4=Mehdi|chapter=Fully Homomorphic Encryption over the Integers with Shorter Public Keys|title=Advances in Cryptology – CRYPTO 2011|volume=6841|pages=487–504|url=http://eprint.iacr.org/2011/441|year=2011|doi=10.1007/978-3-642-22792-9_28|series=Lecture Notes in Computer Science|isbn=978-3-642-22791-2|doi-access=free|editor-last=Rogaway |editor-first= P. }}

{{cite book|last1=Coron|first1=Jean-Sébastien|last2=Lepoint|first2=Tancrède|last3=Tibouchi|first3=Mehdi|title=Advances in Cryptology – EUROCRYPT 2013 |chapter=Batch Fully Homomorphic Encryption over the Integers |series=Lecture Notes in Computer Science |doi=10.1007/978-3-642-38348-9_20|chapter-url=http://eprint.iacr.org/2013/036|year=2013|volume=7881 |pages=315–335 |isbn=978-3-642-38347-2 }}

{{cite book|last1=Coron|first1=Jean-Sébastien|last2=Lepoint|first2=Tancrède|last3=Tibouchi|first3=Mehdi|title=Public-Key Cryptography – PKC 2014 |chapter=Scale-Invariant Fully Homomorphic Encryption over the Integers |series=Lecture Notes in Computer Science |doi=10.1007/978-3-642-54631-0_18|chapter-url=http://eprint.iacr.org/2014/032|year=2014|volume=8383 |pages=311–328 |isbn=978-3-642-54630-3 }} Some of these works included also implementations of the resulting schemes.

=Second-generation FHE=

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,Z. Brakerski, C. Gentry, and V. Vaikuntanathan. [http://eprint.iacr.org/2011/277 Fully Homomorphic Encryption without Bootstrapping], In ITCS 2012 building on techniques of Brakerski-Vaikuntanathan;Z. Brakerski and V. Vaikuntanathan. [http://eprint.iacr.org/2011/344 Efficient Fully Homomorphic Encryption from (Standard) LWE]. In FOCS 2011 (IEEE)
  • The NTRU-based scheme by Lopez-Alt, Tromer, and Vaikuntanathan (LTV, 2012);A. Lopez-Alt, E. Tromer, and V. Vaikuntanathan. [https://eprint.iacr.org/2013/094 On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption]. In STOC 2012 (ACM)
  • The Brakerski/Fan-Vercauteren (BFV, 2012) scheme,

{{cite journal

|last1=Fan |first1=Junfeng

|last2=Vercauteren |first2=Frederik

|title=Somewhat Practical Fully Homomorphic Encryption

|journal=Cryptology ePrint Archive

|url=https://eprint.iacr.org/2012/144

|date=2012}}

building on Brakerski's {{em|scale-invariant}} cryptosystem;Z. Brakerski. [http://eprint.iacr.org/2012/078 Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP], In CRYPTO 2012 (Springer)

  • The NTRU-based scheme by Bos, Lauter, Loftus, and Naehrig (BLLN, 2013),J. Bos, K. Lauter, J. Loftus, and M. Naehrig. [https://eprint.iacr.org/2013/075 Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme]. In IMACC 2013 (Springer) building on LTV and Brakerski's scale-invariant cryptosystem;

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 overstretchedM. Albrecht, S. Bai, and L. Ducas. [https://eprint.iacr.org/2016/127 A subfield lattice attack on overstretched NTRU assumptions], In CRYPTO 2016 (Springer) variant of the NTRU computational problem. This NTRU variant was subsequently shown vulnerable to subfield lattice attacks,

{{cite journal|last1=Cheon|first1=J. H.|last2=Jeong|first2=J|last3=Lee|first3=C.|title=An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero|journal=LMS Journal of Computation and Mathematics|volume=19|number=1|pages=255–266 |date=2016|doi=10.1112/S1461157016000371|doi-access=free}} 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 T operations on data encrypted with security parameter k has complexity of only T\cdot\mathrm{polylog}(k).C. Gentry, S. Halevi, and N. P. Smart. [http://eprint.iacr.org/2011/566 Fully Homomorphic Encryption with Polylog Overhead]. In EUROCRYPT 2012 (Springer)

C. Gentry, S. Halevi, and N. P. Smart. [http://eprint.iacr.org/2011/680 Better Bootstrapping in Fully Homomorphic Encryption]. In PKC 2012 (SpringeR)C. Gentry, S. Halevi, and N. P. Smart. [http://eprint.iacr.org/2012/099 Homomorphic Evaluation of the AES Circuit]. In CRYPTO 2012 (Springer) 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.

{{cite journal|last1=Smart|first1=Nigel P.|last2=Vercauteren|first2=Frederik|title=Fully Homomorphic SIMD Operations |journal=Designs, Codes and Cryptography|volume=71|number=1|pages=57–81 |date=2014|url=http://eprint.iacr.org/2011/133|doi=10.1007/s10623-012-9720-4|s2cid=11202438|citeseerx=10.1.1.294.4088}} Many of the advances in these second-generation cryptosystems were also ported to the cryptosystem over the integers.

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=

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.C. Gentry, A. Sahai, and B. Waters. [http://eprint.iacr.org/2013/340 Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based]. In CRYPTO 2013 (Springer) 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.Z. Brakerski and V. Vaikuntanathan. [http://eprint.iacr.org/2013/541 Lattice-Based FHE as Secure as PKE]. In ITCS 2014 Jacob Alperin-Sheriff and Chris Peikert then described a very efficient bootstrapping technique based on this observation.J. Alperin-Sheriff and C. Peikert. [http://eprint.iacr.org/2014/094 Faster Bootstrapping with Polynomial Error]. In CRYPTO 2014 (Springer)

These techniques were further improved to develop efficient ring variants of the GSW cryptosystem: FHEW (2014) and TFHE (2016). 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. The efficiency of FHEW was further improved by the TFHE scheme, which implements a ring variant of the bootstrapping procedureN. Gama, M. Izabachène, P.Q. Nguyen, and X. Xie [https://eprint.iacr.org/2014/283 Structural Lattice Reduction: Generalized Worst-Case to Average-Case Reductions and Homomorphic Cryptosystems]. In EUROCRYPT 2016 (Springer) using a method similar to the one in FHEW.

=Fourth-generation FHE=

In 2016, Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song (CKKS)

{{cite conference

|last1=Cheon |first1=Jung Hee

|last2=Kim |first2=Andrey

|last3=Kim |first3=Miran

|last4=Song |first4=Yongsoo

|title=Homomorphic encryption for arithmetic of approximate numbers

|series=Lecture Notes in Computer Science

|publisher=Springer, Cham

|conference=ASIACRYPT 2017 |date=2017 |volume=10624

|book-title=Takagi T., Peyrin T. (eds) Advances in Cryptology – ASIACRYPT 2017 |pages=409–437|doi=10.1007/978-3-319-70694-8_15 |isbn=978-3-319-70693-1

}}

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 [https://www.youtube.com/watch?v=culuNbMPP0k&feature=youtu.be&t=3397 privacy-preserving machine learning applications]. The scheme introduces several approximation errors, both nondeterministic and deterministic, that require special handling in practice.Kim A., Papadimitriou A., Polyakov Y. [https://eprint.iacr.org/2020/1118 Approximate Homomorphic Encryption with Reduced Approximation Error], In CT-RSA 2022 (Springer)

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.{{Cite journal|last1=Li|first1=Baily|last2=Micciancio|first2=Daniele|date=2020|title=On the Security of Homomorphic Encryption on Approximate Numbers|url=https://eprint.iacr.org/2020/1533.pdf|journal=IACR ePrint Archive 2020/1533}} 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.{{Cite journal|last1=Cheon|first1=Jung Hee|first2=Seungwan|last2=Hong|first3=Duhyeong|last3=Kim|date=2020|title=Remark on the Security of CKKS Scheme in Practice|url=https://eprint.iacr.org/2020/1581.pdf|journal=IACR ePrint Archive 2020/1581}}{{cite web|title=Security of CKKS|url=https://palisade-crypto.org/security-of-ckks|access-date=10 March 2021}}

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 has modulus n and encryption exponent e, then the encryption of a message m is given by \mathcal{E}(m) = m^e \;\bmod\; n. The homomorphic property is then

:

\begin{align}

\mathcal{E}(m_1) \cdot \mathcal{E}(m_2) &= m_1^e m_2^e \;\bmod\; n \\[6pt]

&= (m_1 m_2)^e \;\bmod\; n \\[6pt]

&= \mathcal{E}(m_1 \cdot m_2)

\end{align}

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}) \\[6pt]

&= \mathcal{E}(m_1 \cdot m_2).

\end{align}

Goldwasser–Micali

In the Goldwasser–Micali cryptosystem, if the public key is the modulus n and quadratic non-residue x, then the encryption of a bit b is \mathcal{E}(b) = x^b r^2 \;\bmod\; n, for some random r \in \{0, \ldots, n-1\}. The homomorphic property is then

:

\begin{align}

\mathcal{E}(b_1)\cdot \mathcal{E}(b_2) &= x^{b_1} r_1^2 x^{b_2} r_2^2 \;\bmod\; n \\[6pt]

&= x^{b_1+b_2} (r_1r_2)^2 \;\bmod\; n \\[6pt]

&= \mathcal{E}(b_1 \oplus b_2).

\end{align}

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

Benaloh

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

:

\begin{align}

\mathcal{E}(m_1) \cdot \mathcal{E}(m_2) &= (g^{m_1} r_1^c)(g^{m_2} r_2^c) \;\bmod\; n \\[6pt]

&= g^{m_1 + m_2} (r_1 r_2)^c \;\bmod\; n \\[6pt]

&= \mathcal{E}(m_1 + m_2 \;\bmod\; c).

\end{align}

Paillier

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

:

\begin{align}

\mathcal{E}(m_1) \cdot \mathcal{E}(m_2) &= (g^{m_1} r_1^n)(g^{m_2} r_2^n) \;\bmod\; n^2 \\[6pt]

&= g^{m_1 + m_2} (r_1r_2)^n \;\bmod\; n^2 \\[6pt]

&= \mathcal{E}(m_1 + m_2).

\end{align}

Other partially homomorphic cryptosystems

{{cite journal|last1=Benhamouda|first1=Fabrice|last2=Herranz|first2=Javier|last3=Joye|first3=Marc|last4=Libert|first4=Benoît|title=Efficient cryptosystems from 2k-th power residue symbols |journal=Journal of Cryptology|volume=30|number=2|pages=519–549|date=2017|url=https://link.springer.com/content/pdf/10.1007/s00145-016-9229-5.pdf|doi=10.1007/s00145-016-9229-5|hdl=2117/103661|s2cid=62063}}

  • Castagnos–Laguillaumie cryptosystem{{cite conference

| last1 = Castagnos | first1 = Guilhem

| last2 = Laguillaumie | first2 = Fabien

| editor-last = Nyberg | editor-first = Kaisa

| contribution = Linearly Homomorphic Encryption from DDH

| contribution-url = https://eprint.iacr.org/2015/047.pdf

| doi = 10.1007/978-3-319-16715-2_26

| pages = 487–505

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Topics in Cryptology – CT-RSA 2015, The Cryptographer's Track at the RSA Conference 2015, San Francisco, CA, USA, April 20–24, 2015. Proceedings

| volume = 9048

| year = 2015| isbn = 978-3-319-16714-5

}}

Fully homomorphic encryption

A cryptosystem that supports {{em|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.{{cite web

|title=A First Glimpse of Cryptography's Holy Grail

|author=Daniele Micciancio

|url=http://cacm.acm.org/magazines/2010/3/76275-a-first-glimpse-of-cryptographys-holy-grail/fulltext

|publisher=Association for Computing Machinery

|date=2010-03-01

|page=96

|access-date=2010-03-17

}}

=Implementations=

{{Primary sources|1=section|date=July 2022}}

A list of open-source FHE libraries implementing second-generation (BGV/BFV), third-generation (FHEW/TFHE), and/or fourth-generation (CKKS) FHE schemes is provided below.

There are several open-source implementations of fully homomorphic encryption schemes. 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.

class="wikitable"

|+ FHE libraries

! Name!!Developer!! BGV !! CKKS !! BFV !! FHEW !! CKKS BootstrappingJung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim and Yongsoo Song. [https://eprint.iacr.org/2018/153 Bootstrapping for Approximate Homomorphic Encryption]. In EUROCRYPT 2018 (Springer).!! TFHE !! Description

HElib{{cite web|title=HElib: An Implementation of homomorphic encryption|url=https://github.com/homenc/HElib|author=Shai Halevi|author2=Victor Shoup|website=GitHub|access-date=31 December 2014}}IBM{{Yes}}{{Yes}}{{No}}{{No}}{{No}}{{No}}BGV scheme with the GHS optimizations.
Microsoft SEAL

{{cite web

|author=Microsoft Research

|title=Microsoft SEAL

|website=Microsoft

|url=https://www.microsoft.com/en-us/research/project/microsoft-seal

|access-date=20 February 2019}}

Microsoft{{Yes}}{{Yes}}{{Yes}}{{No}}{{No}}{{No}}
OpenFHEDuality Technologies, {{ill|Samsung Advanced Institute of Technology|kr}}, Intel, MIT, University of California, San Diego and others.{{Yes}}{{Yes}}{{Yes}}{{Yes}}{{Yes}}{{Yes}}Successor to PALISADE.
PALISADE

{{cite web

|title=PALISADE Lattice Cryptography Library

|url=http://palisade-crypto.org

|access-date=1 January 2019}}

New Jersey Institute of Technology, Duality Technologies, Raytheon BBN Technologies, MIT, University of California, San Diego and others.{{Yes}}{{Yes}}{{Yes}}{{Yes}}{{No}}{{Yes}}General-purpose lattice cryptography library. Predecessor of OpenFHE.
HEAAN

{{cite web

|title=Homomorphic Encryption for Arithmetic of Approximate Numbers

|url=https://github.com/snucrypto/HEAAN

|author=Jung Hee Cheon|author2=Kyoohyung Han|author3=Andrey Kim|author4=Miran Kim|author5=Yongsoo Song

|website=GitHub

|access-date=15 May 2016}}

CryptoLab{{No}}{{Yes}}{{No}}{{No}}{{Yes}}{{No}}
FHEW

{{cite web

|title=FHEW: A Fully Homomorphic Encryption library

|url=https://github.com/lducas/FHEW

|author=Leo Ducas|author2=Daniele Micciancio

|website=GitHub

|access-date=31 December 2014}}

Leo Ducas and Daniele Micciancio{{No}}{{No}}{{No}}{{Yes}}{{No}}{{No}}
TFHE

{{cite web

|title=Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds

|url=https://tfhe.github.io/tfhe

|author=Ilaria Chillotti|author2=Nicolas Gama|author3=Mariya Georgieva|author4=Malika Izabachene

|access-date=31 December 2016}}

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva and Malika Izabachene{{No}}{{No}}{{No}}{{No}}{{No}}{{Yes}}
FV-NFLlib{{cite web

|title=FV-NFLlib

|url=https://github.com/CryptoExperts/FV-NFLlib

|author=Crypto Experts

|website=GitHub

|access-date=1 November 2019}}

CryptoExperts{{No}}{{No}}{{Yes}}{{No}}{{No}}{{No}}
NuFHE{{cite web

|title=A GPU implementation of fully homomorphic encryption on torus

|url=https://github.com/nucypher/nufhe

|author=NuCypher

|website=GitHub

|access-date=1 November 2019}}

NuCypher{{No}}{{No}}{{No}}{{No}}{{No}}{{Yes}}Provides a GPU implementation of TFHE.
REDcuFHE{{cite web

|title=A Multi-GPU Implementation of the CGGI Cryptosystem

|url=https://github.com/TrustworthyComputing/REDcuFHE

|author=Trustworthy Computing (TwC) Group

|website=GitHub

|access-date=7 March 2023}}

TwC Group{{No}}{{No}}{{No}}{{No}}{{No}}{{Yes}}A multi-GPU implementation of TFHE.
Lattigo{{cite web

|title=Lattigo v3.0.5

|url=https://github.com/tuneinsight/lattigo

|author=EPFL-LDS

|website=GitHub

|access-date=13 September 2022}}

EPFL-LDS, Tune Insight{{Yes}}{{Yes}}{{Yes}}{{No}}{{Yes}}Jean-Philippe Bossuat, Christian Mouchet, Juan Troncoso-Pastoriza and Jean-Pierre Hubaux. [https://eprint.iacr.org/2020/1203 Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys]. In EUROCRYPT 2021 (Springer).{{No}}Implementation in Go along with their distributed variantsChristian Mouchet, Juan Troncoso-Pastoriza, Jean-Philippe Bossuat and Jean-Pierre Hubaux. [https://eprint.iacr.org/2020/304 Multiparty Homomorphic Encryption from Ring-Learning-With-Errors]. enabling Secure multi-party computation.
TFHE-rs{{cite web

|title=TFHE-rs

|url=https://github.com/zama-ai/tfhe-rs

|author=Zama

|website=GitHub

|date=15 June 2023}}

Zama{{No}}{{No}}{{No}}{{No}}{{No}}{{Yes}}Rust implementation of TFHE-extended. Supporting Boolean, integer operation and univariate function evaluation (via Programmable Bootstrapping{{cite book |last1=Chillotti |first1=Ilaria |last2=Joye |first2=Marc |last3=Paillier |first3=Pascal |title=Cyber Security Cryptography and Machine Learning |chapter=Programmable Bootstrapping Enables Efficient Homomorphic Inference of Deep Neural Networks |series=Lecture Notes in Computer Science |date=2021 |volume=12716 |pages=1–19 |doi=10.1007/978-3-030-78086-9_1 |isbn=978-3-030-78085-2 |s2cid=231732347 |chapter-url=https://eprint.iacr.org/2021/091.pdf |access-date=17 November 2022 |language=en}}).
Liberate.FHE{{cite web

|title=Liberate.FHE

|url=https://github.com/Desilo/liberate-fhe

|author=Desilo

|website=GitHub

|access-date=7 March 2024}}

Desilo{{No}}{{Yes}}{{No}}{{No}}{{No}}{{No}}A multi-GPU implementation of CKKS.

class="wikitable"

|+ FHE frameworks

! Name !!Developer !! FHEW !! TFHE !! HElib !! SEAL !! PALISADE !! Lattigo !! Description

Concrete{{cite web

|title=Concrete

|url=https://github.com/zama-ai/concrete

|author=Zama

|website=GitHub

|access-date=20 May 2022}}

Zama{{No}}{{Yes}}{{No}}{{No}}{{No}}{{No}}TFHE-extended compiler with a Python Frontend.

{{cite web

|title=Concrete Python

|url=https://pypi.org/project/concrete-python/

|author=Zama

|website=Pypi

|date=15 June 2023

}}

E3

{{cite web

|title=Encrypt-Everything-Everywhere (E3)

|url=https://github.com/momalab/e3

|author=MoMA Lab, New York University Abu Dhabi

|website=GitHub

|access-date=27 July 2019|date=2019-07-24

}}

MoMA Lab at NYU Abu Dhabi{{Yes}}{{Yes}}{{Yes}}{{Yes}}{{Yes}}{{No}}
SHEEP

{{cite web

|title=SHEEP, a Homomorphic Encryption Evaluation Platform

|url=https://github.com/alan-turing-institute/SHEEP

|author=Alan Turing Institute, London, UK

|website=GitHub

|access-date=1 November 2019|date=2019-11-01

}}

Alan Turing Institute{{No}}{{Yes}}{{Yes}}{{Yes}}{{Yes}}{{No}}
T2

{{cite web

|title=T2: A cross compiler and standardized benchmarks for FHE computation

|url=https://github.com/TrustworthyComputing/T2-FHE-Compiler-and-Benchmarks

|author=Trustworthy Computing (TwC) Group

|website=GitHub

|access-date=3 February 2023|date=2023-03-02

}}

TwC Group{{No}}{{Yes}}{{Yes}}{{Yes}}{{Yes}}{{Yes}}
HELM

{{cite web

|title=HELM: Navigating Homomorphic Evaluation through Gates and Lookups

|url=https://github.com/TrustworthyComputing/helm

|author=Trustworthy Computing (TwC) Group

|website=GitHub

|access-date=29 July 2024|date=2024-07-29

}}

TwC Group{{No}}{{Yes}}{{No}}{{No}}{{No}}{{No}}
Juliet

{{cite web

|title=Juliet: A Configurable Processor for Computing on Encrypted Data

|url=https://github.com/TrustworthyComputing/Juliet

|author=Trustworthy Computing (TwC) Group

|website=GitHub

|access-date=25 June 2024|date=2024-06-25

}}

TwC Group{{No}}{{Yes}}{{No}}{{No}}{{No}}{{No}}
PEEV{{Citation |last=TrustworthyComputing |title=TrustworthyComputing/PEEV-verifiableFHE |date=2024-07-18 |url=https://github.com/TrustworthyComputing/PEEV-verifiableFHE |access-date=2024-07-18}}

|TwC Group

|{{No}}

|{{No}}

|{{No}}

|{{Yes}}

|{{No}}

|{{No}}

|Verifiable encrypted computations based on Rinocchio ZKP and BGV homomorphic Encryption.

=Standardization=

In 2017, researchers from IBM, Microsoft, Intel, the NIST, and others formed the open [https://homomorphicencryption.org/ Homomorphic Encryption Standardization Consortium], which maintains a community security Homomorphic Encryption Standard.{{cite web|date=2017-07-13|title=Homomorphic Encryption Standardization Workshop|url=https://www.microsoft.com/en-us/research/event/homomorphic-encryption-standardization-workshop/ |access-date=2022-05-12|publisher=Microsoft}}{{cite web|date=2019-08-16|title=Intel, Microsoft Research and Duality Technologies Convene AI Community for Privacy Standards|url=https://newsroom.intel.com/news/intel-microsoft-research-duality-technologies-convene-ai-community-privacy-standards/ |access-date=2022-05-12|publisher=Intel Newsroom}}{{cite web|date=8 March 2021|title=Intel, Microsoft join DARPA effort to accelerate fully homomorphic encryption|url=https://www.csoonline.com/article/3610752/intel-microsoft-join-darpa-effort-to-accelerate-fully-homomorphic-encryption.html}}

See also

References

{{Reflist|30em}}