What will be post-quantum cryptography?

There is a race to create new ways to protect data and communications from threats from heavy-duty quantum computers

Few of us paid attention to the small lock symbol that appears in our web browsers each time we go to the website of the online store, send and receive emails, check our bank account or credit card. However, it signals that online services use HTTPS, a web protocol that encrypts the data that we send over the Internet and the responses that we receive. This and other forms of encryption protect various electronic communications, as well as things like passwords, digital signatures, and medical records.



Quantum computers can undermine this cryptographic protection. Today, these machines are not yet powerful enough, but they are rapidly evolving. It is possible that no later than ten years later - and perhaps even earlier - these machines can become a threat to the widely used cryptography methods. That is why security researchers and companies are developing new cryptographic approaches that can withstand future quantum hacker attacks.

How does digital encryption work?

There are two main types of encryption. Symmetric encryption requires that the sender and recipient have identical digital keys for encrypting and decrypting data, while asymmetric encryption — or encryption with a public key — uses a public key that allows people to encrypt messages for a recipient who alone has a private key that allows them to decrypt .



Sometimes these two approaches are used together. In the case of HTTPS, for example, web browsers use public keys to verify the authenticity of sites and obtain a key for symmetric encryption of communications.



The goal is to prevent hackers from using significant computing power to try to guess the keys used. For this, popular cryptographic methods, including RSA and encryption using elliptic curves, usually use the so-called. one-way functions with a secret input are mathematical constructions that are relatively easy to calculate in one direction to obtain keys, but it is very difficult for an attacker to reverse engineer.



Hackers can try to crack the code by picking up all possible key options. But the defending parties make this task very difficult for them, using pairs of very long keys - as in the 2048-bit RSA, which uses keys with a length of 617 decimal numbers. Enumerating all the possible options for private keys will take thousands - if not millions - of years on ordinary computers.

Why do quantum computers endanger encryption?

Because they can help hackers make their way through algorithmic secret moves much faster. Unlike classical computers that use bits that can only take values ​​1 or 0, quantum machines use qubits that can simultaneously represent various possible states, intermediate between 0 and 1 - this phenomenon is called superposition. They can also influence each other from a distance due to a phenomenon such as entanglement.



Due to this phenomenon, the addition of several additional qubits can lead to exponential jumps in computing power. A 300-qubit quantum machine is capable of representing more values ​​than the number of atoms in the observable Universe. Assuming that quantum computers will be able to overcome some of their inherent limitations regarding performance, someday they can be used to check all possible cryptographic key options in a relatively short time.



Hackers are also more likely to try to use algorithms to optimize certain tasks. One of these algorithms , published by AT&T Bell Labs' Love Grover, helps quantum computers search for options much faster. Another algorithm , published in 1994 by Peter Shore, then also a professor at Bell Labs, and now a professor at MIT, helps quantum computers find incredibly fast integer multipliers.



Shore's algorithm threatens public key systems such as RSA, whose mathematical defense in particular depends on how difficult it is to reverse engineer the result of multiplying very large primes (factorization). A report on quantum computing, published last year by the U.S. National Academy of Sciences, Engineering and Medicine, predicts that a powerful quantum computer running the Shore algorithm will be able to crack 1024-bit RSA variants in less than a day.

Will quantum computers be able to crack cryptographic protection in the near future?

Unlikely. A study by national academies claims that in order to pose a real threat, quantum computers will need much more computing power than the best of them have today.



However, the year in which quantum code hacking will become a serious headache - which some security researchers have dubbed Y2Q - can get unexpectedly fast. In 2015, researchers concluded that a quantum computer would need a billion qubits to quickly crack a 2048-bit RSA encryption. In a more modern work , it is indicated that a computer with 20 million qubits will be able to cope with this task in just 8 hours.



This is far beyond the capabilities of today's most powerful computers, with only 128 qubits . But the progress of quantum computing is unpredictable. Without cryptographic protection that takes into account quantum computing, all kinds of services - from robomobiles to military equipment, financial transactions and communications - are at risk of attack from hackers who gain access to quantum computers.



Any enterprise or government that wants to store data for several decades should already think about what risks the new technology carries, since the encryption they use today can be cracked in the future. It can take years to transcode huge volumes of historical data into a more reliable form, so it would be better to use reliable coding today. From here comes the request for post-quantum cryptography.

What will be post-quantum cryptography?

This is the development of new types of cryptographic methods that can be applied using today's classic computers, but which will be invulnerable to tomorrow's quantum ones.



One of the lines of defense is the increase in the size of digital keys to significantly increase the number of options in which it will be necessary to search by search. For example, a simple doubling of the key size from 128 to 256 bits quadruples the number of possible options that a quantum machine that uses the Grover algorithm will have to sort out.



Another approach involves the use of more complex functions with a secret input, such that it would be hard to handle even with a powerful quantum computer that executes the Shore algorithm. Researchers are working on a wide range of approaches, including such exotic ones as lattice cryptography and a key exchange protocol using supersingular isogeny.



The purpose of research is to choose one or more methods that can then be widely applied. The U.S. National Institute of Standards and Technology launched in 2016 the development of post-quantum encryption standards for government use. He has already narrowed down the initial set of applications from 69 to 26, but says that the first draft of the standards are likely to appear no earlier than 2022.



The critical importance of this task is due to the fact that encryption technologies are deeply embedded in many different systems, so it will take a lot of time to remake and introduce new algorithms. A study of national academies from last year noted that it took more than 10 years to completely get rid of one widely used cryptographic algorithm that turned out to be vulnerable. Given the speed of quantum computer development, perhaps the world does not have much time left to deal with this new security problem.