Decades-old math theorem cracks US government encryption algorithm

The information security landscape is rapidly changing in response to quantum computing technology, which is capable of cracking modern encryption techniques in minutes, but a promising US government encryption algorithm for the post-quantum world was just cracked in less than an hour thanks to a decades-old math theorem.

In July 2022, the US National Institute of Standards and Technology (NIST) chose a set of encryption algorithms that it hoped would stand up to the encryption-cracking power of quantum computers and tasked researchers with probing them for vulnerabilities, offering a $50,000 prize for anyone who was able to break the encryption.

A researcher at Katholieke Universiteit Leuven (KU Leuven) took up the challenge and broke through one of the algorithms known as SIKE in less than an hour using a single classical computer and a mathematical theorem developed by Dr. Ernst Kani at Queen's University in Canada in 1997.

The theorem revolves around manipulating mathematical objects in the abstract to probe their various properties, Dr. Kani explains in a Queen's University statement: "Doing pure mathematics is an end by itself, so we don't think of real-world applications ... But, later, many of those studies are useful for different purposes.

"When [Pierre] Fermat proposed [Fermat's Last Theorem] hundreds of years ago, his intent was to be able to factor certain large numbers. The application to cryptography came only much later in 1978.

"Basically, all the methods we use today for data encryption are based on mathematics."

The math in Dr. Kani's theorem involves "gluing" together two elliptical curves to find where such a process might fail and under what conditions. The 1997 paper describing these failures became the basis of the successful attack on the SIKE algorithm by Wouter Castryck and Thomas Decru, researchers at KU Leuven.

Consequences for quantum encryption algorithms

Quantum computers are incredibly powerful devices that rely on principles in quantum mechanics to process data faster by orders of magnitude than even the most advanced supercomputers are capable of, though quantum computers are still in their relative infancy.

The successful breaking of the SIKE algorithm shows that it cannot be a secure means of encrypting data in a post-quantum world, narrowing down the field of possible candidates for future encryption technology, allowing researchers to focus their attention elsewhere.

This kind of probing is an important process since without this kind of rigorous and creative thinking most of our modern communications will remain vulnerable to exposure in the short-to-medium term.

"Our problem had nothing to do with cryptography, which is why I was surprised when I heard of the algorithm attack. It was quite ingenious, what they did there!" Dr. Kani said. "One of the co-authors of the SIKE algorithm expressed surprise in the fact that genus two curves could be used to gain information about elliptic curves. But this was precisely our original strategy in the 1980's and 1990's (and afterwards).

"Cryptography uses a lot of sophisticated mathematics, especially arithmetic geometry," Dr. Kani added. Computing experts and math experts have to work together to advance this field."