NIST Chooses Falcon as Standard for Post- Quantum Cryptographic Signature

It all began with a seminal paper published back in 1996. Mathematician Peter Shor had come up with an algorithm capable of cracking RSA, the asymmetric encryption that was later to become a cornerstone of the Internet. But no worry: in order to achieve such a feat, said algorithm would need the mammoth computing power that only a quantum computer could one day deliver. A rather distant prospect at the turn of the century. Nevertheless, it dawned on cryptographers that RSA’s days were counted. Same thing by the way for another encryption method relying on elliptic curves. Time therefore to mull over more robust successors...

“Over the years, four alternatives have cropped up, says Pierre-Alain Fouque, a professor at Rennes 1 University, in Brittany, France. McEliece’s error-correcting codes, multivariate cryptography, isogeny-based and lattice-based methods. A priori, all these techniques are quantum resistant. We call them conjectures because there is no formal proof that they do resist although there exists no algorithm that can break them for the time being.”

Two decades down the road, the quantum computer is now closer to becoming a reality. Preparing for this revolution, the US Department of Commerce’s National Institute of Standards and Technology (NIST) initiated a world wide competition in late 2016, calling upon cryptographers to devise methods among which the best ones would be selected for future standards. Out of 82 submissions, NIST recently chose a first batch of four: Kyber for general encryption when accessing secure websites, Sphinx+, Dilithium and Falcon for digital signatures.

Compactness and secure cryptography

The Falcon is a lattice-based signature algorithm.

“We all use signatures on a daily basis for a lot of things. For instance when shopping online, there a certificate guaranteeing that we are indeed logging to the real website and not a fake one. More broadly speaking, the signature guarantees the integrity of a message and the authenticity of the sender. In practical terms, it must be secured but also very compact. Too big, it would have to be sent in several packets often arriving piecemeal with different delays. Which would slow down the wholecommunication.”

And compactness is precisely one of Falcon’s forte. It is a big advantage. We really wanted to propose something efficient for the companies. The current method, the one relying on elliptic curves, also has good compactness. So in order to replace it, we had to come up with something just as good.

Pattent-Free Algorithms

Falcon was devised by a group of scientists^[1] from different organizations. “We had people from Thales, from IBM, from PQShield, from NNC Group, as well as mathematicians from Brown University who were pioneers when they built an encryption scheme called NTRU. They would later found the NTRU Cryptosystems company that was ultimately acquired by OnBoardSecurity, a company of Qualcomm. NTRU relied on a principle pretty similar to Falcon. That’s why we invited them to join the proposal.”

The group is not an industrial consortium whatsoever. “By the way, NIST mandates that all the algorithms submitted be patent-free. They must be non proprietary so that everybody can use them. In the past, we have seen patented encryption schemes, which turn out to be prejudicial as it actually had the effect of slowing down of the development of certain cryptographic methods.”

A while back, Fouque also participated to the AES and SHA-3 cryptographic competitions. “I’ve always been fond of these contests. They are formidable accelerators of research. Many people working. A lot of means allocated. A lot of findings coming out. It’s most stimulating.”

And Falcon now being chosen by NIST? “Very gratifying of course. We tell ourselves that our work will be useful to everybody. Having said that, one must keep in mind that Falcon wasn’t built ex nihilo. We rely upon research started by others some twenty years ago.”

Post-Quantum TLS project

Fouque recently became Head of Capsule, a new cryptographic research team gathering University of Rennes, CNRS and Inria. “We come from a previous team in cybersecurity that had grown quite a lot. We decided to split it in two and dedicate one to cryptography only. It gives more visibility to this latter topic.”

Fouque is also Scientific Officer of the Post-Quantum TLS project which is a part of a larger Quantum Priority Research Programme and Equipment (PEPR) launched by the French government. “Our project gathers 13 research teams nationwide with a budget of €8M. It aims at bringing state of the art to the French industry and help companies to implement post-quantum cryptography in their products in order to obtain a competitive advantage^[2].”