Paper 2019/258
Tight Time-Memory Trade-offs for Symmetric Encryption
Joseph Jaeger and Stefano Tessaro
Abstract
Concrete security proofs give upper bounds on the attacker's advantage as a function of its time/query complexity. Cryptanalysis suggests however that other resource limitations - most notably, the attacker's memory - could make the achievable advantage smaller, and thus these proven bounds too pessimistic. Yet, handling memory limitations has eluded existing security proofs.
This paper initiates the study of time-memory trade-offs for basic symmetric cryptography. We show that schemes like counter-mode encryption, which are affected by the Birthday Bound, become more secure (in terms of time complexity) as the attacker's memory is reduced.
One key step of this work is a generalization of the Switching Lemma: For adversaries with
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2019
- Keywords
- provable securitytime-memory trade-offs
- Contact author(s)
- jsjaeger @ eng ucsd edu
- History
- 2019-03-06: received
- Short URL
- https://ia.cr/2019/258
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/258, author = {Joseph Jaeger and Stefano Tessaro}, title = {Tight Time-Memory Trade-offs for Symmetric Encryption}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/258}, year = {2019}, url = {https://eprint.iacr.org/2019/258} }