Selected Algorithm 2022 OFFICIAL COMMENT: FALCON

[Bros, Maxime P. (IntlAssoc)]

Dear all,

 

I hope you’re doing well.

 

We would like to thank the community for the feedback on the potential change in the keygen of Falcon (NIST FIPS 206 – FN-DSA) that we received in the email thread about this, and during our 5th Standardization Conference in Rockville, Maryland.

 

From this feedback and our internal discussions, we have decided to accept the change which consists of replacing a part of Falcon keygen with the equivalent part of Hawk’s keygen to avoid using floating-point arithmetic. Namely, we will change only the Reduce() algorithm in NTRUSolve() which will allow implementations to use fixed-point instead of floating-point as described in [1]. Please note that using fixed-point in the signing process would require too much memory (roughly 256 bits per value), thus it will not be considered.

 

In addition to this change, after extensive internal discussions and communications with the Falcon team, we decided to allow the use of emulated floating-point as specified in the Falcon reference implementation and in [2]. More precisely, it means that FIPS 206 will allow one to use native or emulated floating-point for the signing algorithm. Please note that the fixed-point (as previously mentioned) for the keygen will be a possibility, not a requirement. This means that one could generate the key AND sign using only emulated or native floating-point.

 

This choice was made to give more freedom to the implementers with respect to the side-channel resistance since emulated floating-point does have disadvantages, but unlike native floating-point it is more likely to be constant time as noted in [2].

However, we encourage the community to keep researching ways to implement side-channel-resistant floating-point.

 

Last but not least, in FIPS 206, the generation of the Falcon’s tree will be part of the signing process by default, but we will also allow it to be precomputed / stored with the private key as an option.

 

While this is our current plan for FIPS 206, we encourage feedback from the community.

 

Sincerely,

 

Dr. Maxime BROS

(on behalf of the NIST FIPS 206 - FN-DSA Team)

 

[1] “Improved Key Pair Generation for Falcon, BAT and Hawk”, Thomas Pornin, 2023,

https://eprint.iacr.org/2023/290.pdf

[2] “New Efficient, Constant-Time Implementations of Falcon”, Thomas Pornin, 2019,

https://eprint.iacr.org/2019/893.pdf

[Scott Fluhrer (sfluhrer)]

You note that you could use either floating point or fixed point in the key generation.

 

Does that mean that they both define the same transform “random coins -> public/private key pair”.  Or, there are essentially two different key generation algorithms (and both are acceptable)?

--
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 on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/SJ0PR09MB96039CA15DE8C0A38E891C699DDB2%40SJ0PR09MB9603.namprd09.prod.outlook.com.

[Vincent Hwang]

Dear NIST,

Recently, it is shown that the emulated floating-point arithmetic does not behave as claimed in [1], see https://eprint.iacr.org/2024/321. The good news is that it doesn't affect the complex FFT in the signature generation of Falcon with suitable range analysis. But this work only analyzes the FFT and not the full signature generation.

Should we regard the C implementation with double as the spec or the one with the emulated floating-point arithmetic as the spec?

Perhaps there are no distinctions in the context of Falcon, but currently, there is no rigorous justification between the double implementation and the emulated floating-point implementation.

Thanks,

Vincent Hwang

--

[Thomas Pornin]

It's the second case: the two keygen algorithms are different, in that from the same seed (more specifically, from the same (f,g) polynomials) you may get different key pairs (there are multiple solutions (F,G) for a given (f,g) pair, and they are not trivially derived from each other), but none of them is better or worse than the others, as far as security is concerned.

In fact there are many keygen algorithms here. The formal description is a single reduction operation which formally uses infinite precision, but practically speaking there is no infinite that fits in a computer, and in fact you'll more or less need to perform multiple passes of reduction, with a limited-precision implementation, to gradually reduce the (F,G) candidate with regard to (f,g). In the code as was submitted with Falcon, IEEE754 binary64 values are used (i.e. the usual "double" type) and multiple passes are applied, each being assumed to skim off about 25 bits from the polynomial coefficients; this already diverges from the strict formal description of Reduce(), since it does not use infinite precision and there can always be some threshold effects which make the reduction end up with a different (but still valid) solution. In the "new code" (ntrugen library, used in Hawk, also applicable to Falcon and BAT), a fixed-point 64-bit representation is used instead, which makes things a lot faster on low-end hardware without a FPU, but also leads to again different (but valid) solutions.

Thomas

[Thomas Pornin]

As far as I know, the implementation is not the spec. The spec is the spec. It seems to me that NIST is not usually providing reference implementations, only specifications (as PDF documents) and test vectors. The existing implementation of Falcon is part of the submission, not of the specification. This is also the dynamic we can observe with other algorithms, e.g. Kyber and Dilithium, where (as far as I know) the last submitted algorithm and the current (draft) spec differ on a couple of details.

When NIST publishes a draft specification I'll adjust the existing C code to match it and make a not-really-reference-but-still-close-enough implementation, since in practice it can be expected that people wanting to use the algorithm will first go for some existing code, so there should be a reasonably reusable implementation somewhere. Ideally I'll also make a Rust or Go implementation, too.

Thomas

[Олена Качко]

Hello all!

We implemented the calculation of the digital signature using a fixed point representation (total data size of 64 bits, consisting of: 1 bit for the sign, 37 bits for the integer part, and 26 bits for the fractional part).

We applied this implementation to the first 100 keys of the author's implementation for n=1024. All signatures were successfully verified for both calculation options (dynamic and pre-tree calculation).

The size of the digital signature after packing, excluding the nonce, message for the signature, and additional two bytes for the length, varies as follows:

• For double data: 1154 to 1165 bytes
• For fixed point data: 1229 to 1243 bytes

The increase in the length of the digital signature does not exceed 7%. Since 64 bits were used for the polynomial coefficient assignment, the memory size for the polynomial assignment does not depend on the data type (double or fixed point).

To create the digital signature, the author's algorithm was used, which excludes arithmetic for data with a fixed point, thus not requiring additional memory when using a fixed point representation.

Thanks

Olena Kachko

Yuri Gorbenko

https://iit.com.ua/

вт, 9 июл. 2024 г. в 12:50, 'Thomas Pornin' via pqc-forum <pqc-...@list.nist.gov>:

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/b4c2b872-a72a-43ea-9b30-9d412a59e374n%40list.nist.gov.