DGHV Symmetric Scheme Algorithm

basic symmetric scheme:

The secret key is odd integer, chosen from some interval p∊ [2^n-1 , 2ⁿ] where n is the bit length of the secret key. The cipher-text of a plain-text m∊ {0,1} is given by:

                                    c = Encrypt (p, m) = pq + 2r + m                                                                               

Where the integers q, r are chosen randomly in some other intervals, such that 2r is smaller than p/2 in absolute value. In this scheme, the cipher-text is an integer whose residue mod p has the same parity of the plaintext m.

                                   Decrypt (p, m) = (c mod p) mod 2r                                                                             

The decryption works as long as the noise r is much smaller than p.

                                    m’ ←[ c- ⌊c/p˥ ]2                                                                                                         

2) Homomorphic behavior: Suppose that we have two plain-texts m1,m2, with two ciphertextsrespectively c₁ = pq₁ + 2r₁ + m₁, c₂ = pq₂ + 2r₂ + m₂ .

a) Addition:

                                          c₁+ c₂= p(q₁+ q₂) + 2(r₁+ r₂) + m₁+ m₂                                                                     

Decryption works as long as 2(r₁ + r₂) ∊ [-p/2, p/2].

b) Multiplication:

    c₁ × c₂ = p(pq₁q₂ + 2r₂q₁ + q₁m₂ + 2q₂r₁ + m₁q₂) + 2(2r₁r₂ + m₂r₁ + m₁r₂) + m₁m₂                                     

Decryption works as long as 2(2r₁r₂ + m₂r₁ + m₂r₂) ∊ [-p/2, p/2]