0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ella Rose Apr 19 '17 at 20:58
1
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.