Crypto Is Preparing For Quantum
No one is sure when large scale quantum cryptography will be available, but when it does, our current systems of encryption will be insufficient to protect data. Several initiatives have been launched to protect data that is being generated and stored today from the prying quantum eyes of tomorrow.
Current asymmetrical encryption methods often work with prime factorization of large numbers. One half of the asymmetrical key is a large number, say a string of 256 digits, and the other half consists of corresponding prime numbers. It is, with our current compute power, easy to compute the sum of prime numbers to verify that a given large number is indeed the sum of those prime factors. But conversely, factorizing a large number into two corresponding prime numbers is difficult. It is theoretically possible, but it will take tremendous compute to discover a key value of prime numbers that sum into that given large number.
Parallelization and exponential expansion
However, this is no longer the case with quantum computing. Quantum’s raw compute power lies not just in simply enormously faster calculation power, but also in parallelization. Whereas binary computing attempts calculations sequentially, quantum computers can process data simultaneously. This means that a quantum computer can try any number of combinations in the same amount of time a traditional computer would attempt the first one. Quantum also expands its power exponentially: every qubit added to the processing power, adds compute in orders of magnitude. In short, a quantum computer will be able to complete a task in minutes that a traditional binary computer would complete in a thousand years.
Read more about the current state of quantum in How far off is quantum computing really?
A new Public Key Infrastructure (PKI) to encrypt data even form the raw compute power of quantum is just the ticket. Experts believe that methods like AES and SHA-3 will not be sufficient enough to withstand quantum decryption (PDF). The challenge with introducing a new system is that it takes several years, if not decades, to implement a new PKI.
Establishing PKI will take a long time
As a real-world example, simply look at the amount of time it took us to phase out SHA-1. Its successor was published in 2001, but when vendors finally started to depreciate the 1990s standard at the end of 2014, it caused an upheaval in the IT world because legacy appliances and applications that required SHA-1 to function. Browsers finally ceased support of the method to protect certificates in 2017, after years of warnings. It still caught some users by surprise. Interestingly, organizations that communicate through Dutch governmental infrastructure PKIOverheid have been required to use SHA-2 for about a decade, after some unpleasantness with a hacked certificate authority. There’s nothing like a good crisis to push technology forward.
Not only does an encryption standard take about 10 to 15 years to establish a firm foothold, everything that is being encrypted today would, with the arrival of quantum computers, be vulnerable to adversarial decryption. All our legacy databases, all the old blockchains, all your previous encrypted messages would be up for grabs with this new power to look back at data protection methods that suddenly have been rendered obsolete. Current thinking is that in about ten years, the IT world will have reached a point where quantum computing will start posing a risk to older traditional encryption methods – that are still very much in use today.
NIST is making progress
Although this is still very much up for debate – cryptography pioneers like Ron Rivest and Adi Shamir, for instance, feel that this is a bridge we should cross if and when we get there – many in the cryptography world think that it is high time we develop some stronger algorithms. Among those is standards institute NIST, which is on its way to develop methods for cryptography that would not be vulnerable to quantum attack. “The goal of post-quantum cryptography (also called quantum-resistant cryptography) is to develop cryptographic systems that are secure against both quantum and classical computers, and can interoperate with existing communications protocols and networks”, writes NIST.
The institute aims to publish a draft for a quantum-resistant algorithm somewhere before the end of 2024 at the latest and has been pushing cryptographers to develop ideas. NIST started its call for proposals in 2016. “We will be doing our own internal review of the algorithms, and we certainly want the public and crypto community to analyze the algorithms as well,” said NIST mathematician Dustin Moody in the announcement of the CFP. The process so far went through two rounds of submissions to gather algorithms. The organization announced 69 candidates in 2017, and 26 last year. The third and final round is currently scheduled for 2021, at the latest.
There are several possible solutions to protect cryptography against the increased computing power of quantum. A simple solution that is already being employed in post-quantum cryptography is an increased key length. Other solutions involve more robust hashing algorithms based on increased randomization, learning algorithms that adapt to the needs for better encryption on the fly, and other ways to increase length and randomness, using Deterministic Random Bit Generators.
Quantum-resistant cryptography today
Several quantum-resistant methods are already in use today. Two of NIST’s candidates, FrodoKEM and Classic McEliece, are recommended by German BSI as future proof encryption algorithms (PDF). Companies like Canadian ISARA and Swiss ID-Quantique are paving the way with business solutions that provide quantum-resistant cryptography. Chrome experimented with TLS that is protected against quantum attack in its pre-release browser Chrome Canary, and Cloudflare used that experimental feature to evaluate the performance and feasibility of two new quantum-resistant ciphers that have been submitted to NIST. Cloudflare submitted its report to the institute for further analysis.
With final NIST submissions arriving within the year and a draft standard published between 2022 and 2024, quantum-resistant cryptography will be standardized sometime very soon. Several security companies already offer (non-standardized) quantum-resistant solutions. It is necessary to protect communications today from prying eyes in ten tot fifteen years. Once quantum takes off, historic data that has been saved without quantum-resistant cryptography can be decrypted, which means data that’s put at rest today, could be vulnerable tomorrow.