Fiat-Shamir Heuristic

Method to convert interactive protocols into non-interactive system such that public verifiability is feasible and both prover and verifier doesn’t need to be online at all times.

Let prover prove to verifier that it possess $s_1\cdots s_k$ secrets co-prime to $N$, without revealing any of the number to verifier. Takes advantage of difficulty of calculating modular square roots as verifier can’t derive $s1$ from $v1$

Take any public coin interactive argument: $\Pi =(\text{Setup},\mathcal{P},\mathcal{V})$ with transcript of the form $a_1,c_1,\dots ,a_r,c_r,a_{r+1}$, then strong FS transformation is used to convert Interactive Argument to a Non-interactive argument, where $\mathcal{P}(\text{pp,x,w})$ uses a random oracle instantiated at the beginning of the protocol to generate uniform challenges, $c_i\leftarrow H(\text{pp},x,a_1,\dots ,a_i)$.

Soundness of FS can be proven using forking-lemma which is used to prove that if an interactive protocol is sound, then it’s non-interactive version compiled using FS is sound.

Soundness of an interactive protocol depends on an efficient extractor $E$ that with the help of an adversary ${\mathcal{A}}^{\ast }$, who convinces a verifier $V$, is able to extract witness $w\in \{0,1{\}}^{\ast }$. Here’s the definition of Knowledge-soundness:

$$\forall x^{\prime }\in \mathcal{L},\mathrm{Pr}[{\text{out}}_V(⟨{\mathcal{A}}^{\ast }(x^{\prime })\leftrightarrow V(x^{\prime })⟩)=1⟹{\mathcal{R}}_{\mathcal{L}}(x^{\prime },E^{{\mathcal{A}}^{\ast }}(\cdot ))=1]\ge \text{noti}(n)$$

Let’s model, an interactive protocol with $E$ and ${\mathcal{A}}^{\ast }$ in experiment:¹

• $E$ simulates $V$ for ${\mathcal{A}}^{\ast }$, runs ${\mathcal{A}}^{\ast }$ and obtains transcript $T_1$.
• $E$ rewinds ${\mathcal{A}}^{\ast }$ to a point where it commits to something.
• Again runs ${\mathcal{A}}^{\ast }$ with new randomness, now obtaining transcript $T_2$.

Now, language $\mathcal{L}$ is structured in such a way that $E$ is able to extract witness from two valid transcripts.

ZK for FS is a little complicated, if underlying interactive protocol exhibits HVZK, then FS compiled non-interactive protocol is also HVZK, and it was proven by GSV98 that any protocol that satisfies HVZK also satisfies statistical zero-knowledge.

Weak Fiat Shamir attacks

There are many practical examples already present where fiat-shamir when applied to a interactive protocol, completely broke the soundness in non-interactive protocol.

• Schnorr’s protocol²
• Chaum-Pedersen ZK protocol²
• Initial versions of Bulletproofs and Plonk³

Weak Fiat Shamir attacks happen when only arguments are used to derive the challenges from random oracle, i.e. $c_i\leftarrow H(a_1,\dots ,a_i)$.

Spartan

attack on spartan is also similar, they forge the final check by making the public input value equal to the verifier check which cancels everything out.

Spartan runs 2 sumchecks to prove correct evaluation of circuit or prove knowledge of witness.

first sumcheck is used to prove r1cs relation, after that, prover calculates evaluations of A,B,C on random value sent by verifier during the sumcheck. At the end of sumcheck, prover receives value which is evaluation of all three on random value.

now, to prove that evaluations are correct, another sumcheck instance is used, where prover sends evaluations to individual polynomials. Receives 3 random values from verifier and batch all 3 instances into one big sumcheck. at the end left with three values which are evaluations of A,B,C=va,vb,vc at rx,ry (two random values for each sumcheck).

Spartan Weak FS from https://eprint.iacr.org/2023/691

Prove final evaluation.

But the twist is last evaluation checks the (ra.va+rb.vb+rc.vc).vz(evalaution of witness and public inputs at r_y)=ey (evaluation sent by prover in last sumcheck). and prover can calculate PI such that it cancel everything out.

VDF

We note one significant departure of our syntax from the syntax of previous works: we allow the time delay T to be an input to the Eval algorithm, instead of T being determined ahead of time as a parameter to Setup.

isn’t this bad for the attacker. I mean it’s eaasier for attacker to know for how much time will the function run?

lol this is actually the cause of the attack in VDF’s soundness. since $T$ wasn’t hashed for calculating $l$, any other $l$ can be sampled before the commitment to $g^{2^T}$, and it can be calculated by finding a small $t$ such that $2^t\equiv 2^T\mathrm{mod}l$,

• y = g^2
• $\pi =g^{\lfloor 2^t/l\rfloor }$
• send $T,g,y,\pi$ to V
• v verifies by checking $y=g^{T\mathrm{mod}l}\cdot \pi$

although, there aren’t any practical attacks possible on implementations because T has to be very large $\simeq 256$ in order to find a smaller power of 2 equal to a uniform number.

How to mitigate and use strong FS

How easily detectable attacks described above are?

• attacks on different implementations and systems depend on the context of public inputs. In case of BP, public inputs were hiding commitments, that’s why attacks was possible. In VDF, since attacks isn’t practically possible, attack is easily detectable.

How to mitigate?

• include all public inputs and prover’s outputs in transcript
• do not create a new transcript for each subprotocol as might be case in spartan’s sumcheck
• include all public parameters like group order, generator, any prime (in RSA), R1CS matrices, etc.

References

• Fiat-Shamir transformation
• The Fiat-Shamir Transform - Ron Rothblum
• The magic of Fiat-Shamir
• Lecture 1: Honest Verifier ZK and Fiat-Shamir

Footnotes

1. Experiment borrowed from here ↩

2. https://eprint.iacr.org/2016/771 ↩ ↩²

3. https://eprint.iacr.org/2023/691 ↩