I'm new to encryption and am trying to implement Paillier encryption from the wikipedia page here: https://en.wikipedia.org/wiki/Paillier_cryptosystem

I managed to implement the encryption and am successfully able to decrypt as well to get the same message - so thats working which is good.

Then I wanted to check homomorphism and followed this formula for homomorphic addition:

$D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}){\bmod n}^{2})=m_{1}+m_{2}{\bmod n}$

And it works as it should until the number goes larger than a certain value.

For example if msg1 = 50 and msg2 = 100, then using the above formula I can multiply their ciphertexts and it will decrypt to added = 150.

But if the addition of the two numbers go higher than 390 the decryption overflows (?). For example:

msg1 = 100 and msg2 = 100, would give added = 200 once decrypted.

msg1 = 290 and msg2 = 100, would give added = 390 once decrypted.

msg1 = 291 and msg2 = 100, would give added = 0 once decrypted.

msg1 = 292 and msg2 = 100, would give added = 1 once decrypted.

msg1 = 293 and msg2 = 100, would give added = 2 once decrypted.

and so on.

Is this expected behaviour? I must be doing something wrong, but going over the implementation I seem to have every step implemented correctly.

Some guidance here would be appreciated.

I am using Matlab as my tool and I am using the variable precision toolbox for my inputs so overflows should not happen from Matlab, the problem must be at my understanding of the system

  • 3
    $\begingroup$ What is your $n$ value? $\endgroup$
    – mikeazo
    Commented May 17, 2018 at 16:21
  • $\begingroup$ @mikeazo my $n$ value is 391, this is from selecting a $p$ value of 23 and a $q$ value of 17. $\endgroup$ Commented May 18, 2018 at 11:31
  • 1
    $\begingroup$ no. if $n$ is so small, it provides no security. You need $n$ to be about 2048-bit. $\endgroup$ Commented Jul 9, 2018 at 19:57

1 Answer 1


The plaintext space for Paillier is integers modulo $n$. You are seeing "overflow" at the modulus, which makes sense. You should choose larger primes for both security reasons and to make it so that you can support larger numbers without the "overflow".


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.