TWFalcon

This repository contains the code accompanying the paper TWFalcon: Triple-Word Arithmetic for Falcon; Giving Falcon the Precision to Fly Securely.

The repository is organised into three folders, each serving a distinct purpose:

• pqm4 — The modified files (only) for the pqm4 benchmarking framework, enabling triple-float arithmetic for FNDSA on ARM Cortex-M4 microcontrollers. These are not the full library, only the changed and added files placed at their correct paths.
• c-fn-dsa-multiple — A full modification of the c-fn-dsa library for testing triple-float arithmetic and analysing floating-point exponent distributions and mu value ranges on a desktop machine.
• c-fn-dsa-precision-test — A full modification of the c-fn-dsa library for computing the numerical precision (absolute and relative error) of the different arithmetic types used in Falcon.

The usage of each folder is described in detail below.

---

Requirements

The dependencies differ per component. Below is an overview of what is needed for each.

pqm4

Tool	Purpose
git	Cloning the pqm4 repository with submodules
arm-none-eabi toolchain (version 13)	Cross-compiling for ARM Cortex-M4 microcontrollers
GNU Make	Building the project
stlink	Flashing binaries to most supported boards
OpenOCD	Flashing binaries to the nucleo-l4r5zi board specifically
pyserial	Reading serial output from the microcontroller

Note: A convenient way to install all of these at once is via nix-shell (see the pqm4 section below).

c-fn-dsa-multiple

Tool	Purpose
GNU Make	Building the executables
clang	Compiling the code

c-fn-dsa-precision-test

Tool	Purpose
GNU Make	Building the executable
clang	Compiling the code
mpfr library (version 4.2)	High-precision floating-point arithmetic
Boehm–Demers–Weiser garbage collector (libgc)	Automatic memory management for mpfr allocations

---

pqm4

This folder contains the modified and added files for the pqm4 repository, targeting ARM Cortex-M4 microcontrollers. It is not a full copy of pqm4, only the changed files at their correct paths. A bash script is included to copy these files into a local checkout of pqm4.

Development environment (nix-shell)

For a reproducible development environment, nix-shell can be used to install all dependencies with the exact versions that were tested. This requires nix to be installed (e.g. apt install nix on Ubuntu):

nix-shell -I nixpkgs=https://github.com/NixOS/nixpkgs/archive/nixos-24.11.tar.gz -p git gcc-arm-embedded-13 gnumake openocd stlink python314 python314Packages.pyserial

Setup

1. Clone the pqm4 repository with all submodules:

git clone --recursive https://github.com/mupq/pqm4.git

2. Check out the tested commit:

cd pqm4
git checkout a24bb4b662016968c19f5e6a0719c9ad530f0286

3. Apply the patches from this repository:

./apply.sh /path/to/pqm4_of_this_git /path/to/pqm4_your_machine

If apply.sh is not marked as executable, first run:

chmod a+x apply.sh

Compilation

The arm-none-eabi toolchain must be installed (available in some Linux package managers as arm-none-eabi-gcc or gcc-arm-none-eabi). The code has been verified to work with version 13 of this toolchain, targeting ARM Cortex-M4.

binutils version warning: The assembly code in this repository requires binutils 2.42-r1 or lower. Using binutils 2.43 or higher causes a breaking change introduced in binutils 2.44, where assembly functions without the .type sym_name, %function directive fail at link time with the following error:

dangerous relocation: unsupported relocation
collect2: error: ld returned 1 exit status

The nix-shell command above installs a known-working environment.

Note: After applying the patches, the pqm4 library only supports FNDSA. Other schemes will not build correctly. Always pass IMPLEMENTATION_PATH explicitly when calling make.

Build with:

make -j4 PLATFORM=your-platform IMPLEMENTATION_PATH=crypto_sign/fndsa_provisional-512/m4f/

Replace your-platform with your target board (e.g. nucleo-l4r5zi), and replace 512 with 1024 to build the 1024-bit variant of FNDSA.

Flashing and running

The build produces two executables: a speed executable and a test executable. The speed executable measures performance by running the implementation many times, while the test executable verifies correctness.

Flash the desired binary to the microcontroller using st-flash:

st-flash write bin/crypto_sign_fndsa_provisional-512_m4f__speed.bin 0x8000000

Replace speed with test in the filename to flash the test executable instead.

This command may require sudo depending on your OS or shell environment.

To read serial output from the device:

python3 hostside/host_unidirectional.py

Note (speed): When running the speed executable, after the initial ========================== line appears, a + will be printed for every signing run. After 100 runs (~10 minutes), the average speed of a full signature and the speed of each individual operation will be printed. When the executable is done, the last line outputted is a single #. The code controlling this output is in mupq/crypto_sign/speed.c.

Note (test): The test executable takes approximately 5 minutes to run all tests. When the executable is done, the last line outputted is a single #. The code controlling this output is in mupq/crypto_sign/test.c.

