One of my favorite pictures depicting a quantum state is that of a coin spinning in mid-air. While spinning, it is neither heads nor tails but both and neither at the same time. Its output value will only be known when it is observed and leaves its quantum state (once the coin lands). Cryptographic security today reminds me of this quantum state. Like a spinning coin, cryptographic security threats must be viewed from all sides.
Quantum threats are only one side of the coin. Classical cryptographic, network, and implementation threats are all on the other side. This side doesn’t have the shiny gloss that the quantum side has, but many would argue it is the biased side of the coin. To get a better understanding of why this is so, we’ll look at the primary threat from a quantum computer: Shor’s algorithm.
In 1994, Peter Shor revealed his algorithm for computing periods (cycle lengths) using a quantum computer. This algorithm, implemented on a suitable quantum computer, would be able to factor or compute discrete logarithms—the classical foundations for public key cryptography. Public key cryptography is generally not used for encryption. Instead, it forms the infrastructure that makes large-scale encryption and cryptocurrency possible—digital key exchanges and signatures. Without these, large scale secure transmission of data would be impossible, and cryptocurrency would be easy to steal.
A quantum computer capable of attacking currently used cryptographic algorithms is known as a Cryptographically Relevant Quantum Computer (CRQC). Its cryptographic relevance depends on the algorithm and key size being attacked. Shor’s algorithm is the most feared and the primary security threat from quantum computing.
So how much progress has been made toward a CRQC and an actual attack using Shor’s algorithm? The best way to judge this is to chart the progress of size of problems solved—both factoring and discrete logarithms—using Shor’s algorithm on a quantum computer. Unfortunately, we don’t yet have a starting point. A “compiled” factoring implementation of Shor’s algorithm—one that used knowledge of the divisors to find the factors—worked on the integers 15 and 21 (in 2007, 2009, 2012, and 2019) but failed on 35 (2019). Discrete logarithm implementations haven’t been attempted. The quantum buzz is filled with talks of ever larger quantum computers, with occasional discussions of more stable quantum qubits. None of the buzz mentions the ability to run a general implementation of Shor’s algorithm on even the smallest values.
Back to the non-quantum side of the coin. Security threats are rising from reactions to the quantum computer threat. The new Shor-resistant algorithms being suggested have not been analyzed nearly as much as the classical algorithms and are far more complicated. During the National Institute of Standards and Technology (NIST)’s multi-round post-quantum cryptography (PQC) competition to find suitable replacement algorithms, critical weaknesses went undiscovered until the latter phases. For example:
- Rainbow, an algorithm that survived to the third round and based on the difficulty of solving a set of multivariate quadratic equations, was broken over the course of a weekend using a laptop
- Supersingular Isogeny Key Exchange/Diffie-Hellman (SIKE/SIDH) survived to the fourth round and was broken in an hour using a single laptop core
Even the surviving algorithms have been attacked, if not broken. A paper out of MOTZOV claimed to reduce security of many of the surviving algorithms to less than NIST standards, and there have since been improvements to this attack.
Another security concern is that the more complicated the algorithm, the higher the likelihood of implementation errors or techniques causing security issues. For example, properly coded algorithms can be vulnerable to power analysis or timing attacks. Mistakes can cause the key to be misused or leaked, and improper use of randomness could break the algorithms.
We must remember that in this constantly changing era, there is more than one side to security. The threats from both sides of the quantum coin should be properly evaluated—and constantly reevaluated—to keep data safe. Not recognizing this imperative puts everyone’s security at risk.
For more on the topic, explore our previous blog in this series.
