[KRS25] How to Prove False Statements: Practical Attacks on Fiat-Shamir

Authors: Dmitry Khovratovich, Ron Rothblum, Oleg Soukhanov | Venue: CRYPTO 2025 | Source

Abstract

The Fiat-Shamir (FS) transform is a prolific technique for compiling public-coin interactive protocols into non-interactive ones by replacing verifier randomness with hash function evaluations. The FS transform is provably sound in the random oracle model. However, when instantiating the random oracle with a concrete hash function, there exist protocols for which soundness fails. Until this work, all known counterexamples were contrived — specifically engineered to make Fiat-Shamir fail. We show that Fiat-Shamir fails for the GKR succinct interactive argument (a standard, widely-studied protocol): we exhibit explicit families of circuits for which an efficient prover can produce an accepting non-interactive GKR proof of a false statement. This is the first counterexample to Fiat-Shamir applied to a natural protocol, raising fundamental questions about the security of deployed non-interactive succinct arguments.

BibTeX

Copy

@Inproceedings{C:KhoRotSou25,
  author = {Dmitry Khovratovich and Ron D. Rothblum and Lev Soukhanov},
  title = {How to Prove False Statements: Practical Attacks on {Fiat}-{Shamir}},
  pages = {3--26},
  editor = {Yael Tauman Kalai and Seny F. Kamara},
  booktitle = {Advances in Cryptology -- {CRYPTO}~2025, Part~VI},
  volume = {16005},
  series = {Lecture Notes in Computer Science},
  address = {Santa Barbara, CA, USA},
  month = {aug~17--21},
  publisher = {Springer, Cham, Switzerland},
  year = {2025},
  doi = {10.1007/978-3-032-01887-8_1},
}