Fixed-point FN-DSA and special vs general purpose

[Jeffrey Burdges]

Apologies if this had come up repeatedly..

Bas Westerbaan and Christopher Patton at CloudFlare have a good suggestion for moving forward on FN-DSA here:

https://blog.cloudflare.com/ml-dsa-will-have-to-do/#fn-dsa-small-key-and-signatures-subtle-signing

"NIST could decide to generate the test vectors (CAVP) from the fixed-point arithmetic implementation. That the more risky floating-point implementation wouldn’t pass the test vectors would be a feature, not a bug, as it would steer implementations towards the safer fixed-point version!"

In other words, the standards process should move forward on FN-DSA but simply ignore all the floating point specifications & implementations, and focus exclusively upon a fix-point design.

I believe that blog only mentions one fix-base version in some dynamic language like Python, but presumably one should look at the fix-base implementations by Thomas Pornin instead, like https://github.com/pornin/rust-fn-dsa

As I understand it, this fixed-point code costs maybe 2x what the floating point code costs, so 6x more than ML-DSA signers.

Around the signer time, there is a miss-leading assertion in that CloudFlare blog post that ML-DSA should be viewed as “general purpose” while FN-DSA should be viewed as “special purpose”. This seems backwards.

In TLS, we have a signature that’s checked by only one verifier, but that remains quite a special behaviour that’s somewhat unique to TLS, even Noise avoids this single-verifier signature.

We typically expect signatures are verified much more often than they are signed, so one should really consider the total CPU time, computed as singer_time + verifier_time * E(num_verifiers), when discussing whether a signature is special or general purpose.

Anecdotally, ML-DSA signers take 2.92 x longer than ML-DSA verifiers. According to that blog post, ML-DSA and FN-DSA verifiers need on 0.7 x as long as ML-DSA verifiers, and fixed-point FN-DSA signers take 6 x longer than ML-DSA, so FN-DSA signers need 17.5 x longer than FN-DSA verifiers. If all that’s correct, then FN-DSA becomes cheaper than ML-DSA in total CPU time once we expect 49 verifiers, but maybe 50 is easier to remember here (and my numbers could be wrong).

It’s clear certificates, app signatures, signed git commits, etc all have E(num_verifiers) vastly larger than this threshold of 50, making FN-DSA the clear choice, even ignoring the bandwidth savings.

Signed email provides a fun example here: We transfer the email only a few times, and do not verify the signature in transport, so maybe we ignore the bandwidth savings of FN-DSA. In principle, the verifier need only verify the signature once, but in practice the signature would be verifier every time the mail reader accesses the signature because of how the integration works, and this likely happens many times, so FN-DSA remains optimal in CPU time.

Best,
Jeff

[Tony Arcieri]

Fixed point implementations definitely have desirable properties around not having to understand the constant-time properties of FPUs.

However, a 2X slowdown in signing speed still seems a bit high. Is there any ballpark estimate of how much future improvement might be possible there?

[Christopher Patton]

Hi Jeffrey, all (long time listener, first time caller),

First, credit where credit is due: this was Bas' observation, not mine. Though I of course agree.

