2025/05/01 by Dinur, Itai, Keller, Nathan, Marmor, Avichai
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2505.00894
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). 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 ST2=O(N). We obtain similar sharp lower bounds for several other cryptanalytic 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 non-adaptive algorithms for the problems in our model, they cannot be used to obtain our results. Consequently, our proof uses a variant of Shearer's lemma for this setting, due to Barthe, Cordero-Erausquin, Ledoux, and Maurey (2011). This seems to be the first time a variant of Shearer's lemma for permutations is used in an algorithmic context.