Interpretation of PQC Algorithm – FALCON

In 1994, Peter Shor designed an algorithm that can solve Integer Factorization Problem and Discrete Logarithms Problem in polynomial time using a quantum computer, which is a tremendous threat to the world of classical public key systems such as RSA and ECC. Fortunately, quantum computers had not yet emerged at that time. However, with the development of quantum technology, this threat is getting closer and closer. In 2016, NIST initiated a call for proposals for PQC(post-quantum cryptography) standards to resist the threat of quantum. FALCON is a signature algorithm submitted to NIST PQC. In 2022, NIST announced four PQC candidates for standardization, and FALCON is one of them. As stated by NIST, FALCON will be standardized since there may be use cases for which Dilithium(another PQC signature algorithm that has been standardized by NIST) signatures are too large. According to NIST, the draft edition of the FALCON standard will be published at the end of 2024, and the final edition will be available in 2025.

What is FALCON?

FALCON stands for “fast Fourier lattice-based compact signatures over NTRU.” It is a quantum-resistant digital signature algorithm. It is used to detect unauthorized modifications to data and authenticate the identity of the signatory. Signatures generated by FALCON can serve as evidence to prove that the claimed signer indeed signed the document. This property is known as “non-repudiation,” meaning the signer cannot later deny having signed it.

How does FALCON work?

FALCON is an instantiation of the theoretical framework described by Gentry, Peikert and Vaikuntanathan for constructing hash-and-sign lattice-based signature schemes. This framework requires two ingredients: a class of cryptographic lattices and a trapdoor sampler. FALCON signature scheme chooses NTRU lattices and fast Fourier sampling. In a nutshell, the FALCON signature scheme may therefore be described as follows:

FALCON = GPV framework + NTRU lattices + Fast Fourier sampling

Why does FALCON do well?

Compared to other PQC signature algorithms, FALCON is characterized by its compactness, flexibility, and fastness in verification.

First of all, the main design principle of FALCON is compactness, which minimize the sum of public key size and signature size. Indeed, in the level I security, FALCON’s public key length is 897 bytes, which is shorter than that of Dilithium by 415 bytes. And FALCON’s signature length is 666 bytes, which is shorter than that of Dilithium by 1754 bytes. 

Moreover, FALCON is flexible. On one hand, it can be turned into an IBE(Identity-Based Encryption) scheme, the performance of which is orders of magnitude faster than pairing-based IBEs. On the other hand, FALCON can also be turned into a ring signature scheme.

Last but not least, FALCON’s performance in signature verification is good, which is faster than Dilithium.

Parameters of FALCON

FALCON specifies two sets of parameters that address security levels I and V as defined by NIST, as the following table:

Where can FALCON be used?

FALCON has been integrated into many software cryptography libraries, such as OQS(short for Open Quantum Safe), which is a project that aims to support the transition to quantum-resistant cryptography, and has been integrated into the widely used OpenSSL library. With its flexibility, FALCON can be used in the following cases:

About WATCHDATA

Coincidentally, in the same year that Peter Shor designed Shor’s algorithm, 1994, Watchdata was founded. The company began developing information security solutions based on public key cryptosystems. Leveraging its expertise in cryptographic algorithms, digital security, and secure chip operating systems, Watchdata’s product solutions provide identity authentication and transaction security for billions of users worldwide. We closely follow the development of post-quantum cryptographic algorithms, actively plan for the future, and closely monitor standard research and development trends. This ensures that our future product designs can address the security challenges of the quantum computing era, providing customers with cutting-edge support for quantum-resistant algorithms to build a robust digital security protection system.