Cryptology ePrint Archive: Report 2020/1213

Expected-Time Cryptography: Generic Techniques and Applications to Concrete Soundness

Joseph Jaeger and Stefano Tessaro

Abstract: This paper studies concrete security with respect to expected-time adversaries. Our first contribution is a set of generic tools to obtain tight bounds on the advantage of an adversary with expected-time guarantees. We apply these tools to derive bounds in the random-oracle and generic-group models, which we show to be tight.

As our second contribution, we use these results to derive concrete bounds on the soundness of public-coin proofs and arguments of knowledge. Under the lens of concrete security, we revisit a paradigm by Bootle at al. (EUROCRYPT '16) that proposes a general Forking Lemma for multi-round protocols which implements a rewinding strategy with expected-time guarantees. We give a tighter analysis, as well as a modular statement. We adopt this to obtain the first quantitative bounds on the soundness of Bulletproofs (BŁnz et al., S&P 2018), which we instantiate with our expected-time generic-group analysis to surface inherent dependence between the concrete security and the statement to be proved.

Category / Keywords: foundations / concrete security, proof systems

Original Publication (with major differences): IACR-TCC-2020

Date: received 2 Oct 2020

Contact author: jsjaeger at cs washington edu

Available format(s): PDF | BibTeX Citation

Version: 20201006:094120 (All versions of this report)

Short URL: ia.cr/2020/1213


[ Cryptology ePrint archive ]