In my studies, I have seen two common ways that an Honest Verifier Zero Knowledge Proof can be converted to a Zero Knowledge Proof. Either make the proof non-interactive with Fiat-Shamir's Heuristic (thus removing the Verifier) or make the Verifier commit the challenge beforehand.

Wouldn't it also be secure for the Prover to commit his initial communications in a Pedersen Commitment? The protocol would look like this:

  1. The Prover calculates the initial communications
  2. The Prover commits the initial communications and sends the commitment(s) to the Verifier.
  3. The Verifier sends a challenge.
  4. The Prover calculates the response.
  5. The Prover sends the response and the information to open the commitment(s) to the Verifier.
  6. If the transcript is valid and the initial communication matches the commitment(s), the Verifier accepts.

If my reasoning is valid, this would make the Zero Knowledge Proofs parallelizable without worrying about any meaningful interdependencies. The commitments that would be used are perfectly hiding, and thus reveal nothing about the contents, meaning the Verifier has no real information about this proof until his inputs are completed. This means the Verifier can't use information from ZKP 1 on ZKP 2's challenge and use that response for part of ZKP 1's challenge, which, as far as I understand, is a problem in parallel composition of Zero Knowledge Proofs.

The downside is the initial communications can be large and it could cost a lot of exponentiations and communications to commit them all in Pedersen Commitment and send them, but you may be able to commit using a hashing function instead, but these aren't perfectly hiding.

  • $\begingroup$ You need a trapdoor commitment to make the simulation work, but then this strategy works out. It is discussed in "Efficient Concurrent Zero-Knowledge in the Auxiliary String Model" by Ivan Damgard (Eurocrypt 2000). $\endgroup$
    – DrLecter
    Nov 1, 2017 at 18:50
  • $\begingroup$ So this works as long as the Simulator (replacing the Prover) knows the DLOG between the generators in the commitment and can thus "cheat" on the commitment and have any initial comm he wants. Then, the Simulator (replacing the Verifier) can just send two challenges like in HVZKP proof. $\endgroup$
    – Zarquan
    Nov 1, 2017 at 20:33
  • $\begingroup$ Exactly, then you have a trapdoor commitment. $\endgroup$
    – DrLecter
    Nov 1, 2017 at 20:35
  • $\begingroup$ One thing I am not clear on. Does the simulator automatically know the trapdoor, or does it have to be extracted from the adversary? $\endgroup$
    – Zarquan
    Nov 1, 2017 at 21:42
  • $\begingroup$ You work in a common reference string (auxiliary string) model. There the simulator knows the trapdoor. But in the real protocol it is set up by a trusted party and so the trapdoor is not known. $\endgroup$
    – DrLecter
    Nov 1, 2017 at 21:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.