Quantum vs. Classical: Where Quantum Computing meets security with Tobias Köppl

In the fifth episode of the PQ-REACT Conversations with our Experts, we discuss and explore the differences between High-Performance Computing and Quantum Computing, the “Eclipse Qrisp” programming language and more with Tobias Köppl from the Fraunhofer Institute.

What is High-Performance Computing, and how does it differ from Quantum Computing?

High-Performance Computing (HPC) is a subfield of computer science concerned with the design of efficient algorithms and software for supercomputers, such as the newly installed computer “Jupiter” in Jülich, which has a computing power of more than one trillion operations per second. Supercomputers use principles from classical electrical engineering, e.g. semiconductor techniques. In contrast, Quantum Computers (QCs) are based on phenomena studied in Quantum Mechanics, such as superconductivity at very low temperatures. In HPC, the basic information unit is stored in a classical bit, whereas in QC, qubits are used. A classical bit attains either the state 0 or 1. On the other hand, a qubit has a quantum-mechanical state such that both states can be attained with a certain probability. This phenomenon is known as superposition between 0 and 1. Moreover, several qubits can be coupled, resulting in a quantum-mechanical system that can represent 2^n different bit strings using n qubits. This second property is known as entanglement. QC exploits both superposition and entanglement to design algorithms that are more efficient than algorithms for classical computing, such as HPC.

Can you explain in simple terms the process of benchmarking Post-Quantum Cryptography? What are the main challenges and expected results?

Post-Quantum Cryptography (PQC) concerns the design and analysis of cryptosystems that are resilient against attackers using quantum algorithms. The need to develop new protection mechanisms for sensitive data was prompted by Shor’s algorithm, published in 1994. It can be used to efficiently decompose an integer into a product of prime numbers. This is of high importance, since it enables an attacker to break the wide spread RSA cryptosystem. As a result, existing cryptosystems have been reviewed, and further cryptosystems have been designed. A challenge in PQC is to equip cryptosystems with keys that cannot be determined by existing or future quantum algorithms. On the other hand, analysing quantum attackers is a complex matter, since nowadays quantum hardware can only attack low-complexity cryptosystems. This is due to a high error rate and a low number of qubits. The current phase of development is known as the NISQ era (Noisy Intermediate-Scale Quantum). Therefore, many researchers try to estimate the quantum resources (e.g., the number of qubits) required by a quantum attacker to break existing cryptosystems.

“Post-Quantum Cryptography (PQC) concerns the design and analysis of cryptosystems that are resilient against attackers using quantum algorithms.”

What is Eclipse Qrisp, and how will it be used in the PQ-REACT project?

Eclipse Qrisp is a Python-based programming language for quantum algorithms, developed by Fraunhofer FOKUS. Unlike many other programming tools, a user does not have to operate on single qubits or gates. Instead, Quantum variables and other tools can be used to implement quantum algorithms. For PQ-REACT, we use Qrisp to implement quantum algorithms that can be used to attack cryptosystems. Using real hardware and simulators, we evaluate their performance using small test cases. Furthermore, Qrisp can be used to estimate the resources required to break cryptosystems of relevant size.

“For PQ-REACT, we use Qrisp to implement quantum algorithms that can be used to attack cryptosystems.”

Moving on to the security aspects. How difficult is it to solve Learning With Errors problems, and why is this important for the security of post-quantum cryptography?

First, one must understand that many cryptosystems rely on a mathematical problem that must be solved to break them. In RSA, the mathematical problem is to factorise a given integer into prime numbers. Recently, the National Institute of Standards and Technology (NIST) has suggested, in various reports, cryptosystems that it considers resilient to quantum attackers. One of these cryptosystems is based on the “Learning with errors problem” given by a linear system of equations with a noisy right-hand side over a modular ring. Since the right-hand side is sampled from a probability distribution, LWE problems are hard to solve. This is because the right-hand side must be assigned to the data to be recovered. Another reason why LWE is hard to solve is that the number of possible solutions scales exponentially with the size of the linear system of equations. In terms of PQ-REACT, we investigate the extent to which existing quantum attackers can solve LWE problems, and the resources required for relevant problem sizes.

“First, one must understand that many cryptosystems rely on a mathematical problem that must be solved to break them.”

Researchers warn that quantum computers capable of breaking Bitcoin’s encryption could emerge by 2027, posing a significant threat to the cryptocurrency’s security. Is it possible? And if so, how can we be prepared for the security challenges of the quantum era?

From my point of view, it will take much more than 2 years to create quantum hardware capable of breaking Bitcoin’s encryption. To break this encryption, a quite complex hash function must be inverted. To be prepared for security challenges arising in the quantum era, further testing of existing and newly developed quantum attackers is required. Cryptosystems such as RSA might have to be replaced. Moreover, one should think about cryptosystems that are themselves based on quantum algorithms.

Listen to the full discussion here.