pith. sign in

arxiv: 2505.00894 · v3 · pith:4F2IXEAOnew · submitted 2025-05-01 · 💻 cs.CR · cs.IT· math.IT

Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations

Itai Dinur , Nathan Keller , Avichai Marmor This is my paper

Pith reviewed 2026-05-22 16:37 UTC · model grok-4.3

classification 💻 cs.CR cs.ITmath.IT
keywords discrete logarithmtime-space tradeoffsnon-adaptive algorithmsShearer's lemmacryptanalysispreprocessinggeneric groupspermutations
0
0 comments X

The pith

Non-adaptive algorithms for discrete log cannot improve on baby-step giant-step time unless advice is Omega(sqrt(N)) bits long.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that adaptivity is crucial for using preprocessing to speed up cryptanalytic algorithms. In the discrete logarithm problem over a generic group of N elements, any non-adaptive algorithm that receives an S-bit advice string and then makes T queries must have either T or S at least on the order of sqrt(N) to reach constant success probability. This matches the classical baby-step giant-step bound and rules out faster non-adaptive methods with small advice. The result stands in contrast to adaptive algorithms such as Pollard's rho, which achieve the tradeoff ST squared equals O(N) when preprocessing is allowed. The proof introduces a unified model for non-adaptive preprocessing and applies a variant of Shearer's lemma for permutations to control query-answer distributions.

Core claim

In the non-adaptive setting with an advice string of S bits, the T equals O(sqrt(N)) online time complexity of the baby-step giant-step algorithm for DLOG cannot be improved unless the advice string is more than Omega(sqrt(N)) bits long. Similar sharp lower bounds are obtained for several other cryptanalytic problems. The results rely on a new model for analyzing non-adaptive preprocessing algorithms together with a Shearer-like inequality for permutations.

What carries the argument

A variant of Shearer's lemma for permutations that supplies an inequality bounding the success probability of non-adaptive query distributions arising from permutation-based search problems.

If this is right

  • Adaptive algorithms can exploit preprocessing to obtain improved tradeoffs such as ST squared equals O(N) for discrete log.
  • The new model unifies the analysis of a wide array of search and decision problems in cryptanalysis.
  • Previous lower-bound techniques cannot separate adaptive from non-adaptive algorithms and therefore cannot yield these results.
  • Sharp time-space lower bounds of the same flavor hold for additional cryptanalytic problems beyond discrete log.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The power of preprocessing in these problems appears to depend critically on the ability to choose later queries after seeing earlier answers.
  • Similar permutation-based inequalities might be useful for analyzing non-adaptive algorithms in other combinatorial search settings.
  • The separation between adaptive and non-adaptive models suggests studying intermediate models with limited adaptivity.
  • The results may guide the design of preprocessing techniques that deliberately incorporate adaptivity to beat the non-adaptive bounds.

Load-bearing premise

The non-adaptive query model with an S-bit advice string accurately captures the power of preprocessing for the considered cryptanalytic search problems.

What would settle it

An explicit non-adaptive algorithm for discrete log that succeeds with constant probability using both T and S smaller than sqrt(N) by more than a constant factor would falsify the main lower bound.

