.jpg)
Abu Dhabi-UAE: 30 March 2021 – Diffie-Hellman revolutionized cryptography in 1976 with a practical method for a secure key exchange protocol. However, researchers are concerned that future quantum computers could compromise the protocol. Therefore, they are exploring a variety of post-quantum replacements.
One approach, called CSIDH, shows promise as a drop-in replacement for the cryptography used in Diffie-Hellman. CSIDH is an isogeny-based protocol that performs walks on a mathematical space known as a supersingular elliptic curve graph. To visualize this scenario, the elliptic curves depicted in Figure 1 are Alice’s and Bob’s public parameters and keys, while the exact path that connects those curves becomes their secret keys.
CSIDH's downside is that it is vulnerable to a powerful quantum technique called a Kuperberg attack. There is a broad debate on how complex CSIDH must be to resist such an attack. Estimates have varied dramatically on the size of the prime numbers used to generate secure keys, which significantly impacts computer processing speed.
Now researchers at the Technology Innovation Institute’s (TII) Cryptography Research Center, in collaboration with a researcher from the University of Oxford, have conducted an in-depth analysis of a refined CSIDH implementation. They also tested their setting against an optimized Kuperberg attack implementation. They found that CSIDH is not as secure as they initially hoped but is also not as vulnerable as other researchers suggested.
Prof. Francisco Rodríguez Henríquez, Technical Director of the Cryptography Research Centre at the Technology Innovation Institute (TII), said, “The quantum analysis we have here is arguably more refined than prior research, which is why we came up with different numbers.”
The researchers also clarified the importance of relatively neglected factors like quantum memory in post-quantum cryptography. For example, people have not explored the tradeoffs between maximum quantum bit-depth, bit-width, and memory. Rodríguez-Henríquez said, “This research also demonstrates the need to take into consideration quantum hardware architectures in assessing the security provided by post-quantum cryptography.”
A promising new key-exchange
Secure communication on the Internet requires securely exchanging keys between two parties. This reduces the risk that a hacker could listen in on the exchange of a secret key to hack a secure communication between them. The Diffie-Helman key exchange method has become the most popular approach because it could provide robust security with minimal computational overhead. But it is vulnerable to future attacks, which could take place when quantum computers become more practical. “CSIDH is a promising key exchange protocol whose security analysis must be examined carefully to address concerns about attacks launched by quantum computers,” Rodríguez-Henríquez said.
Researchers have been exploring a variety of potential replacements using various cryptographic techniques such as lattice-based, code-based, and isogeny-based cryptographic methods. They all bring different tradeoffs in terms of computational performance, communication overhead, and key size. In 2018, researchers devised CSIDH, which shows promise since it can work with short public and private keys and minimal communications overhead. However, it is not as computationally efficient as other approaches.
It can also function as a drop-in replacement for Diffie-Helman. Other methods need to add extra communications round trips to perform key encapsulation operations.
One significant aspect of CSIDH’s computational requirements is the size of the prime numbers required to offer reasonable security guarantees. The original authors speculated that a prime number of 512-bits seemed to provide sufficient security against known quantum attacks and that a 1,024-bit prime number would provide a buffer. However, other researchers speculated that at least 6,000-to-8,000-bit prime numbers would be required. This is a significant difference since the computational cost of the underlying arithmetic operations increases quadratically. A 512-bit prime would need about a tenth of a second on a competent computer, while an 8,000-bit prime could take tens of seconds. This is not practical for mass adoption.
Clarifying the problem
The TII researchers decided to clarify the problem by combining all best practices to improve CSIDH and make it the most performant implementation to date. Then they developed an elaborate software library to implement the fastest quantum algorithm for attacking this.
In terms of improving the algorithm, they combined various techniques discovered by earlier researchers, such as optimal strategies for computing isogenies, low exponents, and a new sub-quadratic Vélu formula for computing isogenies. Although prior research had quantified the impact of exponent strategy optimization and low exponents, no one had previously combined all these techniques together.
Rodríguez-Henríquez said, “The idea was to implement the fastest possible CSIDH we could come out with.”
Next, they refined the code to simulate the execution of the most efficient quantum Kuperberg attack possible, which they ran on a quantum simulator to test its performance. They found that a 4,000-bit prime number would be sufficient for achieving NIST level 1 of security, which is better than some more dire analysis but not quite as good as initially predicted. From a practical standpoint, this is the difference between about a third of a second and thirty seconds to run the algorithm on a standard computer.
Rodríguez-Henríquez said, “People have known about Kuperberg, but we dove more deeply into how to code it into a quantum algorithm.”
The importance of [quantum] memory
But the researchers also stumbled across the significance of another factor that has not been widely explored in quantum security – quantum memory. “Some of these attacks would need a quantum memory that would occupy all of the New York City area,” Rodríguez-Henríquez said.
This shines a light on an important technical aspect of quantum computers that has not been widely considered in security research. Most popular descriptions of quantum computers today characterize the need to have multiple quantum gates that manipulate the quantum information in the qubits. The number of quantum gates characterizes the width of the quantum circuit. The US National Institute of Standards and Technology (NIST) generally uses another factor, MAXDEPTH, which reflects how much circuit depth a quantum computer would need to keep a calculation running to compromise a cryptographic algorithm. This is important since quantum calculations tend to degrade quickly.
But to date, precious little research has gone into exploring the quantum memory requirements, which are sometimes more of a factor than width or depth. Rodríguez-Henríquez believes that future research will need to consider limitations around width, depth, memory, and how cryptographic oracles are implemented to further refine post-quantum security.
Rodríguez-Henríquez said, “We are concerned that this is not captured in NIST security considerations. We must agree on how these attacks will be realized as a community. This is a hard task because we still do not have quantum computers, and we are still imagining how they will look. The effectiveness of these attacks will depend on the architecture and memory handling that these quantum computers will have.”
He is also hopeful that this research can inspire other researchers to push CSIDH research further forward. TII’s researchers have combined all the best protocols into one state-of-the-art CSIDH algorithm and published it for others to explore. “This is a source where you can find all the tricks put together,” Rodríguez-Henríquez said.
Caption: Creating an isogeny-based shared secret between the users Alice and Bob. The left-hand side image shows Alice and Bob’s public/secret keys consisting of a publicly known elliptic curve (public key) and a secret path to arrive at that elliptic curve (secret key). The right-hand side image shows Alice and Bob agreeing on a specific elliptic curve (their shared secret) after running a CSIDH key exchange protocol (Credit of this figure: Krijn Reijnders).
