Cryptology ePrint Archive: Report 2020/663

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:

[ Cryptology ePrint archive ]