I'm reading a paper based on Homomorphic Encryption: “Fully Homomorphic Encryption over the Integers: From Theory to Practice” (PDF).

Now, I need a diagram of this algorithm if possible with all the operation that the sender of cyber text do.

I'm reading the text and I encountered some problems:

  1. Given several multiples $q_ip$ of $p$.

    What is $q_i$?

  2. $c = q p + 2r + m$.

    When noise is raised/introduced in the system?


2 Answers 2


The author starts talking about multiples of $p$, because he wants to talk about the problem of find a $gcd$ (great common divisor) of a list of numbers (in this case, the $gcd$ is the secret $p$). He is somehow trying to make you understand why we cannot encrypt the binary messages $m \in \{0, 1\}$ by simply adding them to $q_i p$.

It means it would be insecure to use $qp + m$ as an encryption of a bit $m$, because encrypting a lot of bits $m_1, m_2, ..., m_N$ as $q_1p + m_1, q_2p + m_2, ..., q_Np + m_N$ would give the attacker a chance to recover the secret key $p$ from this list of encrypted values.

Therefore, to guarantee the security of the encryption process, we add a small noise. And to guarantee that the decryption will work, we chose this noise to be even, this is why we pick a small value $r$ and use $qp + 2r + m$ as the encryption of $m$.

Thus, the noise is introduced on the encryption. But, when we add or multiply two ciphertexts, we generate a third ciphertext whose noise is bigger than the noise of those two, so, we may say that the noise is also introduced when we operate over the ciphertexts.

And answering your comment: no, the sender does not choose the value of $2r$. It must be a random value. The only thing known is the interval in which the values of $r$ are sampled from and that interval is defined by the parameters that the sender chooses for the scheme (of course, following the restrictions that those parameters must respect).


qi is the i-th integer of the list q of integers.
2r is added in the encryption process.

  • $\begingroup$ 1) qi is the list of integer that i want convert in cyber text? 2) When 2r is added in the process? Is the sender of message that decide what value assumes "r"? $\endgroup$
    – aRaKaNoiD
    Jan 11, 2016 at 17:24
  • $\begingroup$ 1) ​ ​ ​ I'm not sure what you mean by that, but I think the answer is no. ​ The list q is chosen during the key generation process. ​ ​ ​ ​ ​ ​ 2) ​ ​ ​ Adding 2r is the end of the encryption process. ​ Yes. ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user991
    Jan 11, 2016 at 17:29
  • $\begingroup$ For the point 1) can you show me a simple example? or give me a link? $\endgroup$
    – aRaKaNoiD
    Jan 12, 2016 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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