Pith. sign in

REVIEW 2 minor 39 references

On the success probability of the quantum algorithm for the short DLP

T0 review · 0 major / 2 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read The Ekerå-Håstad algorithm recovers the short discrete logarithm with probability at least 1 - 10^{-10} in one run.

desk verdict The paper gives an explicit lower bound showing the Ekerå-Håstad short-DLP algorithm reaches success probability 1-10^{-10} in one run and approaches 1 asymptotically when the classical search radius is set in terms of m. read the letter →

arxiv 2309.01754 v4 submitted 2023-09-04 cs.CR quant-ph

Martin Eker{aa} This is my paper
classification cs.CRquant-ph
keywords shortalgorithmprobabilitysuccessekerstadboundclassical
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper establishes a lower bound on the success probability of the Ekerå-Håstad quantum algorithm for the short discrete logarithm problem in groups of unknown order. By this bound the probability reaches at least 1 - 10^{-10} for any short d when the classical post-processing uses meet-in-the-middle or random-walk search over suitably limited spaces. The same bound shows that the probability tends to one as the bit length m of d grows to infinity once the search limits are parameterized in m. The results apply directly to Diffie-Hellman key exchange with short exponents in safe-prime groups and, via reduction, to the integer factoring problem underlying RSA.

What carries the argument

Lower bound on the probability that classical meet-in-the-middle or random-walk post-processing recovers d from the states produced by the quantum component of the Ekerå-Håstad algorithm.

What would settle it

An explicit computation or small-instance simulation that measures the fraction of runs in which the post-processing recovers a chosen short d and checks whether that fraction stays above the stated lower bound.

Watch

Extended reading notes

Core claim

Ekerå and Håstad introduced a variation of Shor's algorithm that solves the short DLP in groups of unknown order. This work proves a lower bound on the probability that the algorithm recovers the short logarithm d in a single run. The bound allows the success probability to reach 1 - 10^{-10} for any short d by efficiently performing a limited search in the classical post-processing using meet-in-the-middle or random-walk techniques. Asymptotically the probability tends to one as the bit length m of d tends to infinity when limits are parameterized in m.

Load-bearing premise

The quantum component produces states from which the classical post-processing recovers d with the stated probability once search-space limits are set appropriately.

Editorial extensions

If this is right

  • Success probability reaches at least 1 - 10^{-10} for any short d.
  • As m tends to infinity the success probability tends to one when search limits are parameterized in m.
  • Meet-in-the-middle and random-walk techniques speed up the classical post-processing step.
  • The algorithm applies directly to Diffie-Hellman in safe-prime groups with short exponents.
  • RSA integer factoring reduces to short DLP so the same bound applies there.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • High single-run success may reduce the number of quantum circuit executions needed in practice for short-exponent cryptosystems.
  • The post-processing techniques could be adapted to improve classical recovery steps in other quantum algorithms for related number-theoretic problems.
  • Parameterizing search limits by m trades increased classical work for near-certain recovery, which could be quantified in concrete runtime analyses.
  • The bound supplies a concrete reliability figure that cryptographers can use when assessing quantum risk to short-exponent Diffie-Hellman.
  • keywords:[
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The manuscript derives an explicit lower bound on the single-run success probability of the Ekerå-Håstad quantum algorithm for the short discrete logarithm problem. The bound is obtained by first upper-bounding the probability that a measured pair (a, b) falls inside a suitable window around a multiple of the hidden logarithm, then showing that a classical meet-in-the-middle or random-walk search recovers d whenever this window condition holds. The resulting probability is at least 1 - 10^{-10} for any fixed short d and tends to 1 as the bit length m of d tends to infinity when the search-space limits are parameterized in m.

Significance. If the derivation holds, the result supplies a concrete, non-asymptotic guarantee on the reliability of a quantum algorithm for short DLP instances, directly strengthening the case for quantum attacks on short-exponent Diffie-Hellman and on RSA via the known reduction from IFP. The explicit constants and the clean separation between the quantum measurement analysis and the classical coverage probability are useful for concrete security estimates.

minor comments (2)
  1. [Abstract] Abstract: the claim that the success probability 'can easily be pushed as high as 1 - 10^{-10}' would be clearer if the precise functional dependence on the search radius and on m were stated in one sentence.
  2. The manuscript does not indicate whether the derived constants are tight; a short remark on possible looseness in the window-probability or coverage bounds would help readers assess room for improvement.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, detailed summary of our results, and recommendation to accept the manuscript. There are no major comments requiring a point-by-point response.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity in the derivation of the success probability bound

full rationale

The paper derives an explicit lower bound on the single-run success probability by first bounding the probability that a measured pair (a,b) lies inside a suitable window around a multiple of the hidden logarithm, then showing that the classical meet-in-the-middle or random-walk search recovers d whenever that window condition holds. Both steps use explicit constants that remain valid for any fixed short d and improve to 1 as m→∞ under the stated parameterization of the search-space limits. No load-bearing step reduces by definition or by self-citation chain to its own inputs; the central claim rests on direct probability calculations from the quantum measurement distribution and standard classical search coverage, which are independent of the target bound itself.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the proof is expected to rest on standard assumptions of quantum Fourier sampling and group theory from prior Shor/Ekerå-Håstad work.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the success probability of the quantum algorithm for the short DLP." pith.science (2026). https://pith.science/paper/2309.01754

@misc{pith2026230901754,
  author       = {Pith},
  title        = {Pith review of: On the success probability of the quantum algorithm for the short DLP},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2309.01754}},
  note         = {Machine review of arXiv:2309.01754}
}
abstract

