Zero knowledge proof for Paillier addition under multiple keys Suppose $m_0, m_1, m_2 \in \mathbb{N}$ such that $m_0 = m_1 + m_2$, $m_i &gt; 0$ (none of them can be 0 or lower)

Under a Paillier cryptosystem, set


$e_0 = E(m_0, r_0)$ for a public key $(g_0, n_0)$
$e_1 = E(m_1, r_1)$ for a public key $(g_1, n_1)$
$e_2 = E(m_2, r_2)$ for a public key $(g_2, n_2)$


Can I prove (to a 3rd party, the verifier) that $m_0 = m_1 + m_2$ (or rather the equation with its encrypted counterparts hold) without revealing either of $m_0, m_1, m_2$ nor the private keys?

I, the prover, know all $m_i$, all public keys $(g_i, n_i)$ (by extension, also all $e_i$) and finally the private key $(\lambda_0,  \mu_0)$ for $(g_0, n_0)$ but not for the rest. Also, I as the prover get to choose all $r_i$



If all $e_i$ where encrypted under the same pubkey $(g,n)$, then I know we could check if $e_0 \cdot (e_1 \cdot e_2)^{-1}$ is a power of $n^2$ (as that evaluates to the encryption of 0), but it is not the case under diferent $(g_i,n_i)$.

Take $(\cdot)^{-1}$ as the modular multiplicative inverse, thus emulating the subtraction in Paillier.



I might use other cryptosystems (ie. ElGamal) as long as they have homomorphic properties
As far as I know, with the same public key $(g,n)$
I would change the problem to prove that if
$e_0 = E(m_1,r_1)\cdot E(m_2,r_2)$
then $m_0 = D(e_0) = m_1 + m_2 \bmod n$ where $D(e_0)$ is the result of decrypting ciphertext $e_0$. Thanks Geoffroy for your helpful comment and LaTeX conversion regarding my incorrect guess on the use of html here. .