Falcon: A Deep Dive into the Math and Mechanics of a Post-Quantum Signature Scheme
By Sir Roderick Medallon, LHD
Falcon (Fast Fourier Lattice-based Compact Signatures Over NTRU) is a post-quantum cryptographic signature scheme that has garnered significant attention due to its strong security guarantees, compact signature sizes, and efficient performance. This detailed report delves into the mathematical foundations of Falcon, exploring its inner workings and elucidating why it is a promising candidate for securing digital communications in a post-quantum world.
Introduction
The advent of quantum computing poses a significant threat to many of today’s widely used cryptographic systems, particularly those relying on the hardness of factoring large numbers or solving discrete logarithm problems, such as RSA and ECC. These systems are vulnerable to efficient quantum algorithms like Shor’s algorithm, which can solve these problems exponentially faster than classical algorithms.
To address this looming threat, researchers have been actively developing post-quantum cryptography (PQC) algorithms that are resistant to attacks from both classical and quantum computers. Among the various PQC candidates, lattice-based cryptography has emerged as a frontrunner due to its strong security guarantees based on the presumed hardness of well-studied lattice problems, relatively efficient implementations, and the versatility to construct a wide range of cryptographic primitives.
Falcon, a lattice-based signature scheme, stands out for its compact signature and public key sizes, and efficient signing and verification operations. This efficiency is achieved through the use of fast Fourier sampling and NTRU lattices.
Mathematical Foundations
Falcon’s security is rooted in the mathematical study of lattices, which are regular, grid-like structures in multidimensional space. More formally, a lattice is defined as the set of all integer linear combinations of a set of linearly independent vectors called basis vectors. The security of lattice-based cryptography arises from the computational difficulty of solving certain problems related to these lattice structures, even for powerful quantum computers.
Lattice Problems
Several computational problems on lattices serve as the foundation for constructing secure cryptographic schemes. These problems involve finding specific points or vectors within the lattice that satisfy certain conditions. Some of the most important lattice problems include:
- Shortest Vector Problem (SVP): This problem asks to find the shortest non-zero vector in a given lattice.
- Closest Vector Problem (CVP): CVP involves finding the lattice point closest to a given target point that doesn’t necessarily lie on the lattice.
- Shortest Independent Vectors Problem (SIVP): SIVP requires finding a set of linearly independent vectors in a lattice that are as short as possible.
- Learning with Errors (LWE): LWE involves distinguishing between a set of noisy linear equations and a set of truly uniform ones.
Falcon’s security specifically relies on the hardness of the Short Integer Solution (SIS) problem over NTRU lattices. This problem is believed to be computationally infeasible even for quantum computers.
NTRU Lattices
Falcon utilizes NTRU lattices, a special type of lattice with unique properties that make them suitable for cryptographic applications. These lattices are defined by a ring of polynomials with integer coefficients modulo a polynomial ɸ (typically xn + 1 or xn – xn/2 + 1) and a prime modulus q.
Fast Fourier Sampling
Falcon employs fast Fourier sampling, a technique that allows for efficient generation of short vectors in the lattice. This contributes to the scheme’s speed and compactness.
Falcon Signature Scheme
Falcon is a hash-and-sign signature scheme, meaning that the message to be signed is first hashed, and then the signature is generated based on the hash value. The scheme can be broken down into three main procedures: key generation, signature generation, and signature verification.
Key Generation
The key generation process involves generating a private key and a corresponding public key.
- Private Key: The private key consists of two polynomials, f and g, with small coefficients, sampled from a discrete Gaussian distribution. These polynomials must satisfy the NTRU equation: fG – gF = q mod ɸ, where F and G are polynomials found using the NTRUGen algorithm 1.
- Public Key: The public key h is derived from the private key elements as h = gf⁻¹ mod ɸ mod q 2.
Signature Generation
The signature generation process takes a message and the private key as input and produces a signature.
- Hashing: The message to be signed is first hashed along with a random salt r to generate a challenge point c 1.
- Sampling: Using the private key (f, g, F, G) and a fast Fourier transform (FFT), a short vector s is generated that satisfies a specific relationship with the challenge point c and the public key h 1.
- Compression: This vector s is then compressed to produce the final signature.
Signature Verification
The signature verification process takes a message, the signature, and the public key as input and verifies the authenticity of the signature.
- Hashing: The verifier uses the public key h, the received signature, and the hashed message to recompute a vector and check if it satisfies the required properties 2.
Security of Falcon
Falcon’s security relies on the hardness of the Short Integer Solution (SIS) problem over NTRU lattices 3. This problem is believed to be computationally infeasible even for quantum computers. The use of fast Fourier sampling and NTRU lattices further enhances the security of the scheme by making it more difficult for attackers to find short vectors in the lattice.
Advantages of Falcon
Falcon offers several advantages that make it a compelling choice for post-quantum signature schemes:
- Compactness: Falcon boasts small signature and public key sizes, making it suitable for bandwidth-constrained environments 4.
- Efficiency: Fast Fourier sampling enables efficient signature generation and verification 4.
- Post-quantum security: The underlying SIS problem is resistant to known quantum algorithms.
Challenges and Considerations
While Falcon offers numerous benefits, there are also some challenges and considerations associated with its implementation and use:
- Implementation Complexity: Falcon’s use of floating-point arithmetic and recursive functions can pose challenges for hardware implementation 2.
- Potential for Side-Channel Attacks: The reliance on floating-point arithmetic may introduce vulnerabilities to side-channel attacks that exploit information leakage during computations 3.
Conclusion
Falcon is a promising post-quantum signature scheme that offers a compelling combination of security, efficiency, and compactness. Its use of NTRU lattices and fast Fourier sampling makes it a strong contender in the post-quantum cryptography landscape. While there are some challenges associated with its implementation, ongoing research and development efforts are addressing these issues and further improving the efficiency and security of Falcon. As the transition to post-quantum cryptography becomes increasingly critical, Falcon is poised to play a significant role in securing digital communications in a world with quantum computers.
References
5 Lyubashevsky, V., Peikert, C., & Regev, O. (2010). On ideal lattices and learning with errors over rings. In Annual International Conference1 on the Theory and Applications of Cryptographic Techniques (pp. 1-23). Springer, Berlin, Heidelberg. 6 Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.2 SIAM review, 41(2), 303-332. 7 Peikert, C. (2016). A decade of lattice cryptography. Foundations and Trends® in Theoretical Computer Science, 10(4), 283-424. 8 Micciancio, D., & Regev, O. (2009). Lattice-based cryptography. In Post-quantum cryptography (pp. 147-191). Springer,3 Berlin, Heidelberg. 9 Prest, T., Fouque, P. A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., … & Zhang, Z. (2020, November). Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 373-403). Springer, Cham. 10 Bernstein, D. J., Buchmann, J., & Dahmen, E. (Eds.). (2009). Post-quantum cryptography. Springer Science & Business Media. 11 Nguyen, P. Q., & Vallée, B. (Eds.). (2010). The LLL algorithm: Survey and applications. Springer Science & Business Media. 12 Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6), 1-40. 13 Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008). Trapdoors for hard lattices and new cryptographic constructions.4 In Proceedings of the fortieth annual5 ACM symposium on Theory of computing (pp. 197-206). 14 Chillotti, I., Gama, N., Georgieva, M., & Izabachène, M. (2020). TFHE: fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1), 34-91. 15 Ducas, L., Durmus, A., Lepoint, T., & Lyubashevsky, V. (2013, August). Lattice signatures and bimodal Gaussians. In Annual Cryptology Conference (pp. 40-56). Springer,6 Berlin, Heidelberg. 16 Alagic, G., Alperin-Sheriff, J., Apon, D., Cooper, D., Dang, Q., Liu, Y. K., … & Whyte, W. (2020). Status report on the second round of the NIST post-quantum cryptography standardization process (No. NISTIR 8309). US Department of Commerce, National Institute of Standards and Technology. 17 Peikert, C. (2014, August). Lattice cryptography for the internet. In International Workshop on Post-Quantum Cryptography (pp. 197-219). Springer, Cham. 18 Hoffstein, J., Pipher, J., Silverman, J. H., & Whyte, W. (2017). NTRUEncrypt. In Encyclopedia of Cryptography and Security (pp. 858-861). Springer, Boston, MA. 19 Goldreich, O., Goldwasser, S., & Halevi, S. (1997, May). Public-key cryptosystems from lattice reduction problems. In Annual International Cryptology Conference (pp. 112-131).7 Springer, Berlin, Heidelberg. 20 Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J. H., & Whyte, W. (2003). NTRUSign: Digital signatures using the NTRU lattice. In Cryptographers’ Track at the RSA Conference (pp. 122-140).8 Springer, Berlin, Heidelberg. 21 Hoffstein, J., Pipher, J., & Silverman, J. H. (1998). NTRU: A ring-based public key cryptosystem. In Algorithmic number9 theory (pp. 267-288). Springer, Berlin, Heidelberg. 22 Albrecht, M. R., Chase, M., Chen, H., Ding, J., Goldreich, O., Gorbunov, S., … & Zhang, B. (2019). Homomorphic encryption security standard. In Homomorphic Encryption Standardization. 23 NIST. (2022). Post-Quantum Cryptography Standardization. Retrieved from https://csrc.nist.gov/Projects/post-quantum-cryptography 24 Prest, T., Fouque, P.-A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Ricosset, T., Seiler, G., Whyte, W., & Zhang, Z. (2020). Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 373–403). Springer, Cham. 1 Pornin, T. (2020). New efficient, constant-time implementations of Falcon. IACR Cryptol. ePrint Arch., 2020, 1378. 2 Fouque, P.-A., Kirchner, P., Pornin, T., & Tibouchi, M. (2022). Faster AVX2 optimized NTT multiplication for Ring-LWE lattice cryptography. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(3), 39–68. 3 Bruinderink, L. G., Hülsing, A., Lange, T., & Yarom, Y. (2016, August). Flush, Gauss, and reload—A cache attack on the BLISS lattice-based signature scheme. In International Conference on Cryptographic Hardware10 and Embedded Systems (pp. 323–345). Springer, Berlin, Heidelberg. 4 Chuengsatiansup, C., Prest, T., Stebila, D., & Tibouchi, M. (2023). FALCON Down Under: Side-Channel Analysis of FALCON Signatures on ARM Cortex-M4. In International Conference on Practice and Theory in Public-Key Cryptography (pp. 180–204). Springer, Cham.
JOIN US
Sign up to receive occasional news from Rod.