Paper 2020/663

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

Wei Dai, 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 $$, or equivalently, to maximize the achievable $$ for a given $$. We target in particular $$, in contrast to recent works (Jaeger and Tessaro, EUROCRYPT '19; Dinur, EUROCRYPT '20) which aim to beat the birthday barrier with one call when $$. 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 $$. If $$, Thiruvengadam and Tessaro's weaker bounds only guarantee $$ when $$. In contrast, here, we show this is true already for $$. We also consider a scheme by Bellare, Goldreich and Krawczyk (CRYPTO '99) which evaluates the primitive on $$ independent random strings, and masks the message with the XOR of the outputs. Here, we show $$, 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.