The idea: Falcon uses a trapdoor: the private key is a good, short description of an NTRU lattice, and the public key is a bad one that looks random. To sign, hash the message to a target point and use the good description to find a lattice point close to it. The small difference is the signature. With only the bad description, finding a close point is hopeless. The delicate part: the closeness has to be randomized just right (Gaussian sampling), or signatures slowly leak the private key.
Why it matters: Being standardized for uses where size matters most.
Good and bad descriptions of a grid
Both pictures show the same grid of points, described by two different pairs of arrows. To find the grid point nearest the orange target, a simple method is to measure the target in arrow-units and round. With the good arrows that lands on the nearest point. With the bad ones, rounding inside long, skinny cells lands far away. Real lattices have hundreds of dimensions, where no known method finds a good description from a bad one. Falcon's private key is a good description of an NTRU lattice. Its public key is a bad one.
The details
A compact lattice signature, about 666 bytes, built on NTRU lattices with the hash-and-sign paradigm (ROM)[1, 2]. Smaller than ML-DSA, but signing needs careful floating-point Gaussian sampling, which is hard to implement safely. That sampling is what keeps signatures from leaking the key, the flaw that broke the earlier GGH and NTRUSign schemes[3].
Nothing on the map depends on it: it is an end point, something people use directly.
About the tags
ROM
Its security proof treats a hash function as a perfectly random function (the random oracle model). Real hashes aren't random functions, so this is a heuristic. For signatures and encryption no practical attack has exploited it. For multi-round proof systems, see the Fiat-Shamir box.
References
Craig Gentry, Chris Peikert and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. Proceedings of the fortieth annual ACM symposium on Theory of computing, 2008. doi:10.1145/1374376.1374407
Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner and Vadim Lyubashevsky. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. Falcon team, 2020. falcon-sign.info
Phong Q. Nguyen and Oded Regev. Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. Journal of Cryptology, 2009. doi:10.1007/s00145-008-9031-0