# Efficiently prove the correctness of Paillier encryption in or "outside" a zk-SNARK

I'm working with a zk-SNARK library [1] that allows me to prove the correctness of arbitrary arithmetic circuits, and I now want to use these zk-SNARKs to prove that some Paillier [2] ciphertext $$c$$ was generated by correctly encrypting some secret plaintext $$m$$ with randomness $$r$$ (as well as that some other properties hold on $$m$$).

To prove this, I encoded Paillier encryption in the arithmetic circuit, i.e. I'm checking that $$c = g^m \cdot r^n \mod n^2$$ holds. This works fine for small key sizes, but for cryptographically secure keys where $$n$$ and $$r$$ are 2048 bits long, especially the modular exponentiation to compute $$r^n$$ (using [3]) takes too long (> 2 hours) and requires too much RAM (~ 260 GB) to prove, way too much to be practical.

Is there a way to efficiently prove the correctness of the ciphertext $$c$$ outside the zk-SNARK circuit and -- more importantly -- "connect" that proof with the zk-SNARK such that I'm able to use both the plaintext $$m$$ and the ciphertext $$c$$ inside the zk-SNARK circuit without users being able to break the secrecy or soundness of the scheme?

Considering that the higher residuosity problem [4] is considered to be hard, I don't think that there's an easier way to prove that $$r^n$$ is actually an n-th power without performing that modular exponentiation, which I can't practically do in the circuit, so it seems that my only option to make this work is to move the Paillier encryption outside the circuit.

• If you are willing to reveal the public key, there are known methods for using elgamal encryption for proving correct encryption (e.g. section 3.3 of (ubilab.org/publications/print_versions/pdf/sta96.pdf). Not sure if this is transferabe to pallier Apr 22 at 7:28