Falcon/FN-DSA implementation in Rust

[Thomas Pornin]

Hello,

I have made a Falcon/FN-DSA implementation in Rust:
https://github.com/pornin/rust-fn-dsa
https://crates.io/crates/fn-dsa

It's fully open-source (license is basically public domain dedication). Of course it is not _the_ FN-DSA, since the draft standard is not published yet; I will modify the code to align it with the actual standard when it goes live.

The code is both portable and optimized, and meant for seamless integration (e.g. it is "no_std" to be compatible with bare-metal embedded system; it detects CPU support of AVX2 at runtime and fallbacks to non-AVX2 code if necessary). On 64-bit x86 and ARMv8, native floating point support is used; integer emulation is used otherwise. All internal behaviour (in particular rounding) should be strictly identical on all platforms. Performance is about the same as that of C code (keygen is faster because it's the ntrugen implementation; verification is faster because I put some extra AVX2 in there).

Apart from the "original Falcon" behaviour (as per the round 3 submission), I followed a variant that incorporates some recent suggestions: including the public key hash into that which is signed; support of external pre-hashing with proper domain separation (i.e. the use of a hash and the OID of the hash functions are including); support for an arbitrary domain-separation context; regeneration of the 40-byte random nonce in case of a restart during signing. All these seem "obviously fine" (they cannot decrease security) and I mimicked the way it is done in ML-DSA. In any case, as stated above, I'll align with the standard when published.

Thomas

[Thomas Pornin]

I have updated the Rust implementation with more SSE2 (x86 and x86_64), NEON (aarch64) and RISC-V optimizations.

Also, I made a C version of the code. That one is mostly a merge of the original Falcon code with the ntrugen code for keygen (https://github.com/pornin/ntrugen); however, it has been revamped with a new API and should be easier to use from applications (e.g. AVX2 optimizations are now used if support is detected at runtime, but do not prevent the code from running on non-AVX2 hardware). Also, floating-point hardware is used only in the few (common) cases where it is safe (e.g. SSE2 or NEON), with a fallback on integer emulation.
https://github.com/pornin/c-fn-dsa
Same license as the Rust code, this is basically public domain. As with the Rust code, this is all tentative and will be adjusted to match the FN-DSA standard when it gets published (backward compatibility will not be maintained).

Performance of the C code is mostly the same as the Rust code.

Thomas

[Thomas Pornin]

I also made a Go version:
https://github.com/pornin/go-fn-dsa

This is basically the same operations as in the Rust and C codes, but in Go syntax. Go does not support SSE2 or NEON intrinsics so that variant loses a bit on some possible optimizations, but it's still decently fast. For signature generation, hardware floating-point is used on 32-bit x86 (with SSE2), 64-bit x86, ARMv8, and 64-bit RISC-V; otherwise, integer emulation is used.

Together with the Rust and C codes, this should cover most use cases. When the FN-DSA draft comes out, I'll update all three implementations to align them with the specified scheme (right now it is a "prospective FN-DSA").

Thomas