# 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 > 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

• Could you detail a bit which variant of Paillier you use, like, what do the different public key exactly correspond to, and the decryption keys? – Geoffroy Couteau Nov 29 '17 at 20:16
• @GeoffroyCouteau Sure, the public key $(g, n)$ is the encryption key, while the private key $(\lambda, \mu)$ is the decryption key (ie, anyone can encrypt but only I can decrypt), traditional encrypting scheme (not signing) – Guillem Nov 30 '17 at 23:35
• Did you ever find a solution to this ? – BGR Jul 12 '18 at 5:19
• No.. I didn't have time though and had to put this project off for the time being – Guillem Jul 13 '18 at 14:53

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