Assuming I have three messages m1,m2,m3 where m1=m2=m3=1 and I compute c1,c2 and c3.

Does that mean that c1=c2=c3 in cipher-text from ? If not, how many times can I encrypt a message m=1 and still produce a unique cipher-text ?

if not possible, can I solve the problem by putting Zeros as padding and still use the additive property ? (e.g. m1=01...m2=001 and m3=0001 and when I calculate x=c1+c2+c3 the decrypted result D{x}=3)

I just started working with cryptography, so please be understanding. :-)


1 Answer 1


Yes, Paillier encryption is secure from known plaintext attack (for single-character message, and any other supported message size). With high likelihood, three ciphertexts $c_1$, $c_2$ and $c_3$ for the same plaintext will be different.

When using public modulus $n$, each Paillier encryption draws a uniformly random number $r$ in range $[0,n)$ (some descriptions say $[0,n^2)$ but it turns out only $r\bmod n$ has an influence on the cryptogram; and in some descriptions it's added $r$ is coprime with $n$, but that's overwhelmingly likely for secure choice of $n$, thus can be omitted). Different $r$ will lead to different cryptograms $c=g^m\cdot r^n\bmod n^2$.

For proper implementation, by the birthday problem 101, the probability is about $k^2/2n$ that among $k$ ciphertexts for the same plaintext, any two are equal. For security against factoring, $n$ must have some thousand bits, thus said probability is entirely negligible for any feasible $k$ and secure choice of $n$. It is much more likely that whatever generates $r$ gets defective, and hickups, leading to identical ciphertexts.

Note: Pailler encryption is homomorphic only for messages that are straight integers $m$. Padding with zeroes on the left can't change $m$ if the homomorphic property must remain.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.