Paper 2020/663

Super-Linear Time-Memory Trade-Offs for Symmetric Encryption

Wei Dai, Stefano Tessaro, and Xihu Zhang


We build symmetric encryption schemes from a pseudorandom function/permutation with domain size $N$ which have very high security -- in terms of the amount of messages $q$ they can securely encrypt -- assuming the adversary has $S < N$ bits of memory. We aim to minimize the number of calls $k$ we make to the underlying primitive to achieve a certain $q$, or equivalently, to maximize the achievable $q$ for a given $k$. We target in particular $q \gg N$, in contrast to recent works (Jaeger and Tessaro, EUROCRYPT '19; Dinur, EUROCRYPT '20) which aim to beat the birthday barrier with one call when $S < \sqrt{N}$. Our first result gives new and explicit bounds for the Sample-then-Extract paradigm by Tessaro and Thiruvengadam (TCC '18). We show instantiations for which $q =\Omega((N/S)^{k})$. If $S < N^{1- \alpha}$, Thiruvengadam and Tessaro's weaker bounds only guarantee $q > N$ when $k = \Omega(\log N)$. In contrast, here, we show this is true already for $k = O(1/\alpha)$. We also consider a scheme by Bellare, Goldreich and Krawczyk (CRYPTO '99) which evaluates the primitive on $k$ independent random strings, and masks the message with the XOR of the outputs. Here, we show $q= \Omega((N/S)^{k/2})$, using new combinatorial bounds on the list-decodability of XOR codes which are of independent interest. We also study best-possible attacks against this construction.

Available format(s)
Publication info
Preprint. MINOR revision.
secret-key cryptographyinformation theorypseudo-randomnessspace-time trade-offs
Contact author(s)
weidai @ eng ucsd edu
tessaro @ cs washington edu
xihu @ cs washington edu
2020-06-04: revised
2020-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Wei Dai and Stefano Tessaro and Xihu Zhang},
      title = {Super-Linear Time-Memory Trade-Offs for Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/663},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.