Eker{\aa} and H{\aa}stad have introduced a variation of Shor's algorithm for the discrete logarithm problem (DLP). Unlike Shor's original algorithm, Eker{\aa}-H{\aa}stad's algorithm solves the short DLP in groups of unknown order. In this work, we prove a lower bound on the probability of Eker{\aa}-H{\aa}stad's algorithm recovering the short logarithm $d$ in a single run. By our bound, the success probability can easily be pushed as high as $1 - 10^{-10}$ for any short $d$. A key to achieving such a high success probability is to efficiently perform a limited search in the classical post-processing by leveraging meet-in-the-middle or random-walk techniques. These techniques may be generalized to speed up other related classical post-processing algorithms. Asymptotically, in the limit as the bit length $m$ of $d$ tends to infinity, the success probability tends to one if the limits on the search space are parameterized in $m$. Our results are directly applicable to Diffie-Hellman in safe-prime groups with short exponents, and to RSA via a reduction from the RSA integer factoring problem (IFP) to the short DLP.

Figures

Figures reproduced from arXiv: 2309.01754 by the authors.

Figure 1
Figure 1. A quantum circuit for inducing the state (1) and measuring the two control registers yielding j and k, respectively. In this figure, a = Pm+ℓ−1 i = 0 2 i ai and b = Pℓ−1 i = 0 2 i bi where ai, bi ∈ {0, 1}, see Sect. 1.4.1. The operations at the bottom are compositions under the group operation by classically pre-computed constant group elements. The bottom work reg￾ister must be of sufficient length ν to store a sup… view at source ↗
Figure 2
Figure 2. A quantum circuit, equivalent to that in [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    Babai: On Lov´ asz’ lattice reduction and the nearest lattice point problem

    L. Babai: On Lov´ asz’ lattice reduction and the nearest lattice point problem. Combinatorica 6(1) (1986), 1–13

    work page 1986

  2. [2]

    Barker et al.: NIST SP 800-56A: Recommendation for Pair-Wise Key- Establishment Schemes Using Discrete Logarithm Cryptography, rev

    E. Barker et al.: NIST SP 800-56A: Recommendation for Pair-Wise Key- Establishment Schemes Using Discrete Logarithm Cryptography, rev. 3 (2018)

    work page 2018

  3. [3]

    Diffie and M.E

    W. Diffie and M.E. Hellman: New Directions in Cryptography. IEEE Trans. Inf. Theory 22(6) (1976), 644–654

    work page 1976

  4. [4]

    Eker˚ a: Modifying Shor’s algorithm to compute short discrete logarithms

    M. Eker˚ a: Modifying Shor’s algorithm to compute short discrete logarithms. IACR ePrint Archive, Report 2016/1128 (2016)

    work page 2016

  5. [5]

    Eker˚ a and J

    M. Eker˚ a and J. H˚ astad: Quantum algorithms for computing short discrete logarithms and factoring RSA integers. In: PQCrypto 2017. Lecture Notes in Computer Science (LNCS) 10346 (2017), 347–363

    work page 2017

  6. [6]

    Eker˚ a: On post-processing in the quantum algorithm for computing short discrete logarithms

    M. Eker˚ a: On post-processing in the quantum algorithm for computing short discrete logarithms. Des. Codes Cryptogr. 88(11) (2020), 2313–2335

    work page 2020

  7. [7]

    Eker˚ a: Quantum algorithms for computing general discrete logarithms and orders with tradeoffs

    M. Eker˚ a: Quantum algorithms for computing general discrete logarithms and orders with tradeoffs. J. Math. Cryptol. 15(1) (2021), 359–407

    work page 2021

  8. [8]

    Eker˚ a: On the success probability of quantum order finding

    M. Eker˚ a: On the success probability of quantum order finding. ACM Trans. Quantum Comput. 5(2):11 (2024), 1–40

    work page 2024

Show all 39 references
  1. [9]

    Eker˚ a: Revisiting Shor’s quantum algorithm for computing general discrete logarithms

    M. Eker˚ a: Revisiting Shor’s quantum algorithm for computing general discrete logarithms. ArXiv 1905.09084v4 (2019–2024)

    1905

  2. [10]

    Eker˚ a: On factoring integers, and computing discrete logarithms and or- ders, quantumly

    M. Eker˚ a: On factoring integers, and computing discrete logarithms and or- ders, quantumly. PhD thesis. KTH Royal Institute of Technology, Sweden (2024)

    2024

  3. [11]

    Gidney: Windowed quantum arithmetic

    C. Gidney: Windowed quantum arithmetic. ArXiv 1905.07682v1 (2019). 15

    1905 arXiv

  4. [12]

    Gillmor: RFC 7919: Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS) (2016)

    D. Gillmor: RFC 7919: Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS) (2016)

    2016

  5. [13]

    Gordon: Discrete logarithms in GF( p) using the number field sieve

    D.M. Gordon: Discrete logarithms in GF( p) using the number field sieve. SIAM J. Discrete Math. 6(1) (1993), 124–138

    1993

  6. [14]

    Griffiths and C.-S

    R.B. Griffiths and C.-S. Niu: Semiclassical Fourier Transform for Quantum Computation. Phys. Rev. Lett. 76 (1996), 3228–3231

    1996

  7. [15]

    Kivinen and M

    T. Kivinen and M. Kojo: RFC 3526: More Modular Exponentiation (MODP) Diffie-Hellman groups for Internet Key Exchange (2003)

    2003

  8. [16]

    J.-L. Lagrange: Recherches d’arithm´ etique, Œuvres compl` etes (tome 3), Nou- veaux M´ emoires de l’Acad´ emie royale des Sciences et Belles-Lettres de Berlin, ann´ ees 1773 et 1775, (1773, 1775), 695–795. (Retrieved via Gallica.)

  9. [17]

    Lenstra, H.W

    A.K. Lenstra, H.W. Lenstra, Jr. and L. Lov´ asz: Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), 515–534

    1982

  10. [18]

    Lenstra, H.W

    A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse and J.M. Pollard: The number field sieve. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC ’90 (1990), 564–572

    1990

  11. [19]

    Van Meter and K.M

    R. Van Meter and K.M. Itoh: Fast quantum modular exponentiation. Phys. Rev. A 71(5):052320 (2005), 1–12

    2005

  12. [20]

    Van Meter: Architecture of a Quantum Multicomputer Optimized for Shor’s Factoring Algorithm

    R. Van Meter: Architecture of a Quantum Multicomputer Optimized for Shor’s Factoring Algorithm. PhD thesis. Keio University, Japan (2008)

    2008

  13. [21]

    Mosca and A

    M. Mosca and A. Ekert: The Hidden Subgroup Problem and Eigenvalue Esti- mation on a Quantum Computer. In: QCQC 1998. Lecture Notes in Computer Science (LNCS) 1509 (1999), 174–188

    1998

  14. [22]

    Nemes: Error bounds for the asymptotic expansion of the Hurwitz zeta function

    G. Nemes: Error bounds for the asymptotic expansion of the Hurwitz zeta function. Proc. R. Soc. A. 473(2203):20170363 (2017), 1–16

    2017

  15. [23]

    Nguyen: Hermite’s Constant and Lattice Algorithms

    P.Q. Nguyen: Hermite’s Constant and Lattice Algorithms. In: The LLL Al- gorithm: Survey and Applications (2010), 19–69, Springer Berlin Heidelberg

    2010

  16. [24]

    (Dated: March 17, 2023)

    NIST and CCCS: Implementation Guidance for FIPS 140-2 and the Crypto- graphic Module Validation Program (2023). (Dated: March 17, 2023)

    2023

  17. [25]

    Parker and M.B

    S. Parker and M.B. Plenio: Efficient Factorization with a Single Pure Qubit and log N Mixed Qubits. Phys. Rev. Lett. 85(14) (2000), 3049–3052

    2000

  18. [26]

    Pollard: Monte Carlo Methods for Index Computation (mod p)

    J.M. Pollard: Monte Carlo Methods for Index Computation (mod p). Math. Comput. 32(143) (1978), 918–924

    1978

  19. [27]

    Rivest, A

    R.L. Rivest, A. Shamir and L. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 21(2) (1978), 120– 126

    1978

  20. [28]

    Schirokauer: Discrete logarithms and local units

    O. Schirokauer: Discrete logarithms and local units. Phil. Trans. R. Soc. Lond. A 345(1676) (1993), 409–423. 16

    1993

  21. [29]

    Seifert: Using Fewer Qubits in Shor’s Factorization Algorithm via Si- multaneous Diophantine Approximation

    J.-P. Seifert: Using Fewer Qubits in Shor’s Factorization Algorithm via Si- multaneous Diophantine Approximation. In: CT-RSA 2001. Lecture Notes in Computer Science (LNCS) 2020 (2001), 319–327

    2001

  22. [30]

    Shanks: Class number, a theory of factorization, and genera

    D. Shanks: Class number, a theory of factorization, and genera. In: Proceed- ings of Symposia in Pure Mathematics, vol. 20 (1971), 415–440, American Mathematical Society

    1971

  23. [31]

    Shor: Algorithms for Quantum Computation: Discrete Logarithms and Factoring

    P.W. Shor: Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS ’94 (1994), 124–134

    1994

  24. [32]

    Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer

    P.W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5) (1997), 1484– 1509. 17 A Algorithms In this appendix, we describe the classical post-processing algorithm in pseudocode: Algorithm 1 Returns d giv...

    1997

  25. [33]

    Let g1 ← gs1, g2 ← gs2 and w = gν1 1 · gν2 2 · x−1

    Let MeetInTheMiddle(g, x, ν1, ν2, B1, B2, s1, s2, µ, c) be the function: 1.1. Let g1 ← gs1, g2 ← gs2 and w = gν1 1 · gν2 2 · x−1. 1.2. Let n ← c jp B1/(B2 + 1) m . Note: As B1 ≥ 1 and 2B1 > B2 ≥ 0, see Cl. 7, it holds that n ≥ c ≥ 1. 1.3. Let T be an empty lookup table. — Note...

  26. [34]

    Let Lτ(j) be the lattice generated by ( j, 2τ) and (2 m+ℓ, 0)

  27. [35]

    Note: The basis (s1, s2) may be found with Lagrange’s algorithm, see [16, 23]

    Let s1 = (s1,1, s1,2) of norm λ1 be a shortest non-zero vector in Lτ(j), and let s2 = (s2,1, s2,2) be a shortest non-zero vector in Lτ(j) linearly independent to s1, so that (s1, s2) forms a Lagrange-reduced basis. Note: The basis (s1, s2) may be found with Lagrange’s algorith...

  28. [36]

    Let s= 2 = µ · s1 be the component of s2 parallel to s1, and let s⊥ 2 = s2 − s= 2 of norm λ⊥ 2 be the component of s2 orthogonal to s1

    Let µ = ⟨s1, s2⟩/| s1 |2. Let s= 2 = µ · s1 be the component of s2 parallel to s1, and let s⊥ 2 = s2 − s= 2 of norm λ⊥ 2 be the component of s2 orthogonal to s1. Note: As (s1, s2) is Lagrange-reduced, it holds that | µ | ≤ 1/2, see Cl. 6

  29. [37]

    Let ν1 and ν2 be integers such that o = ν1s1 + ν2s2

    Let v = ( {−2mk}2m+ℓ , 0) ∈ Z2, and let o be the vector in Lτ(j) yielded by Babai’s nearest plane algorithm [1] upon input of v and the basis ( s1, s2). Let ν1 and ν2 be integers such that o = ν1s1 + ν2s2

  30. [38]

    Note: It holds that B1 ≥ 1 and 2B1 > B2 ≥ 0, see Cl

    Let B1 ← 2m+τ √ 2/λ1 + 1 and B2 ← 2m+τ √ 2/λ⊥ 2 + 1/2 . Note: It holds that B1 ≥ 1 and 2B1 > B2 ≥ 0, see Cl. 7

  31. [39]

    off-drift

    Return MeetInTheMiddle(g, x, ν1, ν2, B1, B2, s1,2/2τ , s2,2/2τ , µ, c). Note that Alg. 1 uses a standard meet-in-the-middle time-memory tradeoff tech- nique that is essentially a generalization of the technique in Shanks’ baby-step giant-step algorithm [30] to two dimensions. ...

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.