# Homomorphic encryption and approximated GCD

I am reading the paper Fully homomorphic encryption over the integers (PDF). The paper reduced the security to the approximated GCD problem. My first question is whether the scheme proposed by the paper is semantically secure?

In the paper, the plaintext set is {0,1} and the scheme is asymmetric. I am now thinking about a symmetric setting in which the plaintext set is integers. For an integer $m_i$, the encryption is $c_i=pq_i+m_i$ and the decryption is $m_i=c_i\mod p$, where $p$ is the key and $q_i$ is some randomly chosen integer. It seems that this scheme is fully homomorphic (if the key is large enough). My question is that whether this scheme is secure at all? If so, what kind of security level I can claim?

## 2 Answers

This cipher is broken against chosen plaintext attack. Submit encryptions of 0 to obtain a set where each element is composed of p times some random q. Then, compute the gcd of some of the pairs until you acquire p.

If p and q are not prime, you will require more then two pairs.

You may be interested in the DoubleMod construction.

• There are other ways to break the construction using known plaintext attack, as well as just knowing that certain ciphertexts are encryptions of identical but unknown messages. – Ella Rose Apr 19 '17 at 20:58

The approximate gcd problem is not the same as the gcd problem. If you would like to encrypt numbers of a different base, then you will have to use appropriate noise for that base (modeled originally by $2\cdot r$).