Paper 2024/1645

Fiat-Shamir Goes Rational (Or: On the Perils of Sublinear Verification)

Abstract

We investigate the existence of non-interactive proof systems where the verifier runs in time sublinear in the input size. This seemingly paradoxical property has been shown possible in interactive settings for specific soundness notions, in particular proofs of proximity (Rothblum, Vadhan, and Wigderson, STOC 2013) and rational proofs (Azar and Micali, STOC 2012). We initiate the study of the Fiat-Shamir paradigm in the sublinear verification setting. We show Fiat-Shamir to generally fail in this context, and, importantly, we study how it fails. Our results include: - General impossibility results from properties of Boolean functions. We introduce an abstract framework that generically applies to the sublinear setting (regardless of the soundness notion). Our framework includes an appropriately adapted variant of Fiat-Shamir, as well as general sufficient conditions under which employing Fiat-Shamir yields insecure protocols. Motivated by their practical interest and simplicity, we then apply our framework to rational proofs. We develop attack strategies that leverage the sublinearity of the verifier and exploit complexity metrics of Boolean functions, revealing an intriguing connection. - Robustness and applicability of our attacks. We ask whether a strengthened variant of Fiat-Shamir—which includes even parts of the public inputs that the verifier has not queried—can yield secure protocols. We show negative results in this setting as well. In particular, we prove that representative protocols for broad and "easy" function classes—shallow Boolean circuits (Campanelli and Gennaro, 2015) and threshold circuits (Azar and Micali, 2013)—become insecure when compiled with either of our Fiat-Shamir transforms. Our general results provide further insights into non-interactive sublinear verification, complementing the concurrent work by Chen, Jin and Wichs (STOC 2025), which shows lower bounds for non-interactive proofs of proximity for a specific problem within P.