If you get an error that /dev/ttyUSB0 cannot be opened, the device may be on a different serial port. To find it, run:

ls -l /dev/serial/by-id/

This might show the device mapped to e.g. ttyACM0. Update line 9 of host_unidirectional.py accordingly.

If no serial output appears, try pressing the reset button on the microcontroller, or re-flash the binary.

Build flags

The behaviour of the FNDSA implementation can be controlled through flags in:

/pqm4/crypto_sign/fndsa_provisional-512/m4f/archflags.h

Flag	Description
FNDSA_TW	Enables the triple-float algorithms. When set, uses the hardware FMA instruction rather than an emulated version.
FNDSA_TW_ASM	Enables assembly-optimised triple-float routines. Requires FNDSA_TW to also be enabled.

To use the hardware FMA instruction, also set the FMA_ARMV7 variable in:

/pqm4/mupq/crypto_sign/fndsa_provisional-512/ref/triple_float.h

Note: After changing any flags, run make clean before recompiling, as make does not detect header-level changes automatically.

For all other documentation on building and using pqm4, refer to the pqm4 GitHub page.

---

c-fn-dsa-multiple

This folder is a modification of the c-fn-dsa library (commit 96e3b92c4f1bafa23545388a207954fef1a74c90) that adds support for triple-float arithmetic and tooling to analyse floating-point behaviour.

It provides three executables:

Executable	Description
test_fndsa	Runs correctness tests. Works for both the integer emulated and triple-float implementations.
print_fpr_exponents	Runs a multithreaded program that counts how often each floating-point exponent occurs across a configurable number of signature runs, per operation. Results are saved to a .csv file with columns: operation, exponent, count.
print_mu	Collects the floating-point values of mu across signature runs and saves them to a .csv file, used to determine the range of mu.

Configuration

Flags and parameters are set in inner.h. The required flag values for each executable are:

Executable	FNDSA_TW	PRINT_EXPONENTS	PRINT_MU
test_fndsa	1 or 0	0	0
print_fpr_exponents	0	1	0
print_mu	0	0	1

Note: For test_fndsa, setting FNDSA_TW=1 tests the triple-float implementation; setting it to 0 tests the integer emulated implementation.

Additional parameters can be configured in the respective source files:

print_fpr_exponents.c

Variable	Description
LOG	Set to FNDSA_LOGN_512 or FNDSA_LOGN_1024 to select the algorithm variant.
SIG_RUNS	Number of signature runs to perform.
NUM_THREADS	Number of threads to use.

print_mu.c

Variable	Description
LOG	Set to FNDSA_LOGN_512 or FNDSA_LOGN_1024 to select the algorithm variant.
SIG_RUNS	Number of signature runs to perform.

Development environment (nix-shell)

nix-shell -I nixpkgs=https://github.com/NixOS/nixpkgs/archive/nixos-24.11.tar.gz -p gnumake clang

Building and running

Each executable is built and run with:

make executable_name && ./executable_name

---

c-fn-dsa-precision-test

This folder is a modification of the c-fn-dsa library that computes the numerical precision of the inputs to the Gaussian sampler, reproducing the precision tests referenced in the Falcon specification.

The fpr type has been extended to a struct that simultaneously holds:

• An integer emulated double value
• A real double value
• A triple-float (tw) value
• A high-precision mpfr value (treated as the ground-truth "infinite precision" reference)
• A low-precision mpfr value

All fpr operations are performed for each representation independently. The high-precision mpfr value is used to compute the absolute and relative error of each other representation. All constants are recomputed for the high-precision and triple-float cases.

The error computation and output code is in sign_sampler.c. Only the exponent $e$ of each error value is saved, in the form $0.xxx \cdot 2^{-e}$. The relative error of mu, the absolute error of sigma, and their sum are saved to a .csv file for each arithmetic type.

Dependencies

The mpfr library (version 4.2) and the Boehm–Demers–Weiser garbage collector must be installed. Because mpfr allocates memory that would require invasive changes to free manually, the garbage collector is used to handle cleanup automatically.

The preferred way to install all dependencies is via nix-shell, which installs the exact versions that were tested:

nix-shell -I nixpkgs=https://github.com/NixOS/nixpkgs/archive/nixos-24.11.tar.gz -p gnumake clang boehmgc mpfr

Alternatively, on Debian/Ubuntu, the garbage collector can be installed via apt (mpfr is likely available through your package manager as well):

apt install libgc-dev

Building and running

make print_error_values && ./print_error_values

---

License

This project is licensed under the MIT License. You are free to use, modify, and distribute this software in accordance with the terms of the MIT license.

Third-Party Dependencies

This repository makes use of third-party libraries and code that are licensed under different terms, including Apache-2.0, CC0 and public domain.

Please refer to the individual repositories and their respective LICENSE files for more details. Specifically, all files in the pqm4 folder act as a patch to the repository pqm4 repository, all licenses of this repository still apply.