Adaptivity in cryptanalytic time-space tradeoffs

What an attacker with precomputation loses when its online queries cannot react to each other

Motivation

Every serious estimate of a cryptographic parameter has to price an attacker who is willing to spend a fortune once. Such an attacker precomputes on the primitive, keeps \(S\) bits of notes, and then attacks many instances with \(T\) online queries each. Hellman’s 1980 algorithm was the first of these, and the model — preprocessing, or auxiliary-input — is now standard.

Almost every good algorithm in that model is adaptive: each query depends on the answer to the last. Hellman’s chains are adaptive, Pollard’s Rho is aggressively adaptive, and the discrete-log preprocessing algorithms of Mihalcik, Bernstein–Lange and Corrigan-Gibbs–Kogan are all adaptive. Nobody knew whether they had to be. Corrigan-Gibbs and Kogan raised the question in 2019 for function inversion and then explained why it is hard there: a strong enough non-adaptive lower bound would resolve a fifty-year-old circuit question of Valiant’s, and would imply data-structure lower bounds nobody can prove.

Dinur, Keller and Marmor found a setting where the question can be answered. In the generic group model, with preprocessing, non-adaptive algorithms for discrete logarithm are provably no better than baby-step giant-step — so unlimited precomputation buys nothing at all without adaptivity, where with it you get a cube-root speedup. The same technique gives sharp non-adaptive bounds for square-DDH and for key recovery against Even-Mansour. This hub holds the two things their paper leaves undone, both of which are about exactly how much adaptivity is worth.

Provenance and history

Shoup introduced the generic group model in 1997 and proved the \(T^{2}/N\) bound for discrete logarithm, matched by Shanks’ 1971 baby-step giant-step algorithm. Preprocessing versions came later: Mihalcik (2010), Bernstein and Lange (ASIACRYPT 2013) and Corrigan-Gibbs and Kogan (EUROCRYPT 2018) all achieve \(ST^{2} = \widetilde{O}(N)\) for DLOG, and the last of these proves it optimal. For the decisional problems, Corrigan-Gibbs and Kogan gave \(\tfrac{1}{2} + \widetilde{O}(\sqrt{ST^{2}/N})\), which is attained for square-DDH but not for DDH; the DDH case stayed open until Akshima, Besselman, Guo, Xie and Ye (STOC 2024) proved the sharp \(\tfrac{1}{2} + \widetilde{\Theta}(ST^{2}/N)\).

The adaptivity question is younger. Corrigan-Gibbs and Kogan posed it in TCC 2019 for function inversion, where the honest answer is that a barrier stands in the way; a line of work followed — Chawin, Haitner and Mazor (TCC 2020), Golovnev, Guo, Peters and Stephens-Davidowitz (CRYPTO 2023), Gajulapalli, Golovnev and King (ITC 2024) — without moving the main bound. Dinur, Keller and Marmor’s Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations (ePrint 2025/783, STOC 2026) changes the target: rather than function inversion, where challenge-independent queries make the problem trivial, it works in a permutation challenge model where a query is a fixed low-degree map of the secret, which is exactly what makes baby-step giant-step non-adaptive and the question non-vacuous.

Their tool is an information-theoretic inequality of Shearer type for random permutations. That is also the source of both open problems: the inequality needs the queried set to be fixed independently of the permutation, which is precisely what one round of adaptivity buys and two rounds destroy.

Parameter lattice

Two axes: which generic-group problem, and how much adaptivity the online algorithm has. Every cell is a bound on the success probability of an \((S,T)\)-algorithm with preprocessing.

1 round (non-adaptive) \(r\) rounds \(T\) rounds (fully adaptive)
DLOG \(\widetilde{\Theta}(T^{2}/N + ST/N)\) — the source’s Theorem 1.1 (not a leaf here) c/0060 — open, conjectured \(\widetilde{O}(T^{2}/N + rST/N)\) \(\widetilde{\Theta}(ST^{2}/N)\) — Corrigan-Gibbs–Kogan (not a leaf here)
square-DDH sharp, and the source’s Appendix B gives the matching attack (not a leaf here) unstated: the source’s \(r\)-round goal covers it but names no formula \(\tfrac{1}{2} + \widetilde{\Theta}(\sqrt{ST^{2}/N})\) — Corrigan-Gibbs–Kogan (not a leaf here)
DDH c/0061 — open: proved with a \(\sqrt{ST/N}\) term, conjectured to be \(ST/N\) unstated \(\tfrac{1}{2} + \widetilde{\Theta}(ST^{2}/N)\) — Akshima et al., STOC 2024 (not a leaf here)
Even-Mansour key recovery sharp, the source’s Theorem 1.3 (not a leaf here) unstated attack with \(S = T_{1} = T_{2} = \widetilde{O}(2^{n/3})\) known (not a leaf here)

The two open cells are the two statements in this hub, and the unstated cells are real gaps rather than oversights: the source’s \(r\)-round goal is posed “for the problems considered in this paper”, but it commits to a formula only for DLOG.

Why the two open cells are different problems

They look like the same request — a better bound in the same model, from the same paper — and they are not.

c/0060 is about the model. Its difficulty is that the source’s Shearer-like inequality controls a random permutation’s information only on sets of query points fixed in advance, and a second round of adaptivity replaces those with composed points like \(f(d + f(d))\). The source says extending the approach “would require new Shearer-type inequalities or alternative techniques”. So a proof needs a new inequality; the matching attack, remarkably, already exists for every \(r\) — build \(T/r\) chains of length \(r\) instead of one chain of length \(T\).

c/0061 is about one problem inside a fixed model. The source’s proof reaches DDH and square-DDH through the same \((N/2)\)-uniformity of the translation function, and one of the two resulting bounds is sharp. So the work is not to strengthen the technique in general but to find the feature of the DDH query structure — a polynomial in three unknowns with its quadratic term restricted to \(d_{1}d_{2}\), rather than a polynomial in one — that the uniformity parameter cannot see. The source suggests importing the tightening that settled the adaptive case.

The first is a new-idea problem, the second an adaptation with a visible route, and neither implies the other.

What a resolution would say about real attackers

The formula in c/0060, if it holds, prices sequentiality. An attacker whose hardware is parallel but shallow — many cores, few rounds of dependence — loses a factor linear in the number of rounds it gives up, and no more. That is a mild loss, and it would mean that Pollard-style adaptivity is a convenience rather than a necessity for anyone who can afford width. If the formula fails, the value of adaptivity is not smooth in how much of it you have, which would be the more interesting outcome and is entirely unexplored.

Statements in this hub