Non-adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-Like Inequality for Permutations

The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results which show that adaptivity provides a significant extra power in cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time.

Most notably, we consider the discrete logarithm (DLOG) problem in a generic group of N elements. The classical 'baby-step giant-step' algorithm for the problem has time complexity T = O( √ N ), uses O( √ N ) bits of space (up to logarithmic factors in N ) and achieves constant success probability.

We examine a generalized setting where an algorithm obtains an advice string of S bits and is allowed to make T arbitrary non-adaptive queries that depend on the advice string (but not on the challenge group element for which the DLOG needs to be computed).

We show that in this setting, the T = O( √ N ) online time complexity of the baby-step giant-step algorithm cannot be improved, unless the advice string is more than Ω( √ N ) bits long. This lies in stark contrast with the classical adaptive Pollard's rho algorithm for DLOG, which can exploit preprocessing to obtain the tradeoff curve ST 2 = O(N ). We obtain similar sharp lower bounds for the problem of breaking the Even-Mansour cryptosystem in symmetric-key cryptography and for several other problems.

To obtain our results, we present a new model that allows analyzing non-adaptive preprocessing algorithms for a wide array of search and decision problems in a unified way.

Since previous proof techniques inherently cannot distinguish between adaptive and nonadaptive algorithms for the problems in our model, they cannot be used to obtain our results. Consequently, we rely on information-theoretic tools for handling distributions and functions over the space S N of permutations of N elements. Specifically, we use a variant of Shearer's lemma for this setting, due to Barthe, Cordero-Erausquin, Ledoux, and Maurey (2011), and a variant of the concentration inequality of Gavinsky, Lovett, Saks and Srinivasan (2015) for read-k families of functions, that we derive from it. This seems to be the first time a variant of Shearer's lemma for permutations is used in an algorithmic context, and it is expected to be useful in other lower bound arguments.