Question about Ahat_transposed in ML-KEM / Kyber

[Simon Hoerder]

Hi,

in the old Kyber spec
(https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf)
line 6 of Algorithm 5, KYBER.CPAPKE.Enc() specifies:
Ahat_transposed[i][j] := Parse(XOF(rho,i,j))

In the new FIPS 203 draft for ML-KEM
(https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf) line 6 of
Algorithm 13, K-PKE.Encrypt() specifies:
Ahat[i][j] := SampleNTT(XOF(rho, i, j))

In both specs line 19, where Ahat_transposed is actually used, specifies:
u := NTTinv(Ahat_transposed * rhat)) + e1

I'm wondering whether I'm missing something but this seems like a
compatibility-breaking change that doesn't affect security and/or
functionality. Unfortunately I'm a little too tired to trusted my own
research at the moment but as far as I can see:
* XOF is completely independent of the Ahat_transposed vs Ahat
question.
* Parse() is the same as SampleNTT() so doesn't affect the
Ahat_transposed vs Ahat question.
* Operator precedence in the original spec is (Ahat_transposed)[i][j],
not (Ahat[i][j])_transposed.

Can someone clarify, please?

Thanks,
Simon

[Dang, Quynh H. (Fed)]

Hi Simon,

Missing the hat (transposed) in the line 6 of Algorithm 13, , K-PKE.Encrypt() as a typo. I just looked at a version on 5/8/2023 I have, the transpose was there.

Thank you for catching the typo!

Regards,
Quynh.

--
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/b68af9d3-8aee-f775-67b5-4f4b71a44269%40hoerder.net.

[D. J. Bernstein]

'Dang, Quynh H. (Fed)' via pqc-forum writes:
> Missing the hat (transposed) in the line 6 of Algorithm 13, ,
> K-PKE.Encrypt() as a typo. I just looked at a version on 5/8/2023 I
> have, the transpose was there.

I suggest adding the following validation process: before releasing the
next spec, go line by line through translating that spec into Sage, and
test whether SUPERCOP checksums for the resulting Sage code match the
SUPERCOP checksums produced by C implementations. Reusable Sage code to
generate SUPERCOP checksums is already available from

https://classic.mceliece.org/mceliece-sage-20221023/test-checksums.sage

and was already tested as part of the current Classic McEliece spec
going through the same process before it was released.

Hashes of NIST KAT *.rsp files can be used the same way as SUPERCOP
checksums here, but SUPERCOP checksums have the advantage of testing
modified ciphertexts, increasing the chance that bugs are caught. Either
way would have worked for this particular Ahat_transposed bug, and both
approaches are much less labor-intensive than full formal verification.

Having a computer-comprehensible version of a spec also opens up the
possibility of declaring that this version _is_ the spec. This has many
advantages, perhaps the most important being to encourage cryptanalysis
of the specified cryptosystems. Currently cryptanalysts doing their own
translations into software, or attacking preexisting software, are often
met with responses saying that what was attacked isn't actually the
specified cryptosystem; other people don't have a push-button way to see
who's right. Such disputes create an incentive for fake attacks, while
making it harder for correct attacks to receive proper recognition.

---D. J. Bernstein

[Dang, Quynh H. (Fed)]

Hi Simon,

After taking a closer look, I think the PKE in our draft is compatible (the same) with the PKE in Kyber's 3rd round spec.

In the Kyber's 3rd round spec, A[index_1][index_2] with index_1 being the row and index_2 being the column in its key gen and the matrix A is generated by one row at a time. In our draft spec, it is the other way around: index_1 being the column and index_2 being the row and the matrix A is generated by one column at a time. However, the order of index_1 and index_2 in the input of the XOF is reversed in each other, so the matrix A is the same in both documents. To see this, let's take a look at the matrix M 2x2 (k = 2) below and the entries in M are the inputs to the XOF to generate the matrix A's entries.

P||0||0 p||1||0
(M)
P||0||1 p||1||1

The matrix M is the same in both documents.

