ML-KEM + ML-DSA : Fifth PQC Standardization Conference

[yogappu]

Hello,
I was going through the fifth PQC conference notes for ML-KEM and DSA from : https://csrc.nist.gov/events/2024/fifth-pqc-standardization-conference and had doubts/needed confirmation for below points.

1. ML-DSA : Change ExpandMask to use SHAKE output from the beginning rather than at an offset
   • As pointed out by Vadim Lyubashevsky, offset not necessary to prevent SHAKE output bits from being reused

As per https://github.com/open-quantum-safe/liboqs/blob/main/src/sig/ml_dsa/pqcrystals-dilithium-standard_ml-dsa-87-ipd_ref/poly.c#L469, the implementation is more closer to Dilithium spec(Sampling the vectors y section) rather than FIPS 204 Algorithm 28
making SHAKE output to be used without "r" offset. Hence, the implementation for ML-DSA already has the fix. Correct ?

2. ML-KEM : Revert A-matrix indexing (minor but compatibility-breaking change)

This is also taken care here and not as per algorithm 12 and 13 of FIPS203 : https://github.com/open-quantum-safe/liboqs/blob/main/src/kem/kyber/pqcrystals-kyber_kyber768_ref/indcpa.c#L174.
For not-transposed matrix : XOF(p,j,i)
For transposed matrix : XOF(p,i,j)
Correct ?

3. ML-DSA : Fix missing check in HintBitUnpack
   • Check is necessary for Strong Unforgeability (SUF-CMA)

I am not sure about this check ? what is missing currently ?
i could find a similar comment https://github.com/open-quantum-safe/liboqs/blob/main/src/sig/ml_dsa/pqcrystals-dilithium-standard_ml-dsa-65-ipd_ref/packing.c#L223. Is this what is being asked above and what is rationale behind it ?

[dstebila]

Tagging @bhess who is our main link with the PQ Crystals team.

[bhess]

Hi @yogappu: See the "Note on the intermediate values for ML-KEM:" and "Note on the intermediate values for ML-DSA:" in https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/example-files.
It contains some clarifications to the FIPS drafts, which are implemented by the pq-crystals upstream implementation that we use in liboqs. I found that the notes clarify the differences to the spec and liboqs passes the NIST supplied test vector. Please let me know if you found futher differences.

[yogappu]

@bhess i had a look at the link provided. So, as per the above link and also my observations, most of the changes proposed in the 5th PQC conference are already implemented in ml-dsa/kem of liboqs.
Right ?

I could notice a proposed change for ML-DSA, that could be backward incompatible that is yet to be implemented since its recently announced.
Change SampleInBall to take all of 𝑐̃, rather than just the first 256 bits.

Additionally, i had few questions listed below, also mentioned in the link provided by you above:
-In addition, ExpandMask (Algorithm 28) pulls bits from the SHAKE bitstream off the front, rather than rc+1 bits further in the bitstream.
In algorithm 28 of FIPS203,
v ← (H(ρ||n)[32rc],H(ρ||n)[32rc +1],...,H(ρ||n)[32rc +32c −1]
However as per Dilithium, "Sampling the vectors y" section, from the hash output 5 bytes, 2 bytes of y are constructed and so on...
I don't understand why 32rc,32rc+1 offsets are mentioned in FIPS spec (i.e for r = 1,c = 20(for dil3), hash bytes[640,641....] are considered ??)

-ML-DSA : Fix missing check in HintBitUnpack
• Check is necessary for Strong Unforgeability (SUF-CMA)
I am not sure about this check.
i could find a similar comment https://github.com/open-quantum-safe/liboqs/blob/main/src/sig/ml_dsa/pqcrystals-dilithium-standard_ml-dsa-65-ipd_ref/packing.c#L223. what is rationale behind it ?
As per my understanding, during encoding h, the index's stored have to be in increasing order. is this check enough for SUF ?

[bhess]

Hi @yogappu. Thanks for the feedback. NIST also sent a mail in the pqc mailing-list outlining the planned changes to final FIPS204.

I could notice a proposed change for ML-DSA, that could be backward incompatible that is yet to be implemented since its recently announced.
Change SampleInBall to take all of 𝑐̃, rather than just the first 256 bits.

The other change I can see would affect compatibility is the planned domain separation to distinguish ML-DSA and Hash-ML-DSA.

I don't understand why 32rc,32rc+1 offsets are mentioned in FIPS spec

I think this is what is planned to be changed (and already implemented), see the mail linked above: ["... we plan to modify the ExpandMask algorithm so that it takes output bits from the beginning of the SHAKE output rather than at an offset."]

-ML-DSA : Fix missing check in HintBitUnpack
• Check is necessary for Strong Unforgeability (SUF-CMA)
I am not sure about this check.

The original post explaining the need for the check is here: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/TQo-qFbBO1A/m/YcYKjMblAAAJ

[yogappu]

Hi @bhess , Thank you for the answers. Really appreciate it :) . Last set of questions below before I close this discussion, promise :)

So, in conclusion, there are only two changes, of all the changes proposed in 5th PQC, that are not available in current liboqs/ml-dsa/ml-kem, and if implemented would be backward incompatible.

1.Change SampleInBall to take all of 𝑐̃, rather than just the first 256 bits.
2.Domain separation for ML-DSA and PreHash-ML-DSA
i. IMO it impacts only PreHash-ML-DSA as it would get a new API as per https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/JKMh0D0pa30
ii.Pure version would not be impacted and current version could be used.
Agree ?

[bhess]

In my understanding these are the two changes that would affect compatibility to final ML-DSA. For domain separation, the linked mail says "the input string will be modified in order to create domain separation.". It appears to be not finally specified yet, but in the example given for FIPS205, the messages to be signed M' are different.

pure:

construct M' = octet(0) || octet(OLEN(ctx)) || ctx || M

pre-hash:

construct M' = octet(1) || octet(OLEN(ctx)) || ctx || OIDPH || PH(M)

[iambatmanandjoker]

@bhess even for ExpandMask, i have the same doubt
v ← (H(ρ||n)[32rc],H(ρ||n)[32rc +1],...,H(ρ||n)[32rc +32c −1]
As per the public comments ,
The ExpandMask function (Algorithm 28) already uses a different input for SHAKE for every
polynomial. It should thus use the output from the beginning of the hash stream and not start
at an offset (i.e. the r is not needed in the expansion in line 4).
But, is 32c needed too, shoudnt it be just v ← H(ρ||n) ?

[iambatmanandjoker]

@baentsch sorry to pull you to this discussion. do you any idea on the questions here ?

[bhess]

Hi @iambatmanandjoker, NIST indicated ["... we plan to modify the ExpandMask algorithm so that it takes output bits from the beginning of the SHAKE output rather than at an offset."], see https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/y8ul-ZcVWI4/m/k6WPyIdxAQAJ.