New answers tagged zero-knowledge-proofs
2
Background: The Fiat–Shamir heuristic converts a certain class of interactive zero-knowledge proof systems—$\Sigma$-protocols, where prover proposes random commitment, verifier responds with random challenge, and prover answers with proof—into signature schemes using a random oracle to determine the challenge from the commitment.
Using a random oracle means ...
0
This is already explained in the linked Buterin blogpost. Essentially what you are trying to achieve here, ie. implementing a MOD "gate" in a zkSNARK is simply cannot be done efficiently. This is because that MOD is not supported in finite cyclic group arithmetic. If there is an efficient MOD gate, then by applying the Chinese Remainder Theorem, one could ...
4
You are correct about the attack, given the way you have defined the Fiat-Shamir-transformed protocol.
Since Fiat-Shamir is subtle for multi-round protocols, the standard way to resolve this is to use parallel instead of sequential composition. Start with a protocol that has soundness error 1/2, and run it $k$ times in parallel (not in sequence) to amplify ...
1
The main idea behind the Fiat-Shamir heuristic is to eliminate the interaction in public coin protocols.
In the interactive model, the randomly selected challenges by the verifier force a malicious prover to provide a wrong proof. As you mention, it is negligible for a malicious prover to convince the verifier after $k$ round.
To make this scheme non-...
1
First (if it's not the case) you have to read carefully the original Groth-Sahai paper : https://eprint.iacr.org/2007/155.pdf
We can focus on a concrete example to understand why it's possible: in the "SXDH" setting for example (page 24);
Let suppose we have a commit $\vec{c_1}$ for a vector of elements of $G_1$ and
a commit $\vec{c_2}$ for a vector of ...
4
A class. Parameters according to which it is standard to compare them, are: prover time, verifier time, proof size, requirement of trusted setup, cryptographic assumptions. For "succinctness", the standard definition requires that verification time is sub-linear and proofs are "small".
STARK however, is a name of a specific zk-SNARKS protocol, see any Eli ...
0
Yes. Say the message is $m$ and the commitment is $C$ such that $C = g^mh^r$. Since you can use verifiable encryption to prove that a given ciphertext encrypts $m$ in relation $g^m = y$ where $g$ and $y$ are also public knowledge, using the Schnorr protocol you can prove that the $m$ in relation $g^m = y$ is same as the $m$ in $C$
Top 50 recent answers are included