In Algorithm 5 (encryption) in the 3rd round Kyber, the order of index_1 and index_2 in the input of the XOF is reversed from its key generation (Algorithm 4), so the output at the step 6 is the transpose of the matrix A, not the matrix A, the transpose of A is produced directly from Parse(XOF()) (no separate transpose operation happen here). This transpose is used as is in step 19 (no further transpose happens here either).

In our draft, Algorithm 13 (Encrypt), the step 6 produces the matrix A (not its transpose). The transpose happens at step 19.

Both documents use column vectors, so the dot product between a matrix and a vector is the same. So, the 2 PKEs are compatible (the same): produce the same output for key gen, encrypt and decrypt.

The elegance of the Kyber's 3rd round spec is that the transpose of A is generated directly at step 6 in encryption (no transpose ever happens), in comparison with our draft.

We specified the dot product on page 10 including how to do (A_hat_Transposed (dot) u_hat) by using A_hat (not A_hat_Transposed). Therefore, the matrix A is not required to get transposed at step 19 in Algorithm 13 in our draft.

However, the rules for the dot product between (A_hat (dot) u_hat) and (A_hat_Transposed (dot) u_hat) are different (see page 10 of our draft). Therefore, many implementors would likely do a transpose operation at the step 19 to avoid having 2 different functions for the dot product: one for A_hat and the other for A_hat_Transposed. They would just write code for (a matrix (dot) a vector) only (the line for w_hat on page 10 of our draft). They would not need to write code for the operation at the line y_hat. They would use a transpose operation for A before doing the dot product if they follow our draft spec.

In order to avoid the unnecessary transpose operation in our draft, we would need the change the order of index_1 and index_2 in the input at step 6 in Algorithm 13 (Encrypt), for example, B <--- SamepleNTT(XOF(p,j,i)) and call B the transpose of A, then replace A_hat_Transposed by B at step 19. This way avoids all the confusion about what dot product to use and whether or not to do a transpose operation when there is a transpose symbol.

Please let me know if something is not clear or wrong!

Thank you and Regards,

Quynh.

> -----Original Message-----
> From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of
> Simon Hoerder
> Sent: Monday, August 28, 2023 4:01 PM
> To: pqc-forum <pqc-...@list.nist.gov>
> Subject: [pqc-forum] Question about Ahat_transposed in ML-KEM / Kyber
>

> Hi,
>
> in the old Kyber spec

> (https://gcc02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fpq-
> crystals.org%2Fkyber%2Fdata%2Fkyber-specification-round3-
> 20210804.pdf&data=05%7C01%7Cquynh.dang%40nist.gov%7Cb1c7925f8bc84
> 6272fdb08dba80192e9%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7
> C638288496953253002%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAw
> MDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%
> 7C&sdata=9u4p4b5GZRWZiUc%2FpM%2FZuvT9ip6DyZ1DWFbZjDA7ojM%3D
> &reserved=0)

[Robin Larrieu]

Hello Quynh,

I wish to revive this topic since it appeared again during a discussion
with Kris Kwiatkowski about test vectors.
Unlike what you say in your latest message, it seems that the PKE are
NOT compatible between the FIPS-203 draft (as it is currently written)
and Kyber's Round 3 spec.

In the draft standard, line 6 of algorithm 12 -- K-PKE.KeyGen() reads:
  Ahat[i,j] <- SampleNTT(XOF(ρ, i, j))
and line 6 of algorithm 13 -- K-PKE.Encrypt() reads again
  Ahat[i,j] <- SampleNTT(XOF(ρ, i, j))

On the other hand, in the Kyber Round 3 spec, line 6 of algorithm 4 --
Kyber.CPAPKE.KeyGen() reads
  Ahat[i,j] := Parse(XOF(ρ, j, i))
and line 6 of algorithm 5 -- Kyber.CPAPKE.Enc() reads
  Ahat_transpose[i,j] := Parse(XOF(ρ, i, j))

So clearly the indices are swapped between the two specifications. This
mismatch could have several interpretations:

