The Arrival of Quantum Computing Could Unravel Existing Cryptographic Systems
By Dr. Vladimir Soukharev, Cryptographer and Head of Post-Quantum at InfoSec Global
It is a race like no other: A grueling, long-distance marathon to solve one of the most critical and difficult mathematical challenges that the world has eve known, and the stakes could not be higher.
As quantum computing leaps from the realms of science fiction into the approaching reality of a not-so-distant future, whether its arrival unlocks extraordinary leaps forward in innovation or unleashes widespread chaos will likely be determined by the small global community of cryptographers. Because as quantum computing offers to unlock the computational impossibilities that have slowed and stymied breakthroughs, particularly in the fields of artificial intelligence and machine learning, it’s arrival also comes with tremendous risk if we are not prepared.
There is a dark underside to the almost incomprehensible speed and power of quantum computing—an exponential acceleration that can only be roughly estimated with today’s technology. But in a world of consumer-facing pop-digital understanding, where the ability to watch your ride home gets closer on an app is heralded as game-changing, few can understand the impending impact of quantum computers. Or its potential to usher in not disruption, but dystopia.
Because what quantum computing will do—besides make the currently impossible eminently achievable—is obliterate the already-strained systems of public-key cryptography that allow today’s digitally connected networks to function securely. In a post-quantum world, nothing is safe: public-key protocols that safeguard every online transaction—shielding everything from small purchases to large financial transactions; personal conversations to security secrets; consumer data to critical infrastructure—will be useless.
InfoSec Global Answers the Call for Post-Quantum Crypto Solutions
As the arrival of large-scale quantum computers is estimated as soon as 10years—the National Institute of Standards and Technology (NIST), a non-regulatory agency of the Department of Commerce (USA), has issued a request for public-key post-quantum cryptographic algorithms. It is a call for solutions to the looming threat of quantum computer’s potential to shatter even today’s toughest encryption codes.
InfoSec Global (ISG), together with partners from academia and industry, has answered that call with two viable solutions. It is an impressive contribution even for much larger organizations and an achievement that positions InfoSec Global at the cutting-edge forefront of what can be described without exaggeration as one of the internet’s most pressing crises.
“Quantum computers are much more powerful than anything we have today,” explains Tomislav Nad, Chief Security Architect of ISG and part of the team that developed one of the solutions submitted to NIST. “By utilizing quantum mechanical phenomena, you are able to solve certain classes of complex problems much more efficiently than classical computers. Today, if you have a crypto algorithm that uses a specific key to sign a message, you would break it by trying all possible keys. For some cryptosystems, more efficient approaches exist, but they are still of exponential difficulty for classical computers. By making the key big enough, we can make that process so difficult enough and time-consuming that it is difficult to achieve in a traditional setting.”
With quantum computing, finding the right key of all possible keys can be done in a significantly more efficient way. For public-key cryptosystems , finding the right key translates to a difficult mathematical problem. A problem which quantum computers can solve in a much lower category of time complexity compared to a classical computer. Quantum computers do have many positive benefits, especially in solving optimization problems used in many fields like finance, economics, pharmaceutics, and machine learning.
Key agreement protocols and signature schemes, used every time an http-secure website is opened, will be rendered obsolete. That means the entire internet will have zero security. Almost everything online relies on these algorithms. If we are not prepared with a post-quantum replacement—and if that replacement has not been implemented before the arrival of quantum computers—the results could be devastating.
Introducting Two Post-Quantum Crypto Solutions: SPHINCS+ and SIKE
To stave off that potential disaster, ISG teamed up with most recognized experts in the field of hash function design and hash-based signature schemes, to devise an solution called SPHINCS+.
SPHINCS+ is a public key signature scheme based on hash functions. Contrary, to classical public-key schemes, quantum computers do not break hash functions. Hash functions are well known and extensively studied constructions in cryptography. Every signature scheme uses a cryptographic hash function but hash-based signatures use nothing else. SPHINCS+ builds on SPHINCS by introducing several improvements regarding security and efficiency. SPHINCS+ is a practical and stateless hash-based signature scheme, making it probably the most attractive answer to quantum-safe signature schemes.
“SPHINCS+ is probably the submission with the most reliable security estimates. This is due to the fact that security is only based on hardness assumptions about cryptographic hash functions. At the same time, SPHINCS+ achieves reasonable sizes and speeds allowing for different trade-offs to suit everyone's needs." Andreas Hülsing ,Eindhoven University of Technology (NL)
The second submission, named SIKE (Supersingular Isogeny Key Encapsulation), developed by a team consisting of ISG’s cryptographers, Dr. David Jao, University of Waterloo, Microsoft Research, Amazon, and other academia and industry partners, approaches the challenge via the younger discipline of isogeny-based cryptography. The solution uses elliptic curves but takes a conceptually different approach resulting in quantum-resistant cryptographic primitives.
Since the solution uses elliptic curves, the basic arithmetic is the same, which allows us to reuse a lot of the existing code. But rather than using the ordinary curves that we find in current cryptography, we use supersingular curves. Quantum computers are very good with commutative structures (a-times-b equals b-times-a) and our isogeny-based approach is non-commutative, so quantum computers are powerless against it.
“The underlying hard problem for isogeny-based cryptography is: given two isogenous supersingular elliptic curves, find an isogeny between them. Currently no quantum algorithm is known for solving this problem in less than exponential time. The main reason why this problem seems intractable for quantum computers is that the endomorphism ring for the supersingular elliptic curve is non-commutative, which shields the problem against attacks.” Dr. David Jao (University of Waterloo and evolutionQ).
The result is a solution that looks very similar to the Diffie-Hellman algorithm that exchanges public keys over an open channel and establishes a common secret key. This allows for greater familiarity when it is time to implement the new encryption, and a high level of efficiency with the ability to reuse existing arithmetic and the smallest post-quantum key sizes currently proposed.
I is the most plausible transition, so we can implement this post-quantum encryption, and the cryptographers managing the process will understand what they are doing and why it works. In addition, it is highly scalable, which will be very important to protecting people that fall between levels of security. That means more flexibility, in addition to being the smoothest drop-in solution for today’s digital infrastructures. You can just remove the current public-key algorithm and put this one in.
As imperative as post-quantum cryptography is, the need for improved algorithms is not just a necessity for a rapidly approaching future. This is not just a coming-soon decision, or even a today decision. This is a yesterday decision. The urgency of post-quantum is hopefully raising awareness of how critical it is to improve encryption is now. People need to understand that we need these solutions today.
