[Resource Topic] 2020/1351: Tight State-Restoration Soundness in the Algebraic Group Model

Welcome to the resource topic for 2020/1351

Title:
Tight State-Restoration Soundness in the Algebraic Group Model

Authors: Ashrujit Ghoshal, Stefano Tessaro

Abstract:

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 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.

ePrint: https://eprint.iacr.org/2020/1351

Talk: https://www.youtube.com/watch?v=JMEvYwjIRjs

Slides: https://iacr.org/submit/files/slides/2021/crypto/crypto2021/320/slides.pdf

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .