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 $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.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- secret-key cryptographyinformation theorypseudo-randomnessspace-time trade-offs
- Contact author(s)
-
weidai @ eng ucsd edu
tessaro @ cs washington edu
xihu @ cs washington edu - History
- 2020-06-04: revised
- 2020-06-03: received
- See all versions
- Short URL
- https://ia.cr/2020/663
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/663, 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}, url = {https://eprint.iacr.org/2020/663} }