Fully Homomorphic Encryption (FHE)

What is FHE?

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. Homomorphic refers to homomorphism in algebra: the encryption and decryption functions can be thought of as homomorphisms between plaintext and ciphertext spaces.

A homomorphism is a map between two algebraic structures of the same type (that is of the same name), that preserves the operations of the structures. This means a map $f: A \rightarrow B$ between two sets $A, B$ equipped with the same structure such that, if $\cdot$ is an operation of the structure (supposed here, for simplification, to be a binary operation), then

f(x \cdot y) = f(x) \cdot f(y)

for every pair $x, y \in A$ . One says often that $f$ preserves the operation or is compatible with the operation.

Homomorphic encryption includes the following types:

Partially homomorphic encryption: only homorphic for the addition or multiplication, not both.
Somewhat homomorphic encryption: partially homomorphic for one operation (addition or multiplication) and homomorphic for the other operation in limited ways. For example, additions are unlimited up to a certain number but only a few multiplications can be done.
Leveled fully homomorphic encryption: both addition and multiplication are possible up to a certain number of times.
Fully homomorphic encryption (FHE): addition and multiplication are unlimited (it’s the real deal).

Partial Homomorphic Encryption Examples

In the following examples, the notation $\mathcal{E}(x)$ is used to denote the encryption of the message .

Unpadded RSA

${\begin{aligned}{\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{aligned}}$

ElGamal

${\begin{aligned}{\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{aligned}}$

Goldwasser–Micali

${\begin{aligned}{\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_{1}r_{2})^{2}\;{\bmod {\;}}n\\[6pt]&={\mathcal {E}}(b_{1}\oplus b_{2}).\end{aligned}}$

Noise

Before the invention of FHE, several types of homomorphic encryption schemes were proposed, but none could achieve what fully homomorphic encryption promised. The reason is that by evaluating circuits on encrypted data, some noise grows; after a point, the noise has reached a threshold that makes decryption impossible. And, for many years, some researchers tried to prove that perhaps there was some information theory that could show that fully homomorphic encryption was impossible; that is, until it was shown to be possible.

From https://crypto.stackexchange.com/questions/35150/noise-in-homomorphic-encryption:

Bootstrapping

With (most) FHE schemes, we are evaluating circuits, or a bunch of gates hooked together. Often, we think of circuits in terms of and/or/not gates. It turns out, however, that you can construct circuits from other types of gates. NAND by itself is functionally complete (here is the proof: https://github.com/ret2basic/nand2tetris/tree/main/projects/01). So, with just a single NAND gate, you can construct any circuit. That is why we need a scheme that can compute at least one NAND gate (in addition to its own decryption circuit).

FHE schemes add noise to the ciphertext. So, you can evaluate a circuit on the input ciphertext(s), but you may add so much noise in the process of doing this that you can no longer decrypt. That is the problem we are faced with. It is important to remember that inputs to the circuits are ciphertexts, and that the output of the circuit is a ciphertext.

LWE

Reference

PreviousLearning with Error (LWE)NextZero Knowledge Proof (ZKP)

Last updated 3 years ago

hashtagWhat is FHE?

hashtagPartial Homomorphic Encryption Examples

hashtagUnpadded RSA

hashtagElGamal

hashtagGoldwasser–Micali

hashtagNoise

hashtagBootstrapping

hashtagLWE

hashtagReference