🔢 mathematics

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

This paper establishes sharp time-space lower bounds demonstrating that non-adaptive cryptanalytic algorithms, even with unlimited preprocessing, cannot match the efficiency of adaptive methods like Pollard's rho for problems such as discrete logarithms, a result proven using a novel application of a Shearer-like inequality for permutations.

Original authors: Itai Dinur, Nathan Keller, Avichai Marmor

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Itai Dinur, Nathan Keller, Avichai Marmor

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to crack a safe. You have a combination lock with a huge number of possible combinations (let's say $N$ ). To crack it, you need to figure out the secret code.

In the world of cryptography, there are two main ways to attack this problem:

The "Smart" Way (Adaptive): You try a combination, see if the light turns red or green, and then use that information to decide your next move. It's like a detective following a trail of clues, adjusting their path based on what they find.
The "Rigid" Way (Non-Adaptive): You write down a massive list of combinations to try before you even touch the safe. You cannot change your list based on what happens. You just run through the list, no matter what.

The Big Discovery

For decades, cryptographers knew that the "Smart" way was powerful. In fact, there's a famous method called Pollard's Rho that is very efficient at cracking these codes, but it requires you to be "Smart" (adaptive). It needs to react to clues as it goes.

However, nobody could prove why the "Rigid" way was so much weaker. Maybe there was just a clever trick we hadn't found yet? Maybe a "Rigid" list could be just as good if we just made it long enough?

This paper says: No.

The authors prove that for certain types of cryptographic locks (like Discrete Logarithms and the Even-Mansour cipher), the "Rigid" way is fundamentally limited. Even if you give the "Rigid" attacker a massive cheat sheet (called an advice string) prepared in advance, they still cannot crack the code faster than a specific speed limit.

The Analogy: The Library of Permutations

To understand how they proved this, imagine the secret code is hidden inside a giant library containing every possible way to rearrange a deck of cards (a permutation).

The Goal: Find the specific arrangement that matches the secret.
The Cheat Sheet (Preprocessing): The attacker is allowed to read the library and write a summary (the advice string) before they start the actual hunt.
The Hunt (Online Phase): The attacker uses the summary to pick specific books to read.

The authors created a new mathematical tool to analyze this. Think of it like a "Shearer-like Inequality."

In simple terms, imagine you have a giant puzzle. If you only look at small, scattered pieces of the puzzle (your queries), you can't see the whole picture. The paper uses a mathematical rule (based on a concept called Shearer's Lemma) to prove that if your pieces are scattered and you can't look at them one by one to decide the next piece (non-adaptive), you simply cannot reconstruct the whole picture fast enough, no matter how much you studied the library beforehand.

The "Translation" Trick

One of the paper's cleverest moves was defining a new game called the "Permutation Challenge."

Imagine the attacker doesn't ask the safe directly. Instead, they ask a translator.

The attacker says: "Check box number 5."
The translator (using the secret code) says: "Okay, I'll actually check box number 42."
The attacker gets the result from box 42.

The paper proves that if the translator is doing a good, random job (which they do in these cryptographic systems), the attacker's "Rigid" list of requests gets scrambled in a way that makes it impossible to gain a huge advantage, even with a cheat sheet.

The Results in Plain English

The paper establishes three main "Speed Limits" for these rigid attackers:

