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

*Wei Dai and Stefano Tessaro and Xihu Zhang*

**Abstract: **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.

**Category / Keywords: **foundations / secret-key cryptography, information theory, pseudo-randomness, space-time trade-offs

**Date: **received 2 Jun 2020, last revised 3 Jun 2020

**Contact author: **weidai at eng ucsd edu,tessaro@cs washington edu,xihu@cs washington edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20200604:004402 (All versions of this report)

**Short URL: **ia.cr/2020/663

[ Cryptology ePrint archive ]