Paper 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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in TCC 2020
- Keywords
- concrete securityproof systems
- Contact author(s)
- jsjaeger @ cs washington edu
- History
- 2020-10-06: received
- Short URL
- https://ia.cr/2020/1213
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1213,
author = {Joseph Jaeger and Stefano Tessaro},
title = {Expected-Time Cryptography: Generic Techniques and Applications to Concrete Soundness},
howpublished = {Cryptology {ePrint} Archive, Paper 2020/1213},
year = {2020},
url = {https://eprint.iacr.org/2020/1213}
}
