NSA begins planning encryption to postquantum cryptography

Quantum-Capable Chip from D-Wave Systems

This week, the US National Security Agency has updated its recommendations on the use of data encryption algorithms due to the need for a gradual transition to cryptographic methods that are resistant to hacking attempts using quantum computers. So far, the recommendations include well-known and tested algorithms with an increased key size. But according to the NSA, the time has come to think about other encryption methods.

The US National Security Agency deals not only with tapping the population, but is also responsible for the security of public services. In particular, the NSA periodically issues recommendations on computer security - for example, on the use of document encryption and communications. And although quantum computers have not yet emerged from the stage of complex and expensive laboratory experiments, it seems that security experts have no doubt: at some point they will become commonplace.
')
Modern encryption systems are based on mathematical problems that require a long search for solutions. This is the decomposition of integers into prime factors, the search for discrete logarithms and elliptic cryptography. Ordinary computers are not able to cope with them for a reasonable time - with an increase in the size of the encryption key, the time required for calculations increases exponentially. But these algorithms, apparently, will not be a problem for quantum computers.

American mathematician Peter Shor is known for his work in the field of geometry, probability theory, combinatorics, theory of algorithms and quantum informatics. And the greatest fame brought him work on the theory of quantum computing. In 1994, he published a paper in which he presented an algorithm potentially capable of hacking public-key cryptography. To do this, you need "only" a quantum computer with several hundred logical qubits.

For example, RSA uses the public key of size M, which is the product of two large prime numbers. One of the ways to crack the RSA cipher is to find the factors of M. The best classical algorithm for their search will work on a regular computer in time M ^1/3 . Shor's algorithm , using the capabilities of quantum computers, is able to do it not much more slowly than calculating the product of these numbers — that is, very quickly.

The NSA said in its appeal that the transition to new encryption systems that are resistant to cracking on quantum computers will begin in the near future - at least the agency is already working on them together with cryptographic specialists. Experts say that such algorithms exist - encryption on hash functions and symmetric ciphers are considered sufficiently strong when using keys of reasonably large sizes.

The text of the reference mentions that algorithms using elliptic curves were at some point considered to be reliably protected from quantum computations — but now it is clear that they will not give such guarantees. Therefore, those organizations that have not yet bothered to switch to using them are advised not to waste their time and wait for radically new encryption systems.

“What the NSA wants to say with this appeal is to express its concern with quantum computers sufficient to apply the enormous effort required to switch from encryption with public keys to post-quantum cryptography ,” explains Nadia Heninger, assistant professor of computer science at the University of Pennsylvania. “This will greatly affect the information security industry, since all companies working under a contract with the government will have to implement new algorithms in their products.”

Fortunately, full-fledged quantum computers, according to experts, we will not have a few more decades. In this regard, the unexpected concern of the Agency about the transition to new encryption algorithms raises questions. Why is the NSA in such a hurry - just because of the fact that it represents the inertia of public services and the scale of the task of translating all systems to the use of new algorithms? Or does the Agency know something about progress in the field of quantum computing, which others do not know? ..