Quantum Algorithm Shrinks Data Needed to Break Encryption Systems

A new algorithm efficiently solves the Elliptic Curve Discrete Logarithm Problem, addressing a fundamental challenge to quantum security. Han Luo and colleagues at Peking University and Tsinghua University present an approach that sharply reduces the number of logical qubits needed to break widely used elliptic-curve cryptosystems. Their work optimises the computationally intensive modular inversion operation within Shor’s algorithm, using refined register-sharing techniques and location-controlled arithmetic. The resulting circuit requires only 1333 logical qubits for a 256-bit prime-field curve, a key improvement over previous implementations and a vital step towards assessing the feasibility of quantum attacks on current encryption standards.

Shor’s algorithm optimisation substantially reduces qubit requirements for breaking elliptic-curve

A new algorithm reduces the logical qubit count to 1333 for a 256-bit prime-field curve, a decrease of 791 qubits compared to the previous low-width implementation. Previously, solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) with comparable security levels demanded at least 1862 logical qubits, rendering practical quantum attacks infeasible. The ECDLP is a cornerstone of the security provided by elliptic-curve cryptography (ECC), which is extensively deployed in protocols such as Transport Layer Security (TLS) for secure web browsing, and in cryptocurrencies like Bitcoin. ECC’s strength lies in the difficulty of solving the ECDLP on classically accessible computers; however, Shor’s algorithm, a quantum algorithm, offers a potential pathway to break this encryption. Optimising a key calculation, modular inversion, within Shor’s algorithm has created a more efficient approach to breaking elliptic-curve cryptography, a widely used method for securing online transactions.

Refined register-sharing techniques and location-controlled arithmetic compactly store intermediate values during computation, thereby lowering the quantum computing power needed to crack a widely-used encryption method. The 256-bit prime-field curve now requires 1333 logical qubits, a sharp improvement over the 2124 qubits needed by a previous, similarly efficient implementation. Register-sharing minimises the number of qubits needed to hold data by reusing the same physical qubits for multiple logical registers throughout the computation. Location-controlled arithmetic further refines this by strategically placing data within the quantum registers to reduce the complexity of operations. Streamlining modular inversion, a computationally intensive part of Shor’s algorithm, is central to this optimisation. Modular inversion is required during point addition on the elliptic curve, and its efficiency directly impacts the overall performance of the algorithm.

Detailed analysis reveals the modular inversion circuit now utilises 3n + 4⌊log₂ n⌋ + O logical qubits, alongside 204n²log₂ n + O(n²) Toffoli gates, important components in quantum computation. Here, ‘n’ represents the bit length of the prime field. Toffoli gates are universal quantum gates, meaning any quantum computation can be constructed using only Toffoli gates. However, they are relatively expensive in terms of qubit count and circuit depth. The ‘O’ notation indicates that the number of qubits and gates grows polynomially with ‘n’, which is crucial for maintaining scalability. For ECC-521, a high-security standard, the qubit count is reduced to 2662, compared to 4258 in prior work. These figures, however, represent theoretical minimums and do not account for the substantial engineering challenges of building and maintaining stable, error-corrected quantum computers; the reduction in qubit requirements allows for a more detailed examination of the trade-offs between computational complexity and security levels in elliptic-curve cryptography. Error correction is vital because qubits are inherently fragile and prone to decoherence, which introduces errors into the computation.

Lower qubit counts enable nearer-term evaluation of cryptographic vulnerabilities

Quantum resources needed to break encryption are steadily being reduced, but a vital dependency on the extended Euclidean algorithm remains. The extended Euclidean algorithm (EEA) is a fundamental algorithm used to compute the greatest common divisor of two integers, and crucially, also provides the coefficients needed to express the GCD as a linear combination of the two integers. This is directly applicable to modular inversion. While the qubit counts for solving the Elliptic Curve Discrete Logarithm Problem are demonstrably lowered, the inherent complexity of implementing many Toffoli gates presents a significant practical obstacle. The sheer number of gates required, even with optimised qubit counts, demands significant advances in quantum hardware and control systems. Nevertheless, this refinement is still valuable work, directly addressing a key bottleneck in post-quantum cryptography development.

A more compact quantum algorithm for solving the Elliptic Curve Discrete Logarithm Problem, a vital calculation underpinning much of modern online security, is now available. Optimising the computationally intensive process of modular inversion, finding the inverse of a number within a specific range, has sharply reduced the number of qubits needed for this calculation. The refined method utilises techniques to efficiently store intermediate results, minimising the quantum resources required and paving the way for more realistic assessments of quantum cryptographic risks. The ability to more accurately estimate the quantum resources needed to break ECC is crucial for guiding the development of post-quantum cryptographic algorithms, which are designed to be resistant to attacks from both classical and quantum computers. This work contributes to a better understanding of the timeline for the potential obsolescence of current encryption standards and informs the transition to more secure alternatives.

Furthermore, the reduction in qubit requirements has implications for the development of quantum key distribution (QKD) systems. While QKD offers information-theoretic security, it often requires significant infrastructure and is susceptible to practical attacks. Understanding the computational cost of breaking ECC with quantum computers provides a benchmark against which the security and practicality of QKD systems can be evaluated. The research presented by Luo and colleagues represents a significant step towards quantifying the quantum threat to elliptic-curve cryptography and accelerating the development of robust post-quantum security solutions.

A new algorithm for solving the Elliptic Curve Discrete Logarithm Problem has been developed, reducing the number of logical qubits required from 2124 to 1333 for a 256-bit prime-field curve. This optimisation of the modular inversion operation is important because it allows for more accurate estimations of the quantum computing power needed to compromise current encryption methods. The research focuses on minimising computational resources, directly addressing a key challenge in post-quantum cryptography development. Authors suggest this work contributes to a better understanding of the potential timeline for the obsolescence of existing encryption standards.