Discrete Logarithms (The Classic Lock):
- The "Smart" attacker (using Pollard's Rho with a cheat sheet) can crack the code in time $T$ with space $S$ if $S \times T^2 \approx N$ .
- The "Rigid" attacker (even with a cheat sheet) is stuck. They cannot beat the old-school "Baby-Step Giant-Step" method. To crack it in time $T$ , they need a cheat sheet of size $S \approx \sqrt{N}$ . If their cheat sheet is smaller than that, they can't go faster than $\sqrt{N}$ time.
- Takeaway: Adaptivity gives a massive, proven boost here.
Even-Mansour Cipher (A Symmetric Lock):
- Similar to the above. The "Smart" attackers can trade space for time very efficiently. The "Rigid" attackers hit a hard wall. They cannot speed up their attack just by having a bigger cheat sheet, unless that cheat sheet is enormous (larger than $\sqrt{N}$ ).
Decisional Diffie-Hellman (The "Is this the right key?" Test):
- The paper proves that for deciding if a key is correct, "Rigid" attackers are also severely limited compared to "Smart" ones.

Why This Matters

Before this paper, we knew "Smart" attackers were strong, but we couldn't prove that "Rigid" attackers were weak. We just suspected it.

This paper provides the mathematical proof that adaptivity is a superpower in cryptography. It shows that the ability to react to clues in real-time isn't just a nice-to-have; it's a fundamental requirement to break these specific codes efficiently. If you are forced to plan all your moves in advance, you are stuck with a much slower, less efficient strategy, no matter how much preparation you do.

The "Secret Sauce" (The Math)

The authors didn't just guess this; they used advanced information theory.

They treated the secret code as a random shuffle of numbers.
They used a concept called KL-divergence (a way to measure how different two probability distributions are) to measure how much the "cheat sheet" actually helped the attacker.
They applied a specialized version of Shearer's Lemma (a rule about how information is shared across subsets) specifically for permutations (shuffles), which had never been done in this context before.

In short, they built a new mathematical lens that finally allowed them to see the difference between a detective who follows clues and one who just reads a map, proving that the detective is infinitely more powerful in this specific game.

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

1. Problem Statement and Motivation

This paper investigates the power of adaptivity in cryptanalytic time-space tradeoffs within the preprocessing (non-uniform) model. In this model, an adversary consists of a preprocessing phase that generates an advice string of $S$ bits based on the problem instance, followed by an online phase that solves specific challenges using $T$ oracle queries and the advice string.

While many state-of-the-art cryptanalytic algorithms (e.g., Pollard's Rho for Discrete Logarithm, adaptive attacks on Even-Mansour) rely heavily on adaptivity—where queries depend on previous oracle responses—it has been unclear whether non-adaptive algorithms (where queries are fixed in advance, potentially depending only on the advice) could achieve similar efficiency. Previous lower bound techniques for these problems were generally unable to distinguish between adaptive and non-adaptive algorithms, often yielding bounds that were too weak to prove that adaptivity provides a significant advantage.

The authors address the question raised by Corrigan-Gibbs and Kogan [CK19]: What is the power of adaptivity in non-uniform cryptanalytic algorithms? Specifically, they aim to prove sharp lower bounds showing that non-adaptive algorithms cannot match the efficiency of adaptive ones in the preprocessing setting for fundamental cryptographic problems.

2. Methodology and Technical Framework

2.1 The Permutation Challenge (PC) Model

To unify the analysis of diverse problems (Discrete Logarithm, DDH, sqDDH, and Even-Mansour key recovery), the authors introduce the Permutation Challenge (PC) model.

Structure: The model involves an "inner permutation" $\sigma: [N] \to [N]$ and a secret $d$ .
Queries: The adversary makes two types of queries:
1. Inner queries: Direct access to $\sigma$ (or $\sigma^{-1}$ ).
2. Outer queries: Access to an "outer function" defined by a translation function $tr(d, m)$ and a post-processing function $post(d, \cdot)$ . The query $m$ is translated to an input for $\sigma$ via $tr$, and the output is post-processed.
Non-Adaptivity Definition: An algorithm is non-adaptive if its pre-translated queries (the $m$ values and inner query indices) are fixed in advance based on the advice string $z$ , but not on the specific challenge $d$ or the outputs of $\sigma$ . Crucially, the actual oracle queries to $\sigma$ may depend on $d$ due to the translation function, allowing the model to capture classical non-adaptive algorithms like Baby-Step Giant-Step.

2.2 Information-Theoretic Tools

The core of the proof relies on information-theoretic tools applied to distributions over the space of permutations $S_N$ , rather than product spaces.

Shearer's Lemma for Permutations: The authors utilize a variant of Shearer's lemma for random bijections (derived from Barthe et al. [BCELM11] and Caputo and Salez [CS24]). This inequality relates the Kullback-Leibler (KL) divergence of a distribution over permutations to the KL divergences of its marginals on subsets of indices.
Concentration Inequalities for Read- $k$ Families: They derive a concentration bound for families of functions over permutations where each function depends on a "read- $k$ " set of variables (each coordinate is accessed by at most $k$ functions). This extends the result of Gavinsky et al. [GLSS15] from product spaces to the space of bijections.
Uniformity of Translation: A key technical condition is that the translation function $tr$ must be $u$ -uniform. This means that for any fixed outer query, the resulting input to the permutation is distributed nearly uniformly over $[N]$ when the secret $d$ is chosen uniformly.

2.3 Proof Strategy

The main theorem (Theorem 4.1) bounds the success probability of a non-adaptive preprocessing adversary by relating it to the success probability of a non-preprocessing adversary.

Hybrid Argument: The proof introduces a "middle game" where the adversary can fix a limited number of permutation values (simulating inner queries) but the rest are sampled uniformly.
KL-Divergence Analysis: By conditioning on the advice string, the authors analyze the KL divergence between the distribution of the permutation in the preprocessing setting versus the uniform distribution.
Application of Shearer-like Bounds: Using the $u$ -uniformity of the translation function, they show that the set of translated outer queries forms a read- $k$ family. The concentration inequality (Theorem 1.9) then bounds the advantage gained from the advice string, showing that unless the advice is sufficiently large ( $S \gg \sqrt{N}$ ), the success probability cannot significantly exceed that of a non-preprocessing algorithm.

3. Key Contributions and Results

The paper establishes sharp lower bounds demonstrating that adaptivity provides a significant advantage in the preprocessing model for several cryptographic problems.

3.1 Discrete Logarithm (DLOG)

Result: For a generic group of prime order $N$ , any non-adaptive $(S, T)$ -algorithm with preprocessing has a success probability bounded by:
$\text{Success} \le 2 \cdot \text{Max}_{S}^{\text{DLOG}}(T) + \frac{4 \log(2) ST}{N} + \frac{T^2}{N}$
where $\text{Max}_{S}^{\text{DLOG}}(T) \le T^2/N$ is the bound for non-preprocessing algorithms (Shoup [Sho97]).
Implication: The online time complexity $T = O(\sqrt{N})$ of the non-adaptive Baby-Step Giant-Step algorithm cannot be improved by preprocessing, unless the advice string size $S$ exceeds $\Omega(\sqrt{N})$ . This contrasts sharply with adaptive algorithms (e.g., Mihalcik [Mih10], Bernstein and Lange [BL13], Corrigan-Gibbs and Kogan [CK18]) which achieve the tradeoff $ST^2 = \tilde{O}(N)$ , allowing $T = O(N^{1/3})$ with $S = \tilde{O}(N^{1/3})$ .

3.2 Decisional Diffie-Hellman (DDH) and sqDDH

Result: Similar bounds are derived for DDH and sqDDH. For sqDDH, the bound is sharp and matches a simple non-adaptive variant of the adaptive algorithm. For DDH, the authors conjecture the bound is not tight and propose the optimal bound is $1/2 + \tilde{O}(T^2/N + ST/N)$ .
Implication: Non-adaptive preprocessing does not offer the same tradeoff improvements as adaptive preprocessing for these decisional problems.

3.3 Even-Mansour (EM) Cryptosystem

Result: For key-recovery attacks on the Even-Mansour cipher, unbounded preprocessing does not speed up non-adaptive attacks (unless $S \ge \tilde{\Omega}(\sqrt{N})$ ).
Implication: This stands in stark contrast to adaptive attacks (e.g., Fouque, Joux, and Mavromati [FJM14]) which can achieve online complexity $T = \tilde{O}(2^{n/3})$ with $S = \tilde{O}(2^{n/3})$ . The non-adaptive lower bound confirms that the memory reduction in adaptive attacks relies fundamentally on adaptivity.

4. Significance and Limitations

Significance

Formal Justification of Adaptivity: The paper provides the first formal proof that adaptivity is essential for achieving sub- $\sqrt{N}$ time complexity in DLOG and sub- $2^{n/3}$ complexity in Even-Mansour key recovery within the preprocessing model.
New Technical Tool: The application of a Shearer-like inequality for permutations (Theorem 1.8) in an algorithmic context is a novel contribution. The authors note this is the first time such a variant has been used for lower bound arguments in this domain.
Unified Model: The Permutation Challenge model successfully abstracts a wide array of search and decision problems, allowing for a collective analysis of their non-adaptive time-space tradeoffs.

Limitations and Open Problems

Challenge-Dependent Queries: The proof strategy relies on the independence of pre-translated queries from the challenge. Extending these results to allow pre-translated queries that depend on the challenge (e.g., $f(d + f(d))$ ) would require new concentration inequalities, as current Shearer-like bounds do not handle such composed inputs effectively.
Adaptive Rounds: The paper leaves open the problem of characterizing time-space tradeoffs for adaptive algorithms with a specific number of adaptivity rounds $r$ . The authors conjecture a bound of $\tilde{O}(T^2/N + rST/N)$ .
DDH Tightness: The lower bound for non-adaptive DDH is conjectured to be loose, with the authors suggesting the true bound might be tighter than the one proven.

The paper concludes that previous generic techniques (compression arguments, pre-sampling, standard concentration inequalities) are inherently limited in distinguishing between adaptive and non-adaptive algorithms, improving over adaptive bounds by at most polylogarithmic factors. The new information-theoretic approach presented here overcomes this barrier for the specific class of non-adaptive algorithms analyzed.