Welcome to the resource topic for 2020/663
Title:
Super-Linear Time-Memory Trade-Offs for Symmetric Encryption
Authors: Wei Dai, Stefano Tessaro, 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.
ePrint: https://eprint.iacr.org/2020/663
Talk: https://www.youtube.com/watch?v=OU0eXp7nock
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .