CryptoDB
Xihu Zhang
Publications
Year
Venue
Title
2020
TCC
Super-Linear Time-Memory Trade-Offs for Symmetric Encryption
📺
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 at $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.
Coauthors
- Wei Dai (1)
- Stefano Tessaro (1)