Testing Cryptographic Codes Using Adiabatic Quantum Methods Experimentally
Have you ever wondered how your bank protects your personal and financial information from cybercriminals? They use end-to-end (in this case bank-to-customer) cryptographic techniques, ensuring privacy and confidentiality, keeping your data from being stolen or altered
In the digital era, when your smart phone is your shopping device, credit card, personal and workplace messaging, cryptography is an essential cybersecurity tool. But how does cryptography work? A widely employed method uses a public key and a private key. Within online banking example, your pin or password is your private key, and the bank uses a public key to protect the data you send to or receive from the bank.
The public key travels through the internet freely because it is designed to be extremely hard to break; and, as we will see next, the strength—and the beauty—of a widely used public key design lies in a simple mathematical trick: the multiplication of two large prime numbers.
The multiplication of two large prime numbers results in huge numbers, called semi prime, usually composed of hundreds or thousands of digits. Deciphering a key based on semiprime numbers is a nightmare since to break such codes you need to find the original prime numbers used to create the key. Factoring semiprimes is computationally extremely inefficient for classical computers, and that is why this method invented by Ron Rivest, Adi Shamir and Leonard Adleman (RSA) in the 70s is still so widely used. Today it can take 300trillion years to break a RSA-2048 bit key! The reason is that, classically, the solving time scales exponentially with the number of bits representing the semiprime.
Now, you probably have heard that quantum computers will be able to crack RSA cryptographic codes using quantum algorithms, such as Shor’s, and steal your data from your bank. From the algorithmic point of view, Shor’s is expected to solve the factorization problem in polynomial computational time. This means that Shor’s algorithm once implemented on a real, ideal quantum computer could crack the same RSA-2048-bitcode in just 10 seconds!
But let’s not lose focus, there is no reason to panic. The truth is that quantum devices are not yet powerful enough to break real-world codes, and they won’t be anytime soon. However, testing quantum algorithms with the potential to break RSA keys is essential to prove that an encryption is quantum safe, helping investigate how obsolete classical methods are.
Novel quantum algorithm to test cryptographic codes
Researchers from the Korea Advanced Institute of Science and Technology (KAIST), in collaboration with PASQAL, have developed a novel adiabatic quantum technique to factorize semiprime numbers using neutral atom quantum computing. In adiabatic quantum computing the system evolves gradually towards an answer.
The team successfully factorized small numbers on a KAIST neutral atom quantum device, showing their method’s potential to challenge modern cryptography. The team shared their results recently in the arxiv. In this new paper professor Jaewook Ahn from KAIST, Loïc Henrietfrom PASQAL, and collaborators discuss how their approach would behave for big semiprime numbers and the number of atoms they would need. They estimate that their approach, in ideal conditions, would scale polynomially in time steps and memory space.
“We needed to estimate the computational resources to find out how the method would scale, because for us an exponential behavior with the computational resources is not acceptable,” said professor Jaewook Ahn from KAIST. “We found that the number of resources would be large, but that, in principle, solving the factorization problem with our method would scale at least polynomially.”
Manipulating atoms to factorize numbers
The proposed method consists in translating the factorization problem into a graph-based problem. A graph has nodes, representing entities, and edges connecting the nodes, representing the relationship between the entities. To factorize a semiprime, n = p x q, candidates to original primes (p and q) are translated into their binary versions and with them construct graphs representing the binary numbers with nodes, and mathematical operations between them with the edges. To find the solution, the algorithm searches for the largest set of nodes that are not connected by edges, called the Maximum Independent Set (MIS), by gradually bringing the system to the energy ground state.
Among the candidates for adiabatic quantum processing, neutral atoms architectures offer exceptional adaptability for tackling a wide variety of graph-based problems. In these devices, atoms are manipulated using arrays of highly focused lasers to create 2D or 3D arbitrary arrays and a second laser to manipulate the atoms’ electronic states to create qubits. An interesting choice for two qubit states is comprised by a ground state and a Rydberg state, which is a very high electronic energy state. An atom in a Rydberg state physically grows influencing adjacent atoms preventing them from reaching the Rydberg state when they are closer than a certain distance, called the Rydberg blockade distance. The experiment conducted at KAIST leverage from these two main properties of neutral atom quantum technologies to represent graphs, where atoms represent the nodes of the graph and two atoms that are closer than their blockade distance are considered connected by an edge.
Creating 3D arrays with neutral atoms to solve graph-based problems
To solve the factorization problem, the team used a hybrid approach where a classical part designs the graph representing the problem and the neutral atoms computer is used to find the solution. With this method, the team successfully factorized the numbers 6 = 2 x 3, 15 = 5x 3, and 35 = 5 x 7 experimentally.
While to factorize the number 6 = 2 x 3, 2Datom arrays were sufficient, the graphs to factorize higher numbers are not always implementable in 2D. Therefore, to address them, the team needed to create3D atomic arrays with the KAIST quantum computer. Being able to create 3D atom arrays in the quantum hardware is crucial, not only for breaking cryptographic codes, but for many other real-world use cases, such as molecular structural-based drug design or air traffic analysis. The team successfully created the 3D qubits arrays to represent the graph problem and solve the associated factorization problem for number 15 = 5 x 3.
“Arranging atoms in three dimensions is not straight forward, it is not yet a technique, it is still an art. However, if you calculate how 2D scale with the number of resources, you will find much bigger numbers than for 3D. To make the atoms connect in the graph efficiently you need to go 3D,” professor Jaewook Ahn explained.
Within the emergence of neutral atoms technologies, the team at KAIST is one of the pioneers at creating three dimensional arrays of neutral atoms. With this new result, KAIST scientists are positioning as one of the few achieving 3D arrays of qubits to perform calculations effectively.
“In 3D we were able to lift some constraints and have more freedom in how to layout the atoms to produce the edges of the graph,” said Louis Vignoli, quantum developer at PASQAL, involved in the work. “However, experimentally 3D is harder to realize than 2D, but the Korean team was able to achieve it.”
What lies ahead in braking cryptographic with quantum
Although quantum computing is still years away to be able to break real-world cryptographic codes, this experimental result represents a big step in the quest for quantum algorithms holding the promise to help test the obsolescence of classical methods.
“Advancing with quantum in fundamental research in this direction is just an evolution in the quest to strength our whole security system. Already, the NIST (American Institute of Standards) is in the process of publishing its first standards for post-quantum cryptography precisely for this reason, because they know that this will happen [quantum being able to break these traditional codes] at some point. Us pushing towards this, is actually a traction force for people to move towards more security,” Louis Vignoli remarked.
“Previously, people regarded adiabatic quantum computing as used for specific purposes, but that is not the situation anymore. We are showing that we can program a general problem, such as factorization, by using proper-design graphs. We are pushing the limit of atom-based adiabatic computing using graphs to become universal computing. We will need more hardware deployment to be able to continue working in this field and try to factorize bigger numbers. The classical part of our hybrid algorithm is near optimal; however, the experimental quantum part has a lot of room for improvement. But this time we were successful, and this is just the beginning,” professor Jaewook Ahn concluded.
References
Park, K. Jeong, S., Kim, M., Kim, K., Byun,A., Vignoli, L., Henry, L-P., Henriet, L., Ahn, J. (December 2023). A Rydberg-atom approach to the integer factorization problem. Available in the arXiv: https://arxiv.org/abs/2312.08703
Would you like to learn more about these techniques on a neutral atom quantum computer? Start your quantum journey using our platforms and algorithms with Quantum Discovery.
Do you have any questions about our technology and applications? Don’t hesitate to reach out to us!