The security of modern digital communication relies on complex mathematical problems that are difficult for conventional computers to solve. Still, a new demonstration showcases the potential of quantum computers to break these safeguards. Tippeconnic from Arizona State University and colleagues successfully break a 5-bit elliptic curve cryptographic key, a fundamental component of many security systems, using a 133-qubit quantum computer. The team achieves this breakthrough by implementing a quantum algorithm that exploits the unique properties of quantum interference to reveal the secret key without directly encoding it within the computation, a significant step towards assessing the real-world threat posed by quantum computers to current encryption methods. This experiment, performed on an IBM quantum processor, demonstrates the ability to solve a cryptographic problem with a relatively small number of qubits and a surprisingly deep circuit, paving the way for further research into quantum-resistant cryptography.

Shor’s Algorithm Breaks 5-Bit Cryptographic Key.

The experiment successfully broke a 5-bit elliptic curve cryptographic key using a quantum attack based on Shor’s algorithm, executed on IBM’s 133-qubit IBM_Torino processor. A key innovation lies in the method’s ability to extract the secret key without directly encoding it into the quantum circuit, enhancing security against certain attacks. The approach focuses on interfering over a specific subgroup of the elliptic curve, allowing researchers to reveal key information through quantum measurement, which manifests as a distinct pattern in the quantum data. The methodology begins by mapping the points of the elliptic curve to integers, simplifying calculations while preserving the necessary mathematical relationships. 

Quantum registers then represent parameters of the equation, including the exponent and a point index, initialised in a superposition of states using carefully timed pulses. A specifically constructed quantum oracle performs a reversible transformation, linking these registers through a function related to the secret key, designed to avoid directly referencing the key itself. Following the oracle’s operation, the algorithm isolates a specific register, focusing on the phase relationship between registers rather than absolute values. A Quantum Fourier Transform is then applied, transforming the data into a frequency domain where the interference pattern becomes more apparent, revealing the modular phase relation and ultimately the secret key.

Classical post-processing analyses the measurement results, identifying the most likely key candidates based on the observed interference pattern. The success of the attack is demonstrated by the consistent appearance of the correct key within the top results, even in the presence of quantum noise. The experiment highlights the power of quantum interference to reveal hidden information and the potential for quantum computers to break commonly used cryptographic algorithms. Researchers emphasise that the observed interference pattern is a physically real phenomenon exploitable for cryptographic attacks.

Summary

Researchers successfully demonstrated a quantum attack on elliptic curve cryptography by breaking a 5-bit key using a modified Shor’s algorithm on IBM’s 133-qubit quantum processor. Despite the extreme complexity of the quantum circuit (over 67,000 layers deep), the system maintained sufficient quantum coherence to produce valid interference patterns. Classical post-processing of the quantum results correctly identified the secret key (k=7) within the top 100 candidate solutions.

The experiment validates that Shor’s algorithm remains effective even with very deep quantum circuits, suggesting potential scalability for attacking larger cryptographic keys. The approach used modular arithmetic techniques to encode the problem without directly referencing the secret key, and visualization of the results confirmed the expected quantum interference patterns.

Source：https://quantumzeitgeist.com/shors-algorithm-breaks-5-bit-elliptic-curve-key-on-133-qubit-quantum-computer/