## CryptoDB

### Paper: Tight State-Restoration Soundness in the Algebraic Group Model

Authors: Ashrujit Ghoshal , University of Washington Stefano Tessaro , University of Washington DOI: 10.1007/978-3-030-84252-9_3 (login may be required) Search ePrint Search Google Slides CRYPTO 2021 Most efficient zero-knowledge arguments lack a concrete security analysis, making parameter choices and efficiency comparisons challenging. This is even more true for non-interactive versions of these systems obtained via the Fiat-Shamir transform, for which the security guarantees generically derived from the interactive protocol are often too weak, even when assuming a random oracle. This paper initiates the study of {\em 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 {\em first} non-trivial concrete security analysis for a non-constant round argument combined with the Fiat-Shamir transform.
##### BibTeX
@inproceedings{crypto-2021-31231,
title={Tight State-Restoration Soundness in the Algebraic Group Model},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-84252-9_3},
author={Ashrujit Ghoshal and Stefano Tessaro},
year=2021
}