[FALCON OFFICIAL] Keygen implementation

1,667 views
Skip to first unread message

Thomas Pornin

unread,
Feb 13, 2024, 2:45:36 PMFeb 13
to pqc-forum
The Falcon team, after discussing with NIST, envisions to modify the key pair generation implementation method by leveraging the techniques described in https://eprint.iacr.org/2023/290 and used in the HAWK scheme (HAWK is described on https://hawk-sign.info/ and was submitted to the additional round for post-quantum signatures). In a nutshell, the Falcon key pair generation process uses the following:

- The two polynomials f and g are generated with a fixed Gaussian distribution centred on zero. If the vector (f,g) has too large a norm, the process starts over.

- Polynomials F and G that fulfill the NTRU equation (fG - gF = q) are computed and reduced (with Babai's round-off algorithm).

- If suitable F and G cannot be found then the process starts over. A solution can be easily verified to fulfill the equation, so there is no risk of accepting "wrong" (F,G).

In general, for given (f,g), there can be several reduced (F,G) solutions and neither is "more correct" than any other. The initial Falcon proposal uses floating-point operations in the reduction process, which raises some implementation issues with various hardware platforms, and slightly impairs test vector reproducibility since different platforms might apply distinct rounding and fall into a different (F,G) solution. The implementation used in HAWK uses only integer computations, making it much easier to reproduce exactly on many software platforms; it is also faster and uses less RAM. As a consequence, though, it can reject some (f,g) pairs for which suitable (F,G) solutions mathematically exist but are not found by the implementation, leading to regeneration of a new (f,g) pair. The rejection rate is less than 29% (about 8.2% for Falcon-512, 28.5% for Falcon-1024), and thus cannot have an impact on security worse than log_2(1 - 0.29) bits, i.e. we may lose, theoretically, at worst 0.49 bits of security or so. No specific structure is known for key pairs that get rejected, but even if there were, it would not matter much for security.

The current implementation of the HAWK keygen uses the library code available at https://github.com/pornin/ntrugen , which also supports Falcon key pair generation directly. That library implements a second change, which is that the Gaussian distribution table used in the generation of (f,g) uses only 16 bits per entry, instead of 64 bits for the current Falcon code. This also slightly reduces the overall key pair generation time, by using fewer bits from the RNG. It should have no non-negligible impact on security.

The main effect of these changes is that for a given source seed, a different key pair is obtained; however, nothing in the rest of Falcon is modified, and the key pair generation methods are interoperable.

Note that we talk here about producing the (F,G) pair from (f,g); the generation of the Falcon tree is another process which can be considered to be a part of key pair generation, or to be instead a component of signature generation whose cost can be shared among distinct uses of the same key, since the tree depends only on the private key. The Falcon tree generation still uses floating-point operations.

While the proposed change is objectively good from a software engineering perspective (smaller, faster, more reproducible...) and seems innocuous for security, we would welcome any feedback from the community on this subject.

--Thomas Pornin, for the Falcon team

Blumenthal, Uri - 0553 - MITLL

unread,
Feb 13, 2024, 3:05:51 PMFeb 13
to Thomas Pornin, pqc-forum

I welcome this change, and would like to see all the floating-point operations gone, making FALCON more similar to HAWK in that sense.

 

Thanks!

--

V/R,

Uri

 

There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.

The other is to make it so complex there are no obvious deficiencies.

                                                                                                                                     -  C. A. R. Hoare

 

 

From: 'Thomas Pornin' via pqc-forum <pqc-...@list.nist.gov>
Reply-To: Thomas Pornin <por...@bolet.org>
Date: Tuesday, February 13, 2024 at 14:46
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXT] [pqc-forum] [FALCON OFFICIAL] Keygen implementation

 

ZjQcmQRYFpfptBannerEnd

--
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/f2f037b9-a490-4623-9650-fadb3fd6672dn%40list.nist.gov.

Simon Hoerder

unread,
Feb 13, 2024, 3:52:14 PMFeb 13
to pqc-...@list.nist.gov
Hi,

if you can eliminate all floating point operations from Falcon, I'd be
very interested in the proposal.

If only some but not all of the floating points are removed, I struggle
to see appeal though. You'd still be in a situation where no established
leakage analysis and side-channel countermeasures exist for a key part
of the algorithm and deployment options would be as limited as for the
current Falcon spec.

Please correct me if I'm wrong but the changes do sound fairly
extensive. I would very much encourage to produce a full spec and
reference implementation for the proposed changes and then allow a
generous amount of time (1 to 2 years?) for study and analysis. Ideally,
I'd like to see a 3rd party security review, a HW implementation and
research into side-channel security (at least one constant time
implementation, preferably also a masked implementation) and fault
resistance before a final FIPS document is released.

Even with Dilithium the hint unpacking issue was discovered by Mike
Hamburg only after the end of the official comment period. Since we
already* have Dilithium and Sphincs+ I believe there's no need to rush;
better make sure we get this 100% right and provide developers with the
knowledge to roll out high quality implementations.

Best,
Simon

*) The final FIPS documents are not published yet but close enough. For
me that counts as already having the algorithms.

