2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – joakimb
    Apr 22 at 7:28

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.