Paper 2019/258

Tight Time-Memory Trade-offs for Symmetric Encryption

Joseph Jaeger and Stefano Tessaro


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 $S$ bits of memory issuing $q$ distinct queries, we prove an $n$-to-$n$ bit random function indistinguishable from a permutation as long as $S \times q \ll 2^n$. This result assumes a combinatorial conjecture, which we discuss, and implies right away trade-offs for deterministic, stateful versions of CTR and OFB encryption. We also show an unconditional time-memory trade-off for the security of randomized CTR based on a secure PRF. Via the aforementioned conjecture, we extend the result to assuming a PRP instead, assuming only one-block messages are encrypted. Our results solely rely on standard PRF/PRP security of an underlying block cipher. We frame the core of our proofs within a general framework of indistinguishability for streaming algorithms which may be of independent interest.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2019
provable securitytime-memory trade-offs
Contact author(s)
jsjaeger @ eng ucsd edu
2019-03-06: received
Short URL
Creative Commons Attribution


      author = {Joseph Jaeger and Stefano Tessaro},
      title = {Tight Time-Memory Trade-offs for Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2019/258},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.