How important is the implementation difficulty of FN-DSA?

I’ve heard a lot about how FN-DSA is difficult to implement, but I’m wondering about what impact this will have in practice. Is this a critical issue, or is it just another thing to overcome?

On one hand, I could imagine FN-DSA taking longer than the other schemes to implement and test properly, but ultimately still coming out secure at the end. On the other hand, I could see bad implementations resulting in digital assets gated behind FN-DSA public keys that have lower entropy than expected.

What do you think?

2 Likes

The reason why I believe FALCON (and cryptography that relies on floating point numbers generally) won’t be widely adopted is that it’s impractical despite being better in theory.

First, the vast majority of other cryptographic schemes rely on discrete arithmetic. There’s a very large body of academic work evaluating those schemes, and many experts who can review them. Understanding whether or not their securely implemented is much more straightforward.

Floating point cryptography is novel and requires extra steps (like sampling), that even smart people have a hard time understanding the correctness of (see this post). And a predecessor to Falcon (NTRUSign) was eventually broken due to side-channel vulnerabilities not directly related to floating points, but the flawed sampling approach implemented in NTRUSign.

Second, unlike ints, floats and floating point operations are handled differently across different hardware architectures. That means even more complexity implementing it to be general across multiple platforms, and the associated costs with needing expertise in floating point arithmetic across EACH platform that you expect to deploy on.

Third, and a consequence of the first two points, is that the accumulated complexity is a barrier to adoption. Sure, FALCON is a little smaller and a little faster than ML-DSA. But the relative complexity of the latter means that I could see it being integrated into standard libraries and audited codebases (upon which others rely) much faster. Most secure deployments will rely on vetted implementations in standard libraries like BoringSSL, OpenSSL, or NaCl. Due to FALCON’s fragility, these libraries will be far more cautious about integrating it broadly, especially across mobile and embedded platforms.

And even if FALCON makes it into core libraries, each downstream project must ensure platform-specific correctness and side-channel resistance. That’s a recurring cost, especially compared to a signature scheme like (SLH|ML)-DSA that’s easier to sandbox and audit.

An instructive historical parallel is the adoption of TCP/IP over the OSI standard. TCP/IP was a more pragmatic design than the more complex and theoretical OSI model. The OSI model was developed by a large committee and was often seen as too cumbersome, while TCP/IP on the other hand was much simpler and easier to implement, and now the whole internet runs on it.

In conclusion, FALCON is an interesting an novel construct that MAY be needed if the other schemes are broken. But given the novelty of the underlying trapdoor assumptions as well as the added complexity of floating points that it brings I would be very surprised if it ever ends up being used outside of very niche settings, where it then competes with other novel approaches (that may also ultimately be standardized) like MPC or isogeny-based crypto.

5 Likes

Exactly, FALCON is a promising theoretical advancement in post-quantum cryptography, but its implementation complexity—from sampling and floating-point handling to the lack of standard libraries—makes it not yet ready for widespread adoption. Meanwhile, algorithms like ML-DSA, which are simpler and easier to audit, are more likely to be deployed sooner and offer better practical security.

2 Likes

That’s my view. I’d be curious for anyone to weigh in on what exactly are the niche use cases that Falcon serves which justifies the additional cost and complexity. But due to the issues I raised above, I think it’s likely that they aren’t in widely deployed systems.

FWIW most blockchains disallow floating point at some level because different CPU architectures can get slightly different results, which can break consensus.

Also, the keygen step is non-deterministic. It can be made deterministic, but that is not currently part of the spec, which is a minus IMO.

2 Likes

Dustin Moody (NIST) just said that the current draft for FN-DSA includes a fixed-point version:

Regarding your specific questions, our current draft includes tweaks to the Gaussian sampler in Keygen made in consultation with the Falcon team, including an allowance for fixed point arithmetic – it’s not identical to either the original Falcon submission or to HAWK, though.