Homomorphic encryption is a form of

Fully Homomorphic Encryption without Bootstrapping

In ''ITCS 2012'' building on techniques of Brakerski-Vaikuntanathan;Z. Brakerski and V. Vaikuntanathan

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

On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption

In ''STOC 2012'' (ACM) * The Brakerski/Fan-Vercauteren (BFV, 2012) scheme, building on Brakerski's cryptosystem;Z. Brakerski

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

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, (Ring) Learning With Errors (RLWE) problem, except for the LTV and BLLN schemes that rely on an ''overstretched''M. Albrecht, S. Bai, and L. Ducas

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, 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 byCraig Gentry
Craig Alan Gentry (born November 29, 1983) is an American former professional baseball
Professional baseball is organized baseball in which players are selected for their talents and are paid to play for a specific team or club system. It is pla ...

, Shai Halevi, and Nigel Smart (cryptographer), 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\backslash cdot\backslash mathrm(k)$.C. Gentry, S. Halevi, and N. P. Smart

Fully Homomorphic Encryption with Polylog Overhead

In ''EUROCRYPT 2012'' (Springer) C. Gentry, S. Halevi, and N. P. Smart

Better Bootstrapping in Fully Homomorphic Encryption

In ''PKC 2012'' (SpringeR)C. Gentry, S. Halevi, and N. P. Smart

Homomorphic Evaluation of the AES Circuit

In ''CRYPTO 2012'' (Springer) 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. 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.

Craig Gentry
Craig Alan Gentry (born November 29, 1983) is an American former professional baseball
Professional baseball is organized baseball in which players are selected for their talents and are paid to play for a specific team or club system. It is pla ...

, 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

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. Jacob Alperin-Sheriff and Chris Peikert then described a very efficient bootstrapping technique based on this observation.J. Alperin-Sheriff and C. Peikert

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. Xi

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.

a solution for encrypted machine learning.

This is due to a characteristic of CKKS scheme that encrypts approximate values rather than exact values. When computers store real-valued data, they remember approximate values with long significant bits, not real values exactly. CKKS scheme is constructed to deal efficiently with the errors arising from the approximations. The scheme is familiar to machine learning which has inherent noises in its structure. 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.

list of homomorphic encryption implementations

is also maintained by the community on GitHub. There are several open-source implementations of second- and third-generation fully homomorphic encryption schemes. Second-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 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.

HomomorphicEncryption.org

group, an open industry/government/academia consortium co-founded in 2017 by Microsoft, IBM, and others. The curren

standard document

includes specifications of secure parameters for RLWE.

Daniele Micciancio's FHE references

*

HElib

Microsoft SEAL

PALISADE

HEAAN

FHEW

an

TFHE

