In recent years, academia, industry and government have invested energy and resources in the field of quantum computing, in computers that exploit the phenomena of quantum mechanics to solve mathematical problems that are difficult or impractical for conventional computers.
If large-scale production of quantum computers ever gets underway, they will be able to smash many of the public-key (or asymmetric) cryptographic systems currently in use. This would seriously undermine the confidentiality and integrity of digital communications on the Internet and elsewhere.
In this context, the goal of cryptography post-quantum (o quantum safe) is to develop ciphers that are safe, both from cryptanalysis attacks conducted with quantum computers, and classical ones, and that can interact at the same time with existing communication protocols and networks.
While public-key cryptography, double-key encryption for encryption / decryption, may be seriously endangered by the advent of quantum computers, symmetric (or private) cryptography and hash functions rely on problems resistant to quantum algorithms. Among these, the greatest threat to symmetric ciphers is represented byGrover's algorithm (conceived by Lov Grover in 1996 at i Bell Labs1). This algorithm running on a quantum computer allows you to search for an element within an unordered list of length N, in a time proportional to the square root of N. On the contrary, on a classical computer the time would be proportional to N This means that to obtain the same level of security, the key length must be doubled.
Among the symmetric key algorithms, theAdvanced Encryption Standard (AES), the Blowfish, Twofish or Serpent, with a key length greater than or equal to 256 bits and under appropriate conditions, they can prove themselves quantum safe.
On the asymmetric cryptography front, however, the prospect is less reassuring. Public key cryptosystems are mainly used to perform two fundamental tasks, the secure exchange of keys, for their subsequent use with symmetric ciphers, and the digital signature.
The most well-known and currently in use public key ciphers include:
- RSA, based on the problem of factorization of whole numbers;
- elliptic curve cryptography, which bases its security on the difficulty of performing certain operations on the points of this type of curve;
- Diffie-Hellman, focused on the difficulty of calculating the discrete logarithm on some cyclic groups.
To each of them it is possible to easily conduct a cryptanalysis attack, decrypting the information without using the key, by means of theShor's algorithm (conceived by Peter Shor in 19942) running on a quantum computer. The reason why Shor's algorithm is able to "break" public key cryptographic systems is the consequence of the fact that they are based on problems with non-polynomial computational complexity, which can be solved by a quantum computer in polynomial time. Specifically, given an integer N, Shor's algorithm factorizes it in a polynomial time in log(N), while on a classical computer time is exponential in N.
Motivated by these considerations, the American National Institute of Standards and Technology (NIST) has undertaken the selection of public key cryptographic algorithms quantum safe at the end of a public call, announced during the 2016 PQCrypto conference and launched in December of the same year.
The invitation collected 82 candidate algorithms which, through peer review processes and selection rounds, narrowed them down, to be completed, presumably by 2024, with the release of a standard.
The new ciphers will be adopted by the United States in analogy to previous initiatives for the introduction of the Data Encryption Standard (DES) and AES.
Between classes of algorithms post-quantum which are proving to be the most promising are the algorithms based on "Code-based cryptography" which, introduced in 1978 by the American Robert McEliece3 for public key cryptography, they did not have much luck due to the excessive key size. The same, today there are variants capable of offering considerably reduced and competitive key sizes. These algorithms are based on the difficulty of searching within a huge unordered set of numbers. It has also been theoretically proved that they belong to the class of so-called NP (Non-deterministic Polynomial) problems that could resist quantum computation.
A second class, Multivariate Cryptography4, is based on the difficulty of solving systems of quadratic algebraic equations in many variables (NP-hardness).
A third class is that based on the algebraic concept of "lattice" (Latex-based cryptography), including variants based on the problem of "learning with errors", which consists in the reconstruction of a function from some of its inaccurate assessments5. This formulation made it possible to define some innovative algorithms for asymmetric cryptography, accompanied by severe security demonstrations.
The implementation of new public key ciphers quantum safe today represents an unavoidable effort. The pervasiveness of the use of current public key algorithms affects everyone's daily life, from secure browsing on the Internet to banking security systems, from digital signatures to crypto-currencies.
A race against time for some, while for others it will still take time for the computational power of a quantum computer to reach the level necessary to make current standards obsolete.
In the meantime, however, in the private sector giants such as Google and IBM conduct experiments aimed at acquiring the so-called "quantum supremacy", challenging each other in the achievement of new and increasingly ambitious computational records. Furthermore, with the same aim, in the international sphere, superpowers such as the United States and China, as well as the European Union, are making ever greater investments for the development of research plans in the field of quantum computing. China, for example, recently announced its intention to build a national laboratory for quantum information sciences in Hefei by 2020, which will be assigned a multi-year budget of ten billion dollars.6.
At the same time, in the European context, the new president of the European Commission, Ursula von der Leyen, has pronounced on the issue stating that the quantum computing is one of the Union's priorities and expressing the will to support development initiatives in this area, also making European computational resources available to academia and research, through the cloud. To this end, the Union has made available a billion dollars to be used within the next ten years7, for the development of certain projects already identified.
In this context, the reason behind the spasmodic "race" of state and private actors, aimed at achieving the aforementioned supremacy in the field of quantum computing, is found in the words that Mike McCaul8, North American politician and member of the American Enterprise Institute, pronounced in 2018 about competition in the field of quantum computing of the United States with global opponents such as China, Russia, North Korea and Iran: "I believe that any superpower reaching this milestone ahead of the others would have the first digital nuclear bomb".
1 Grover, "A fast quantum mechanical algorithm for database search", Proceedings, 28th Annual ACM Symposium on the Theory of Computing, p. 212, 1996.
2 Shor, "Algorithms for quantum computation: Discrete log and factoring", in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, Santa Fe, IEEE Computer Society Press, pp. 124-134, 1994.
3 McEliece, "Public-Key System Based on Algebraic Coding Theory", DSN Progress Report 44, pp. 114-116, 1978.
4 Matsumoto, Imai, "A class of asymmetric cryptosystems based onpolynomials over finite rings", IEEE International Symposium on InformationTheory, Abstract of Papers, pp. 131-132, 1983.
5 Goldreich, Goldwasser, Halevi, "Public-key cryptosystem from lattice reductions problem", in Proc. Of Crypto '97, volume 1294 of LNCS pp. 112-131, IACR, Springer-Verlag, 1997.
6https://itbrief.com.au/story/apac-jumps-on-quantum-computing-bandwagon
7https://www.ilsole24ore.com/art/la-cina-l-occidente-e-sfida-globale-big-...
8https://fedmanager.com/news/congressman-quantum-computing-equivalent-to-...
Photo: IBM
