Score:1

Do we need to consider overflow in paillier encryption?

de flag

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?

Score:3
cn flag

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.

rzxh avatar
de flag
Great thanks to you again! Really didn't think about the malicious situation at all.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.