I have two numbers $x_1$ and $x_2$, and there are two Paillier homomorphic encryption (public, private) key pairs $(p_1,r_1)$ and $(p_2, r_2)$. I only know $p_1, r_1$ and $p_2$. Suppose $C_1=E_{p_1}(x_1)$ and $C_2=E_{p_2}(x_2)$, here $E$ means Paillier homomorphic encryption.

How can I prove $x_1$ equals $x_2$ when I only gives $C_1$, $C_2$, $p_1$ and $p_2$? Thank you!

  • $\begingroup$ If they are encrypted under the same public key, then this is easy, and is shown in the Damgard-Jurik paper. Since these are different public keys, it is more challenging. I would suggest a cut-and-choose type of approach. $\endgroup$ Jun 22 '18 at 7:33
  • $\begingroup$ Thank you. Can you please give more details? Like some reference papers? $\endgroup$
    – Felix LL
    Jun 22 '18 at 7:56

Your Answer

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

Browse other questions tagged or ask your own question.