One of the most important applications of quantum computing is in cybersecurity, as quantum computing threatens some of the most prominent encryption algorithms in use today.
The common public-key cryptography systems in use today such as RSA and Diffie-Hellman rely on the inherent difficulty of using classical computers to factor large numbers. Mathematician Peter Shor invented an algorithm in 1994 that used a theoretical quantum computer to factor large numbers exponentially faster than classical computers, which would allow the breaking of existing public-key cryptography schemes with a sufficiently powerful quantum computer. As quantum computers have moved over the last few decades from theory to practice, researchers, governments, and standards-setting organizations have had to prepare for how to adapt to a world where practical quantum computing renders existing encryption algorithms obsolete.
To that end, the U.S. Department of Commerce’s National Institute of Standards and Technology (“NIST”) announced in July 2022 that it had selected four algorithms as standards to replace existing encryption algorithms in a post-quantum future.
This was the culmination of a competition that NIST has been running since 2017, beginning with 69 candidate algorithms. Of the four algorithms that were selected, only one, “CRYSTALS-Kyber,” is a public-key encryption algorithm that would prevent a sender’s messages from being read by anyone without the sender’s private decryption key. The other three algorithms, “CRYSTALS-Dilithium,” “FALCON,” and “SPHINCS,” are all digital signature algorithms that do not encrypt a message, but are used to verify the identity of the sender of a message and that the message has not been modified. Each of these algorithms is still in an experimental stage, as computer scientists and mathematicians continue to research methods for attacking these algorithms using either classical or quantum computers.
The difficulty in developing effective post-quantum cryptography algorithms was highlighted in early August 2022 when researchers at KU Leuven, a Belgian university, published a paper demonstrating that they had defeated another promising post-quantum cryptography algorithm named “SIKE” in one hour on a single classical computer. Along with the four post-quantum cryptography algorithms that NIST selected, NIST also advanced four alternate algorithms to a fourth round of competition. One of those algorithms, “Supersingular Isogeny Key Encapsulation” or “SIKE,” offered a possible alternative public-key encryption algorithm that researchers intended to not be breakable by a quantum computer. However, the two researchers at KU Leuten, Wouter Castryck and Thomas Decru, discovered a weakness in the SIKE algorithm that allows for a brute-force search of a more limited number of intermediate possible values used in generating the private key. Castryck and Decru implemented their attack on a single core Intel computer at 2.60 GHz, and were able to break SIKE at parameters previously believed to meet NIST’s quantum security requirements in about 62 minutes. This was the second post-quantum cryptography algorithm designated as a candidate by NIST to be defeated this year.
