The challenge is enormous due to the physical demands of qubits, but there is broad consensus in the quantum community that in the coming decades we will see the materialization of a quantum computer.
Selection of new encryption algorithms: post-quantum algorithms
The selection process for new encryption algorithms follows an open competition coordinated by NIST (National Institute of Standards and Technology), an agency of the United States Department of Commerce. click here to read about Googles 25e Verjaardag.
The new algorithms are called post-quantum , although they do not require a quantum computer to execute. Perhaps a more precise term would be “quantum computer resistant” or, in English, “quantum-proof”, “quantum-safe” or “quantum-resistant”.
In 2016, NIST announced the competition, and at the end of 2017, a total of 69 algorithms were selected as candidates for the first round. In the second round, more than 40 algorithms were discarded due to problems detected in studies carried out by various teams. Of the initial candidates, 7 were selected in 2020 to advance to round 3. NIST is expected to conclude the process with a fourth round, finally selecting the candidates that will be standardized.
The advancement of the development of quantum computers plays a crucial role in this process. Depending on such progress, NIST may choose to accelerate or delay the standardization process, and could even open additional calls for new proposals.
Requirements for post-quantum algorithms
The current algorithm that facilitates the exchange of information is based on schemes where security is closely linked to the difficulty that current computers have in factoring large numbers into two prime numbers.
The existence of a known quantum algorithm, Shor, capable of solving the factorization problem, implies that current schemes are no longer secure when a sufficiently powerful quantum computer is available. The new algorithms that are being evaluated are based on novel mathematical problems for which there is no known method, whether in quantum or classical computers, that allows them to be solved.
It is crucial to understand that any encryption scheme relies on not knowing an algorithm to solve the fundamental problem. This condition does not imply that there is no solution in the future. In fact, many algorithms proposed in the NIST process were discarded due to the discovery of new algorithms capable of breaking them. A notable example is the case of SIKE, developed in collaboration between engineers from Amazon, Microsoft and the University of Versailles. SIKE advanced to round 3, but was dismissed when an algorithm was identified that could break it using a conventional laptop in a matter of hours. This example highlights the dynamic and constantly evolving nature of the field of cryptography.
