1
$\begingroup$

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

$\endgroup$
5
$\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.

| improve this answer | |
$\endgroup$
  • 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 at 15:00
  • $\begingroup$ Thanks .. can you explain the relation with the noise growth ? $\endgroup$ – witdev May 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 at 16:39

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.