On 13/02/2024 20:45, 'Thomas Pornin' via pqc-forum wrote:
> The Falcon team, after discussing with NIST, envisions to modify the key
> pair generation implementation method by leveraging the techniques
> described in https://eprint.iacr.org/2023/290
> <https://eprint.iacr.org/2023/290> and used in the HAWK scheme (HAWK is
> described on https://hawk-sign.info/ <https://hawk-sign.info/> and was
> --
> 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
> <mailto: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/f2f037b9-a490-4623-9650-fadb3fd6672dn%40list.nist.gov <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/f2f037b9-a490-4623-9650-fadb3fd6672dn%40list.nist.gov?utm_medium=email&utm_source=footer>.

Christine Cloostermans

unread,
Feb 16, 2024, 2:31:09 AMFeb 16
to Simon Hoerder, pqc-...@list.nist.gov

Hi all,

 

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

However, we agree with Simon here: we do not see a (significant) benefit from removing the (partial) FP operations of the key generation of Falcon. 


Key generation is in many cases not even performed on an embedded device.

In many cases, keys are provisioned beforehand and therefore this change would not help with easing Falcon implementation.

Even in the cases where key generation would be performed on chip, the FP operations that remain are still a question mark for side-channel protection.

 

Without removing FP operations from signing (that does not impact performance as grossly as FP to Integer conversion does), we do not see a clear benefit for embedded context.

 

Cheers, on behalf of the NXP PQC team,

 

Christine


Op di 13 feb 2024 om 21:52 schreef Simon Hoerder <si...@hoerder.net>:
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/a589e4f6-4a42-4160-a1ac-edc577222e26%40hoerder.net.

Blumenthal, Uri - 0553 - MITLL

unread,
Feb 16, 2024, 12:09:17 PMFeb 16
to Christine Cloostermans, Simon Hoerder, pqc-...@list.nist.gov

One significant benefit of removing all the FP operation from FALCON would be simplification of its validation process – the fact that validation difficulties are explicitly called out in the NIST reports should tell something.

 

-- 

V/R,

Uri

 

 

From: <pqc-...@list.nist.gov> on behalf of Christine Cloostermans <cvv...@gmail.com>
Date: Friday, February 16, 2024 at 02:31
To: Simon Hoerder <si...@hoerder.net>
Cc: "pqc-...@list.nist.gov" <pqc-...@list.nist.gov>
Subject: [EXT] Re: [pqc-forum] [FALCON OFFICIAL] Keygen implementation

 

Hi all,   Let me start by saying that we do agree that removing FP operations is a good general direction for improvement on embedded platforms. However, we agree with Simon here: we do not see a (significant) benefit from removing the (partial)

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside the Laboratory.

ZjQcmQRYFpfptBannerEnd

Maxime Bros

unread,
Apr 5, 2024, 8:49:31 PMApr 5
to pqc-forum, Blumenthal, Uri - 0553 - MITLL, pqc-...@list.nist.gov, Christine Cloostermans, Simon Hoerder
Dear all,

I hope you’re doing well.

First, we would like to thank the community for the feedback on the potential change in the keygen of Falcon (FN-DSA).
At this moment, NIST’s opinion on this change is not final, but we do lean a little bit towards accepting the modification of replacing Falcon Round 3 NTRUGen procedure by Hawk’s one as mentioned by Thomas’ Pornin in this thread. I will try to explain why in this email.

This change would bring some improvements:


1) Keygen without floating point (provided that the FFT part is done in the signature algorithm, which does not slow signature a lot according to Falcon’s team experiments)

2) Easier to get a constant time keygen

3) Keygen would use less RAM

4) Numerically stable keygen (given a seed, there is no ambiguity on the key a correct implementation will generate)


It is worth noting that these improvements come without impacting the security (as far as we are aware of), and they do not change the signature nor the verification process. In fact, only a small portion of the keygen as specified in the 3rd Round specs would be modified, namely the generation of F and G.
 
Item 4) above addresses validation’s concerns, as raised by Uri, and it is worth noting that besides NIST’s CAVP, testability is a priority for a lot of people / companies / institutions.

The use of floating point in FN-DSA and the challenges it raised could delay by a great deal its adoption, and so even if this tweak only solves the problem partially, we do agree on that, it is still an improvement that one gets almost “for free”.
 
Overall, NIST agrees with Falcon’s Team that this idea sounds reasonable, but we also want to ensure that the community supports the idea!

Thus, we encourage more people to answer on this thread to make sure that we’ve heard as much of the community’s opinion before we make a decision.
 
Feel free to reach out to us during the NIST 5th Standardization Conference as well.
 
Sincerely,
 
Dr. Maxime BROS
(on behalf of the NIST FIPS 206 - FN-DSA Team)

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov.

--
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+unsubscribe@list.nist.gov.

Thomas Pornin

unread,
Apr 11, 2024, 8:49:19 AMApr 11
to pqc-forum, Maxime Bros, Blumenthal, Uri - 0553 - MITLL, pqc-...@list.nist.gov, Christine Cloostermans, Simon Hoerder
In relation to the new Falcon keygen implementation, I have also written a Python equivalent, which outputs the exact same key pairs as the C code, for the same input seed. This is a one-file implementation meant to support tests and debug, in particular printing out intermediate values. It is available there:
Thomas

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

--
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.

Anjan Roy

unread,
Apr 11, 2024, 1:23:04 PMApr 11
to Thomas Pornin, pqc-forum, Maxime Bros, Blumenthal, Uri - 0553 - MITLL, Christine Cloostermans, Simon Hoerder
Dear Thomas,

Thank you very much for making it available.  It'll be very useful.

Regards,
Anjan Roy 

Reply all
Reply to author
Forward
0 new messages