DGHV Asymmetric Scheme

Scheme Construction:

For a specific (η bits) odd positive integer p, we use the following distribution over γ –bit inte-gers:

Dγ,ρ (ρ) = {choose q ←Z ∩ [0, 2^γ/p ), r ← Z ∩(-2^ρ, 2^ρ): output x = pq + r}

KeyGen(λ): The secret key is an oddη–bit integer:

                 P ← (2Z + 1) ∩ [2^n-1, 2^η).

For the public key, sample xi← D γ,p for I = 0,…….., τ. Relabel so that x0 is the largest. Restart

unless x0 is odd and  rp(x0) is even. The public key pk= ‹ x0, x1,……. xτ ›.

Encrypt (pk, m∊{0,1}) and a random integer r in (-2^ρ,2^ρ’), and output

                                                c ← [m + 2r + 2 Ʃ _i∊S x_i] _x0                                                                            

Evaluate (pk, C,c1,c2,…….,ct): Given the (binary) circuit C with t inputs, and t ciphertexts ci, apply the (integer) addition and multiplication gates of C to the cipher-texts, performing all the operations over the integers, and return the resulting integer.

Decrypt (sk, c): Output m’←(c mod p) mod2.

Remark: Decryption can also be written as: m’←[c-⌊c/p˥]2.

Homomorphic properties:

The homomorphic properties of the asymmetric scheme is interpreted as the symmetric one