We sift through the news so you don’t have to
Editor’s note: In this regular news segment, we focus on the signal vs. the noise across various media sources — traditional media outlets, industry announcements, and debates online — to help you
AI systems are breaking an internet that was designed at human-scale — by making it cheaper than ever to coordinate, transact, and generate voice, video, and text that are increasingly indistinguishable from human activity. We’re already beset w
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 Ron Rothblum (Technion, Succinct) shows 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, he constructs an explicit circuit for which we can generate an accepting proof for a false statement.
Joint work with Dmitry Khovratovich and Lev Soukhanov
About a16z crypto research
a16z crypto research is a multidisciplinary lab that works closely with our portfolio companies and others toward solving the important problems in the space, and toward advancing the science and technology of the next generation of the internet.
More about us: a16z.com/2022/04/21/announcing-a16z-crypto-research
More from the a16z crypto team Subscribe to our ‘web3 weekly newsletter’: a16zcrypto.substack.com
Listen to our ‘web3 with a16z’ podcast: a16zcrypto.com/web3-with-a16z-podcast/
