The Optimal Bound for Non-Adaptive DDH with Preprocessing
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
Discrete logarithm, Diffie–Hellman and its square variant have the same generic security without preprocessing, and for years they had the same bound with preprocessing too. Then the adaptive DDH case was settled sharply in 2024, and the source paper settled the non-adaptive discrete-log case in 2025 — leaving one cell of the table with a bound its own authors do not believe. The proved bound carries a square root; the source says twice that the square root is an artefact of combining two arguments, and names what should replace it. The reason to take that seriously is the control experiment sitting next to it: for square-DDH, the very same theorem is sharp.
View PDF · LaTeX source · Formal statement — not yet formalized
The model. \(N\) prime and \(\sigma : \mathbb{Z}_{N} \to [N]\) a uniformly random bijection presenting \(g^{j}\) as \(\sigma(j)\). The DDH secret is \((d_{1}, d_{2}, d_{3}, k)\) with \(d_{1},d_{2},d_{3} \leftarrow \mathbb{Z}_{N}\) and \(k \leftarrow \{0,1\}\); the algorithm must output \(k\). An outer query is \((a_{1},a_{2},a_{3},b) \in \mathbb{Z}_{N}^{4}\) (excluding \(a_{1} = a_{2} = a_{3} = N\)), answered with \(\sigma\) applied to \[a_{1}d_{1} + a_{2}d_{2} + a_{3}d_{3} + b \bmod N \quad (k = 0), \qquad a_{1}d_{1} + a_{2}d_{2} + a_{3}(d_{1}d_{2}) + b \bmod N \quad (k = 1),\] so \(k=0\) presents \(\sigma(d_{1}), \sigma(d_{2}), \sigma(d_{3})\) and \(k=1\) presents \(\sigma(d_{1}), \sigma(d_{2}), \sigma(d_{1}d_{2})\). An \((S,T)\)-algorithm is a preprocessing pair \((\mathcal{A}_{0}, \mathcal{A}_{1})\) with \(S\) bits of advice and \(T\) online queries; it is non-adaptive if, in the source’s words, “given any \(z\), its queries are fixed and do not (further) depend on \(\sigma\)” — the coefficient tuples are chosen before the challenge, though the oracle queries they become still depend on the secret.
What is proved (the source’s Theorem 1.2). Every non-adaptive \((S,T)\)-algorithm for DDH — and for square-DDH — succeeds with probability at most \[\frac{1}{2} + \frac{2T^{2}}{N} + \sqrt{\frac{2\log_{e}(2)\,ST}{N}}.\]
Conjecture. There is a function \(c(\cdot)\), polylogarithmic in \(N\), such that for every prime \(N\) and every non-adaptive \((S,T)\)-algorithm for the DDH problem in the generic group model over a group of order \(N\), the success probability is at most \[\frac{1}{2} + c(N)\cdot\left(\frac{T^{2}}{N} + \frac{S T}{N}\right).\]
How the source states it. Twice, in its own words. After Theorem 1.2: “For the DDH problem, we conjecture that the bound on the success probability is not sharp, and the ‘right’ bound is \(\tfrac{1}{2} + \widetilde{O}(T^{2}/N + ST/N)\).” And in its open-problems paragraph: “Another open problem, mentioned above, is to close the gap between upper and lower bounds for non-adaptive \((S,T)\)-algorithms for the DDH problem. As written, we conjecture that the bound of Theorem 1.2 is not tight, and the optimal bound is” the same value. It also names the route: “Possibly, the techniques used in the recent result [ABG$^{+}$24] which determined the maximal success rate of adaptive algorithms can be combined with our techniques to show this improved bound in the non-adaptive setting.”
One half, not two. The source writes “the optimal bound is”, which claims both an upper bound and a matching attack. This page states the upper-bound half only, because the source’s own framing of the missing work is “to close the gap between upper and lower bounds”, and because a matching non-adaptive attack in this regime would be a variant of algorithms the source already cites. A reviewer who reads “optimal” as asserting both halves at once would state a two-sided conjecture and would be making a defensible choice this page does not make.
Sources
- Dinur, Keller and Marmor. Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations. IACR ePrint 2025/783; STOC 2026. Theorem 1.2 and the first statement of the conjecture are on printed p. 5 = PDF p. 6; the open-problems restatement is printed p. 10 = PDF p. 11; the DDH permutation-challenge game is §3.3, PDF p. 18; the proof is §5.2. Printed and PDF page numbers differ by one; both are given.
- Akshima, Besselman, Guo, Xie and Ye. Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem. STOC 2024. The sharp \(\tfrac{1}{2} + \widetilde{\Theta}(ST^{2}/N)\) for adaptive algorithms, and the techniques the source expects to be combinable with its own.
- Corrigan-Gibbs and Kogan. The Discrete-Logarithm Problem with Preprocessing. EUROCRYPT 2018. The earlier \(\tfrac{1}{2} + \widetilde{O}(\sqrt{ST^{2}/N})\) for both decisional problems, and the algorithm whose non-adaptive variant attains the square-DDH bound.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open. No improvement on Theorem 1.2 for DDH has been published, and no attack matching its square-root term is known.
Where the loss is, according to the source. The bound “is obtained by combining two different bounds”, and that combination is what produces \(\sqrt{ST/N}\). The source’s confidence that the loss is real, and not just unproven-to-be-absent, comes from the neighbouring case: “For the sqDDH problem, the theorem is sharp, as a simple non-adaptive variant of the adaptive algorithm of [CK18] sketched in Appendix B attains its success probability bound.” So one instance of the same theorem is tight and the other is believed lossy — that is a much stronger signal than a bound nobody has managed to improve.
What makes it a real question rather than bookkeeping. Both bounds come out of the same route: the source instantiates its permutation-challenge model and shows the translation function is \((N/2)\)-uniform, using the fact that each query is a polynomial of degree at most \(2\) in the secrets. For square-DDH the query is a polynomial in a single unknown \(d_{1}\), of degree at most \(2\); for DDH it is a polynomial in three unknowns with the quadratic term restricted to \(d_{1}d_{2}\). The uniformity parameter is the same for both, so the proof genuinely cannot tell them apart, and a solution has to exhibit the structural difference the parameter hides. That is a specific and unusually well-posed demand.
Why the regime matters. The conjecture strengthens Theorem 1.2 exactly when \(ST/N\) is small, where \(ST/N \ll \sqrt{ST/N}\); when \(ST \ge N\) both bounds are vacuous. So the content is entirely in the range that matters for parameter setting — an attacker with, say, \(S = T = N^{1/3}\) sits well inside it.
The route the source names, and what it would need. Akshima, Besselman, Guo, Xie and Ye settled the adaptive case at \(\tfrac{1}{2} + \widetilde{\Theta}(ST^{2}/N)\) by a tighter argument than the earlier \(\sqrt{ST^{2}/N}\); the source suggests transplanting that tightening into its non-adaptive framework. Whether the two techniques compose is exactly the open question: one is an argument about adaptive query structure, the other is an information-theoretic inequality that requires query independence, and nothing in either paper says they fit together.
What a refutation would look like. A non-adaptive algorithm achieving advantage \(\widetilde{\Omega}(\sqrt{ST/N})\) for DDH in some range — that is, a genuine use of the square root. Because the square-DDH attack exists and attains its bound, the natural first move is to ask what that attack does when the two exponents are independent rather than equal, and whether the loss it then suffers is a power or a constant.
Checked against the literature, 2026-08-23. The source’s ePrint was last revised 2026-05-26 for STOC 2026, and the copy read here is that revision. No work found that improves Theorem 1.2’s DDH case or exhibits a matching attack. ePrint 2024/1171 (STOC 2024) settles the adaptive case and is the paper the source points at, not a resolution of this. Note that 2024/1171 was itself read by this site in an earlier harvest and recorded as posing no open problem of its own. This is a targeted check, not an exhaustive sweep.
A conjecture that is unusually cheap to state and unusually well-motivated. No new definitions, no new model: it is one term in one inequality, in a model that has been standard since 1997, with a control experiment attached. That combination is rare enough to be worth a page even though the statement is, in one sense, small — it is the last unsettled cell in the non-adaptive column for the three standard generic-group problems, the others being the source’s own sharp DLOG and square-DDH bounds.
How it relates to its companion. c/0060 varies the number of adaptivity rounds and keeps DLOG; this page keeps one round and changes the problem. They share a paper, a model and a technique, and neither implies the other — a proof of either would be a real advance in the same direction, which is why they sit under one hub joined by variant-of rather than by an implication edge.
What a reviewer should be suspicious of, in order. First, the one-half-versus-two-halves reading: if the source means to conjecture the matching attack as well, the page’s statement is weaker than the source’s sentence, and the difference should be recorded on whichever page ends up standing. Second, whether the conjectured \(\widetilde{O}\) is intended to hide the same polylogarithmic factors as Theorem 1.2’s explicit constants — the page’s \(c(N)\) formalization assumes so. Third, whether “non-adaptive” here should permit the algorithm to see the challenge encodings before fixing its coefficients; the source’s definition says queries are fixed given the advice, and this page follows it, but for the decisional problems that reading deserves a second look, since the three challenge encodings are themselves what the coefficients act on.