1
$\begingroup$

Does the problem of noise growth exist in the Paillier homomorphic scheme ?

$\endgroup$
6
$\begingroup$

Does the problem of noise growth exist in the Paillier homomorphic scheme ?

No, it does not. Unlike Lattice-based schemes, you can do as many homomorphic additions as you want in Paillier (without doing anything like a "reboot"), and it's never a problem.

$\endgroup$
4
  • 4
    $\begingroup$ Yes. It must sometime be taken into account that the homomorphic property of the Paillier scheme is modulo $N$. $\endgroup$
    – fgrieu
    May 20 '20 at 15:00
  • $\begingroup$ Thanks .. can you explain the relation with the noise growth ? $\endgroup$
    – witdev
    May 20 '20 at 15:26
  • $\begingroup$ @witdev: The value $g^x r^n \bmod n^2$ is a valid encryption of the plaintext $x$ (for any $0 < r < n$, $r$ r.p. to $n$. The multiplication of the two ciphertexts $g^x r^n \bmod n^2$ and $g^y r'^n \bmod n^2$ is thus $g^{x+y} (rr')^n \bmod n^2$, and thus is always a valid encryption of $x+y \bmod n$. This always holds, and hence there is no 'noise growth'; the interaction of the random values $r, r'$ never interferes with the decryption process (and so you don't run into the same problems you do with Lattice based systems) $\endgroup$
    – poncho
    May 20 '20 at 16:39
  • $\begingroup$ Paillier is a encryption scheme based on the number theroy and there is non-existing noise like lattice-based cryptography. $\endgroup$
    – Land
    Jun 17 at 2:37

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.