This paper initiates the study of state-restoration soundness in the algebraic group model (AGM) of Fuchsbauer, Kiltz, and Loss (CRYPTO '18). This is a stronger notion of soundness for an interactive proof or argument which allows the prover to rewind the verifier, and which is tightly connected with the concrete soundness of the non-interactive argument obtained via the Fiat-Shamir transform.
We propose a general methodology to prove tight bounds on state-restoration soundness, and apply it to variants of Bulletproofs (Bootle et al, S&P '18) and Sonic (Maller et al., CCS '19). To the best of our knowledge, our analysis of Bulletproofs gives the first non-trivial concrete security analysis for a non-constant round argument combined with the Fiat-Shamir transform.
Category / Keywords: foundations / Zero-knowledge proof systems, concrete security, Fiat-Shamir transform, Algebraic Group Model, state-restoration soundness. Original Publication (with major differences): IACR-CRYPTO-2021 Date: received 26 Oct 2020, last revised 25 Jun 2021 Contact author: ashrujit at cs washington edu Available format(s): PDF | BibTeX Citation Note: Major update with updated security definitions Version: 20210625:222303 (All versions of this report) Short URL: ia.cr/2020/1351