It's true that when we say "general purpose" we're putting a lot of weight on TLS. This is because TLS represents the vast majority of signature generations and verifications that we have a role in. We would therefore like a signature that is pretty balanced between public key and signature size and signature and verification time. This is especially true as we move to Merkle Tree Certificates (https://datatracker.ietf.org/group/plants/about/), which will remove all but one public key and one signature for each authenticating party.

That's not to say that FN-DSA doesn't have real use cases, even in TLS. More generally, just because we judge a scheme to be "special purpose" in this blog doesn't mean that scheme lacks an important use case. For example, the multivariate schemes are somewhat flying under the radar right now, but even UOV (big public keys, tiny signatures) could have tons of uses in privacy enhancing technologies. 

Ultimately, the criteria we used in this blog are subjective and heavily informed by our view of the internet. I wouldn't put too much stock into our particular sorting here.

Best,

Chris P.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/FDD70DB7-2F02-4EA2-8584-66DB12BDE970%40gnunet.org.

[Thom Wiggers]

Hi,

Unashamedly plugging some work co-authored by PQShield colleagues, they show that it is possible to fully implement signing for Falcon in fixed point: https://eprint.iacr.org/2026/1531

From the abstract:

>  It is approximately a factor of two slower than the original floating-point \falcon implementation, but achieves a speedup of an order of magnitude compared to emulated floating-point implementations.

This implementation strategy does restrict the set of secret keys that are valid a little bit, so it would be a bummer if NIST would encode requirements that rule out this implementation strategy.

Regards,

Thom Wiggers

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAG2Zi23t1Fj9W0e7j2ReVWZQ%2BGahGBLy6Rjhp-s2kp95nDXoQg%40mail.gmail.com.

[Sebastien Riou]

Fixed point implementations definitely have desirable properties around not having to understand the constant-time properties of FPUs.
However, a 2X slowdown in signing speed still seems a bit high. Is there any ballpark estimate of how much future improvement might be possible there?

This observation is valid on one particular platform. I guess it was something like a pure software implementation running on a laptop machine, with the CPU running at GHz.

Now if you consider other platforms:

- On a Cortex-M33 without FPU, the observation is probably very different and I would be surprised if the fixed point version is the slower one.

- In a pure hardware implementation, I would be surprised if the fixed point version is the slower one

Are my examples 'corner cases' ? I don't think so, they are just harder to program and benchmark than a laptop so they are much less studied. In terms of deployment, their numbers dwarf all laptops (first because in a laptop you are likely to find dozens of Cortex-M33 already).

Anyway the more important point in my opinion, is that those two examples are where performances / footprint "really" matters: they are constrained implementation deployed in systems that last decades. By comparison, the CPU in a laptop or a server is typically only few years old and if perfromances for a particular algorithms are considered not good enough, the next generation tend to offer new instructions to improve the situation (happened with AES, GCM, random numbers...)

Finally, 2X slower on a laptop is probably not noticeable by a human while 2X on a MCU running below 100MHz can be noticeable and a real show stopper in some applications (mass transportation ticketing / access control for example).

 

Best regards,

 

Sebastien Riou

Fellow, Product Security Architecture

PQShield Ltd

 

M:             +33 782 320 285

E:              sebasti...@pqshield.com

W:             www.pqshield.com

On Wed, 12 Aug 2026 at 01:39, Tony Arcieri <bas...@gmail.com> wrote:

Fixed point implementations definitely have desirable properties around not having to understand the constant-time properties of FPUs.

However, a 2X slowdown in signing speed still seems a bit high. Is there any ballpark estimate of how much future improvement might be possible there?

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/e4f966c8-14b9-40e4-b079-7fa7a78a6c49n%40list.nist.gov.

[John Mattsson]

Thanks Thom,

That is great news! The fixed-point approach in [1] is probably the only implementation we would use. If Sebastien Riou is correct [2] that [1] is faster on M3 and in pure hardware, I don't see any reason to include an FP option in FIPS 207.

[1] https://eprint.iacr.org/2026/1531

[2] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/hIZo9htrDww/m/_YlKcrdGDQAJ

Cheers,

John Preuß Mattsson

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/EC60FA0B-17AC-448D-B8D4-59EF854EDBE0%40thomwiggers.nl.

[Bachir Lachguel]

Hi everyone,

I'm one of the co-authors of https://eprint.iacr.org/2026/1531, here is some additional information on our implementation choices.

There are two ways to implement Falcon in floating-point : using native floating-point hardware or using software-emulated floating-point. Software-emulated floating-point is the only possible option on a MCU (like the Cortex-M33).

@Jeffrey: Pornin's implementation uses fixed-point for the key generation, but still uses floating-point for the signing procedure.

 

In our paper we propose two implementation choices for *fixed-point* .

• A "Type 1" that is very easy to specify, as all intermediate variables share the same scaling factor. (@Tony) Our Type 1 implementation in C is 2x slower than native (FPU accelerated) floating-point arithmetic but still faster (8x) than emulated floating-point.

• A "Type 2" that is a bit more involved to specify, but still much simpler than emulated floating-point: each variable has its own, compile-time scaling factor. Type 2 enables smaller machine word sizes than Type 1, resulting in faster performances and less memory. So there is some room for improvement (@Tony). We showcase this implementation strategy here : Type 2 implementation in Python.

Our paper will also be presented at CRYPTO 2026 next week.

Best regards,

Bachir Lachguel

[John Mattsson]

Hi Bachir,

Thank you so much for this work! Do you have any performance estimates for “Type 2”? I would very much encourage research into performance comparisons between “Type 1”, “Type 2”, and floating-point implementations in terms of execution time, energy consumption, gate count on constrained CPUs such as ARM Cortex-M3, as well as in pure hardware. I think this is a research topic of very high practical relevance.

Given previous comments like:

    "I welcome this change, and would like to see all the floating-point operations gone"

    "If you can eliminate all floating point operations from Falcon, I'd be

    very interested in the proposal."

    "Let me start by saying that we do agree that removing FP operations is a good general direction for improvement on embedded platforms."

    “One significant benefit of removing all the FP operation from FALCON would be simplification of its validation process"

    "Reading Do Not Disturb a Sleeping Falcon makes us think about whether FN-DSA should drop floating-point support."

    “Wouldn't it still be better to ditch the Floating Point?”

    "That the more risky floating-point implementation wouldn’t pass the test vectors would be a feature"

I very much expect many comments on FIPS 206 IPD to call for the floating-point option to be removed entirely. After reading [1], my company became much more skeptical of floating-point implementations, and we agree with Cloudflare that floating-point implementations not passing the test vectors would be a feature [2]. After reading [3], I no longer see any reason to allow floating-point signing in FIPS 206.

Cheers,

John Preuß Mattsson

[1] Do Not Disturb a Sleeping Falcon: Floating-Point Error Sensitivity of the Falcon Sampler and Its Consequences

https://eprint.iacr.org/2024/1709

[2] FN-DSA: small key and signatures / subtle signing

https://blog.cloudflare.com/ml-dsa-will-have-to-do/#fn-dsa-small-key-and-signatures-subtle-signing

[3] Toward a Secure Fixed-Point Implementation of the Falcon Signature Scheme

https://eprint.iacr.org/2026/1531

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/b922f22c-0353-4247-a2fb-d38d0c52bd29n%40list.nist.gov.

[Jeffrey Burdges]

> On 12 Aug 2026, at 02:56, Christopher Patton <cpa...@cloudflare.com> wrote:
>
> It's true that when we say "general purpose" we're putting a lot of weight on TLS. This is because TLS represents the vast majority of signature generations and verifications that we have a role in.

It’s clear CloudFlare does mostly TLS handshake signatures, so it’s clear from where you guys were coming. And I’ve no objection to ML-DSA as the TLS handshake signature, since single-verifiers makes FN-DSA expensive. I simply want to push back on the special vs general purpose characterisation, especially since I was quoting you guy. ;)

