Cryptography
A closer look at: post-quantum cryptography
Date:
Changed on 09/02/2022
Quantum computers are expected to be capable of breaking existing cryptographic algorithms, threatening the security of our data. The aim of post-quantum cryptography is to address this issue, devising new ways of protecting data and communications against the threat posed by super powerful quantum computers.
Not many internet users will pay much attention to the tiny padlock that appears on their web browsers every time they’re shopping online, sending an email or checking their online banking. However, it is this symbol that confirms that their data is protected by a type of encryption.
Whether it’s passwords, PIN codes, digital signatures, medical records or electronic communications - a security breach can have serious consequences. This is true for individuals, but is arguably even more of a concern for companies (in finance or the space industry, for example) and governments (armies, diplomatic corps) who handle sensitive data on a daily basis.
Traditional cryptography: secure enough for current data
Today, almost all digital communications are protected by three cryptosystems:
- Asymmetric cryptography (also known as public-key cryptography), which uses a key that is accessible to the public to allow people to encrypt messages for a recipient who is the only person with the private key needed to decrypt them. This is chiefly used to establish an encrypted channel between two parties, either for authentication or digital signatures.
- Symmetric cryptography (also known as secret-key cryptography), where both the sender and the recipient must have identical digital keys in order to encrypt and decrypt data. This is used to effectively encrypt data, such as when an encrypted channel has been previously established via asymmetric algorithms.
- Hashing, which draws on the avalanche effect whereby each output bit is dependent on each input bit. This is used to verify the integrity of files or electronic signatures.
The majority of current IT systems and services, such as digital identities, the Internet, mobile networks and cryptocurrencies, use a combination of symmetric and asymmetric algorithms, creating mathematical problems that are very difficult to solve in order to provide sufficient protection against most modern technology.
The quantum computer - a threat to current encryption
But this could all be about to change. In 1994, Peter Shor demonstrated that a sufficiently powerful quantum computer and a specific algorithm (later termed “Shor’s algorithm”) could be used to break asymmetric algorithms in no time at all.
While it would take standard computing hundreds or even thousands of years to solve public-key cryptography mathematical problems, making them effectively “unbreakable”, a fully-developed quantum computer would enable computer hackers to make their way past algorithms much more quickly, using its quantum properties to find the secret key more quickly.
Symmetric key cryptography could withstand quantum attacks, but is limited by the fact that both terminals have to share a key in advance. As such, it is not suitable for when a user needs a secure connection between their browser and an e-commerce website, for instance.
Although the machines that are currently in development are not yet powerful enough to constitute a genuine threat, most experts believe that it might only be ten years until this is the case. Without specific “quantum security”, a whole host of things - from driverless vehicles and online communications to financial transactions and military equipment - could have their security compromised, making them an easy target for hackers with access to quantum computers.
Post-quantum cryptography: countering the threat of the quantum computer
The solution lies in developing “quantum security” algorithms that are capable of withstanding attacks from quantum computers. This is what scientists and major security companies are currently working on, devising a wide range of post-quantum cryptography standards that are compatible with today’s computers, but which will also be capable of withstanding attacks from quantum computers in the future.
quantum cryptography versus post-quantum cryptography
It’s easy to get confused between the two terms. Whereas quantum cryptography draws on quantum mechanics in order to boost current levels of security, post-quantum cryptography concerns algorithms designed to withstand attacks from quantum computers. The challenge of post-quantum cryptography is to prepare for the era of quantum computing, bringing algorithms and mathematical standards up to speed so that they can be used by all on a standard computer.
“The first uses quantum properties, meaning specific mechanisms are required. You couldn't do that on a standard computer. The second only involves new algorithms - for normal users, the machines will remain the same. They will, however, be capable of withstanding potentially ‘quantum’ attacks” explains David Pointcheval, director of the Cascade project team at the Inria Paris research centre and director of the IT Department at the École Normale Supérieure.
One of the ideas the scientists have come up with is to increase the size of the digital keys in order to significantly increase the number of permutations that can be searched for using raw processing power. Another involves developing more complex trap functions that even a highly powerful quantum computer using an algorithm such as Shor’s algorithm would struggle to decrypt.
Trellis-based constructions and supersingular isogeny key exchange are two other important candidates for post-quantum cryptography that researchers are currently working on.
Spin-off from Inria and the Sorbonne, the Cryptonext Security startup markets software programs capable of withstanding the phenomenal computational power of quantum computers. The founders, Ludovic Perret et Jean-Charles Faugère, are from the Polsys team, renowned internationally as one of the best at resolving nonlinear systems using exact algorithms.
A range of obstacles to overcome
But before companies can get their hands on cryptographic solutions capable of dealing with the processing power of quantum computers, there are still a number of problems that have to be solved.
The first is the size of the keys themselves. In the post-quantum algorithms currently being developed, the size of the keys ranges from forty thousand kilobytes up to a megabyte (compared to hundreds or thousands of bits for current algorithms). What this means is that we have to find an efficient way of storing these keys.
Bandwidth needs are also a problem when it comes to developing post-quantum cryptography, since these are likely to massively increase with the arrival of the quantum computer. The same goes for existing network infrastructures and architectures, which in all likelihood will need to be upgraded or even replaced in order to support these new solutions. This could take several years.
The urgency of the situation is an issue in itself: cryptographic technology is deeply-rooted in a number of different systems, meaning it will take some time to untangle them and to deploy new ones. Can post-quantum cryptography become a reality before the arrival of an all-powerful quantum computer? The race is on.
Quantum computing and algorithms: a top priority for Inria