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.
[1] https://github.com/akosba/jsnark
[2] https://en.wikipedia.org/wiki/Paillier_cryptosystem
[3] https://en.wikipedia.org/wiki/Exponentiation_by_squaring
[4] https://en.wikipedia.org/wiki/Higher_residuosity_problem
