No fixed-construction reduction from Fiat-Shamir + GKR to SNARK

Unconditional · against fixed-construction reductions · KRS25

Statement

For every hash function, Fiat–Shamir applied to the GKR-based succinct interactive argument for non-deterministic bounded-depth computation is not an adaptively sound SNARK: there is an explicit circuit, depending on the hash function, for which an efficient prover produces an accepting non-interactive proof of a false statement of its choice — KRS25. Versions of the attack also break non-adaptive soundness, with an attacking circuit independent of the underlying cryptographic objects, but either the circuit has very large depth or the attack makes additional assumptions on the underlying primitives — KRS25.

Notes

  • The attacked argument is a standard protocol, unlike earlier counterexamples to Fiat–Shamir, which are protocols built to fail (GK03) — KRS25.