Quantum algorithm breakthrough raises new timeline for breaking current encryption
Researchers have significantly improved the success rate of a quantum algorithm that cracks certain types of encryption, pushing it toward practical viability. The finding accelerates debate over when quantum computers will pose a realistic threat to today's security infrastructure—a concern already shaping investment and regulatory planning in cryptography and cybersecurity.
Originaltitel: On the success probability of the quantum algorithm for the short DLP
Ekerå and Håstad have introduced a variation of Shor's algorithm for the discrete logarithm problem (DLP). Unlike Shor's original algorithm, Ekerå–Hå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å–Håstad's algorithm recovering the short logarithm <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> </mml:mrow> </mml:math> in a single run. By our bound, the success probability can easily be pushed as high as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>−</mml:mo> <mml:msup> <mml:mn>10</mml:mn> <mml:mrow> <mml:mo>−</mml:mo> <mml:mn>10</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> for any short <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> </mml:mrow> </mml:math> . 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> </mml:mrow> </mml:math> of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> </mml:mrow> </mml:math> tends to infinity, the success probability tends to one if the limits on the search space are parameterized in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> </mml:mrow> </mml:math> . 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.