How Thales developed globally recognised algorithm for post-quantum cryptography

An algorithm co-developed by Thales will become part of the first US and global standard for post-quantum cryptography, which aims to thwart the threat of cyber-attacks by quantum computers. Designed by a laboratory set up in 2013, the algorithm is the result of a five-year competition.

Quantum computers may still be little more than prototypes, but they pose a future threat to our cyber defences. Despite its English-sounding name, Falcon is very much a French invention – at least in part. The algorithm, which was co-developed by Thales and University of Rennes 1 together with partners from the UK, Canada and the US (IBM, NCC Group and Qualcomm), will become part of the first US and international standard on post-quantum cryptography. In mid-July, the National Institute of Standards and Technology (NIST) selected Falcon for inclusion following a five-year competition. The standard is expected to be finalised by 2024.

The NIST launched the competition in 2017 in a bid to develop a new post-quantum cryptography standard. Of the 82 candidate security protocols, only four made it through the final phase after demonstrating their ability to withstand attacks carried out by quantum computers. The winning algorithms have already been published online and are available royalty-free. Although the standard is being developed in the US, it is expected to serve as a global benchmark.

Falcon is a digital signature algorithm. According to Eric Brier, Chief Technology Officer, Cyber Defence Solutions at Thales, a digital signature “validates the authenticity of a message. It provides assurance that a message hasn’t been altered, and that it has come from a known user. It’s an essential component of any modern communication protocol.” Digital signatures can be used, for instance, to share encrypted communication keys or to authenticate machines on industrial networks.

Quantum apocalypse

Although quantum computers remain little more than prototypes, the risk of a “quantum apocalypse” is very real, according to Pierre-Yves Jolivet, Vice-President, Cyber Defence Solutions at Thales. “We need to start taking this risk seriously now,” says Jolivet. “Some of the data being exchanged today will still be sensitive in 10 years’ time. It could be captured now and decrypted at some point in the future.” In 2013, Thales set up a dedicated laboratory on the Paris-Saclay campus south of the capital in order to counter this threat.

Almost all the security protocols in use today are vulnerable because they solve mathematical problems by large integer factorisation or by calculating discrete logarithms. If a working quantum computer were to fall into the hands of a malicious state or organisation, our existing system of cyber defences could collapse overnight. “Our solution was to dig around for other mathematical problems that even a quantum computer can’t crack, and that would take thousands of years to solve,” explains Brier. At the same time, the algorithm needed to remain watertight against non-quantum attacks.

Embedded systems

But as Brier explains, there is “a whole world” between selecting the right mathematical problem – in this case, Euclidean lattice reduction – and developing a functioning algorithm. “The mathematical problem is crucially important, of course, but it takes a huge amount of work to develop an unbreakable algorithm that can withstand physical attacks yet isn’t too unwieldy to be of practical use to Thales’s customers,” explains Brier. The researchers were particularly interested in making the algorithm compact and frugal enough to be compatible with embedded systems without sacrificing performance – a goal they claim to have achieved. “We’ve obtained a proof of security for Falcon, which means that breaking the algorithm is as hard as breaking the underlying mathematical problem,” adds Brier. In order to demonstrate their robustness, each candidate algorithm was subjected to deliberate attacks by the other teams. “Falcon has come this far because nobody could break it,” says Brier. Having made it through the competition, Falcon could well be appearing in IT security systems around the globe in the coming years.

FURTHER READING

France’s National Agency for Information Systems Security (ANSSI) is warning organisations to start protecting themselves against quantum cyber-attacks now. The new NIST standards will have far-reaching consequences beyond the United States. In a press release issued on 18 July, France’s National Agency for Information Systems Security (ANSSI) acknowledged the global significance of the competition, commending the NIST’s “scientific choice” and confirming that “the four algorithms should now be considered the options of choice in the design of most post-quantum security products.”

“Some of our existing encryptors include versions of post-quantum algorithms and/or are designed for easy implementation of these algorithms,” says Jolivet. With the ANSSI recommending that IT security systems transition to post-quantum cryptography by 2030, Thales is staking out its position as a provider of a soon-to-be essential product. “We made it further through the NIST competition than any of our direct competitors in civil encryption and military cybersecurity,” adds Jolivet. Thales is therefore well-placed to lead from the front in this emerging sector.