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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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, 2017 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$).

Improve this answer
$\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.