With interest growing in developing universal quantum computers, examining post quantum algorithms and quantum cryptography that can replace modern cryptosystems is of vital importance to the security of our data in a world where a large scale, fault tolerant quantum computer exists.
Shor’s algorithm is the killer algorithm for cryptography. But having a quantum computer large enough to run this algorithm is still many years away. While some scientists argue that a quantum computer that can run Shor’s algorithm will never be possible to build, since it requires millions of qubits, others believe it’s inevitable and that we need to start preparing for this future.
There are two approaches. One is post-quantum cryptography, which is a new set of standard of classical cryptographic algorithms, and the other is quantum cryptography, which uses the properties of quantum mechanics to secure data. Both may have a place in the future of secure communication, but they work fundamentally differently.
Post-Quantum Cryptography
Post-quantum cryptography is classical cryptography that stands up to the attacks of a large quantum computer. It does not use any quantum properties. It doesn’t need any specialized hardware. It’s based on hard mathematical problems, just like the cryptography we have today. However, post-quantum cryptography avoids using integer factorization and discrete log problems to encrypt data. We already know that these problems are vulnerable to algorithms run on a quantum computer.
All of these post-quantum cryptography algorithms would not need any quantum hardware to encrypt data. They base the encryption on new mathematical problems that are not vulnerable to known quantum computing attacks. And of course, we have to make sure that while it stands up to (known) quantum computing attacks, it also holds against supercomputers.
The government and NIST has been worried about this possibility for a while. Even as early as 2013 there have been talks about moving away from the Suite B cryptography ciphers to something that can be quantum secure. In late 2016, NIST ran a competition for Post-Quantum Cryptography Standardization to find a suitable quantum-resistant public-key encryption algorithms.
What properties does the winning algorithm have to have?
- It must stand up to quantum computing attacks, as well as classical attacks.
- It must be fast. We don’t want to slow down communication. This encryption also needs to run on the web, smartphones, sensors, and a lot of other devices that have more limited compute power. A very slow algorithm will hamper communication.
Further details about the 26 candidate algorithms are published in the NIST Internal Report (NISTIR) 8240, Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process.
The 26 algorithms had very different approaches, but mostly lay in 3 families: lattice based, error correcting code based, and multivariate based cryptosystems. Lattice based systems have a large body of work behind them, starting back in 1996, and are considered one of the strongest candidates for post-quantum cryptographic standards.
Lattice-Based Cryptography
How does a lattice based cryptographic system work? This is lattice is a grid of points — you’re familiar with a two (x, y) or three dimensional grid with coordinates (x, y, z), but a grid can extend to many more dimensions. There are multiple potential problems that are hard to solve here as the number of dimensions increase: closest vector problem, bounded distance problem, and the covering radius problem. Lattice-based problems use hundreds or thousands of dimensions, and the goal is to find two lattice points that are close together. There are no efficient algorithms, classical or quantum, that can solve these in less than exponential time.
In 2020 and 2021, NIST will continue to review and test these post-quantum encryption standards, with the aim to have drafts of the recommended standards ready sometime between 2022–2024.
After that begins the process of upgrading computing systems worldwide to use these algorithms. In a world where the a large quantum computer exists, we’d need to upgrade almost everything being sent online, and that’s a LOT of change. This is expensive and costly, and will take a lot of time. Previously, it has taken 20 years to move encryption algorithms from mathematical problems to full implementation . This includes building the software, implementing the hardware layer if needed, and knowing how precisely hard it would be to break . And now we have to include research on the risk analysis of quantum computers that haven’t been built yet. Waiting to find a quantum-safe cryptosystem until the point when a quantum computer does approach the magnitude to break modern encryption would be entirely too late.
Quantum Cryptography
Quantum cryptography actually uses quantum mechanical principles as the basis of the security. Because these cryptography systems utilize the laws of physics instead of mathematical proofs, they are theoretically “unbreakable”. Of course, that doesn’t apply to side channel attacks.
Quantum key distribution uses these quantum mechanical properties to create a shared key and distribute it, while being certain* that a third party hasn’t eavesdropped. For quantum states, we have several properties of nature that gives quantum information an extra level of security. Quantum states collapse when they are measured. If an attacker tried to read out information in an entanglement based protocol, the quantum states would no longer be in a superposition. Additionally, the no-cloning theorem for quantum mechanics states that it’s impossible to copy a quantum state. So, an attacker couldn’t copy the quantum information being transmitted and do operations on their copy. If someone tries to eavesdrop, Alice and Bob will know.
Quantum cryptography is based on the laws of physics, and not our knowledge and understanding of mathematics and hard problems. This means that it will remain secure no matter how much more powerful both classic computers and quantum computers become.
Long distance quantum communication utilizes quantum properties. BB84 and E91 (entanglement-based) are the most famous communication protocols for quantum key exchange. These protocols generate a shared secure key.
BB84 Quantum Key Exchange Protocol
How would you do the BB84 protocol with a quantum system?
1. Alice prepares the bit string she wants to send and randomly selects a polarization basis. She can select either a horizontal/vertical polarization basis, where horizontal polarization is the 0 state, and vertical polarization is a 1. Or she can select a diagonal polarization basis, with the downward angled polarization basis being a 1 state, and a upward for the 0 state.2. Alice prepares a sequence of photons, sending the polarization
For example, Alice selects a bit string 01 and chooses a horizontal/vertical polarization. Then, the first photon she sends will be horizontally polarized, and the second will be vertically polarized.
3. Bob chooses whether to measure in the diagonal basis, or the horizontal/vertical basis. However, this means he loses information when he randomly chooses the wrong basis. If he chooses to measure a diagonal polarized photon with a horizontal and vertical detector, he gets a random answer and destroys the original polarization. If he chooses the correct basis, we will be sure that the readout result is the correct one. We detect and record the results for the entire bit string.
(Practically, this can be imagined by a polarizing filter, like in fancy sunglasses. It works by only letting through photons of the correct polarization. The lack of a photon means the polarizing filter blocked it from transmitting.)
4. Alice and Bob publicly compare their encoding basis. Using the chart above, Alice says that for photon 1, I used the horizontal basis. If Bob used the diagonal basis to read this out, the result he got was random. They discard that bit in the sequence. They keep only the bits when the basis they prepared the photon in and the measurement basis match. The shared key is the remaining sequence.
Eve can come in and listen in on the photons , if she wants to. She is in the same position as Bob to choose a random basis. However, as soon as she interferes with the photons, Eve introduces errors into the measurements. Alice and Bob can check for errors by choosing a subset of the key and publicly compare it. If there are more errors than expected (more than the expected losses in the channel or measurement), they discard the key.
Why don't we always use Quantum Cryptography?
So why don’t we just use quantum cryptography if it’s so secure? Quantum cryptography requires specialized equipment. For example, you need these photon detectors, beamsplitters, and other equipment to make it work. So we can’t put all of this into a small device like your phone.
Also, just because the encryption itself is fundamentally secure by the laws of physics, that doesn’t mean no attacks can ever occur. Even without quantum computers, intrusion does occur even on currently secure classical cryptographic algorithms. It’s not because some computer can break the encryption. Side channel attacks can occur. These happen because of weakness in the implementation of the cryptosystem instead of a weakness in the algorithm itself. Even though you can be sure that no one has directly intercepted the photons in the process of creating the key in the quantum key distribution protocols, side channel attacks do exist in quantum cryptography as well.
The hardware requirements make it very difficult to use quantum cryptography everywhere. So, we will still need a post-quantum cryptographic protocol to secure the majority of devices. Post-quantum cryptography and quantum cryptography are fundamentally different, but both have their place in strengthening security in a potential future where we have large quantum computers.