a) In your first response on this thread, you suggested that there was a
typo and a "transpose" may be missing in K-PKE.Encrypt(). If that is so,
then the indices must be swapped in K-PKE.KeyGen() so that the scheme
remains mathematically correct. This would indeed make the draft
equivalent to Kyber's spec.
This would also be consistent with the convention chosen for FIPS-204,
where line 3 of algorithm 26 -- ExpandA reads:
  Ahat[r,s] <- RejNTTPoly(ρ||IntegerToBits(s, 8)||IntegerToBits(r, 8)).

b) In your second response, you suggested that A[index_1, index_2] could
in fact mean that index_1 is the column and index_2 is the row. This
would again make the draft equivalent to Kyber's Spec.
However, this notation would be inconsistent with the formulas in page
10 for linear algebra. For this reason, I highly doubt that this
interpretation is correct, but it shows that confusion is possible even
with rather standard notation. I thus suggest to add an entry in section
"2.3 Mathematical Symbols" to define explicitly the notation A[i,j] as
"the element in row i and column j of matrix A" (and do the same in
FIPS-204) so there is no ambiguity.

c) One could decide that the current version of the draft is correct. In
this case NIST should mention this change in section "1.3 Differences
From the CRYSTALS-KYBER Submission" to avoid any confusion.

Since this question is crucial for interoperability, could you please
clarify which of these interpretations is correct ?
Let me mention that the test vectors recently published by Kris
Kwiatkowski and Roderic Chapman are assuming interpretation c).

Best regards,
Robin Larrieu

[Dang, Quynh H. (Fed)]

Hi Robin,

See my comment below.

> -----Original Message-----
> From: Robin Larrieu <robin....@cryptonext-security.com>
> Sent: Thursday, October 19, 2023 12:47 PM
> To: Dang, Quynh H. (Fed) <quynh...@nist.gov>; pqc-forum <pqc-
> fo...@list.nist.gov>
> Subject: Re: [pqc-forum] Question about Ahat_transposed in ML-KEM /
> Kyber
>

[Dang, Quynh H. (Fed)] You are right here. I looked at the second equation instead of the first to determine which index was row when I wrote the second email. Personally, I intended to be compliant with the Kyber's 3rd round.

> %2F&data=05%7C01%7Cquynh.dang%40nist.gov%7Cc2d0040aa97a4c1c9ae90
> 8dbd
> >>
> 0c31831%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C63833330858
> 69508
> >>
> 57%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luM
> zIiLCJBTi
> >>
> I6Ik1haWwiLCJXVCI6Mn0%3D%7C2000%7C%7C%7C&sdata=TcpODmDnoXZu
> mfgbrC%2BX
> >> 3onvNO%2BZiCui3oXLXPFvCh8%3D&reserved=0

[Paul Duncan]

Hi Robin and Quynh,

The indices are swapped between K-PKE.Encrypt() in the FIPS 203 draft
and Kyber.CPAPKE.Enc() in the the round 3 Kyber specification, but they
are compatible with one another because the "A hat" matrix is referenced
as "A hat transposed" on line 19 of K-PKE.Encrypt() in the FIPS 203
draft.

That said, I agree that the FIPS 203 draft is confusing as-is, and I
think it should be updated to make things clearer.

Specifically, I think NIST should make the following changes on
line 6 of K-PKE.Encrypt() in FIPS 203:

1. Swap the positions of the i and j parameters to XOF().
2. Change "A hat" to "A hat transposed".

If NIST is unwilling to make that change to K-PKE.Encrypt(), then I
prefer your option (c); add a note to the changes from Kyber pointing
out that the indices have been swapped on line 6 and that the "A hat"
matrix needs to be transposed on line 19.

Thanks,

> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/90287153-0cf3-4751-829f-379c068151df%40cryptonext-security.com.

--
Paul Duncan <pa...@pablotron.org>
https://pablotron.org/

[Paul Duncan]

Hi Robin,

My mistake, I see what you are saying now: the indices are swapped
in KeyGen() between the two specifications.

