Implementation of the DGHV fully homomorphic encryption scheme

Project README

```
An implementation of the DGHV fully homomorphic scheme
```

This is an implementation of the DGHV fully homomorphic scheme with compressed public-key. This implementation is described in the following article:

[1] J.S. Coron, D. Naccache and M. Tibouchi, "Public-key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers", Proceedings of Eurocrypt 2012.

available at http://eprint.iacr.org/2011/440

The implementation is done with the SAGE 4.7.2 mathematical library under Python, available at http://www.sagemath.org/.

An encryption scheme is fully homomorphic when it is possible to perform implicit addition and multiplication of plaintexts while manipulating only ciphertexts. The first construction of a fully homomorphic encryption (FHE) scheme was described by Gentry in 2009.

The DGHV scheme is a FHE scheme published in:

[2] M. van Dijk, C. Gentry, S. Halevi and V. Vaikuntanathan, "Fully Homomorphic Encryption over the Integers". Proceedings of Eurocrypt 2010.

and available at http://eprint.iacr.org/2009/616

In DGHV a ciphertext has the form:

c= q*p + 2*r + m

where p is the secret-key, m is the bit plaintext (m=0 or 1), q is a large random, and r is a small random.

To decrypt, compute m=(c mod p) mod 2. It is easy to see that decryption works as long as the noise 2*r is smaller than p.

Given two ciphertexts
c1= q1*p + 2*r1 + m1
c2= q2*p + 2*r2 + m2

we have:

c1+c2=(q1+q2)*p+2*(r1+r2)+m1+m2

Therefore one can obtain the encryption of m1+m2 (mod 2)=m1 xor m2 simply by computing c1+c2.

Similarly we have:

c1*c2=q12*p+2*(2*r1*r2+r1*m2+r2*m1)+m1*m2

Therefore one can obtain the encryption of m1*m2 simply by computing
c1*c2. However one gets a new ciphertext with noise roughly
twice larger than in the original ciphertexts c1 and c2. Since the
noise must remain below p, the number of permitted multiplications on
ciphertexts is therefore limited. This is called a somewhat
homomorphic encryption scheme.

To obtain a fully homomorphic encryption scheme, i.e. unlimited addition and multiplication on ciphertexts, one must be able to reduce the amount of noise in a ciphertext; this is called a ciphertext refresh.

Gentry's key idea to refresh a ciphertext is to homomorphically
evaluate the decryption circuit on the ciphertext bits, using an
encryption of the secret-key bits. This is called bootstrapping.
Then instead of getting the plaintext bit (as we would get if we
would evaluate the decryption circuit with the secret-key bits in
clear), we get an **encryption** of the plaintext bit, i.e. a new
ciphertext for the same plaintext. Now if the decryption circuit has a
small enough depth, then the amount of noise in the new ciphertext can
be actually smaller than in the original plaintext, hence a ciphertext refresh.

However the previous decryption algorithm m=(c mod p) mod 2 does not have a small depth, therefore the decryption procedure must be "squashed" so that it can be expressed as a low depth circuit. How this is done in explained in [2].

So far we have only described a secret-key encryption scheme, i.e. to encrypt one must know the secret-key p. However it is easy to obtain a public-key encryption scheme. For this generate a public set of ciphertexts xi which are all different encryptions of 0:

xi=qi*p+2*ri

and to encrypt a bit m compute:

c=m+2*r+random_subset_sum(xi)

It is easy to see that c is indeed an encryption of the bit m.

We provide an implementation of the DGHV scheme with the fully homomorphic capability, i.e. we implement the key generation, encryption, decryption, add, mult and ciphertext refresh procedures.

The implementation is done using the Sage 4.7.2 mathematical library under Python, available at http://www.sagemath.org/

First run sage, then type:

sage: load "dghv.sage" sage: testPkRecrypt()

The testPkRecrypt() function demonstrates key generation, addition and multiplication of ciphertexts, and ciphertext refresh. It runs for four sets of parameters (toy, small, medium and large), as described in [1].

In DGHV the ciphertext size must be huge to prevent attacks based on lattice reduction algorithms; at least 10^7 bits. The secret p is comparatively smaller, roughly 2000 bits. Since roughly 10^4 ciphertexts xi must be included in the public-key, that would give a public-key size of 10^11 bits, i.e. 12.5 GB.

To reduce the public-key size we implement the following technique
described in [1]. Instead of generating xi as xi=qi*p+2*ri, one first
generates a pseudo-random Xi of the same size, and computes a small
correction di such that xi=Xi-di is small modulo p. Then only these
small corrections need to be stored in the public-key, with the seed
of the PRNG. Using this compression technique the public-key size
becomes 10^4*(2*10^3)=2*10^7 bits, i.e. 2.5 MB, which is more
manageable.

Open Source Agenda is not affiliated with "Fhe" Project. README Source: coron/fhe