Recently, I gave a little talk at ISE about quantum computing; I tried to delve into the subject a little deeper than what you might receive from a popular magazine or web news outlet. Following my talk, the ISE team jumped into a deeper discussion, questioning if an algorithm that is deemed "quantum resistant" is really safe. After all, with some celebrated exceptions (think one-time pad), no cryptographic algorithm can be totally resistant to cryptanalysis—even in the conventional sense.
Shor's algorithm1 is one example of a quantum algorithm (i.e., an algorithm that exploits the performance of distinctly quantum circuits). It factors integers and finds discrete logarithms exponentially faster than the best conventional algorithms; that is, in polynomial time versus exponential time. This is bad news for some asymmetric key cryptographic ciphers, viz, RSA, and Diffie- Hellman (DH). However, ciphers based in elliptic curve math, such as the elliptic curve DH analog, are "immune" to breaking by Shor's algorithm, which means that they cannot be broken by factoring. Those who market ECC (elliptic curve cryptography) products like to say that they are "quantum resistant," and there are many other asymmetric key cryptosystems that are also immune to Shor's algorithm because factoring won't break them. These cryptosystems are also called quantum resistant (see reference 2). But, the question is, are these algorithms resistant to all quantum algorithms (now and in the future)?
Currently, no practical quantum computers are publicly available. However, many quantum algorithms have been published that solve many types of problems—not just cryptographic breaks. There is no reason to believe that cryptographic methods resistant to quantum computing attacks will remain inherently resistant. Furthermore, many of these so-called post-quantum cryptography3 algorithms have not been scrutinized to the point that RSA, DH, and ECC have. Anyone with knowledge of cryptography knows that no confidence can be assigned to an algorithm unless it has been intensively studied and vetted.
The news is not all bad; there are efforts afoot to find the next crypto-algorithm that will stand up against quantum computers should they become reality. The government, specifically NIST4 (and no doubt the NSA), and many academic institutions are studying algorithms that show promise of being quantum resistant. The first task is to make sure that the problem that these algorithms are based upon is hard to solve on conventional computers. Then they must be hard to solve on quantum computers (i.e., no known quantum algorithms exist that efficiently solve that problem). This takes significant research and time, so the fruits of these programs are still in the distant future. And, let's hope the rise of quantum computers is even further out.
While vendors and their customers like to describe their products as quantum resistant, it is probably more accurate to state that these methods are instead "not currently quantum breakable". As they say, caveat emptor.
References
- Shor's algorithm
- quantum resistant
- Post quantum cryptography
- NSA preps quantum resistant algorithms to head off crypto apocolypse
Additional Information
Readers interested in further details about this topic can reach us at: contact@www.ise.io