The parameters to XOF() on line 6 of K-PKE.KeyGen() in the FIPS 203
draft are (rho, row, column), while the parameters to XOF() on line 6 of
Kyber.CPAPKE.KeyGen() in the round 3 Kyber specification are (rho,
column, row).

So FIPS 203 draft and Kyber round 3 specification are both internally
consistent with themselves, but, as you said, the parameters to XOF()
in KeyGen() are swapped relative to each other.

Sorry about the confusion.

Separate from the incompatibility that you are pointing out, I do still
think that NIST should change "A hat" to A hat transpose" and "XOF(rho,
i, j) to "XOF(rho, j, i)" on line 6 of K-PKE.Encrypt() in the FIPS 203
draft.

Thanks,

> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/ZTGHZ0vIlqClM6Rz%40u3.home.

[Bobby McGee]

The "changes" in FIPS 203 were made to make things clearer, i.e. each of the two samplings is generation of NTT(A), done the same way, with the transpose put in the appropriate place.  I think it's an improvement to have line 6 of both key gen and encryption read

6: Aˆ [i, j] ← SampleNTT(XOF(ρ, i, j))

and someone at NIST though so too.  If you know how the algorithm works and why the transpose is there, it's not like you're going to accidentally forget it.

[Robin Larrieu]

Bobby,

This thread brings several issues together and it is easy to get
confused, so let me try to clarify.

Le 20/10/2023 à 16:43, Bobby McGee a écrit :
> The "changes" in FIPS 203 were made to make things clearer, i.e. each
> of the two samplings is generation of NTT(A), done the same way, with
> the transpose put in the appropriate place.  I think it's an
> improvement to have line 6 of both key gen and encryption read
>
> 6: Aˆ [i, j] ← SampleNTT(XOF(ρ, i, j))
>
> and someone at NIST though so too.  If you know how the algorithm
> works and why the transpose is there, it's not like you're going to
> accidentally forget it.

I agree with you that dropping the transpose in line 6 makes things
clearer in the sense that the sampling is now obviously done the same
way in KeyGen and Encrypt.
However, the real issue is that the row/column indices are swapped in
the input of XOF compared to Kyber, making the two schemes incompatible
with each other.
More precisely, each coefficient of A is generated (both in KeyGen and
Encrypt):
- from the output of XOF(rho, row, column) in the FIPS-203 draft
- from the output of XOF(rho, column, row) in the Kyber specification.

To be honest, I was focused on the transposition, thought everything was
fine, and I missed this index swap at first. Several responses in this
thread seem to show that I am not the only one.

Summarizing, as said by Paul Duncan earlier, "FIPS 203 draft and Kyber

round 3 specification are both internally consistent with themselves,

but not with each other".
As an additional issue, this change was not mentioned in section "1.3
Differences From the CRYSTALS-KYBER Submission"; this means someone
trying to patch an existing Kyber implementation could easily miss that,
and get an implementation that would NOT be interoperable with compliant
implementations.
So:
- if this change is intentional, it should be mentioned in section 1.3
- if not, the indices should be swapped (both in KeyGen and Encrypt) to
maintain compatibility with the Kyber spec.

Discussion with Quynh Dang reached the conclusion that this change was
most likely a typo, and that the initial intent was to keep the same
underlying PKE for Kyber and ML-KEM. I was then encouraged to submit an
official comment (included below for reference) to
fips-203...@nist.gov in order to formally raise the issue.

Best regards,
Robin Larrieu


