Likely, as with many introductions and textbooks to quantum computing, you’ve been introduced to two Quantum Algorithms with a lot of promise. Grovers and Shor’s Algorithm promise a lot, with the former being able to search through data faster than classical algorithms and Shor’s famous for being able to factorize numbers also faster than classical approaches. We’ll outline some of the current cryptographic protocols and whether quantum provides a real threat to their security. Much of our modern world, whether banking, cryptocurrencies such as bitcoin or Ethereum, and the Internet rely on secure cryptography in order to function. Could Quantum Computing make these security protocols redundant?
Grover’s Algorithm
For the TLDR, the algorithm provides a massive speed-up through a variety of options. It can effectively search through unsorted entries with a speed that scales as the square root of N (the number of options). That means that say a message that could have originated from 100 options can be cracked with 10 checks. However, a traditional classical approach would be required around half of N (or 50) keys to be checked. So 10 versus 50 is a very different number, but in reality, the number of keys to be checked would be in the billions and this is where the difference becomes incredible. For example take the square root of a billion (under 32,000), which is the number of checks that Grover’s algorithm would need to make. Classically on average, we would need to check half a billion entries, which is thousands of times slower. The N over two classical checks come from averaging the best and worse cases. We could find the correct key at the start or the very end, meaning the average of 0 and N which is N/2.
Shor’s Algorithm
Shor is another algorithm that has security experts worried. TLDR, the algorithm has factor numbers in polynomial time. To learn more about how the algorithm works in reality, you can investigate the algorithm and its implementation in one of the Open Source Frameworks named Qiskit. The current classical best has subexponential run-time and is the General Number Field Sieve (GNFS), which was published in 1993. But loosely classical algorithms are exponential, which means that they blow up as the numbers to be factored become larger. Currently, Shor’s algorithm can be implemented in existing Quantum Computers such as those provided from IBM’s Q service, but there are a limited number of qubits available which limits the usefulness to factorizing very small insignificant numbers such as 15 that can be easily factorized by a human, let alone a computer. However the technique is proven, and with the promise of companies such as PsiQuantum looking to produce millions of qubits, the number of digits that can be factorized will increase.
Security experts are keen to check the progress of quantum computers against their ability to attack ever-larger numbers to factorise. Of course one can produce larger keys in a potential game of cat and mouse, where a Quantum Computer needs to find even larger factors.
Classical Security
Since school, you have probably seen some elementary ways to hide information, perhaps with a simple shift of characters such as a Ceaser cypher. Cryptography has come a long way since then and there are increasingly complex and more secure forms of communication. We will outline some of those schemes.
Symmetric and Asymmetric Key Distribution
Many of the schemes we outline you will have come across or used without knowing on the internet. You may have seen the “padlock” logo near the URL of this site meaning that SSL security is being used to simply read Quantum Zeitgeist!
Symmetric systems employ a key that can be used for both encryption and decryption. A popular scheme that is used is called AES (Advanced Encryption Standard). The protocol has been in development since around 2001 and is a well-used protocol being employed by many standards and can support up to 256-bit keys. AES is a subset of the Rijndael block cypher which was developed by Vincent Rijmen and Joan Daemen.
Asymmetric systems rely on using some facet of complex mathematics such as factoring. For example, encryption can be performed easily with a public key, but decryption requires the factors of that key – and this is not a trivial problem for a large enough key. Algorithms that are popular in this class are DSA and RSA. The latter is named after Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977. Many are familiar with the basics of Public Key Cyropgraphy, where can a public key is based around the multiplication of two large prime numbers. The two prime numbers remain the private key and in order to decrypt an encrypted message, those two factors must be known to decrypt a message.
Perhaps one of the more famous use cases of Quantum Computing comes from the Shor Algorithm as discussed which does better at factorising numbers than any known classical algorithm. Complexity theorists are still unsure whether a classical algorithm can be found that can do as well as Shor, but for now, Shor’s algorithm is likely to the greatest threat to technologies such as RSA.
Secure Hash Algorithms or SHA are another form of technology in common use such as SHA-256. The process relies on a one-way function that takes a message and turns it into a message digest. Cryptographic hash functions have numerous security applications, such as digital signatures, message authentication codes (MACs), and other forms of authentication. Normally very quick to perform and validate. Of course if one can scan through all the possible keys that are used to create the hash, then messages can be read. Grover’s algorithm could be one form of possible attack for SHA technology as one needs to quickly “try” out a number of possibilities.
Quantum Resistant Cryptography
Playing a game of every increasing standard is one way to keep abreast of the threat of Quantum Computing advancements. Currently, there is not an existing threat for Quantum Computers breaking cryptographic standards, but as the investment in Quantum Computing ramps up, the capacity and computational ability rises and could catch up with some existing standards. There is even a name for this push: Post-Quantum Cryptography.
Post-Quantum Cryptography
Systems are thought to be PQC if they are secure against a Quantum Computer, not today’s Quantum Computers with a small number of qubits but tomorrow’s where a scale-up in performance could be a threat. Many public-key algorithms remain insecure against the threat of Shor’s algorithm because, at their core, security relies on solving hard mathematical problems such as the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. Therefore researchers are keen to find new algorithms which are quantum-proof at their core. There are a multitude of possible contenders, and they come under six main types or approaches.
- Lattice-based cryptography
- Multivariate cryptography
- Hash-based cryptography
- Code-based cryptography
- Supersingular elliptic curve isogeny cryptography
- Symmetric key quantum resistance
Each of these is a field in itself and can be explored by the keen reader! All have some merits and drawbacks and just like there is not one singular standard today, it’s likely in the future that multiple technologies with co-existing standards. The easier one to understand is Symmetric key quantum resistance, which means using a sufficiently large symmetric key. Supersingular isogeny key exchange is thought with a key size of SIDH using 2688-bit public keys to be resistant against a 128-bit quantum computer. One aspect that will likely emerge with the maturation of Quantum Computers is a way to standardize their cryptographic power and thus one can benchmark classical standards against quantum standards.
One should also remember to think ahead. If secure information is not meant to be broken for a long time, then practitioners should think about the status-quo today because insecure methods might be easily breakable on historically encoded information (for example use 512 bit keys in place of 256). We know Information and data can stay around for a long-time. For that reason it can make sense to use the best-of-breed encryption available today.
Quantum computers could feasibly break RSA-2048 encryption in 8-hours but this would require somewhere around 20 million qubits. Google’s Craig Gidney et al demonstrated that a quantum system could beat 2,048-bit RSA encryption with 20 million qubits in a day. Of course, this is still rather a large number of qubits compared to current machines which are barely out of double-digit numbers of qubits. The method found a more efficient way to perform modular exponentiation (finding the remainder when a number is raised to a certain power and then divided by another number). If you think that millions of qubits remain a pipe-dream of researchers, think again. If you want to learn more see the original paper titled: “How To Factor 2048 Bit RSA Integers In 8 Hours Using 20 Million Noisy Qubits“.
Some developers are bullish on the number of qubits that can be reliably produced, with Jeremy O’Brien from PsiQuantum targeting a million qubits. He has put into production his roadmap for getting to a million qubits. IBM has also produced their roadmap (not quite at the million levels), but it does show how quickly a qubit scale-up could occur. By 2025 it is thought that a few thousand qubits could be readily available from the likes of IBM and PsiQuantum. But these developments are not done insolation, there are hundreds of start-ups emerging in Quantum Computing alongside large technology companies such as Google and Honeywell. So many are looking at ways to build and handle vast numbers of “noisy” qubits. The NISQ (Noisy Intermediate-Scale Quantum) devices (a term coined by John Preskil) is an era in which we learn to cope with the performance restrictions of imperfect qubits without propagating errors rendering them pointless. That said better-performing qubits are certainly a large area of development. So two things we can expect are better quality qubits and more of them. Both will contribute greatly to the usability of Quantum Computers in real-world applications. When is not known exactly. But radical underestimations in time could be catastrophic if important secrets or assets are at stake.
Crypto + Quantum
There is increasing interest in Quantum Secure schemes that can make it harder or impossible for Quantum algorithms to break. Already there are even some cryptocurrencies that are based around being Quantum secure or quantum-resistant technologies – one is named QRL for Quantum Resistant Ledger. QRL employs is aNIST-approvedpost-quantum secure digital signature scheme. Particularly as cryptocurrencies have taken hold especially among the public, there could be worries that coins or tokens are not fundamentally secure and therefore no surprise that schemes such as QRL with the token by the same name have emerged.