Do we need to consider overflow in paillier encryption?

Question

Homomorphic multiplication of plaintexts in Paillier cryptosystem can be constructed as follow: Dsk(E(x1)^x2 mod N^2) = x1x2 mod N. So after the decryption, we get the result of multiplication x1x2. My question is, is it necessary for us to think about the situation : x1*x2>N which leads to an overflow? Or because the parameter N is quite large(usually 1024 bits or even 2048 bits) so in most usage scenarios we don't have to consider this problem by default?

Answer 1

Yes, it is often necessary to consider overflows in Paillier encryption. The reason is simple: even though in most situations, the values are supposed to be way too small to cause any overflow issue, what does prevent malicious users to cause overflows in order to cheat?

Without a specific scenario, it is hard to be more precise, but there are many situations where, if nothing is done, a cheater could (by forcing overflows to happen, by using very large values with Paillier) create errors in the system, learn private information, or succeed at something they should not be allowed to succeed at.

Here is an example: in this paper, Yehuda Lindell develops a two-party protocol for ECDSA signing. The signing process is essentially performed homomorphically and interactively, inside a Paillier ciphertext. Then, if nothing is done to prevent overflows, security is broken; to prevent this, the paper uses range proofs: zero-knowledge proofs to guarantee that an encrypted value is not large enough to cause overflows.