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

  • $\begingroup$ 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? $\endgroup$ – Geoffroy Couteau Nov 29 '17 at 20:16
  • $\begingroup$ @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) $\endgroup$ – Guillem Nov 30 '17 at 23:35
  • $\begingroup$ Did you ever find a solution to this ? $\endgroup$ – BGR Jul 12 '18 at 5:19
  • $\begingroup$ No.. I didn't have time though and had to put this project off for the time being $\endgroup$ – 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. .

  • $\begingroup$ Answering the now-deleted part of your answer on using html: you don't have to use html for typing math here, the website directly supports LaTeX math writing (you can edit your answer to see how I formatted your equation). $\endgroup$ – Geoffroy Couteau Apr 8 '18 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.