# Paillier Homomoprhic addition overflows after a certain value

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

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

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".