eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2020/1351

Tight State-Restoration Soundness in the Algebraic Group Model

Ashrujit Ghoshal and 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.

Note: Major update with updated security definitions

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2021
Keywords
Zero-knowledge proof systemsconcrete securityFiat-Shamir transformAlgebraic Group Modelstate-restoration soundness.
Contact author(s)
ashrujit @ cs washington edu
History
2021-06-25: last of 5 revisions
2020-10-29: received
See all versions
Short URL
https://ia.cr/2020/1351
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1351,
      author = {Ashrujit Ghoshal and Stefano Tessaro},
      title = {Tight State-Restoration Soundness in the Algebraic Group Model},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1351},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1351}},
      url = {https://eprint.iacr.org/2020/1351}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.