> Dear NIST,
>
> The PQC-forum group had a discussion about the generation of the
> public matrix A in ML-KEM that does not match what was done in the
> Kyber submission.
> See the thread "[pqc-forum] Question about Ahat_transposed in ML-KEM /
> Kyber".
> Recall that in ML-KEM, the matrix A is generated in NTT representation
> by deterministically expanding a pseudo-random string from a seed and
> the row/column indices. Specifically, the coefficient in row i and
> column j of the matrix A, denoted Ahat[i,j] is generated:
> - from the output of XOF(rho, i, j) in the FIPS-203 draft
> - from the output of XOF(rho, j, i) in the Kyber submission
>
> Notice that the row/column indices in the input of XOF are swapped in
> FIPS-203 compared to the Kyber submission. According to Dang, Quynh H.
> (Fed) <quynh...@nist.gov>, this mismatch is unintentional, and the
> underlying PKE should have been the same in ML-KEM and Kyber.
> - Assuming this is the case, there are a few changes to do in the
> description of algorithms 12 -- K-PKE.KeyGen() and 13 --
> K-PKE.Encrypt() as proposed below.
> - If this change was in fact intentional, the difference should be
> mentioned in section "1.3 Differences From the CRYSTALS-KYBER
> Submission" (and the rest of this email can be ignored).
>
>
> # Changes required in algorithm 12 -- K-PKE.KeyGen():
>
> Indices i,j must be swapped in the input of XOF, that is rewrite line
> 6 as
>   Ahat[i,j] <- SampleNTT(XOF(ρ, j, i))
> instead of

>   Ahat[i,j] <- SampleNTT(XOF(ρ, i, j))
>
>

> # Changes required in algorithm 13 -- K-PKE.Encrypt()
>
> For correctness of the scheme, generation of matrix Ahat must be done
> in a compatible way with what is done in KeyGen. Due to the
> multiplication by Ahat_transpose in line 19, there are several
> possible presentations that make sense, each with their own advantages
> and disadvantages. Here are the main possibilities that I can think of
>
> 1) Simply swap the indices as in KeyGen, that is
> - rewrite line 6 as Ahat[i,j] <- SampleNTT(XOF(ρ, j, i))
>
> 2) Sample directly the transpose of Ahat, using either of the two
> options:
> 2.a) as in the Kyber specification
> - rewrite line 6 as Ahat_transpose[i,j] <- SampleNTT(XOF(ρ, i, j))
>
> 2.b) using an auxiliary notation Bhat for Ahat_transpose:
> - rewrite the comment in line 4 as "re-generate matrix A in [snip], by
> its transpose Bhat=Ahat_transpose"
> - rewrite line 6 as:  Bhat[i,j] <- SampleNTT(XOF(ρ, i, j))
> - rewrite line 19 as:  u <- NTT^(-1)( * r) + e1
>
> 3) Use left-multiplication in line 19
> - rewrite line 6 as Ahat[i,j] <- SampleNTT(XOF(ρ, j, i))
> - rewrite line 19 as:  u <- NTT^(-1)(r_hat * Ahat) + e1
> - rewrite line 21 as:  v <- NTT^(-1)(r_hat * t_hat) + e2 + mu
>
>
> # Advantages and disadvantages of each option (personal opinion)
>
> Option 1) makes it clear that generation of matrix Ahat is done in the
> same way in KeyGen and Encrypt.
> On the other hand, this means implementers must be careful of the
> transpose in line 19 (u <- NTT^(-1)(Ahat_transpose * r) + e1). Recall
> that page 10 gives the formula for a multiplication of the form yhat =
> Ahat_transpose * uhat, so this is well defined.
>
> Option 2) corresponds to a straightforward implementation trick of
> generating A directly in its transposed form, as used in the Kyber
> reference implementation. In particular, option 2.a) matches exactly
> the Kyber specification, but it may be confusing due to the multiple
> appearances of Ahat_transpose. Option 2.b) avoids most risk of
> confusion by removing all matrix transposition in the pseudo-code, at
> the cost of introducing a new notation.
>
> Option 3) visually echoes what happens in KeyGen and Decrypt which
> could give a better intuition on how the scheme works as a whole and
> why it is correct. It also makes it clear that generation of matrix
> Ahat is done in the same way in KeyGen and Encrypt, while also
> removing all matrix transposition to avoid confusion. It would however
> require a more extensive editing work in the rest of the document to
> make all equations consistent.
>
> I do not have a strong opinion on which option is the best, but if I
> had to choose one I would recommend option 1.
>
>
> Best regards,
> Robin Larrieu
> CryptoNext Security