# Is there any way to prove two numbers that are equal after Paillier encryptions?

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!

• 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. – Yehuda Lindell Jun 22 '18 at 7:33
• Thank you. Can you please give more details? Like some reference papers? – Felix LL Jun 22 '18 at 7:56