8
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\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
    Commented Nov 29, 2017 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
    Commented Nov 30, 2017 at 23:35
  • $\begingroup$ Did you ever find a solution to this ? $\endgroup$
    – BGR
    Commented Jul 12, 2018 at 5:19
  • $\begingroup$ No.. I didn't have time though and had to put this project off for the time being $\endgroup$
    – Guillem
    Commented Jul 13, 2018 at 14:53

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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
    Commented Apr 8, 2018 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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