KATs for Validation of Discrepant Signatures of Deterministic Falcon With Floating-Point Errors

[Falcon] has been selected as one of the three post-quantum standardized signature algorithms by NIST. Due to compactness and better overall performance, Falcon is an attractive option in some constraint applications. However, the lattice Gaussian sampling of Falcon is complicated and heavily relies on the floating-point arithmetic, which might bring about some unpredicted issues on its security.

In this work, we mainly focus on the impact of floating-point errors on Falcon. Specifically, we investigate the insecurity of discrepant Falcon signatures for the same syndrome with respect to small floating-point errors. This is well-suited for the case of [Deterministic Falcon].

We observe that the following two sources of discrepant signatures for deterministic variant of Falcon.

• The different computation order for operations in the two signing modes, i.e. "sign_dyn" and "sign_tree"

• The optimized floating-point FMA (Fused Multiply-Add) instructions

More detailed information is given in our paper [Do Not Disturb a Sleeping Falcon: Floating-Point Error Sensitivity of the Falcon Sampler and Its Consequences].

Therefore, we give the KATs (Known-Answer Tests) to perform the "sanity check" for the discrepant signatures in this artifacts.

Experimental Setup

We have tested the codes under the following experimental configurations:

• System : Ubuntu 20.04
• Compilation: GCC 9.4.0

File Composition

We both report the KATs on the discrepant signatures from the reordered operations in two signing modes (dyn and tree) for different implementations (fpemu, fpnative, avx2, avx2_fma) and the optimized FMA instructions. We also evaluate the results for two parameter sets, i.e. n = 512 and n = 1024.

• dyntree
  • fpemu (64-bit unsigned integer emulated floating-point)
  • fpnative (C "double" floating-point type)
  • avx2 (AVX2 instricutions)
  • avx2_fma (AVX2 instructions with FMA)
• fma
  • dyn
  • tree

Note that we just provide the comparisons between "fpemu" and "avx2_fma" for the same signing mode in folder "fma/", since these implementations (fpemu,fpnative,avx2) without FMA instructions will generate the same results.

How to Compile

Automatic Executing

We provide some bash scripts to immediately compile and run the off-the-shelf C codes without having to go to different directories frequently.

$ bash run_dyntree_512.sh
$ bash run_dyntree_1024.sh
$ bash run_fma_512.sh
$ bash run_fma_1024.sh

Manual Executing

We need to note the following points:

• In folder "dyntree/", for the same parameter and the same implementation,

  • the "dyn/" code should be executed before that of "tree/".

• In folder "fma/", for the same parameter and the same signing mode,

  • the code without FMA (fpemu) should be executed before the code enabling FMA (avx2_fma).

---

We use Makefile to compile the C codes. Let us give an example.

1. We open the directory where we want to,

$ cd dyntree/det/1024/fpemu

2. We further enter the next level folder

$ cd dyn/

3. We compile the C codes by using the Makefile of the given implementation

$ make

4. Then we find the executable file to run the program

$ cd build
$ ./PQCgenKAT_sign

5. Then enter the "tree" folder to compile and execute

$ cd ../../tree
$ make
$ cd build 
$ ./PQCgenKAT_sign

6. Finally, we generate the KATs files in the "KAT/" folder at the same directory for "dyn/" and "tree/"

Final KATs

Specifically, we further modified the PQCgenKAT_sign.c source file supported by NIST and might generate three following KATs files in the "KAT/" folder:

• PQCsignKAT_1024.req (the initial request file)
• PQCsignKAT_1024_tmp.rsp (the temporary file)
• PQCsignKAT_1024.rsp (the final respond file)

We can check the discrepant signatures in the final PQCsignKAT_1024.rsp files.

License

These codes are released under the MIT License.