(open-source homomorphic encryption libraries) {{DEFAULTSORT:Homomorphic Encryption Homomorphic encryption, Cryptographic primitives Public-key cryptography Information privacy

encryption
In cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in ...

that permits users to perform computations on its encrypted data without first decrypting it. These resulting computations are left in an encrypted form which, when decrypted, result in an identical output to that produced had the operations been performed on the unencrypted data. Homomorphic encryption can be used for privacy-preserving outsourced storage and computation
Computation is any type of calculation that includes both arithmetical and non-arithmetical steps and which follows a well-defined model (e.g. an algorithm).
Mechanical or electronic devices (or, History of computing hardware, historically, peop ...

. This allows data to be encrypted and out-sourced to commercial cloud environments for processing, all while encrypted.
For sensitive data, such as health care information, homomorphic encryption can be used to enable new services by removing privacy barriers inhibiting data sharing or increase security to existing services. For example, predictive analytics
Predictive analytics encompasses a variety of statistics, statistical techniques from data mining, predictive modelling, and machine learning that analyze current and historical facts to make predictions about future or otherwise unknown events.
...

in health care can be hard to apply via a third party service provider due to medical data privacy concerns, but if the predictive analytics service provider can operate on encrypted data instead, these privacy concerns are diminished. Moreover, even if the service provider's system is compromised, the data would remain secure.
Description

Homomorphic encryption is a form ofencryption
In cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in ...

with an additional evaluation capability for computing over encrypted data without access to the secret key
A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can Encryption, encode or Encryption, decode cryptographic data. Based on th ...

. The result of such a computation remains encrypted. Homomorphic encryption can be viewed as an extension of public-key cryptography
Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys
KEYS (1440 AM broadcasting, AM) is a radio station serving the Corpus Christi, Texas, Corpus Christi, Texas area with a talk radio, talk ...

. ''Homomorphic'' refers to homomorphism
In algebra
Algebra (from ar, الجبر, lit=reunion of broken parts, bonesetting, translit=al-jabr) is one of the areas of mathematics, broad areas of mathematics, together with number theory, geometry and mathematical analysis, analysis. I ...

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.
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
Ductility is a mechanical property commonly described as a material's amenability to drawing
Drawing is a form of visual art in which an artist uses instruments to mark paper
Paper is a thin sheet material produced by mechanically a ...

. 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.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. 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 cryptosystemThe Goldwasser–Micali (GM) cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic encryption, probabilistic public-key encryption sch ...

(unbounded number of exclusive or
Exclusive or or exclusive disjunction is a logical operation
In logic
Logic is an interdisciplinary field which studies truth and reasoning
Reason is the capacity of consciously making sense of things, applying logic
Logic ...

operations)
* Benaloh cryptosystemThe Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1985 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in ...

(unbounded number of modular additions)
* Paillier cryptosystem
The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing ''n''-th residue classes is believed to be computationally difficult. The ...

(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
In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a data compression, compressed representation of set (ma ...

)
First-generation FHE

Craig Gentry
Craig Alan Gentry (born November 29, 1983) is an American former professional baseball
Professional baseball is organized baseball in which players are selected for their talents and are paid to play for a specific team or club system. It is pla ...

, 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 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 lattice cryptography, 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 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
Craig Alan Gentry (born November 29, 1983) is an American former professional baseball
Professional baseball is organized baseball in which players are selected for their talents and are paid to play for a specific team or club system. It is pla ...

, 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 lattice cryptography, 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 David Naccache, Naccache in 2008, and also to one that was proposed by Bram Cohen in 1998.
Cohen's cryptosystem, 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 FHE

The homomorphic cryptosystems of this generation are derived from techniques that were developed starting in 2011-2012 by Zvika Brakerski,Craig Gentry
Craig Alan Gentry (born November 29, 1983) is an American former professional baseball
Professional baseball is organized baseball in which players are selected for their talents and are paid to play for a specific team or club system. It is pla ...

, 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. VaikuntanathanFully Homomorphic Encryption without Bootstrapping

In ''ITCS 2012'' building on techniques of Brakerski-Vaikuntanathan;Z. Brakerski and V. Vaikuntanathan

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

On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption

In ''STOC 2012'' (ACM) * The Brakerski/Fan-Vercauteren (BFV, 2012) scheme, building on Brakerski's cryptosystem;Z. Brakerski

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

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, (Ring) Learning With Errors (RLWE) problem, except for the LTV and BLLN schemes that rely on an ''overstretched''M. Albrecht, S. Bai, and L. Ducas

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, 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

Fully Homomorphic Encryption with Polylog Overhead

In ''EUROCRYPT 2012'' (Springer) C. Gentry, S. Halevi, and N. P. Smart

Better Bootstrapping in Fully Homomorphic Encryption

In ''PKC 2012'' (SpringeR)C. Gentry, S. Halevi, and N. P. Smart

Homomorphic Evaluation of the AES Circuit

In ''CRYPTO 2012'' (Springer) 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. 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,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. Jacob Alperin-Sheriff and Chris Peikert then described a very efficient bootstrapping technique based on this observation.J. Alperin-Sheriff and C. Peikert

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. Xi

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

CKKS scheme supports efficient rounding operations in encrypted state. The rounding operation controls noise increase in encrypted multiplication, which reduces the number of bootstrapping in a circuit. In Crypto2018, CKKS is focused aa solution for encrypted machine learning.

This is due to a characteristic of CKKS scheme that encrypts approximate values rather than exact values. When computers store real-valued data, they remember approximate values with long significant bits, not real values exactly. CKKS scheme is constructed to deal efficiently with the errors arising from the approximations. The scheme is familiar to machine learning which has inherent noises in its structure. 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

In the following examples, the notation $\backslash mathcal(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 $\backslash mathcal(m)\; =\; m^e\; \backslash ;\backslash bmod\backslash ;\; n$. The homomorphic property is then :$\backslash begin\; \backslash mathcal(m\_1)\; \backslash cdot\; \backslash mathcal(m\_2)\; \&=\; m\_1^e\; m\_2^e\; \backslash ;\backslash bmod\backslash ;\; n\; \backslash \backslash [6pt]\; \&=\; (m\_1\; m\_2)^e\; \backslash ;\backslash bmod\backslash ;\; n\; \backslash \backslash [6pt]\; \&=\; \backslash mathcal(m\_1\; \backslash cdot\; m\_2)\; \backslash end$ 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 $\backslash mathcal(m)\; =\; (g^r,m\backslash cdot\; h^r)$, for some random $r\; \backslash in\; \backslash $. The homomorphic property is then :$\backslash begin\; \backslash mathcal(m\_1)\; \backslash cdot\; \backslash mathcal(m\_2)\; \&=\; (g^,m\_1\backslash cdot\; h^)(g^,m\_2\; \backslash cdot\; h^)\; \backslash \backslash [6pt]\; \&=\; (g^,(m\_1\backslash cdot\; m\_2)\; h^)\; \backslash \backslash [6pt]\; \&=\; \backslash mathcal(m\_1\; \backslash cdot\; m\_2).\; \backslash end$ Goldwasser–Micali In theGoldwasser–Micali cryptosystemThe Goldwasser–Micali (GM) cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic encryption, probabilistic public-key encryption sch ...

, if the public key is the modulus $n$ and quadratic non-residue $x$, then the encryption of a bit $b$ is $\backslash mathcal(b)\; =\; x^b\; r^2\; \backslash ;\backslash bmod\backslash ;\; n$, for some random $r\; \backslash in\; \backslash $. The homomorphic property is then
:$\backslash begin\; \backslash mathcal(b\_1)\backslash cdot\; \backslash mathcal(b\_2)\; \&=\; x^\; r\_1^2\; x^\; r\_2^2\; \backslash ;\backslash bmod\backslash ;\; n\; \backslash \backslash [6pt]\; \&=\; x^\; (r\_1r\_2)^2\; \backslash ;\backslash bmod\backslash ;\; n\; \backslash \backslash [6pt]\; \&=\; \backslash mathcal(b\_1\; \backslash oplus\; b\_2).\; \backslash end$
where $\backslash oplus$ denotes addition modulo 2, (i.e. Exclusive disjunction, exclusive-or).
Benaloh
In the Benaloh cryptosystemThe Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1985 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in ...

, 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 $\backslash mathcal(m)\; =\; g^m\; r^c\; \backslash ;\backslash bmod\backslash ;\; n$, for some random $r\; \backslash in\; \backslash $. The homomorphic property is then
:$\backslash begin\; \backslash mathcal(m\_1)\; \backslash cdot\; \backslash mathcal(m\_2)\; \&=\; (g^\; r\_1^c)(g^\; r\_2^c)\; \backslash ;\backslash bmod\backslash ;\; n\; \backslash \backslash [6pt]\; \&=\; g^\; (r\_1\; r\_2)^c\; \backslash ;\backslash bmod\backslash ;\; n\; \backslash \backslash [6pt]\; \&=\; \backslash mathcal(m\_1\; +\; m\_2\; \backslash ;\backslash bmod\backslash ;\; c).\; \backslash end$
Paillier
In the Paillier cryptosystem
The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing ''n''-th residue classes is believed to be computationally difficult. The ...

, if the public key is the modulus $n$ and the base $g$, then the encryption of a message $m$ is $\backslash mathcal(m)\; =\; g^m\; r^n\; \backslash ;\backslash bmod\backslash ;\; n^2$, for some random $r\; \backslash in\; \backslash $. The homomorphic property is then
:$\backslash begin\; \backslash mathcal(m\_1)\; \backslash cdot\; \backslash mathcal(m\_2)\; \&=\; (g^\; r\_1^n)(g^\; r\_2^n)\; \backslash ;\backslash bmod\backslash ;\; n^2\; \backslash \backslash [6pt]\; \&=\; g^\; (r\_1r\_2)^n\; \backslash ;\backslash bmod\backslash ;\; n^2\; \backslash \backslash [6pt]\; \&=\; \backslash mathcal(m\_1\; +\; m\_2).\; \backslash end$
Other partially homomorphic cryptosystems
*Okamoto–Uchiyama cryptosystem
*Naccache–Stern cryptosystem
*Damgård–Jurik cryptosystem
*Sander–Young–Yung encryption scheme
*Boneh–Goh–Nissim cryptosystem
*Ishai–Paskin cryptosystem
*Joye-Libert cryptosystem
*Castagnos–Laguillaumie cryptosystem
Fully homomorphic encryption

A cryptosystem that supports 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.Implementations

A list of open-source FHE libraries implementing second-generation and/or third-generation FHE schemes is provided below. An up-to-datlist of homomorphic encryption implementations

is also maintained by the community on GitHub. There are several open-source implementations of second- and third-generation fully homomorphic encryption schemes. Second-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 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.

Standardization

A community standard for homomorphic encryption is maintained by thHomomorphicEncryption.org

group, an open industry/government/academia consortium co-founded in 2017 by Microsoft, IBM, and others. The curren

standard document

includes specifications of secure parameters for RLWE.

See also

*Homomorphic secret sharing *Homomorphic signatures for network coding *Private biometrics *Verifiable computing, Verifiable computing using a fully homomorphic scheme *Client-side encryption *Searchable symmetric encryption *Secure multi-party computation *Format-preserving encryption *Polymorphic code *Private set intersectionReferences

External links

Daniele Micciancio's FHE references

*

HElib

Microsoft SEAL

PALISADE

HEAAN

FHEW

an

TFHE

(open-source homomorphic encryption libraries) {{DEFAULTSORT:Homomorphic Encryption Homomorphic encryption, Cryptographic primitives Public-key cryptography Information privacy