I was introduced to NIZK from the notion of CRS: since we have a trusted CRS, then a prover can simulate a challenge by querying the CRS.

Similarly, the prover can simulate the challenge of a verifier by using the Fiat-Shamir heuristic.

  • Can someone explain if there is any relation between the two?
  • Are they two different methods or very similar?
  • Can we replace the oracle with a PRF and a CRS?

Sorry for the confusion, if someone can clarify the two models and also give me pointers would be really appreciated.


Since there are no answers here yet, I'll write down my own opinion.

  1. The Fiat-Shamir heuristic for augmenting Sigma-protocols (or possibly any 3-move honest-verifier ZKPoK?) works as follows: For the problem statement $X$ and first prover message $A$, the prover self-generates the challenge $e = H(X,A)$and uses it to generate its final response $z$. Note that these proofs can be replayed.

  2. In Damgard's paper “Efficient Concurrent Zero-Knowledge in the Auxiliary String Model” the Common Reference String model is used to generate a trapdoor commitment scheme, enabling the verifier to simulate a proof and thus guaranteeing zero-knowledge. In this setting, since the prover still actively participates in the protocol and Special Soundness is assumed, the prover cannot cheat.

To me it seems that your conjecture is true. Given a collision-resistant hash function $H$ (a criterion I think a PRF satisfies), digesting $A$ and the common reference string together should derive a ZKPoK out of a Sigma Protocol. But the thing is, that string should only be unique, and it is solely in the interest of the verifier that it be so. Therefore even a malicious verifier can be trusted to provide it properly, and the overhead of a CRS setup having to generate unique strings can be avoided.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.