{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:15:46Z","timestamp":1778040946889,"version":"3.51.4"},"reference-count":48,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T00:00:00Z","timestamp":1769990400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"crossref","award":["2022-06725"],"award-info":[{"award-number":["2022-06725"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]},{"award":["2022-06725"],"award-info":[{"award-number":["2022-06725"]}],"id":[{"id":"https:\/\/ror.org\/03zttf063","id-type":"ROR","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2026,4,23]]},"abstract":"<jats:p>\n                    Eker\u00e5 and H\u00e5stad have introduced a variation of Shor's algorithm for the discrete logarithm problem (DLP).   Unlike Shor's original algorithm, Eker\u00e5\u2013H\u00e5stad's algorithm solves the short DLP in groups of unknown order.   In this work, we prove a lower bound on the probability of Eker\u00e5\u2013H\u00e5stad's algorithm recovering the short logarithm\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>d<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    in a single run.   By our bound, the success probability can easily be pushed as high as\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\u2212<\/mml:mo>\n                        <mml:msup>\n                          <mml:mn>10<\/mml:mn>\n                          <mml:mrow>\n                            <mml:mo>\u2212<\/mml:mo>\n                            <mml:mn>10<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:msup>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    for any short\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>d<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    .   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\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>m<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    of\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>d<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    tends to infinity, the success probability tends to one if the limits on the search space are parameterized in\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>m<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:math>\n                    .   Our results are directly applicable to Diffie\u2013Hellman in safe-prime groups with short exponents, and to RSA via a reduction from the RSA integer factoring problem (IFP) to the short DLP.\n                  <\/jats:p>","DOI":"10.62056\/an2isgsfg","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T18:09:08Z","timestamp":1777918148000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["On the success probability of the quantum algorithm for the short DLP"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7061-2374","authenticated-orcid":false,"given":"Martin","family":"Eker\u00e5","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/026vcq606","id-type":"ROR","asserted-by":"publisher"}],"name":"KTH Royal Institute of Technology","place":["Stockholm, Sweden"]},{"id":[{"id":"https:\/\/ror.org\/04qn5a624","id-type":"ROR","asserted-by":"publisher"}],"name":"Swedish NCSA, Swedish Armed Forces","place":["Stockholm, Sweden"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:shor94","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/SFCS.1994.365700","article-title":"Algorithms for quantum computation: Discrete logarithms and\n  factoring","author":"P. W. Shor","year":"1994"},{"key":"ref2:shor97","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","article-title":"Polynomial-Time Algorithms for Prime Factorization and\n  Discrete Logarithms on a Quantum Computer","volume":"26","author":"P. W. Shor","year":"1997","journal-title":"SIAM\u00a0J. Comput."},{"key":"ref3:ekera-modifying","volume-title":"Modifying Shor's algorithm to compute short discrete\n  logarithms","author":"M. Eker\u00e5","year":"2016"},{"key":"ref4:ekera-hastad","series-title":"Lecture Notes in Computer Science (LNCS)","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-319-59879-6_20","article-title":"Quantum Algorithms for Computing Short Discrete Logarithms\n  and Factoring RSA Integers","volume":"10346","author":"M. Eker\u00e5","year":"2017"},{"key":"ref5:ekera-pp","doi-asserted-by":"publisher","first-page":"2313","DOI":"10.1007\/s10623-020-00783-2","article-title":"On post-processing in the quantum algorithm for computing\n  short discrete logarithms","volume":"88","author":"M. Eker\u00e5","year":"2020","journal-title":"Des. Codes Cryptogr."},{"key":"ref6:diffie-hellman","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","article-title":"New directions in cryptography","volume":"22","author":"W. Diffie","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref7:nistsp800-56a","doi-asserted-by":"publisher","DOI":"10.6028\/NIST.SP.800-56Ar3","volume-title":"Recommendation for Pair-Wise Key-Establishment Schemes Using\n  Discrete Logarithm Cryptography","author":"E. Barker","year":"2018"},{"key":"ref8:rfc3526","doi-asserted-by":"publisher","DOI":"10.17487\/RFC3526","volume-title":"More Modular Exponential (MODP) Diffie\u2013Hellman groups\n  for Internet Key Exchange (IKE)","author":"T. Kivinen","year":"2003"},{"key":"ref9:rfc7919","doi-asserted-by":"publisher","DOI":"10.17487\/RFC7919","volume-title":"Negotiated Finite Field Diffie\u2013Hellman Ephemeral\n  Parameters for Transport Layer Security (TLS)","author":"D. Gillmor","year":"2016"},{"key":"ref10:rsa","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key\n  cryptosystems","volume":"21","author":"R. L. Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref11:ekera-phd-thesis","volume-title":"On factoring integers, and computing discrete logarithms and\n  orders, quantumly","author":"M. Eker\u00e5","year":"2024"},{"key":"ref12:seifert","series-title":"Lecture Notes in Computer Science (LNCS)","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/3-540-45353-9_24","article-title":"Using Fewer Qubits in Shor's Factorization Algorithm via\n  Simultaneous Diophantine Approximation","volume":"2020","author":"J.-P. Seifert","year":"2001"},{"key":"ref13:gidney19","volume-title":"Windowed quantum arithmetic","author":"C. Gidney","year":"2019"},{"key":"ref14:vmi05","doi-asserted-by":"publisher","first-page":"52320","DOI":"10.1103\/PhysRevA.71.052320","article-title":"Fast quantum modular exponentiation","volume":"71","author":"R. Van Meter","year":"2005","journal-title":"Phys. Rev.\u00a0A"},{"key":"ref15:van-meter-phd-thesis","volume-title":"Architecture of a Quantum Multicomputer Optimized for\n  Shor's Factoring Algorithm","author":"R. Van Meter","year":"2008"},{"key":"ref16:ekera-success","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/3655026","article-title":"On the success probability of quantum order finding","volume":"5","author":"M. Eker\u00e5","year":"2024","journal-title":"ACM Trans. Quantum Comput."},{"key":"ref17:ekera-general","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1515\/jmc-2020-0006","article-title":"Quantum algorithms for computing general discrete logarithms\n  and orders with tradeoffs","volume":"15","author":"M. Eker\u00e5","year":"2021","journal-title":"J. Math. Cryptol."},{"key":"ref18:ekera-revisiting","volume-title":"Revisiting Shor's quantum algorithm for computing general\n  discrete logarithms","author":"M. Eker\u00e5","year":"2024"},{"key":"ref19:gidney-ekera","doi-asserted-by":"publisher","first-page":"433","DOI":"10.22331\/q-2021-04-15-433","article-title":"How to factor 2048 bit RSA integers in 8 hours using 20\n  million noisy qubits","volume":"5","author":"C. Gidney","year":"2021","journal-title":"Quantum"},{"key":"ref20:gouzien-sangouard","doi-asserted-by":"publisher","first-page":"140503","DOI":"10.1103\/PhysRevLett.127.140503","article-title":"Factoring 2048-bit RSA Integers in 177 Days with 13\u00a0436\n  Qubits and a Multimode Memory","volume":"127","author":"\u00c9. Gouzien","year":"2021","journal-title":"Phys. Rev. Lett."},{"key":"ref21:grrgs23","doi-asserted-by":"publisher","first-page":"40602","DOI":"10.1103\/PhysRevLett.131.040602","article-title":"Performance Analysis of a Repetition Cat Code Architecture:\n  Computing 256-bit Elliptic Curve Logarithm in 9\u00a0Hours with 126\u00a0133 Cat\n  Qubits","volume":"131","author":"\u00c9. Gouzien","year":"2023","journal-title":"Phys. Rev. Lett."},{"key":"ref22:gidney25","volume-title":"How to factor 2048 bit RSA integers with less than a\n  million noisy qubits","author":"C. Gidney","year":"2025"},{"key":"ref23:lukin25","doi-asserted-by":"publisher","first-page":"1432","DOI":"10.1145\/3695053.3731039","article-title":"Resource Analysis of Low-Overhead Transversal Architectures\n  for Reconfigurable Atom Arrays","author":"H. Zhou","year":"2025"},{"key":"ref24:jgs26","doi-asserted-by":"publisher","first-page":"13205","DOI":"10.1103\/v9ln-c4v2","article-title":"Network requirements for distributed quantum computation","volume":"8","author":"H. Jacinto","year":"2026","journal-title":"Phys. Rev. Res."},{"key":"ref25:webster26","volume-title":"The Pinnacle Architecture: Reducing the cost of breaking\n  RSA-2048 to 100\u00a0000 physical qubits using quantum LDPC codes","author":"P. Webster","year":"2026"},{"key":"ref26:cain26","volume-title":"Shor's algorithm is possible with as few as 10,000\n  reconfigurable atomic qubits","author":"M. Cain","year":"2026"},{"key":"ref27:griffiths-niu","doi-asserted-by":"publisher","first-page":"3228","DOI":"10.1103\/PhysRevLett.76.3228","article-title":"Semiclassical Fourier Transform for Quantum Computation","volume":"76","author":"R. B. Griffiths","year":"1996","journal-title":"Phys. Rev. Lett."},{"key":"ref28:zalka","volume-title":"Fast versions of Shor's quantum factoring algorithm","author":"C. Zalka","year":"1998"},{"key":"ref29:parker-plenio","doi-asserted-by":"publisher","first-page":"3049","DOI":"10.1103\/PhysRevLett.85.3049","article-title":"Efficient Factorization with a Single Pure Qubit and $\\log\n  N$ Mixed Qubits","volume":"85","author":"S. Parker","year":"2000","journal-title":"Phys. Rev. Lett."},{"key":"ref30:mosca-ekert","series-title":"Lecture Notes in Computer Science (LNCS)","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/3-540-49208-9_15","article-title":"The Hidden Subgroup Problem and Eigenvalue Estimation on a\n  Quantum Computer","volume":"1509","author":"M. Mosca","year":"1999"},{"key":"ref31:cfs25","series-title":"Lecture Notes in Computer Science (LNCS)","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/978-3-032-01878-6_13","article-title":"Reducing the Number of Qubits in Quantum Factoring","volume":"16001","author":"C. Chevignard","year":"2025"},{"key":"ref32:ms22","doi-asserted-by":"publisher","first-page":"183","DOI":"10.46586\/tosc.v2022.i1.183-211","article-title":"Quantum Period Finding is Compression Robust","volume":"2022","author":"A. May","year":"2022","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref33:nemes","doi-asserted-by":"publisher","first-page":"20170363","DOI":"10.1098\/rspa.2017.0363","article-title":"Error bounds for the asymptotic expansion of the Hurwitz\n  zeta function","volume":"473","author":"G. Nemes","year":"2017","journal-title":"Proc. R. Soc. A."},{"key":"ref34:lagrange","first-page":"695","article-title":"Recherches d'arithm\u00e9tique \u2014 Nouveaux M\u00e9moires de\n  l'Acad\u00e9mie royale des Sciences et Belles-Lettres de Berlin,\n  ann\u00e9es\u00a01773 et\u00a01775.","volume":"3","author":"J.-L. Lagrange","year":"1869"},{"key":"ref35:nguyen","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-642-02295-1_2","article-title":"Hermite's Constant and Lattice Algorithms","author":"P. Q. Nguyen","year":"2010"},{"key":"ref36:lll","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"A. K. Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref37:shanks","series-title":"Proceedings of Symposia in Pure Mathematics","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1090\/pspum\/020\/0316385","article-title":"Class number, a theory of factorization, and genera","volume":"20","author":"D. Shanks","year":"1971"},{"key":"ref38:pollard-rho-lambda","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1090\/S0025-5718-1978-0491431-9","article-title":"Monte Carlo Methods for Index Computation $(\\text{mod }\n  p)$","volume":"32","author":"J. M. Pollard","year":"1978","journal-title":"Math. Comput."},{"key":"ref39:oorschot-wiener","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00003816","article-title":"Parallel Collision Search with Cryptanalytic Applications","volume":"12","author":"P. C. van Oorschot","year":"1999","journal-title":"J. Cryptol."},{"key":"ref40:gaudry-schost","series-title":"Lecture Notes in Computer Science (LNCS)","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-24847-7_15","article-title":"A Low-Memory Parallel Version of Matsuo, Chao, and\n  Tsujii's Algorithm","volume":"3076","author":"P. Gaudry","year":"2004"},{"key":"ref41:galbraith-ruprai","series-title":"Lecture Notes in Computer Science (LNCS)","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/978-3-642-10868-6_22","article-title":"An Improvement to the Gaudry\u2013Schost Algorithm for\n  Multidimensional Discrete Logarithm Problems","volume":"5921","author":"S. Galbraith","year":"2009"},{"key":"ref42:quaspy","volume-title":"The Quaspy library for Python","author":"M. Eker\u00e5","year":"2026"},{"key":"ref43:babai","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","article-title":"On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice\n  point problem","volume":"6","author":"L. Babai","year":"1986","journal-title":"Combinatorica"},{"key":"ref44:bloom","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/time trade-offs in hash coding with allowable errors","volume":"13","author":"B. H. Bloom","year":"1970","journal-title":"Commun. ACM"},{"key":"ref45:gnfs","series-title":"STOC '90","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1145\/100216.100295","article-title":"The number field sieve","author":"A. K. Lenstra","year":"1990"},{"key":"ref46:gordon","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1137\/0406010","article-title":"Discrete Logarithms in $GF(p)$ Using the Number Field\n  Sieve","volume":"6","author":"D. M. Gordon","year":"1993","journal-title":"SIAM J. Discrete Math."},{"key":"ref47:schirokauer","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1098\/rsta.1993.0139","article-title":"Discrete logarithms and local units","volume":"345","author":"O. Schirokauer","year":"1993","journal-title":"Phil. Trans. R. Soc. Lond. A"},{"key":"ref48:fips-140-2-ig","volume-title":"Implementation guidance for FIPS\u00a0140-2 and the\n  cryptographic module validation program","author":"National Institute of Standards","year":"2023"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:02:03Z","timestamp":1778040123000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":48,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/an2isgsfg","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,4]]},"assertion":[{"value":"2026-02-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc3-1-11"}}