Can Paillier Homomorphic Encryption handle more than one binary plaintext?

Question

I am reading about Paillier Homomorphic Encryption, given here: https://en.wikipedia.org/wiki/Paillier_cryptosystem

I have two questions:

1) Is this restricted to only two plaintexts? Can I extend the homomorphic properties to more than two plaintexts?

2) Refer to:

$D(E(m_1, r_1)E(m_2, r_2) \mod n^2) = m_1 + m_2 \mod n$

what would happen if $(m_1 + m_2) > n$? Wouldn't that lose data?

Answer 1

1. This will work with any number of plaintexts, $m=\left[m_1,\cdots ,m_k\right]$: $$ \begin{align} D\left(E\left(m_1,r_1\right)\cdots E\left(m_k,r_k\right)\right) & = D\left(g^{m_1}r_1^N\cdots g^{m_k}r_k^N\right)\\ &=D\left(\left(g^{m_1} \cdots g^{m_k}\right)\left(r_1^N\cdots r_k^N\right)\right) \\ &=D\left(\left(g^{m_1 +\cdots + m_k}\right)\left(r_1 \cdots r_k\right)^N\right)\\ &=D\left(E\left(m_1+\cdots +m_k,r_1 \cdots r_k\right)\right)\\ &=m_1 +\cdots + m_k \end{align} $$

We can see this last step is valid, as $\gcd(a,N)=1$ and $\gcd(b,N)=1\implies \gcd(ab,N)=1$ which we can extend infinitely.

2. That is correct, if $m_1 + m_2 > N$ then there will be a loss of information. This is stated in the original equation. To add together larger numbers, we must choose a larger $N$