Hi all,
After discussion among ourselves and with the Dilithium team, we plan to make the following changes from version 3.1 of the Dilithium spec (https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf ) to our MLWE-sig standard based on Dilithium:
Please let us know if you have any comments or objections regarding these proposed changes.
Ray Perlner (on behalf of the NIST PQC team)
After discussion among ourselves and with the Dilithium team, we plan to make the following changes from version 3.1 of the Dilithium spec (https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf ) to our MLWE-sig standard based on Dilithium:
- In order to support hedged signing, we plan to replace line 12 in Figure 4 in version 3.1 of the Dilithium spec. with “rho' ß H(K | rnd | mu)” where rnd is either "" in the deterministic case or a random 512-bit string in the randomized one. (Hedged signing was discussed in earlier PQC-Forum messages. The basic idea is that the use of the private key in deriving the per-signature randomness rho’ provides robustness against a bad RNG, as in deterministic signing, but in hedged signing additional fresh randomness is included in the computation of rho’, so it will be easier to avoid side-channel pitfalls that can arise with completely deterministic signatures.)
- In order to make sure the argument for the BUFF security of Dilithium given in section 6.1 of https://eprint.iacr.org/2020/1525.pdf holds for all security strength categories, we plan to increase the size of the variable tr (which first appears at line 7 of Figure 4 in version 3.1 of the Dilithium spec.) from 256 bits to 512 bits.
- In order to make sure the argument for the BUFF security of Dilithium given in section 6.1 of https://eprint.iacr.org/2020/1525.pdf holds for all security strength categories, we plan to increase the size of the variable tr (which first appears at line 7 of Figure 4 in version 3.1 of the Dilithium spec.) from 256 bits to 512 bits.
This seems reasonable. However, the specification could be clarified to state that "tr" is a 512-bit SHAKE-256 of the public key, which has been serialized into bytes as specified in the Dilithium specification itself. ( Some in IETF etc. have even proposed non-standard encodings for Dilithium public keys without realizing that both signature generation and verification would then require re-serialization of public keys into this format. )
Hi Ray (and Markku, all),
We would like to have your feedback on an alternatives proposal for Dilithium signing, which is a bit orthogonal to what you are currently advocating for with the hedged approach (protection against bad randomness, single API / easy testing).
Sampling y
directly from a randomness source has significant performance and memory
requirements benefits for very constrained devices, which include a good
randomness source, e.g., according to SP 800-90 A/B/C.
It would
remove the need for most of the masked Keccak operations and provide more
flexibility for masked implementations, e.g., share-wise generation of y.
The output
is indistinguishable from the randomized hedged version, and security is no
less assuming the provided randomness is cryptographically secure.
In fact,
the side-channel leakage is actually reduced with respect to the hedged version
since no leakage on masked Keccak for rho’ and y is obtained.
More
benchmark details are provided in our eprint [1] and presentation at RWC23 [2].
We
understand that it would not be the best fit for default Dilithium, as not all
platforms include a good randomness source.
However,
the benefits for platforms that have this feature seem significant enough to us
to consider it for inclusion in the standard.
NIST
mentioned before that some standards will get Special Publications with further
implementation details, e.g., small SPHINCS+.
So if it
cannot be part of the main draft, is it possible to consider the
fully-randomized version as a Special Publication?
Best
regards
Tobias
[1]
https://eprint.iacr.org/2022/1406
[2]
https://iacr.org/submit/files/slides/2023/rwc/rwc2023/68/slides.pdf
Hi Markku,
I think cryptographic specifications would generally benefit from enabling such a testing mode as you propose. That could be realized by parametrizing each function which uses randomness with a randomness source. The latter can then be a deterministic PRNG and used for testing with a specific seed. In normal usage, it might be a TRNG or a TRNG-driven (seeded) PRNG. In that latter case, one can also specify the optimal way of hedging against weaknesses in the underlying TRNG, namely by additionally seeding the PRNG with the input message to be signed or encrypted. This would for example make some "static-IV" constructions for encryption unnecessary.
The only downside of such a standardization approach that I see is the complexity and overhead it creates for defining the interface and behaviour of the generic randomness source. That would probably only be worthwhile if it finds broad agreement across standardization bodies, so that implementers have to understand a single "randomness source framework".
In any case I think that independently from the very general
idea, for the PQC schemes a standardized testing mode is
necessary.
- Falko
--
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/CA%2BiU_qneV1zj0vHaSXMQTNYZtO9ofRR%2Bw9TS9_zs6e1zEXxx0Q%40mail.gmail.com.
MTG AG
Dr. Falko Strenzke
Executive System Architect
Phone: +49
6151 8000 24
E-Mail: falko.s...@mtg.de
Web: mtg.de
MTG Exhibitions – See you in 2023
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
Dear Tobias,
We agree that on some platforms, it could be useful to bypass the XOF in generating private randomness for Dilithium. However, I don't think it would be feasible to include this option in the FIPS. It seems to me that in order to give a testable specification for a version of Dilithium that makes separate calls to a RBG when the submitted version uses the output of SHAKE with a private seed, there'd need to be fairly extensive rewriting of the specification and code, separate KATs etc. which would need significant vetting and might slow standardization down.
A separate SP later may be possible. To be clear, though, I don’t think we would be able to specify a version of Dilithium that would directly access the entropy source, since this would go against the existing guidance of SP 800-90. To quote from the abstract of SP 800-90b which specifies entropy sources:
"This Recommendation specifies the design principles and requirements for the entropy sources used by Random Bit Generators, and the tests for the validation of entropy sources. These entropy sources are intended to be combined with Deterministic Random Bit Generator mechanisms that are specified in SP 800-90A to construct Random Bit Generators, as specified in SP 800-90C."
I take it the idea would be to allow implementations of Dilithium to replace the XOF with many separate calls to a DRBG, with the understanding that the DRBG is reseeded with fresh entropy often enough that side channel protections aren’t needed on the DRBG.
Best,
Ray Perlner
Hi Ray,
We acknowledge the additional complexity that this feature (or any change at this point) brings, and would of course not want to risk slowing down standardization.
On the other hand, we cannot overstate the impact this feature will have on the security (much less leakage on the very sensitive y), efficiency (masked SHA3 is much slower than a DRBG) and complexity (less need for *fast* masked SHA3 software/hardware) of secure embedded systems.
We believe it involves only a minor change to the specification/implementation.
I have attached a diff file to enable this change in the Dilithium reference implementation [A].
This is just to demonstrate that functionally there is little change needed.
The KAT files can be generated without any changes to the framework, they can be generated by running “make; PQCgenKAT_sign2” for example.
For convenience, I have also attached them.
Of course, we will leave it up to you to decide whether it makes sense for FIPS or SP.
As to your second point, the proposal is indeed to replace the SHAKE pseudo-randomness with a SP 800-90C certified DRBG, not with output from a TRNG directly.
This would mean that y is generated from the same source as seedbuf in key generation, and rhoprime in sign (for the current randomized version).
Kind regards,
Joost (on behalf of the NXP team)
[A] https://github.com/pq-crystals/dilithium/tree/master/ref, commit 3e9b9f1412f6c7435dbeb4e10692ea58f181ee51
From: 'Perlner, Ray A. (Fed)' via pqc-forum <pqc-...@list.nist.gov>
Sent: Tuesday, May 2, 2023 7:58 PM
To: Tobias Schneider <to.schn...@gmail.com>; pqc-forum <pqc-...@list.nist.gov>
Cc: Markku-Juhani O. Saarinen <mjos....@gmail.com>
Subject: [EXT] [pqc-forum] RE: Planned changes to the Dilithium spec.
Caution: This is an external email. Please take care when clicking links or opening attachments. When in doubt, report the message using the 'Report this email' button |
--
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/DM6PR09MB48551286C1575593C7A5FE2D9C6F9%40DM6PR09MB4855.namprd09.prod.outlook.com.
Hi all,
we support the suggestions of Markku to use a fixed size "rnd" that is either random or a fixed value for the mentioned reasons (simplified testing with a unified API and reduced reason to view the variants as two different algorithms). To prevent vendors from needing to support both variants and their vastly different requirements regarding physical security (e.g. the hard fault protection of deterministic Dilithium: https://eprint.iacr.org/2018/355.pdf), we would welcome a wording in the standard making it clear that supporting either variant is sufficient and that the selection can be implementation specific, even not visible to the user.
Additionally, we propose to set the length of rnd to 256 bits. This way, all inputs to H fit into a single block, while security properties are not negatively affected.
Cheers,
Peter (on behalf of the Infineon PQC Team)
---------- Forwarded message ---------
From: Markku-Juhani O. Saarinen <mjos....@gmail.com>
Date: Fri, Apr 21, 2023 at 9:49 AM
Subject: [pqc-forum] Re: Planned changes to the Dilithium spec.
To: pqc-forum <pqc-...@list.nist.gov>
Cc: Perlner, Ray A. (Fed) <ray.p...@nist.gov>
On Thursday, April 20, 2023 at 11:06:43 PM UTC+2 Perlner, Ray A. (Fed) wrote:
After discussion among ourselves and with the Dilithium team, we plan to make the following changes from version 3.1 of the Dilithium spec (https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf ) to our MLWE-sig standard based on Dilithium:
1. In order to support hedged signing, we plan to replace line 12 in Figure 4 in version 3.1 of the Dilithium spec. with “rho' ß H(K | rnd | mu)” where rnd is either "" in the deterministic case or a random 512-bit string in the randomized one. (Hedged signing was discussed in earlier PQC-Forum messages. The basic idea is that the use of the private key in deriving the per-signature randomness rho’ provides robustness against a bad RNG, as in deterministic signing, but in hedged signing additional fresh randomness is included in the computation of rho’, so it will be easier to avoid side-channel pitfalls that can arise with completely deterministic signatures.)
Hi,
In our public comments on draft FIPS 204, we (Ericsson) also requested that NIST clarify exactly which additional security properties beyond unforgeability that ML-KEM satisfy (if any). I would expect NIST to do so in the final version.
I don't see any need to make an erratum for IR 8413. It is a status report for an ongoing standardization project. I think it might even be beneficial to leave it alone as a historical document.
Cheers,
John
--
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/20240221114536.845256.qmail%40cr.yp.to.