Skip to main content
Cryptography

Return to Answer

Fixed formatting and removed the “kickstart the discussion” part since we’re a Q&A site, not a forum.
Source Link
e-sushi
e-sushi
  • 18.1k
  • 12
  • 85
  • 235

Since there are no answers here yet, I'll write down my own opinion so as to kickstart a discussion.

  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$X$ and first prover message A$A$, the prover self-generates the challenge e = H(X,A)$e = H(X,A)$and uses it to generate its final response z$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$H$ (a criterion I think a PRF satisfies), digesting A$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.

Since there are no answers here yet, I'll write down my own opinion so as to kickstart a discussion.

  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.

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.

Source Link
Arya Pourtabatabaie
Arya Pourtabatabaie
  • 263
  • 2
  • 6

Since there are no answers here yet, I'll write down my own opinion so as to kickstart a discussion.

  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.