Homomorphic encryption (HE):

An encryption scheme E is called homomorphic over an operation # if E(x1)#E(x2) = E(x1#x2) where x1, x2 belongs to X (data/message space)

Why HE is important?

Allows computation over the data without revealing the data itself.

Different categories of HE schemes (based on the number of allowed operations on the encrypted data):

1) Partially Homomorphic Encryption (PHE)

· allows only one type of operation for an unlimited number of times (i.e., no bound on the number of usages)

· supports only addition or multiplication operation

· used for particular applications such as e-voting, Private Information Retrieval

· algorithms: RSA (supports only multiplication), Goldwasser-Micali (supports only addition)

2) Somewhat Homomorphic Encryption (SWHE)

· allows some types of operations for a limited number of times

· supports both addition and multiplication

· the size of the ciphertexts grows with each homomorphic operation which limits the maximum number of allowed operations

· algorithms: Yao, SYY, BGN

3) Fully Homomorphic Encryption (FHE)

· allows unlimited number of operations for unlimited number of times

· Gentry provided a general framework to obtain an FHE scheme in 2009 Craig Gentry (2009) https://crypto.stanford.edu/craig/craig-thesis.pdf. Gentry’s FHE scheme is based on hard problems on ideal-lattices. It is the first plausible and achievable FHE scheme. Theoretically, an arbitrary computation can be broken down into binary NAND operations and hence the computation can be achieved by a suitable circuit made of NAND gates. For example, see 2-bit multiplication circuit here https://en.wikipedia.org/wiki/Binary_multiplier#/media/File:Binary_multi1.jpg. This means an encryption algorithm that is homomorphic for NAND operation can be theoretically considered an FHE. However, as the computation becomes more complex, the equivalent NAND circuit will become deeper and the noise in ciphertexts increase with the depth. After a certain depth, the accumulated noise becomes so much that it will be impossible to decrypt the ciphertext, thus making the encryption scheme SWFHE only. One way to solve the noise problem is to transform the ciphertext at each depth level so that the noise level reduces, thereby increasing the maximum depth of the circuit that can be decrypted. This step is called bootstrapping in Gentry’s FHE scheme where a ciphertext with noise N’< N is transformed to a fresh ciphertext with noise smaller than sqrt2(N), hence allowing the possibility of arbitrary-depth decryptable circuit and thereby FHE.

Post Gentry FHEs

After the introduction of ideal-lattice based FHE by Gentry in 2009, many FHE schemes optimizing Gentry’s FHE as well as other novel FHE schemes have been developed. Main FHE families after Gentry’s breakthrough are:

1. Gentry’s FHE based on ideal lattice

2. Over Integers FHE schemes — hardness of the scheme is based on the Approximate GreatestCommon Divisor (AGCD) problems

3. Learning with Error (LWE) based FHE schemes

4. NTRU like FHE schemes

References

1. Abbas Acar, Hidayet Aksu, A. Selcuk Uluagac, Mauro Conti, A Survey on Homomorphic Encryption Schemes: Theory and Implementation, 2017, https://arxiv.org/abs/1704.03578
2. https://www.reddit.com/r/crypto/comments/6yg2nw/a_survey_on_homomorphic_encryption_schemes_theory/dmo4q95/?context=3
3. Gentry Craig, Computing Arbitrary Functions of Encrypted Data, 2009, https://crypto.stanford.edu/craig/easy-fhe.pdf