How quantum-safe cryptography will ensure a secure computing future

The National Institute of Standards and Technology (NIST), a US government lab that publishes standards for government agencies to safely use cryptography, has just announced the winners of a six-year-long competition to create quantum-safe algorithms.

Why is that important? Medical, financial, and health records — for sensitive data protection, encryption and authentication is crucial. Today it’s pretty robust, but future quantum computers could change that. It’s been said time and time again that this emerging, powerful technology based on nature’s quantum intricacies could break cryptography, wreaking havoc in our digital lives. Still, this is unlikely to happen.

To prevent this from happening, researchers have been working on a technology called quantum-safe cryptography. These cutting-edge constructions are based on different mathematical approaches to those widely adopted today. For example, techniques rooted in lattice and isogeny-based mathematics.

With the winning quantum-resistant cryptographic systems NIST has just announced, the world could soon be safe from any potential threat of quantum computers of the future.

Scientists working at IBM took part in a lot of winning algorithms. One of the winning schemes that has been developed by IBM researchers and their partners is the CRYSTALS-Kyber public-key encryption scheme. The other ones are the CRYSTALS-Dilithium, Falcon, and SPHINCS+ digital signature schemes, which were also developed by IBM scientists and collaborators.

Also, a fifth scheme created by IBM, the so-called SIKE encryption scheme, has been earmarked for further study and possible later standardisation. When adopted, the new schemes should be able to keep computing systems safe from quantum hacking. Organisations around the world should consider migrating to them as soon as possible.

NIST is a US government lab that publishes standards for government agencies to safely use cryptography. Relied on by most public and private organizations globally, these standards detail how to use different cryptographic algorithms so that a user’s computer securely communicates with the computer of the intended recipient. They are the basis for today’s secure global communications – be it making a purchase on the web or transferring sensitive data.

But that only applies to classical computers. Quantum computers are different.

Quantum computers harness the properties of quantum mechanics and promise to solve, in the future, specific problems beyond the power of classical machines. And while a quantum computer could help us create new materials much more efficiently than we do today while getting a better handle on financial market fluctuations and so much more, they could also break some of NIST’s current standardized crypto algorithms, exposing the sensitive data they were used to encrypt.

This is why we need to adopt new standards to get ahead of this issue.

For example, at IBM, the research into this new type of quantum-safe encryption started around 2015. One of the top cryptographers at their lab in Zurich, Vadim Lyubashevsky, had just moved to Switzerland from France and, having obtained funding from the Swiss National Foundation, kicked off the research. He wasn’t going at it alone: the funding allowed him to hire several key people, including a then-PhD student at ETH, Gregor Seiler, who later became instrumental in building lattice-based cryptosystems.

And then in 2016, NIST sent crypto ripples across industry and academia, having launched an international competition to develop new quantum-resistant algorithms. Several companies around the world have joined the arena, while a number of top people across the crytpography spectrum, from theoreticians to practitioners, worked either at IBM or with IBM to contribute to the recently announced new schemes by NIST.

Today, there are two types of cryptography: symmetric and asymmetric.

It’s the asymmetric one, commonly used for our day-to-day communication by secure web browsers, chats, VPNs and so on, that could be cracked by a quantum computer. It relies on a private and a public key that is mathematically linked, with the public key responsible for encryption or verification. The private key is only intended for a specific party decrypting or signing the data.

Many asymmetric crypto algorithms rely on a maths problem called prime factorisation, and the longer the key – the more bits it contains – the more difficult it is to break the encryption. And while today’s computers can’t break these algorithms, a quantum computer could – thanks to Shor’s algorithm, developed by Peter Shor in 1994. That’s because factoring numbers, no matter how long a sequence is, is child’s play for a quantum computer with millions of qubits.

Today, crypto protocols such as SSL, Transport Layer Security and HTTPS are based on so-called cryptographic “primitives” – low-level cryptographic algorithms. These include digital signatures, authentication schemes and encryption schemes. But these protocols become useless if the crypto primitives are compromised.

That’s where lattice cryptography can help. It relies on the area of maths dubbed “geometry of numbers,” where data is hidden inside lattices, complex algebraic structures. While it’s easy to create a point in space that is close to the lattice, the hardness of lattice-based cryptography is because it’s difficult to go in the opposite direction. Finding the nearest place in the lattice from a point in space requires time that is exponential in the dimension of the lattice.

This problem has been studied since the 1970s and an efficient algorithm for it would have many applications in a lot of important areas. It has also received a lot of attention from the quantum algorithms community.

NIST has announced that it will standardize the winning cryptosystems by 2024. It means that the US government will start adopting these schemes and requiring that their suppliers use them too.

There probably won't be just one standard. As we've seen with classical cryptography, there are many different standards being used for scientific or political reasons. Eventually with time, if one standard is clearly better, people typically gravitate towards it for new systems.

Today, we are still at a very early stage of quantum-safe crypto. The needs of people who consume crypto might be different in a decade. They might value some characteristics more than the ones being emphasized today and might want to use schemes optimal for those specific purposes. Having said this, it's hard to imagine something being faster than lattice cryptography which is being envisioned by many experts to be used across different fields in the future.

It is crucial for organisations worldwide to understand the risks of quantum computers and to realise that solutions thanks to NIST’s selection of quantum-safe standards are becoming available. They should start preparing today.