FALCON: New post-quantum cryptography standard advances data security

Credit card and bank account numbers, medical records, and countless other personal data types are vulnerable during electronic wireless transactions without cryptography. 

And as 5G powers the connected intelligent edge, stimulating the cloud economy with next-level capabilities, secure and private wireless connectivity are more important than ever. Billions of devices are poised to be intelligently connected, which is why Qualcomm Technologies, Inc. helped develop — and the U.S. recently adopted — the FALCON cryptography standard.

Advancing the quantum computing era

Today, the most used cryptographic algorithms are based on complex mathematical problems, such as factoring large numbers, which can take many years on today’s most powerful computers. However, the advent of quantum computing is poised to challenge the status quo.

It’s become clear that the move toward quantum computing will bring substantial changes to our society; specifically, how we define and shape data security and user privacy moving forward. As quantum computing harnesses the laws of quantum mechanics, it changes the ways computers can operate, creating the possibility of solving mathematical problems that are too complex for traditional computers.

There is a high expectation for quantum computing to transform and even disrupt some industries such as finance, global energy and materials, pharmaceuticals, and electronics. For instance, it can offer a powerful electronics industry tool to deal with big challenges like materials development, product design, and smart manufacturing.

Other business matters that can be tackled by quantum computing include:

• optimizing financial portfolios,
• designing efficient logistics networks that mix trucks and cars, and
• training AI to power autonomous vehicles.

These are some of the challenges that traditional computers cannot easily crack but could be solved by a powerful quantum computer.

Quantum computing isn’t a simple speed-up of computers — it makes specific types of operations amazingly faster, while not affecting others. 

Cybersecurity is another example of important industries expected to be impacted by this transformation. Although public key cryptography has historically protected sensitive data in transit and at rest, quantum computers can be used to break even complex public key codes by exploiting the mathematical structure in ways that classical computers are incapable of doing. Therefore, a new generation of quantum-resistant encryption algorithms is needed to avoid potentially catastrophic security breaches worldwide.

Post-quantum cryptography: a new generation of algorithms

The U.S. Department of Commerce’s National Institute of Standards and Technology (NIST) has been supporting the development of such algorithms, also known as post-quantum cryptography algorithms, conducting three rounds of standardization for algorithms that even quantum computers cannot break. The third round began in July 2020 and concluded in July 2022 with NIST's selection of four algorithms.

The algorithms are designed to address two main objectives for which encryption is typically used:

• General encryption: used to protect information exchanged across a public network, such as the case when we access secure websites
• Digital signatures: used for identity authentication, such as the case when we need to verify identities during a digital transaction

For general encryption, NIST has selected the CRYSTALS-KYBER algorithm. Some of its advantages are small encryption keys that two parties can exchange easily, and speed of operation.

NIST has selected three algorithms for digital signatures: CRYSTALS-DILITHIUM, FALCON, and SPHINCS+.

NIST's stringent post-quantum cryptography requirements notably require that digital signature schemes provide Existentially Unforgeable Signatures concerning an Adaptive Chosen Message Attack (EUF-CMA) security. This ensures that an attacker cannot form a signature for a particular message to be validated with a specific public key unless the attacker has already seen a signature for that message and that public key. FALCON and the other finalists successfully provide this property.

Additionally, FALCON provides the smallest signatures and the smallest combined size of signature and public key of any of the finalists. NIST specifically referenced this property, noting that while the DILITHIUM algorithm was chosen for standardization as the preferred signature algorithm due to its use of fewer different mathematical operations during key and signature generation, there are situations where DILITHIUM signatures may be larger than acceptable. In these situations, FALCON is the recommended choice.

Under the hood

FALCON (along with CRYSTALS-DILITHIUM, and CRYSTALS-KYBER) are based on a mathematical problem known as Lattice Reduction. Lattice reduction is one of the best-known post-quantum mathematical hard problems. Cryptographic systems based on lattice reduction have been proposed, and even standardized, since the mid-90s. Lattices in high dimensions have properties that are very useful for security. In particular, you can have a large collection of points in space and not easily be able to find two points which are close to each other.

The secret key for lattice-based cryptography is a set of points that are close to each other. The public key is a set of points that are far apart. Finding the secret key from the public key is difficult, even for quantum computers, because it requires some brute force searching of every possibility, and while quantum computers can speed that up, the speed gains are much less dramatic than for other kinds of public key cryptography. As such, lattice problems have been considered a promising candidate for post-quantum cryptography ever since they were first proposed.

Our commitment to innovation 

All these algorithms were created by experts collaborating from multiple organizations. Specifically, FALCON was developed by a team of researchers working at Qualcomm Technologies, Inc., Brown University, IBM, NCC Group, University of Rennes, and Thales.

FALCON is an innovative digital signature algorithm developed for the quantum computing era that will deliver advanced data security and privacy to users worldwide. It is designed to offer superior protection, compactness, speed, scalability, and memory economy.

At such a critical moment in international cybersecurity, we have been focused on providing meaningful contributions to the innovative next-generation cryptographic standards. As we bring together distributed AI, power-efficient compute, and ubiquitous connectivity at the connected intelligent edge, we’re also addressing the security and privacy challenges of a hyper-connected world by defining and creating new state-of-the-art cryptography solutions in collaboration with industry leaders.

What’s next?

As NIST completes full standardization of post-quantum cryptography algorithms before 2024, we will collaborate with its university and corporate research partners to prepare FALCON-ready technologies and services, enabling customers to begin taking early advantage of the standard's enhanced security ahead of wider global adoption.