In fact, the TLS handshake involves only one signing operation, but involves afaik five or more signature verifications by the user’s machine, one for the handshake, and one for the CA, and three or more CT logs. It’s clear the CA and CT logs should be using FN-DSA since each signature is verified many many times. I suppose even submitting the certificate to the CT log system could result in more than the threshold 50 verifications, no? Anyways, the vast majority of classical signature use cases favour FN-DSA like I said before.

Merkle Tree Certificates rock of course. I’d expect the Merkle tree size would often be dictated by the organisation, but Merkle trees cost some bandwidth too. FN-DSA sounds friendlier to smaller Merkle trees.


> On 12 Aug 2026, at 12:12, 'Bachir Lachguel' via pqc-forum <pqc-...@list.nist.gov> wrote:
>
> • A "Type 2" that is a bit more involved to specify, but still much simpler than emulated floating-point: each variable has its own, compile-time scaling factor. Type 2 enables smaller machine word sizes than Type 1, resulting in faster performances and less memory. So there is some room for improvement (@Tony). We showcase this implementation strategy here : Type 2 implementation in Python.

> Our paper will also be presented at CRYPTO 2026 next week.

Ahh, this maybe where I saw that blog or someone citing some python code. Yes, obviously fixed-point sounds preferable, probably I misread Pornin's comments.

Thanks for correction & links!

Best,
Jeff