Cryptology ePrint Archive: Report 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 $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.

Category / Keywords: secret-key cryptography / provable security, time-memory trade-offs

Original Publication (with major differences): IACR-EUROCRYPT-2019

Date: received 28 Feb 2019

Contact author: jsjaeger at eng ucsd edu

Available format(s): PDF | BibTeX Citation

Version: 20190306:025235 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]