Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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:
Given several multiples $q_ip$ of $p$.
What is $q_i$?
$c = q p + 2r + m$.
When noise is raised/introduced in the system?
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.
