FIPS 206 Status Update
John Mattsson
Hi,
At the NIST 6th PQC Standardization Conference, Ray Perlner
from NIST presented “FIPS 206 Status Update” and asked for comments:
We discussed this internally and have the following comments:
- "Separate pure/prehash versions"
Does this include both External-μ and HashFN-DSA?
We would like to see External-μ (and would prefer to not have HashFN-DSA, but do not object.
(FN-DSA mandates a SHAKE implementation anyway).
https://keymaterial.net/2024/11/05/hashml-dsa-considered-harmful/
- "Only allows randomized signing"
Is this randomized as in randomized ECDSA that was used in PS3 software signing. Or is it Hedged like in ML-DSA? We hope it is hedged.
- "Includes BUFF transform"
That seems good. Have NIST also incorporated the suggestions in [1]?
Our understanding is that these are needed to prove EUF-CMA security.
We really like that
of the five last signatures NIST have standardized, EdDSA and ML-DSA has SUF-CMA proofs and LMS, XMSS, and SLH-DSA are widely believed to be SUF-CMA.
If possible, we prefer if
NIST do not
standardize anything that is not believed to be SUF-CMA.
We hope ECDSA was the last signature with trivial attacks on SUF-CMA security to ever be standardized.
[1]
https://eprint.iacr.org/2024/1769.pdf
- "Should we add support for key/message-recovery mode?"
Hard to answer without more details such as
how many bytes
could be saved
and what the security properties would be. We found Elliptic Curve Qu-Vanstone Implicit Certificate Scheme (ECQV)
interesting and would likely have investigated using them for constrained IoT if it was not for the PQC migration.
Looking at Falcon, pk seems to be bigger that the signature, so
we assume key recovery would come with significant changes to the sig format
or that only parts of the key is recovered.
We would love to see a more detailed information on this proposal. If FN-DSA signatures could recover several hundred of bytes of information that would be very interesting and would ease the pain of PQC migration for systems with constrained radio.
- "Should we add support for a fixed-point version of signing?"
We would say yes. Reading "Do Not Disturb a Sleeping Falcon" does not inspire trust in using floating-point arithmetic at all. Falcon in a certified cryptographic module is likely fine, but any use of Falcon with an external floating point implementation seems worrisome. Reading "Do Not Disturb a Sleeping Falcon" makes us think about whether FN-DSA should drop floating-point support...
Cheers,
John
John Mattsson
One additional comment is that as several European governments are recommending strength Category 3 or above, it would have been nice with a FN-DSA-768. Products wanting to follow these European recommendations will need to use FN-DSA-1024, which is not so small anymore.
Algorithm Public Key (B) Signature (B) Total (B)
--------------------------------------------------------
Falcon-512 897 666 1563
Falcon-1024 1793 1280 3073
ML-DSA-44 1312 2420 3732
ML-DSA-65 1952 3309 5261
--------------------------------------------------------
Cheers,
John
Phillip Gajland
Regarding the SUF-CMA security of Falcon, in our original analysis, we were unable to prove SUF-CMA security under the standard ring SIS assumption because the norm in the SIS problem was too large.
However, in our new work (which we plan to update on ePrint in the coming days), we now prove the SUF-CMA security under a different assumption. Specifically, the UF-CMA security follows from the one-wayness of the preimage-sampleable trapdoor function, while SUF-CMA security is now based on the second-preimage resistance of this function. Initially, we had attempted to prove SUF-CMA security under the collision resistance.
The assumption we now rely on is a second preimage version of a multi-target inhomogeneous (ring) SIS problem. In this problem, an adversary is given t ISIS targets along with corresponding short preimages. The adversary must then output a second (different) short preimage for one of the targets. Interestingly, we show that this assumption is in fact equivalent to the SUF-CMA security. Specifically, an attack on this assumption would directly imply an attack on the SUF-CMA security of Falcon.
Assuming that this problem is as hard as the standard SIS problem, we show that Falcon-512 provides 113 bits of (S)UF-CMA security, while Falcon-1024 provides 256 bits. By reducing the number of allowed signing queries from 2^64 to 2^58, we can increase the bit security of Falcon-512 to 119 bits.
Regarding the changes introduced in our original analysis, we believe NIST has decided to include them in the upcoming standard. Specifically, the salt will be sampled outside the repeat loop (instead of inside, as in the original specification), and the public key will also be hashed.
Falcon is less flexible than Kyber in terms of its parameter sets because the ring dimension needs to be a power of two. Therefore, Falcon-768 is not a valid parameter set, as 768 is not a power of two. In response to: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/1HXzjlMUU6Y/m/KNSPqC02BgAJ.
Best regards,
Phillip
Quynh Dang
Hi John,
Regarding the SUF-CMA security of Falcon, in our original analysis, we were unable to prove SUF-CMA security under the standard ring SIS assumption because the norm in the SIS problem was too large.
However, in our new work (which we plan to update on ePrint in the coming days), we now prove the SUF-CMA security under a different assumption. Specifically, the UF-CMA security follows from the one-wayness of the preimage-sampleable trapdoor function, while SUF-CMA security is now based on the second-preimage resistance of this function. Initially, we had attempted to prove SUF-CMA security under the collision resistance.
The assumption we now rely on is a second preimage version of a multi-target inhomogeneous (ring) SIS problem. In this problem, an adversary is given t ISIS targets along with corresponding short preimages. The adversary must then output a second (different) short preimage for one of the targets. Interestingly, we show that this assumption is in fact equivalent to the SUF-CMA security. Specifically, an attack on this assumption would directly imply an attack on the SUF-CMA security of Falcon.
Assuming that this problem is as hard as the standard SIS problem, we show that Falcon-512 provides 113 bits of (S)UF-CMA security, while Falcon-1024 provides 256 bits. By reducing the number of allowed signing queries from 2^64 to 2^58, we can increase the bit security of Falcon-512 to 119 bits.
--
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 visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/7fd9d672-1f76-46bb-b732-08b62319ee7cn%40list.nist.gov.
Phillip Gajland
Thanks for your interest.
Unfortunately, further reducing the number of signing queries does not improve the bit security.
For the UF-CMA security of Falcon-512, assuming the starting bit security of the multi-target ISIS instance is 120, then 7 bits are lost due to losses from Rényi divergence arguments. These arguments are particularly sensitive to the number of signing queries. Setting the number of signing queries from 2^64 to 2^58 allows the loss in each of the two required Rényi arguments to be reduced to half a bit, resulting in a total loss of approximately one bit. The SUF-CMA security bound is dominated by the UF-CMA term, so the bit security of Falcon-512 remains effectively the same.
Regards,
Phillip
John Mattsson
Hi Philip,
>we show that Falcon-512 provides 113 bits of (S)UF-CMA security, while Falcon-1024 provides 256 bits.
That is great news. Looking forward to reading your paper. Thanks for sharing!
Cheers,
John
John Mattsson
Hi,
Regarding key and message recovery, I looked at the following references:
[1] https://falcon-sign.info/falcon.pdf
[2] https://csrc.nist.gov/CSRC/media/Presentations/Falcon/images-media/Falcon-April2018.pdf
In [1] (2020) it is stated about message recovery: "It makes the signature twice longer, but allows to entirely recover a message which size is slightly less than half the size of the original signature". This seems to indicate no actual reduction in byte size. Is this interpretation correct?
In [2] (2018) it is specified that a message up n * log q bits can be recovered. I assume this is log2, so ≈ 869 bytes for Falcon-512 and ≈ 1739 bytes for Falcon-1024. The Falcon-1024 parameters from [2] are:
+-------+-----------+------------------+--------------+
| Mode | Classical | Message-recovery | Key-recovery |
+-------+-----------+------------------+--------------+
| |pk| | 1793 | 1793 | 40 |
| |sig| | 1233 | 2466 | 2466 |
+-------+-----------+------------------+--------------+
Assuming [2] is correct, my understanding is that the number of bytes “saved” with message recovery is ≈ min(|m| - 1233, 506) for Falcon-512 and min(|m| - 1233, 506) for Falcon-1024. To avoid increasing overhead for small messages, message recovery should only be used for messages larger than 666/1233 bytes. For messages larger than ≈ 869/1739 bytes, partial message recovery would be necessary. And as of the message is often required to select the correct public key, partial recovery may be needed in such use cases as well.
For Falcon-1024, key recovery would save 520 bytes when both the public key and signature are transmitted together. For Falcon-512, the savings would be ≈ (897 - 666 - 40) = 191 bytes. In constrained applications where size is critical, the public key can often be cached, but saving 191 or 520 bytes per certificate could still be significant in protocols using certificate chains by value.
I don't know how message or key recovery affects security proofs. That the term "key recovery" is used both for attacks and a mode is not optimal.
Cheers,
John
John Mattsson
OLD: ≈ min(|m| - 1233, 506) for Falcon-512
NEW: ≈ min(|m| - 666, 203) for Falcon-512
Vadim Lyubashevsky
Hi,
Regarding key and message recovery, I looked at the following references:
[1] https://falcon-sign.info/falcon.pdf
[2] https://csrc.nist.gov/CSRC/media/Presentations/Falcon/images-media/Falcon-April2018.pdf
In [1] (2020) it is stated about message recovery: "It makes the signature twice longer, but allows to entirely recover a message which size is slightly less than half the size of the original signature". This seems to indicate no actual reduction in byte size. Is this interpretation correct?
Sorry, the statement in the Falcon document doesn't make much sense to me right now. It should say something like, "it makes the signature a little less than twice longer, but allows to entirely recover a message whose size is slightly less than the public key". Working out some numbers, when counting the signature and the message, one could save up to around 210 bytes when using Falcon-512 and 460 bytes when using Falcon-1024. For key recovery, 32 bytes more can be saved when sending the longer signature instead of the public key.
Best,
Vadim
Vadim Lyubashevsky
In [1] (2020) it is stated about message recovery: "It makes the signature twice longer, but allows to entirely recover a message which size is slightly less than half the size of the original signature". This seems to indicate no actual reduction in byte size. Is this interpretation correct?
Sorry, the statement in the Falcon document doesn't make much sense to me right now. It should say something like, "it makes the signature a little less than twice longer, but allows to entirely recover a message whose size is slightly less than the public key".
John Mattsson
Hi,
- Seems to me like the "key recovery" mode as specified in Section 3.12 of the Falcon specification can be implemented as a normal KeyGen(), Sign(), Verify() API, with no changes to the application, and that the code needed on top of the normal variant would be quite small.
+------------ ---+----------------+---------------+-----------+
| Variant | Public Key (B) | Signature (B) | Total (B) |
+----------------+----------------+---------------+-----------+
| FN-DSA-512 | 897 | 666 | 1563 |
| FN-DSA-512-KR | 32 | 1292 | 1324 |
| FN-DSA-1024 | 1793 | 1280 | 3073 |
| FN-DSA-1024-KR | 64 | 2520 | 2584 |
+----------------+----------------+---------------+-----------+
For use cases that always send public keys and signatures together (such as current certificate chains in TLS and IPsec) this alternative KR version lowers overhead (I don't know how it affects security and performance).
- Actually recovering the key h would require a new Recover() API. And to benefit you would have to use the key with normal FN-DSA-512. Would it be ok to use the same key H(h)/h with both FN-DSA-512-KR and FN-DSA-512?
- Vadim Lyubashevsky wrote:
>Working out some numbers, when counting the signature and the message, one could save up to around 210 bytes when using Falcon-512 and 460 bytes when using Falcon-1024.
The message recovery mode seems significantly more complex in practice, you would need several new APIs and significant changes to the application, and unless message recovery is supported by other algorithms, you loose crypto agility. If you have variable length messages you would need to support no message recovery, full message recovery, and partial message recovery. Would it be ok to use the same key h with and without message recovery?
Cheers,
John
Falko Strenzke
- "Separate pure/prehash versions"
Does this include both External-μ and HashFN-DSA? We would like to see External-μ (and would prefer to not have HashFN-DSA, but do not object. (FN-DSA mandates a SHAKE implementation anyway).
The way Falcon is defined requires a pre-hash variant for memory-efficient signature verification for all protocols where the message precedes the signature. This is due to the first step in Falcon's signature verification being
c ← HashToPoint(r∥m, q, n)
This allows message consumption only after seeing the signature. Large messages will have to be completely buffered in pure mode for probably all existing protocols. In LAMPS at least for SLH-DSA, which exhibits the same bottleneck, this was seen as a reason to specify the pre-hash variants as well.
External-µ does not solve this problem in all cases. It only means that the full message may not have to be send to the HSM. Memory-exhaustion of the platform receiving the message is not addressed.
Falko
MTG
AG
Dr. Falko Strenzke
Phone: +49
6151 8000 24
E-Mail: falko.s...@mtg.de
Web: mtg.de
MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
Commercial register: HRB 8901
Register Court: Amtsgericht Darmstadt
Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
Chairman of the Supervisory Board: Dr. Thomas Milde
This email may contain confidential and/or privileged
information. If you are not the correct recipient or have
received this email in error,
please inform the sender immediately and delete this
email.Unauthorised copying or distribution of this email is
not permitted.
Data protection information: Privacy policy