How to Prove False Statements: Practical Attacks on Fiat-Shamir
Ron Rothblum
Video
Abstract:
The Fiat-Shamir (FS) transform is a prolific and powerful technique for compiling public-coin interactive protocols into non-interactive ones. Roughly speaking, the idea is to replace the random coins of the verifier with the evaluations of a complex hash function. The FS transform is known to be sound in the random oracle model (i.e., when the hash function is modeled as a totally random function). However, when instantiating the random oracle using a concrete hash function, there are examples of protocols in which the transformation is not sound. So far all of these examples have been contrived protocols that were specifically designed to fail.
In this work we show such an attack for a standard and popular interactive succinct argument, based on the GKR protocol, for verifying the correctness of a non-deterministic bounded-depth computation. For every choice of FS hash function, we show that a corresponding instantiation of this protocol, which has been widely studied in the literature and used also in practice, is not (adaptively) sound when compiled with the FS transform. Specifically, we construct an explicit circuit for which we can generate an accepting proof for a false statement.
Joint work with Dmitry Khovratovich and Lev Soukhanov.
Bio:
Ron rothblum is an Associate Professor at the Faculty of Computer Science at the Technion. Prior to that, he was a postdoc at MIT (2015-2018) and Northeastern University (2017-2018). He completed his PhD at the Weizmann Institute, where he was advised by Prof. Oded Goldreich. He is interested in theoretical computer science at large and especially in cryptography and complexity theory.