FHE over the Integers

This is a fully homomorphic encryption relying only on modular arithmetic introduced by van Dijk et al . The authors first create a somewhat homomorphic scheme which is bootstrappable and then apply Gentry's technique to construct a fully homomorphic scheme. We refer to Gentry's article for the precise definitions of "somewhat homomorphic" and "bootstrappable" schemme.

One of the main advantages of this scheme represents its conceptual simplicity. The security of the scheme is reduced to the approximate gcd problem over the integers, that is, given a list of integers that are near-multiples of an unknown integer d, find d.

A somewhat homomorphic encryption scheme

Using a theorem of Gentry, the authors are able to construct a homomorphic encryption scheme that can handle circuits of any depth from a scheme that is capable of evaluating just a little more than its own decryption circuit.

Let us first construct a somewhat homomorphic encryption scheme.

Definition. Let ${\mathcal {E}}=(Keygen,Encrypt,Decrypt,Evaluate)$ be an encryption scheme where $Decrypt$ is implemented by a circuit that depends only on the security parameter. For a given value $\lambda$ of the security parameter, the set of augmented decryption circuits consists of two circuits, both take as input a secret key and two ciphertexts. One circuit decrypts both ciphertexts and adds the resulting plaintext bits modulo $2$, the other decrypts both ciphertexts and multiplies the resulting plaintext bits modulo $2$. The authors denote this set by $D_{\mathcal {E}}(\lambda )$.

A homomorphic encyption scheme ${\mathcal {E}}=$ is called bootstrappable if for every value of the security parameter, the scheme can handle all the circuits in $D_{\lambda }$.

Given such a scheme ${\mathcal {E}}$ and a paramater $d=d(\lambda )$, there is an efficient transformation that outputs the description of another encryption scheme ${\mathcal {E}}^{(d)}$ which is compact, has the same $Decryption$ circuit as ${\mathcal {E}}$, and is homomorphic for all circuits of depth up to $d$.

If we assume that the initial bootstrappable scheme ${\mathcal {E}}$ is circular secure then it can be converted into a single compact fully-homomorphic encryption scheme ${\mathcal {E}}'$.

We refer to Gentry's article [2] for the precise definition of "compact", "bootstrappable" and "circular security".

The construction of the scheme

The construction has many parameters controlling the number of integers in the public key and the bit-length of various integers. We choose omit most of them in this presentation, but we refer the interested reader to M. van Dijk et al. for their precise description.

$Keygen(\lambda )$: The secret key is an odd $\eta$ bit integer. For the public key $p_{k}$, integers $x_{0},x_{1},\dots ,x_{\tau }$ are sampled uniformly from a given set of near-multiples of $p$. As previously mentioned, finding the secret key $p$ would require force an attacker to give a resolution for an approximate gcd problem in the integers. The latter is known to be very difficult.

$Encrypt(p_{k},m\in \{0,1\})$: Choose a random subset $S\subseteq \{1,2,\dots ,\tau \}$ and a random integer $r$ in a specified range, and output $c\leftarrow \left(m+2r+2\sum _{i\in S}x_{i}\right){\pmod {x_{0}}}$.

$Evaluate(p_{k},C,c_{1},\dots ,c_{t})$: Given the (binary) circuit $C$ with $t$ inputs and ciphertexts $c_{1},\dots ,c_{t}$, apply the integer addition and multiplication gates of $C$ to the ciphertexts, performing all the operations over the integers and output the result, an integer.

$Decrypt(s_{k},c)$: Output $m'\leftarrow$ ($c$ mod $p$) mod 2.

Remark. The encryption can be viewed as adding the underlying message $m$ to a random subset sum of encryptions of zero. Indeed, notice that each $w_{i}=2x_{i}{\pmod {x}}_{0}$ and also $x_{0}$ is essentially an encryption of zero; its noise is even. Moreover, $c=m+2r+\sum _{i\in S}w_{i}-k\cdot x_{0}$ for some integer $k$.

The proposers of the scheme prove that ${\mathcal {E}}$ can handle circuits if these can be represented by multivariate polynomials with degree smaller than some given, explicit bound.

Ciphertext compression

The authors of the scheme describe various optimisations in order to keep the evaluated ciphertexts of the same length as the original "fresh" ciphertexts. However, the size of the evaluated ciphertexts is still very large large for applications.

To solve this problem, the authors propose a compression of these ciphertexts down to the size of an RSA modulus. This reduces the communication complexity of the scheme dramatically.

The price of this optimisation is that the compressed ciphertexts cannot be further evaluated and hence this compression can be used only on the final output ciphertexts, after all the desired evaluations were completed.

Making the scheme fully homomorphic

In order to successfully transform ${\mathcal {E}}$ into a bootstrappable scheme, the authors slightly modify the decryption circuit of ${\mathcal {E}}$. The problem with ${\mathcal {E}}$ is that its decryption equation $m'\leftarrow (c-\lfloor c/p\rfloor )$ mod 2, requires Boolean circuits that are deeper than what ${\mathcal {E}}$ can handle.

An idea of Gentry is used to “squash”, i.e. to simplify, the decryption circuit. In this transformation, one adds to the public key some extra information about the secret key. This extra information is then used to “post process” the ciphertext such that the latter can be decrypted more efficiently.

This is paid for by introducing another so called “hardness assumption”, basically assuming that the extra information in the public key does not help an attacker break the scheme.

In the modified scheme, we add to the public key from the original ${\mathcal {E}}$ a set ${\mathcal {y}}=\{y_{1},\dots ,y_{\theta }\}$ of $\theta$ rational numbers belonging to $[0,2)$ such that there is a sparse (in a precise sense) subset $S\subset \{1,\dots ,\theta \}$ with $\sum _{I\in S}y_{i}\approx 1/p$ (mod 2). The secret key is replaced by the indicator vector of the subset $S$.

The new key generation procedure will output the aforementioned public and secret keys.

To encrypt or evaluate, one generates a ciphertext $c*$ as in the scheme ${\mathcal {E}}$. Then for each $I\in S$, set $z_{i}\leftarrow c*\cdot y_{i}$ (mod 2) (of course, these operations are done with a bounded number of bits of precision). The procedure outputs $c*$ and the vector $z=<z_{1},\dots ,z_{\theta }>$.

To decrypt, one just has to output $m'\leftarrow c*-\lfloor s_{i}z_{i}\rfloor$ (mod 2).

It can be easily shown that the modified scheme is correct for all the circuits that the original scheme ${\mathcal {E}}$ could handle.

On the other hand, the authors prove (see Theorem 3 of loc. cit.) that new scheme can handle its decryption circuit, hence it can be bootstrapped and transformed into a fully homomorphic encryption scheme.