The security industry is concerned about the development of increasingly powerful quantum computers. Today’s encryption methods can be quickly reversed. But quantum secure cryptographic methods should prevent this. […]
The development of quantum computers is currently frenzied. With the participation of, among others, the IBM research laboratory in Rüschlikon near Zurich, corresponding computers with increasing power are being supplied. Currently, there is a system in use with 127 quantum bits, or qubits for short.
By the end of the year, IBM Research plans to deploy a 433-qubit computer. This number is expected to increase tenfold in the coming years. In 2025, Kookaburra, a quantum computer with 4148 qubits, will be launched if everything goes according to plan.
This is a breathtaking development when you consider that each extra qubit represents a doubling of the computing power and thus makes Moore’s law of classical computer technology look old. This states that every doubling of the transistors on a chip represents a doubling of performance.
Quantum computers therefore become very powerful very quickly. That has enormous advantages. Computers are expected to soon be able to solve previously unsolvable or highly complex calculations, such as in bioinformatics. On the other hand, the almost unlimited potential also means that the encryption methods used today can be cracked in no time.
Corresponding algorithms have already been presented. Lov Grover showed that quantum computers can significantly reduce key searching in symmetric encryption processes. For asymmetric cryptography methods, Peter Shor showed in 1994 that quantum computers can efficiently factor the products of large prime numbers used here.
Unknown “expiry date”
However, it is still uncertain when exactly this will be the case, ie when such a quantum computer will be available. As Rolf Opplinger of the National Research Center for Cybersecurity NCSC explains in a “technology overview” on the subject, “even under ideal conditions, Shor’s algorithm requires a number of qubits that grow linearly with the bit length of the corresponding keys, i.e. typically a few thousand ‘.
But apparently that’s purely theoretical. “Under real conditions, error correction methods are also required, so the number of qubits needed can run into the millions,” he continues.
That doesn’t mean, however, that the “expiry date” of current cryptographic methods is in the distant future and we’re getting some breathing room. Because on the one hand there is a chance that more efficient algorithms for prime number decomposition could be found, on the other hand secret services in particular are known to follow the strategy of “harvest now, decrypt later”, i.e. encrypted data is tapped in reserve in order to then decode it, when quantum computing has made sufficient progress.
Post-quantum cryptography today
From this point of view, there is little time to establish so-called post-quantum cryptography (PQK) methods. But here too, the development of appropriate methods is in full swing and has become more concrete this summer. The US National Institute of Standards and Technology (NIST) recently announced the algorithms that will one day make up the PQK standard. The methods selected by NIST have also been highly developed with the participation of IBM researchers in Rüschlikon.
The focus is on the two main algorithms Crystals-Kyber for encryption and Crystals-Dilithium for digital signatures, where Crystals stands for “Cryptographic Suite for Algebraic Lattices”. Thus, both methods focus on lattice vector problems (lattice-based).
In particular, Kyber is a Key Encapsulation Mechanism (KEM) whose security relies on the difficulty of solving the problem of learning with errors. The challenge is to sample multiple points from a grid, some of which may be misplaced, and use them to determine or “learn” the function that produced them.
The process turns out to be difficult and, above all, different enough that there are no known quantum algorithms that could solve it quickly.
In addition to the two Crystals algorithms, NIST has also proposed “Falcon” and “Sphincs+” methods for the PQK standard, which can be used for digital signatures. These two are also “Lattice-based” and are intended to complement the main algorithms in terms of intended use. Falcon has smaller parameters while dilithium is easier to implement and implement.
Sphincs+, on the other hand, could serve as a backup algorithm if the others could be cracked.
The “Rainbow” signature process has shown that such a hack can also happen. This also made it to the NIST final selection. But cryptographer Ward Beullens managed to crack the private key in Rainbow within 53 hours with his notebook.
In addition to PQK, quantum mechanical systems can also be used to protect data from decryption with quantum computers. Currently, this is mainly achieved with the so-called key agreement.
However, such systems can still be deployed to a very limited extent, for example only over relatively short distances of several hundred kilometers and via dedicated channels. Yet here too Switzerland leads the way with offers, for example from the Geneva-based company ID Quantique.
Conclusion: Possible immediate measures
A conclusion about quantum-resistant encryption could be that companies can already protect data that especially deserves protection against future quantum computer hackers. This is because the threat to symmetric cryptographic methods is smaller than to asymmetric methods.
Using a key twice as long is sufficient here. The Federal Department of Cryptology (FUB Kryptology) therefore recommends that authorities only use information classified as secret with a symmetric process and a key length of at least 256 bits.
The use of, for example, AES-256 (Advanced Encryption Standard) instead of AES-128 can therefore also be considered a recommended practice for companies.