read the original abstract

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(\sqrt{N})$, uses $O(\sqrt{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(\sqrt{N})$ online time complexity of the baby-step giant-step algorithm cannot be improved, unless the advice string is more than $\Omega(\sqrt{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 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper introduces a new model for non-adaptive preprocessing algorithms in cryptanalytic search and decision problems. It proves sharp time-space lower bounds using a variant of Shearer's lemma for permutations (Barthe et al. 2011). For the discrete logarithm problem in a generic group of size N, it shows that any non-adaptive algorithm with S-bit advice requires T = Omega(sqrt(N)) online time for constant success probability unless S = Omega(sqrt(N)), in contrast to the adaptive ST^2 = O(N) tradeoff achievable by Pollard's rho. Similar bounds are claimed for other problems.

Significance. If the central lower bounds hold, the result demonstrates that adaptivity confers a strict asymptotic advantage in the preprocessing setting for these problems, which prior techniques could not separate. The first algorithmic use of a permutation Shearer inequality is a methodological contribution that may apply more broadly to non-adaptive query models.

major comments (1)
  1. [Proof of Theorem 4.1 and Section 3] Proof of Theorem 4.1 (and the invocation in Section 3): the direct application of the Barthe et al. (2011) permutation Shearer inequality to the joint distribution over the fixed advice string, non-adaptive queries, and group-element answers requires verification that the induced distribution satisfies the uniform marginal and convexity hypotheses of the lemma. The non-adaptive model fixes queries independently of the challenge, which may introduce dependence that violates the exact conditions needed to obtain the tight ST^2 = Omega(N) bound; if the marginals are not uniform or the functional terms do not match, the derived lower bound may loosen.
minor comments (2)
  1. [Abstract and Introduction] The abstract and introduction contrast the new non-adaptive bounds with adaptive algorithms but should explicitly state the precise success probability and group model assumptions used in the lower bound statements.
  2. [Section 2 (model definition)] Notation for the advice string length S and query count T should be introduced with explicit dependence on N before the main theorems.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of our manuscript and for the constructive comments. We address the major comment below and will incorporate clarifications in the revised version.

read point-by-point responses

  1. Referee: [Proof of Theorem 4.1 and Section 3] Proof of Theorem 4.1 (and the invocation in Section 3): the direct application of the Barthe et al. (2011) permutation Shearer inequality to the joint distribution over the fixed advice string, non-adaptive queries, and group-element answers requires verification that the induced distribution satisfies the uniform marginal and convexity hypotheses of the lemma. The non-adaptive model fixes queries independently of the challenge, which may introduce dependence that violates the exact conditions needed to obtain the tight ST^2 = Omega(N) bound; if the marginals are not uniform or the functional terms do not match, the derived lower bound may loosen.

    Authors: We appreciate the referee highlighting the need for explicit verification of the lemma's hypotheses. In our setting, the advice string and non-adaptive queries are fixed prior to the challenge, but the group element answers are determined by a uniformly random permutation of the group (modeling the generic group). This ensures that the marginal distribution on each coordinate (corresponding to the queried positions) is uniform over the group elements, satisfying the uniform marginal condition. The convexity hypotheses hold as the relevant entropy functions are convex with respect to the permutation measure, consistent with the application in Barthe et al. The independence of queries from the challenge does not violate these properties because the randomness is in the underlying permutation, which remains uniform and independent of the fixed query positions. Therefore, the application yields the tight bound as claimed. To address the concern, we will add a short subsection or paragraph in Section 3 explicitly verifying these conditions for the non-adaptive case. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external inequality

full rationale

The paper's central lower bounds for non-adaptive DLOG and related problems are obtained by applying a variant of Shearer's lemma for permutations, explicitly attributed to the independent 2011 work of Barthe, Cordero-Erausquin, Ledoux, and Maurey. This is a general combinatorial fact external to the present paper, not derived from or dependent on any self-citation, fitted parameters, or definitions internal to the current work. The abstract and proof outline state that previous techniques cannot distinguish adaptive from non-adaptive cases, so the new model plus the cited inequality is used to obtain the ST^2 = Omega(N) tradeoff; no equation or step reduces the claimed Omega(sqrt(N)) bound to a tautology or to the paper's own inputs by construction. The derivation is therefore self-contained against the external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on a variant of Shearer's lemma for permutations whose applicability to the query model is asserted but not detailed in the abstract; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption A Shearer-like inequality holds for the distribution of permutations arising from non-adaptive query-answer pairs in the generic group model.
    Invoked to bound the success probability of non-adaptive algorithms with limited advice.

pith-pipeline@v0.9.0 · 5904 in / 1233 out tokens · 47219 ms · 2026-05-22T16:37:54.745748+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · 2 internal anchors

  1. [1]

    Tight time- space tradeoffs for the decisional diffie-hellman problem

    [ABG+24] Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie, and Yuping Ye. Tight time- space tradeoffs for the decisional diffie-hellman problem. In STOC 2024 , pages 1739–1749. ACM,

    work page 2024

  2. [2]

    Time-Space Tradeoffs and Short Collisions in Merkle-Damg˚ ard Hash Functions

    [ACDW20] Akshima, David Cash, Andrew Drucker, and Hoeteck Wee. Time-Space Tradeoffs and Short Collisions in Merkle-Damg˚ ard Hash Functions. In CRYPTO 2020 , volume 12170 of Lecture Notes in Computer Science , pages 157–186. Springer,

    work page 2020

  3. [3]

    Correlation and Brascamp–Lieb inequalities for Markov semigroups

    [BCELM11] Franck Barthe, Dario Cordero-Erausquin, Michel Ledoux, and Bernard Maurey. Correlation and Brascamp–Lieb inequalities for Markov semigroups. Internat. Math. Res. Notices, 2011(10):2177–2216,

    work page 2011

  4. [4]

    Bernstein and Tanja Lange

    [BL13] Daniel J. Bernstein and Tanja Lange. Non-uniform cracks in the concrete: The power of free precomputation. In ASIACRYPT 2013, volume 8270 of Lecture Notes in Computer Science , pages 321–340. Springer,

    work page 2013

  5. [5]

    The Distinction Between Fixed and Random Generators in Group-Based Assumptions

    42 [BMZ19] James Bartusek, Fermi Ma, and Mark Zhandry. The Distinction Between Fixed and Random Generators in Group-Based Assumptions. In CRYPTO 2019, volume 11693 of Lecture Notes in Computer Science , pages 801–830. Springer,

    work page 2019

  6. [6]

    [BW00] Alex Biryukov and David A. Wagner. Advanced slide attacks. In EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 589–606. Springer,

    work page 2000

  7. [7]

    Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models

    [CDG18] Sandro Coretti, Yevgeniy Dodis, and Siyao Guo. Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models. In CRYPTO 2018, volume 10991 of Lecture Notes in Computer Science , pages 693–721. Springer,

    work page 2018

  8. [8]

    Steinberger

    [CDGS18] Sandro Coretti, Yevgeniy Dodis, Siyao Guo, and John P. Steinberger. Random Oracles and Non-uniformity. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, volume 10820 of Lecture Notes in Computer Science , pages 227–258. Springer,

    work page 2018

  9. [9]

    Tight quantum time- space tradeoffs for function inversion

    [CGLQ20] Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian. Tight quantum time- space tradeoffs for function inversion. In FOCS 2020, pages 673–684. IEEE,

    work page 2020

  10. [10]

    Lower bounds on the time/memory tradeoff of function inversion

    [CHM20] Dror Chawin, Iftach Haitner, and Noam Mazor. Lower bounds on the time/memory tradeoff of function inversion. InTCC 2020, volume 12552 ofLecture Notes in Computer Science , pages 305–334. Springer,

    work page 2020

  11. [11]

    The discrete-logarithm problem with preprocessing

    [CK18] Henry Corrigan-Gibbs and Dmitry Kogan. The discrete-logarithm problem with preprocessing. In EUROCRYPT 2018, volume 10821 ofLecture Notes in Computer Science, pages 415–447. Springer,

    work page 2018

  12. [12]

    The function-inversion problem: Bar- riers and opportunities

    [CK19] Henry Corrigan-Gibbs and Dmitry Kogan. The function-inversion problem: Bar- riers and opportunities. In TCC 2019, volume 11891 of Lecture Notes in Computer Science, pages 393–421. Springer,

    work page 2019

  13. [13]

    Stronger 3SUM-Indexing Lower Bounds

    [CL23] Eldon Chung and Kasper Green Larsen. Stronger 3SUM-Indexing Lower Bounds. In Nikhil Bansal and Viswanath Nagarajan, editors, SODA 2023, pages 444–455. SIAM,

    work page 2023

  14. [14]

    Tweaking Even-Mansour ciphers

    [CLS15] Benoit Cogliati, Rodolphe Lampe, and Yannick Seurin. Tweaking Even-Mansour ciphers. In CRYPTO 2015, volume 9215 of Lecture Notes in Computer Science , pages 189–208. Springer,

    work page 2015

  15. [15]

    Entropy factorization via curvature

    43 [CS24] Pietro Caputo and Justin Salez. Entropy factorization via curvature. CoRR, abs/2407.13457,

    work page arXiv

  16. [16]

    Limitations of the Even-Mansour construction

    [Dae91] Joan Daemen. Limitations of the Even-Mansour construction. In ASIACRYPT 1991, volume 739 of Lecture Notes in Computer Science, pages 495–498. Springer,

    work page 1991

  17. [17]

    Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited

    [DGK17] Yevgeniy Dodis, Siyao Guo, and Jonathan Katz. Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited. In EUROCRYPT 2017, volume 10211 of Lecture Notes in Computer Science , pages 473–495,

    work page 2017

  18. [18]

    Data structures lower bounds and popular conjectures

    [DKKS21] Pavel Dvor´ ak, Michal Kouck´ y, Karel Kr´ al, and Veronika Sl´ ıvov´ a. Data structures lower bounds and popular conjectures. In ESA 2021, volume 204 of LIPIcs, pages 39:1–39:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik,

    work page 2021

  19. [19]

    Steinberger, and Aishwarya Thiruven- gadam

    [DSST17] Yuanxi Dai, Yannick Seurin, John P. Steinberger, and Aishwarya Thiruven- gadam. Indifferentiability of iterated Even-Mansour ciphers with non-idealized key-schedules: Five rounds are necessary and sufficient. In CRYPTO 2017, vol- ume 10403 of Lecture Notes in Computer Science , pages 524–555. Springer,

    work page 2017

  20. [20]

    Time-space tradeoffs for sponge hashing: Attacks and limitations for short collisions

    [FGK22] Cody Freitag, Ashrujit Ghoshal, and Ilan Komargodski. Time-space tradeoffs for sponge hashing: Attacks and limitations for short collisions. In CRYPTO 2022, volume 13509 of Lecture Notes in Computer Science , pages 131–160. Springer,

    work page 2022

  21. [21]

    Multi-user col- lisions: Applications to discrete logarithm, even-mansour and PRINCE

    [FJM14] Pierre-Alain Fouque, Antoine Joux, and Chrysanthi Mavromati. Multi-user col- lisions: Applications to discrete logarithm, even-mansour and PRINCE. In ASI- ACRYPT 2014, volume 8873 of Lecture Notes in Computer Science , pages 420–

    work page 2014

  22. [22]

    Three tutorial lectures on entropy and counting

    [Gal14] David Galvin. Three tutorial lectures on entropy and counting. CoRR, abs/1406.7872,

    work page internal anchor Pith review Pith/arXiv arXiv

  23. [23]

    Data structures meet cryptography: 3sum with preprocessing

    [GGH+20] Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikun- tanathan. Data structures meet cryptography: 3sum with preprocessing. In STOC 2020, pages 294–307. ACM,

    work page 2020

  24. [24]

    On the power of adaptivity for function inversion

    [GGK24] Karthik Gajulapalli, Alexander Golovnev, and Samuel King. On the power of adaptivity for function inversion. In ITC 2024, volume 304 of LIPIcs, pages 5:1– 5:10. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik,

    work page 2024

  25. [25]

    Revisiting time-space tradeoffs for function inversion

    44 [GGPS23] Alexander Golovnev, Siyao Guo, Spencer Peters, and Noah Stephens-Davidowitz. Revisiting time-space tradeoffs for function inversion. In CRYPTO 2023, volume 14082 of Lecture Notes in Computer Science , pages 453–481. Springer,

    work page 2023

  26. [26]

    Unifying Presampling via Concentration Bounds

    [GLLZ21] Siyao Guo, Qian Li, Qipeng Liu, and Jiapeng Zhang. Unifying Presampling via Concentration Bounds. In TCC 2021, volume 13042 of Lecture Notes in Computer Science, pages 177–208. Springer,

    work page 2021

  27. [27]

    Lower Bounds on the Efficiency of Generic Cryptographic Constructions

    [GT00] Rosario Gennaro and Luca Trevisan. Lower Bounds on the Efficiency of Generic Cryptographic Constructions. In FOCS 2000 , pages 305–313. IEEE Computer Society,

    work page 2000

  28. [28]

    Hoza, Avishay Tal, and Roei Tell

    [HHTT21] Pooya Hatami, William M. Hoza, Avishay Tal, and Roei Tell. Fooling constant- depth threshold circuits (extended abstract). In FOCS 2021, pages 104–115. IEEE,

    work page 2021

  29. [29]

    Planted clique conjectures are equivalent

    [HS24] Shuichi Hirahara and Nobutaka Shimizu. Planted clique conjectures are equivalent. In STOC 2024, pages 358–366. ACM,

    work page 2024

  30. [30]

    Constructive Proofs of Concentra- tion Bounds

    [IK10] Russell Impagliazzo and Valentine Kabanets. Constructive Proofs of Concentra- tion Bounds. In APPROX-RANDOM 2010 , volume 6302 of Lecture Notes in Computer Science, pages 617–631. Springer,

    work page 2010

  31. [31]

    Lower bounds for discrete logarithms and related problems

    [Sho97] Victor Shoup. Lower bounds for discrete logarithms and related problems. In EUROCRYPT 1997, volume 1233 of Lecture Notes in Computer Science , pages 256–266. Springer,

    work page 1997

  32. [32]

    Random Oracles and Auxiliary Input

    [Unr07] Dominique Unruh. Random Oracles and Auxiliary Input. In CRYPTO 2007 , volume 4622 of Lecture Notes in Computer Science, pages 205–223. Springer,

    work page 2007

  33. [33]

    [Val77] Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In MFCS 1977, volume 53 of Lecture Notes in Computer Science , pages 162–176. Springer,

    work page 1977

  34. [34]

    A note on concentration of submodular functions

    [Von10] Jan Vondr´ ak. A note on concentration of submodular functions. CoRR, abs/1005.2791,

    work page internal anchor Pith review Pith/arXiv arXiv

  35. [35]

    On obfuscating point functions

    [Wee05] Hoeteck Wee. On obfuscating point functions. In Harold N. Gabow and Ronald Fagin, editors, STOC 2005, pages 523–532. ACM,

    work page 2005