CryptoDB
Xihu Zhang
Publications
Year
Venue
Title
2021
ASIACRYPT
Tight Security for Key-Alternating Ciphers with Correlated Sub-Keys
📺
Abstract
A substantial effort has been devoted to proving optimal bounds for
the security of key-alternating ciphers with independent sub-keys in
the random permutation model (e.g., Chen and Steinberger, EUROCRYPT '14;
Hoang and Tessaro, CRYPTO '16). While common in the study of
multi-round constructions, the assumption that sub-keys are truly
independent is not realistic, as these are generally highly
correlated and generated from shorter keys.
In this paper, we show the existence of non-trivial distributions of
limited independence for which a t-round key-alternating cipher
achieves optimal security. Our work is a natural continuation of the
work of Chen et al. (CRYPTO '14) which considered the case of t = 2
when all-subkeys are identical. Here, we show that key-alternating
ciphers remain secure for a large class of (t-1)-wise and
(t-2)-wise independent distribution of sub-keys.
Our proofs proceed by generalizations of the so-called
Sum-Capture Theorem, which we prove using Fourier-analytic
techniques.
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 (2)
- Xihu Zhang (2)