Falcon#
Falcon (Fast-Fourier Lattice-based Compact Signatures over NTRU) is a hash-and-sign lattice-based signature scheme. It is based on the GPV framework instantiated over NTRU lattices and a new technique called “fast Fourier sampling”.
Falcon was designed with the idea of compactness: the objective was to minimize \(|pk| + |sig|\), the bit-size of the public key and the signature. So lattice-based signatures were chosen using the hash-and-sign GPV framework [GPV08]. This framework was chosen due to the proofs that it is secure in the classical Random Oracle Model under the SIS assumption [GPV08] (adapted for NTRU lattices) and in the Quantum Random Oracle Model [BDF+10].
This framework requires two ingredients: a class of lattices and a trapdoor sampler. The class of lattices chosen for Falcon are the NTRU lattices introduced in [HPS98]. They have the advantages of providing a compact instantiation of GPV [DLP14], as their structure reduces the size of the public key, of speeding up many operations, and [SS13] showed that GPV with NTRU can be used in a provably secure way.
The second ingredient is the trapdoor sampler, which takes as input a matrix \(\boldsymbol{A}\), a trapdoor \(T\), and a target \(\boldsymbol{c}\) and returns a short vector \(\boldsymbol{s}\) such that \(\boldsymbol{s}^t \boldsymbol{A} = c \mod q\). The trapdoor sampler used in Falcon is the one introduced in [DP16], “fast Fourier nearest plane”[1] which can be randomized to provide a trapdoor sampler that combines the security of the most secure sampler (Klein’s algorithm [Kle00]) with the efficiency the fastest generic trapdoor sampler (Peikert’s [Pei10]) while being compatible with NTRU lattices.
An important parameter is the standard deviation \(\sigma\). If it’s too low it may leak the secret basis, and if it’s too high the vectors returned are not optimally short. The fast Fourier sampler shares similarities with Klein’s, including the optimal value \(\sigma\). Following [Pre17], \(\sigma = \eta_{\epsilon}(\mathbb{Z}_{2n}) \cdot \| {B}_{GS} \|\).
Parameters#
Parameter set |
NIST level |
Ring degree \(n\) |
Modulus \(q\) |
Standard deviation \(\sigma\) |
\(\sigma_{\min}\) |
\(\sigma_{\max}\) |
Max. signature square norm \(\lfloor \beta^2 \rfloor\) |
|---|---|---|---|---|---|---|---|
Falcon-512 |
1 |
512 |
12289 |
165.736617183 |
1.277833697 |
1.8205 |
34 034 726 |
Falcon-1024 |
5 |
1024 |
12289 |
168.388571447 |
1.298280334 |
1.8205 |
70 265 242 |
Parameter set |
Public key |
Signature |
|---|---|---|
Falcon-512 |
897 |
666 |
Falcon-1024 |
1793 |
1280 |
Implementations#
The reference implementation can be found in the Resources section of the homepage. There is a browsable version and a source code archive.
There is also a Python implementation done by Thomas Prest, one of the authors.
An implementation can be found in the submission package, though it differs from the current version.
Falcon is integrated in PQclean. It includes an AVX2-optimized version.
An ARM Cortex-M4 version is available in the pqm4 library.
Note
It seems that the reference implementation does not follow NIST’s API notes.
Benchmarks#
The following benchmarks were obtained with the speed program provided in the reference implementation, running on an Intel i7-8565u.
The time are all in microseconds, except for the key generation which is in milliseconds.
CT indicates that the operations use a constant-time version of hash-to-point.
Parameter set |
Key generation |
Sign |
Sign CT |
Sign with expanded key |
Sign with expanded key CT |
Verify |
Verify CT |
|---|---|---|---|---|---|---|---|
512 |
7.92 |
357.83 |
374.78 |
239.96 |
252.36 |
32.84 |
56.11 |
1024 |
25.43 |
700.00 |
721.45 |
456.85 |
534.86 |
83.26 |
117.59 |
A benchmark is also available on Falcon’s homepage.
Attacks#
The paper includes a section called Security in which known attacks are listed. Among them we find:
Key recovery using lattice reduction with, for example, DBKZ [MW16].
An overview of how to forge signature using Kannan’s embedding with a sieve algorithm is given. This example is used to calculate the estimated bit security of the two levels based on [BDGL16], [Laa16], and [ADPS15].
There are a number of side-channel attacks that have been published:
Improved Power Analysis Attacks on Falcon, [ZLYW23].
FALCON Down: Breaking FALCON Post-Quantum Signature Scheme through Side-Channel Attacks, [KA21].
There is a presentation which gives an overview of how the attack works.
A Differential Fault Attack against Deterministic Falcon Signatures, [BS23].
Bibliography#
Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key exchange - a new hope. Cryptology ePrint Archive, Paper 2015/1092, 2015. https://eprint.iacr.org/2015/1092. URL: https://eprint.iacr.org/2015/1092.
Sven Bauer and Fabrizio De Santis. A differential fault attack against deterministic falcon signatures. Cryptology ePrint Archive, Paper 2023/422, 2023. https://eprint.iacr.org/2023/422. URL: https://eprint.iacr.org/2023/422.
Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 10–24. Society for Industrial and Applied Mathematics, January 2016. URL: http://epubs.siam.org/doi/10.1137/1.9781611974331.ch2 (visited on 2023-07-20), doi:10.1137/1.9781611974331.ch2.
Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. Cryptology ePrint Archive, Paper 2010/428, 2010. https://eprint.iacr.org/2010/428. URL: https://eprint.iacr.org/2010/428.
Léo Ducas and Thomas Prest. Fast fourier orthogonalization. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '16, 191–198. New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2930889.2930923, doi:10.1145/2930889.2930923.
Léo Ducas, Vadim Lyubashevsky, and Thomas Prest. Efficient Identity-Based Encryption over NTRU Lattices. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology - ASIACRYPT 2014, volume 8874, pages 22–41. Springer Berlin Heidelberg, Berlin, Heidelberg, 2014. URL: http://link.springer.com/10.1007/978-3-662-45608-8_2 (visited on 2023-07-18), doi:10.1007/978-3-662-45608-8_2.
Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, 197–206. Victoria British Columbia Canada, May 2008. ACM. URL: https://dl.acm.org/doi/10.1145/1374376.1374407 (visited on 2023-07-18), doi:10.1145/1374376.1374407.
Emre Karabulut and Aydin Aysu. Falcon down: breaking falcon post-quantum signature scheme through side-channel attacks. In 2021 58th ACM/IEEE Design Automation Conference (DAC), volume, 691–696. Dec 2021. doi:10.1109/DAC18074.2021.9586131.
Philip Klein. Finding the closest lattice vector when it's unusually close. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '00, 937–941. USA, 2000. Society for Industrial and Applied Mathematics.
Thijs Laarhoven. Search problems in cryptography: from fingerprinting to lattice sieving. PhD thesis, Mathematics and Computer Science, February 2016. Proefschrift.
Daniele Micciancio and Michael Walter. Practical, Predictable Lattice Basis Reduction. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016, volume 9665, pages 820–849. Springer Berlin Heidelberg, Berlin, Heidelberg, 2016. URL: http://link.springer.com/10.1007/978-3-662-49890-3_31 (visited on 2023-07-20), doi:10.1007/978-3-662-49890-3_31.
Chris Peikert. An efficient and parallel gaussian sampler for lattices. Cryptology ePrint Archive, Paper 2010/088, 2010. https://eprint.iacr.org/2010/088. URL: https://eprint.iacr.org/2010/088.
Thomas Prest. Sharper bounds in lattice-based cryptography using the rényi divergence. Cryptology ePrint Archive, Paper 2017/480, 2017. https://eprint.iacr.org/2017/480. URL: https://eprint.iacr.org/2017/480.
Damien Stehlé and Ron Steinfeld. Making ntruencrypt and ntrusign as secure as standard worst-case problems over ideal lattices. Cryptology ePrint Archive, Paper 2013/004, 2013. https://eprint.iacr.org/2013/004. URL: https://eprint.iacr.org/2013/004.
Shiduo Zhang, Xiuhan Lin, Yang Yu, and Weijia Wang. Improved power analysis attacks on falcon. Cryptology ePrint Archive, Paper 2023/224, 2023. https://eprint.iacr.org/2023/224. URL: https://eprint.iacr.org/2023/224.