# Fully Homomorphic Encryption (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**:**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).

Fully homomorphic encryption (FHE) is an encryption scheme that allows for arbitrary computations over encrypted content. Only the owner of the key can decrypt the result of the computation.

In the following examples, the notation is used to denote the encryption of the message .

****

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.Noise in Homomorphic encryption

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.

Homomorphic encryption

Wikipedia

Homomorphic encryption - Wikipedia

Homomorphism

Wikipedia

Homomorphism - Wikipedia

What exactly is bootstrapping in FHE?

Cryptography Stack Exchange

What exactly is bootstrapping in FHE? - Cryptography Stack Exchange

Real-World Cryptography

Manning Publications

Real-World Cryptography

Last modified 1yr ago