Why don’t post-quantum encryption standards exist yet?

post-quantum encryption standards d-wave
The controversial adiabatic D-wave computer, which has many qubits, but isn’t yet showing proper entanglement or speedup when compared to optimized classical calculations (publicly). https://www.flickr.com/photos/jurvetson/

TL;DR — With increased funding, quantum computing is moving into a “Manhattan Project” era, where the timeline to a small, useable quantum computer could be drastically reduced. When the first quantum computers are ready to go in the next 5–10 years, we need to have security protocols in place. Post-quantum cryptography solutions do currently exist. We still have time, but we need to take the threat seriously.

Establishing global post-quantum security standards

Small, useable quantum computers are less than a decade away. That timeline doesn’t even account for recent increases in funding for several areas of quantum computing research — logical qubit development, quantum error correction, quantum security, and additional post-quantum cryptography research have been announced this year in the USA and Europe. There is currently no standard of encryption against a quantum computing attack. But there are known quantum-safe algorithms. We might be late on the traditional timeline for establishing quantum security standards, but that just means we need to start now.

We perhaps can trust that scientists and companies building the first quantum computers have no interest in getting into your bank account. But even if export of the technology is limited, do you really want to remain under the pre-quantum cryptography world, where the government or certain players can break your cryptography, but you just try and trust that they won’t? (History tells us, that if they can, they will). Do you want foreign governments in control of your data?

Once quantum computers are being used by labs and academics, and companies think they have plenty of time to protect against breaches, how do we prevent malicious use of quantum computers? With the internet of things and the increased breaches, is it safe to assume that the academics and researchers who have control of these systems remain in control? Academic institutions aren’t the most secure places, and with cyberattacks becoming more common, the idea that a hacker could take control of the first quantum computer for malicious use doesn’t really seem too crazy. So protecting against quantum computing attacks is priority.

Post-quantum cryptography techniques are already practical

A lot of applications use elliptic curve cryptography as the basis for encryption or key exchange, often suggested as an improvement to security over RSA. Interestingly enough, it seems that elliptic curve cryptography can be broken with less qubits than RSA, making it even more vulnerable than the most famous quantum-breakable algorithm. Because the Elliptic Curve Diffie-Hellman exchange (ECDHE) protocol is so ubiquitous, the Supersingular Isogeny Key Exchange, which is very similar to ECDHE and has forward secrecy, is a natural candidate to replace ECDHE even though it can be slightly quantum-weakened. Therefore, we would need to ensure a large enough key size (~768 bits) is computationally practical, which has been confirmed by research groups at the University of Waterloo.

Another interesting technique is focused on lattice-based cryptography. Microsoft is pursuing research in practical applications of post-quantum cryptography. Their research has led to integrating post-quantum cryptography techniques, particularly ring-learning with errors problem, into the TLS protocol, with an increase in 21% overhead and 8KiB size increase in the handshake. The thorough paper covers implementation of the ring learning with errors, integration into TLS, and performance, which covers all the pieces to demonstrate that post-quantum cryptography is practical at this time.

Besides these, there’s research in hash-based cryptography (hashing offers a degree of quantum resistance, so bitcoin may be saved for the time being), algorithms focused on error-correcting codes, as well as upgrades to key sizes of symmetric key cryptography, such as AES, if that is computationally practical.

Quantum computing, cryptography, and telecommunication all have been mostly academic exercises, with little knowledge reaching the general population, and even less conversation going on between physicists and computer scientists. There are current post-quantum cryptography techniques to protect again quantum computing attacks. Many cryptographic systems, ones that had been used for decades, were thought to be secure until some breakthrough took place. There’s no guarantee that some development later on won’t break the current ‘quantum-safe’ systems, but it gives us a starting point to protect our data while quantum computing commercialization continues to ramp up.

“Standards are critical for wide scale implementation”

-European Telecommunications Standards Institute, meeting on adopting Kerberos for post-quantum cryptography, August 2013

Leave a Reply