By Dr. Vladimir Soukharev, Cryptographer and Head of Post-Quantum Solutions at InfoSec Global
As the world moves rapidly closer to the extraordinary, game changing impact of large-scale quantum computers, cryptographers around the world are racing to find a solution to ensure its benefits are realized and its risks are minimized. The clock is ticking.
According to many physicists and engineers, quantum technology developments could usher in a new era of quantum computational power in just 10 years.
For those who labor in fields defined by optimization problems—such as artificial intelligence, genetic research and engineering, for instance—quantum computers will unlock extraordinary breakthroughs, with an efficiency that will be mind-blowing and lifesaving. However, these incredible benefits will come with a serious risk—because whenever physicists, engineers and cryptographers are able to utilize quantum computers, so will state-sponsored threat actors and cybercriminals. When armed with quantum technology, they will essentially have a skeleton key to break security protocols that are difficult or impossible for current computers to crack.
If we don’t discover and deploy a cryptographic solution—and fast—it will be as if the digital security, we depend on daily is virtually non-existent. That cryptographic dependence spans from the simplest Amazon purchase or Venmo payment to the highest levels of global security and critical infrastructure protection.
Quantum computers can efficiently—in polynomial time—factor large integers and solve the discrete logarithm problem (“given g and h = gˣ in group G, find x”). Since, these two mathematical problems are considered difficult for classical computers to solve, they are the cornerstones for most public-key cryptography used today. Even the most powerful modern computers would have to run for, literally, years to crack this encryption. A quantum computer, though, could crack it in mere minutes at most. As classical public-key cryptosystems will not be able to protect information from quantum computers, cryptographers have been researching possible approaches to mitigate the global risks of threat actors armed with such incredible computing power.
One option would be to design a theoretical quantum-based cryptosystem. This would serve as a solution, but it requires replacement of the hardware and software which makes this approach extremely inefficient and expensive to implement. Even if we could, though, what would happen to classical computers used for cryptography when large-scale quantum computers materialize? Would we just throw them away, even though as the transition to quantum would not happen overnight?
For an indefinite period of time following the arrival of quantum computers, we will need a system that allows conventional and quantum computers to coexist. This is why developing quantum-safe cryptography for classical computers is vital, and why post-quantum cryptography must develop systems that empower classical computers with quantum resistance.
The day-to-day reality of a world driven by a hybrid mix of quantum and conventional computers is what makes utilizing elliptic curves for quantum-resistant cryptography so promising. One highly practical and efficient quantum-resistant cryptographic solution has been developed, in close collaboration with InfoSec Global’s cryptographers. Based on supersingular elliptic curves, it is called Supersingular Isogeny Key Encapsulation (SIKE).
Over time, elliptic curves have proven themselves to be highly reliable mathematical tools and cryptographic primitives, being not only an object of profound theoretical interest but also a base for sound practical applications. Elliptic Curve Cryptography (ECC) has been progressively studied by mathematicians, computer scientists and engineers, with many cryptographic schemes based on elliptic curves already standardized.
Today, after meticulous theory and practice, the cryptographic community recognizes the advantages of using elliptic curves. Unfortunately, traditional elliptic curve-based schemes are based on discrete logarithm problems, which are no problem for quantum computers at all.
Does that mean that quantum computing will bring an end to elliptic curve-based cryptosystems? Thankfully, no—because ECC can be extended to obtain quantum-resistant schemes by using elliptic curve isogenies.
A bit of theory: an isogeny between two elliptic curve groups E and E' is a group homomorphism, that is, a function that preserves structural properties of these groups. It is easy to check if two elliptic curves E and E' over the same finite field are isogenous: it happens if and only if those curves have the same size. Nevertheless, finding the isogeny that would map between them is a difficult problem for any computer.
Elliptic curves can be ordinary, which are widely used today for purposes of discrete logarithms, or supersingular. The main difference between them lies in their endomorphism ring End(E), an algebraic structure which defines the way isogenies work with each other—it is commutative for ordinary curves and non-commutative for supersingular curves. This makes isogenies between supersingular elliptic curves the best candidates for the post-quantum cryptography protection. Absence of commutativity in their underlying structure provides us with quantum-resistance, since quantum computers are not able to tackle such types of problems.
One of the first isogeny-based cryptographic schemes designed for key-agreement protocols is Supersingular Isogeny Diffie-Hellman (SIDH).The “Diffie-Hellman” pays tribute to the Diffie-Hellman key exchange scheme, which its logic closely resembles. The technical computations inside SIDH are, of course, different, but on the visible side, the workflow is very similar. Such similar logical structure makes SIDH one of the most promising replacements for today’s IT infrastructure.
Basically, a public-key cryptographic key agreement scheme works as follows: each user generates their secret private key, then computes their public key using global public parameters and their private key. Then, both users exchange their public keys. Finally, each user combines their own private key and the other user’s public key to compute the common private key. Both users should arrive at the same common private key, which they can later use for secure communication via symmetric ciphers.
In a classical elliptic curve-based key agreement scheme, the private key is a scalar; it is used to multiply the global generator point on the elliptic curve, resulting in a public key, which is also a point on the same elliptic curve. For an isogeny-based key agreement scheme, the private key is an isogeny; it can be represented by a secret point on the initial elliptic curve; this point, in its turn, can be represented by a scalar, since the combination of that scalar and the public bases points yields that secret elliptic curve point. The public key consists of an elliptic curve, which is the image curve under the secret isogeny, and two points, which are images of the other party’s bases points under that secret isogeny. Simply put, the public key is an elliptic curve and two elliptic curve points on that curve. To dig more deeply into mathematics content of the isogeny-based key agreement scheme, watch this presentation.
SIKE is a key encapsulation mechanism (KEM), based on SIDH. The underlying primitives and techniques are the same. SIKE is derived by turning SIDH into a public-key encryption scheme and then transforming it into a KEM. The main difference and advantage of SIKE, compared to SIDH, is that the resulting shared key is based not only on the users’ keys, but also on the random value generated by the initiator of the protocol. This approach provides better security. In fact, it provides indistinguishability under chosen ciphertext attack (IND-CCA)security, which is one of the strongest provable security properties for such schemes.
What are the benefits of elliptic curve isogeny-based schemes, compared to other post-quantum candidates? First, they are the most plausible drop-in replacement for today’s IT infrastructure, as elliptic curves are already familiar to information security experts, making this solution easier to understand and implement. Also, these schemes have the shortest key sizes, meaning the smallest computing overhead, and have easily scalable parameters for the desired level of security. Importantly, the elliptic curve isogeny-based schemes can provide both ephemeral and static key exchange schemes, while all other post-quantum candidates provide only ephemeral key exchange ones.
Quantum computers are coming, sooner than many may have realized. Whether their arrival manifests the innovations and possibilities that have remained beyond our grasp or whether they make chilling global risks and vulnerabilities a daily reality. This will depend largely on how well we design and deploy our digital fortifications now. With more study and testing, SIKE could prove to be the key to foiling quantum-wielding adversaries with security that is practical, efficient and strong enough to withstand the extraordinary computational power that will be here before we know it.
.jpg)
.jpg)