Known Answer Tests for ML-KEM

[Mitchell]

Anyone have a link for these test vectors?

[Krzysztof Kwiatkowski]

Hi,

I don’t think NIST provided KATs. But I’ve generated some KATs by using Kyber [1] and Dilithium[2] software packages. You can find them here:
https://github.com/post-quantum-cryptography/KAT

[1] https://github.com/pq-crystals/kyber/commit/4ecce06d584a4e7cecc42f141aadae39b8431b06
[2] https://github.com/pq-crystals/dilithium/commit/918af1a6eaedcedf9fdd8aaaca6c1fccd5a7a51f

> On 5 Oct 2023, at 08:30, Mitchell <berry...@gmail.com> wrote:
>
> Anyone have a link for these test vectors?
>

> --
> 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/34270a14-4294-4643-9ed2-d778f9d08bc2n%40list.nist.gov.

[Bas Westerbaan]

Do note though that ML-KEM, an thus the test vectors, are not final yet., 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/C8BF3C02-8538-4795-A06D-0DC508F4896F%40amongbytes.com.

[Mitchell]

> not final yet

And yet everyone is coalescing around it, likely with no changes in the final design.

If you are going put out a new draft then put out the vectors, if the draft changes then put out vectors for that also. Don't think this is a controversial opinion to hold and doesn't seem like a big ask this late in the game. We had five years of people providing test vectors the moment their algorithms changed and now it's a drought with a single finalised KEM.

[Paul Hoffman]

On Oct 5, 2023, at 07:52, Mitchell <berry...@gmail.com> wrote:
>
> > not final yet
> And yet everyone is coalescing around it, likely with no changes in the final design.

This is not true, at least from what I see in the IETF. Many developers are being responsible in their early testing, including choosing naming that will clearly indicate that they are using the pre-standard algorithm now.

The development environment you are in might be doing it less carefully, but please don't assume that "everyone" is doing so.

--Paul Hoffman

[Mitchell]

> Many developers are being responsible in their early testing, including choosing naming that will clearly indicate that they are using the pre-standard algorithm now.

Care to provide some examples of this? From what I see it's all ML-KEM without a single test vector to verify against.

Is it really so hard to provide something the public can check?

[Paul Hoffman]

On Oct 5, 2023, at 08:39, Mitchell <berry...@gmail.com> wrote:
>
> > Many developers are being responsible in their early testing, including choosing naming that will clearly indicate that they are using the pre-standard algorithm now.
>
> Care to provide some examples of this? From what I see it's all ML-KEM without a single test vector to verify against.

The work in the IETF is being discussed in the PQUIP Working Group (of which I am co-chair). See <https://datatracker.ietf.org/group/pquip/about/>, particularly the mailing list archive from the past week or so. Discussing early test vectors is absolutely appropriate there; note that what you will see there are from individuals like yourself, not from NIST.

--Paul Hoffman

[Kampanakis, Panos]

 

- Experimental identifiers in https://github.com/open-quantum-safe/oqs-provider/blob/main/oqs-template/oqs-kem-info.md which clearly state which NIST round the quantum-safe algorithm is from.

- Names “X25519Kyber768Draft00”, “SecP256r1Kyber768Draft00” in https://www.iana.org/assignments/tls-parameters/tls-parameters.xhtml which clearly state they are not the final ML-KEM, but the round 3 version.

- Names “ecdh-nistp256-kybe...@openquantumsafe.org”, …, “x25519-kyber-5...@amazon.com“ in https://github.com/csosto-pk/pq-ssh/blob/master/draft-kampanakis-ssh-pq-ke.txt  for SSH which have the version in the name.

 

A couple more KATs from early implementations, not NIST

- for Kyber round 3 https://github.com/aws/s2n-tls/blob/a6517c5fe97b1aa1898f2233498613dd53735bd8/tests/unit/kats/kyber_r3.kat

- for TLS 1.3 https://github.com/aws/s2n-tls/blob/a6517c5fe97b1aa1898f2233498613dd53735bd8/tests/unit/kats/tls13_server_hybrid_key_share_recv.kat , https://github.com/aws/s2n-tls/blob/a6517c5fe97b1aa1898f2233498613dd53735bd8/tests/unit/kats/generate_pq_hybrid_tls13_handshake_kats.py , https://github.com/aws/s2n-tls/blob/a6517c5fe97b1aa1898f2233498613dd53735bd8/tests/unit/kats/hybrid_prf.kat

 

 

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Mitchell
Sent: Thursday, October 5, 2023 11:39 AM
To: pqc-forum <pqc-...@list.nist.gov>
Cc: Paul Hoffman <paul.h...@icann.org>; pqc-forum <pqc-...@list.nist.gov>; Mitchell <berry...@gmail.com>
Subject: RE: [EXTERNAL] [Ext] [pqc-forum] Known Answer Tests for ML-KEM

 

CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.

 

--

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/a44cd588-519d-4a07-8811-be748643e158n%40list.nist.gov.

[Mitchell]

I'm still waiting for an official set of known answers. If you are honestly putting your hand up in lieu of the Kyber team then bravo and good on you for trying, but I will still wait for something a bit more legit before publishing anything myself.

The silence here is deafening. Where's the actual KATs for ML-KEM?

On Friday, 6 October 2023 at 01:55:57 UTC+11 Paul Hoffman wrote:

[Moody, Dustin (Fed)]

Here is what we said about this already:

https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/EKoI0u_PuOw/m/EJWyWH96AAAJ

Simon (and others),

We agree that having test vectors is very important.  However, we don't typically put the test vectors in the FIPS themselves.   For example, if you look at the SHA-3 standard FIPS 202, in appendix B we point somewhere else, rather than having them in that document.  Specifically, it points to our Computer Security Resources Center page

https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values

where we prefer to put them.  That way they can be more easily updated, while it is much more difficult to update a FIPS.  We will update that page for the new PQC algorithms, and we'll be sure to announce when we do that.  Thanks,

Dustin

Dustin Moody

NIST

---

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Mitchell <berry...@gmail.com>
Sent: Thursday, October 5, 2023 1:13 PM

To: pqc-forum <pqc-...@list.nist.gov>
Cc: Paul Hoffman <paul.h...@icann.org>; pqc-forum <pqc-...@list.nist.gov>; Mitchell <berry...@gmail.com>

Subject: Re: [Ext] [pqc-forum] Known Answer Tests for ML-KEM

 

--
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/ade6e5d3-e456-424a-8ddd-153541ff5718n%40list.nist.gov.

[Mitchell]

Thanks Dustin, do appreciate your stoic perseverance through all this.

That said, who owns the ML-KEM standard? Seems fair to expect some vectors from either the Kyber team or NIST with these changes? I really don't see why draft KATs are so hard to do, the explanation in your link is quite handwavey about reasoning. Tangential, already getting reports of interop failures with rust dilithium and the bouncycastle implementation,  it's only a matter of time before it happens with Kyber. People are rolling out these modifications independently and there's not a single source of ground truth for anyone on Earth to point to, this frankly comes across as a failure of process and procedures.

This stuff isn't hard. Why not just do it?

[John Mattsson]

Thanks Dustin,

I think NIST is typically doing an _excellent_ work with test vectors. In addition to the test vectors on the Computer Security Resources Center page, there is also a NIST-hosted server called Automated Cryptographic Validation Test System (ACVTS) provides algorithm test vectors.

https://csrc.nist.gov/csrc/media/Presentations/2023/validation-testing-for-block-cipher-modes/images-media/sess-6-celi-bcm-workshop-2023.pdf

Berry Mitchell wrote:
>People are rolling out these modifications independently.
I am a bit shocked to see how eager people are to use non-standardized algorithms. I think the only reasonable thing to do is to wait until the final NIST standards are published. Using non-standardized algorithms not only creates interoperability problems but also risks creating security problems.

Cheers,
John

 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/ccc1f175-df26-45ca-98bd-251a1197a395n%40list.nist.gov.

[Peter Schwabe]

Mitchell <berry...@gmail.com> wrote:

Dear Mitchell, dear all,

> Thanks Dustin, do appreciate your stoic perseverance through all this.
>
> That said, who owns the ML-KEM standard? Seems fair to expect some vectors
> from either the Kyber team or NIST with these changes? I really don't see
> why draft KATs are so hard to do, the explanation in your link is quite
> handwavey about reasoning. Tangential, already getting reports of interop
> failures with rust dilithium and the bouncycastle implementation, it's
> only a matter of time before it happens with Kyber. People are rolling out
> these modifications independently and there's not a single source of ground
> truth for anyone on Earth to point to, this frankly comes across as a
> failure of process and procedures.
>
> This stuff isn't hard. Why not just do it?

The Kyber reference implementation includes two Makefile targets that
you can use to generate test vectors; the "standard" branch should
mostly be compatible with the NIST draft standard (for some details see
below).

More specifically, if you do

git clone https://github.com/pq-crystals/kyber.git
cd kyber/
git checkout standard
cd ref/
make

you will obtain binaries

nistkat/PQCgenKAT_kem512
nistkat/PQCgenKAT_kem768
nistkat/PQCgenKAT_kem1024

that generate KATs using the code that NIST made available for sumitting
teams during the competition. You will also obtain binaries

test/test_vectors512
test/test_vectors768
test/test_vectors1024

that generate somewhat more extensive test vectors that we use to ensure
that our implementaitons (ref and avx2) are compatible. See also the
runtests.sh script in the root directory of the kyber repo.

I believe that neither of those KAT values are actually very good. The
NIST KAT vectors do not include negative tests and our test vectors
include only fairly rudimentary negative tests. Also, a carefully
crafted set of KATs should trigger a few special cases, for example,
more blocks of Keccak output for the matrix generation than usual.

It would be great to have a discussion about what the "official" KATs
should look like and what cases should be covered.


There are two known differences between what the "standard" branch
implements and what is currently in the NIST draft standard;
specifically:

* The round-3 specification of Kyber and all implementations so far,
including the one in the "standard" branch, generate the entry of the
matrix A at position (i,j) as

A[i][j] = Parse(XOF((\rho,j,i))

The draft standard generates the entries as

A[i][j] = Parse(XOF((\rho,i,j))

Either draft standard or implementation will need to change. As this
change wasn't listed in Section 1.3 of the draft standard, I'm
assuming that this was unintentional and might be changed in an
updated draft standard. If not, it will obviously need to change in
the implementation.

* The implementation of Encaps does not at the moment check-and-abort on
malformed public keys. This is a separate discussion that is still
ongoing and I will update the code depending on the outcome of this
discussion. As malformed public keys are anyway right now not part of
any of the testvectors, this has no impact on the KATs.


Does this help?

All the best,

Peter

> On Friday, 6 October 2023 at 04:16:55 UTC+11 Moody, Dustin (Fed) wrote:
>
> > Here is what we said about this already:
> >
> >
> > https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/EKoI0u_PuOw/m/EJWyWH96AAAJ
> >
> > Simon (and others),
> >
> > We agree that having test vectors is very important. However, we don't
> > typically put the test vectors in the FIPS themselves. For example, if
> > you look at the SHA-3 standard FIPS 202, in appendix B we point somewhere
> > else, rather than having them in that document. Specifically, it points to
> > our Computer Security Resources Center page
> >
> >
> > https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values
> >
> > where we prefer to put them. That way they can be more easily updated,
> > while it is much more difficult to update a FIPS. We will update that page
> > for the new PQC algorithms, and we'll be sure to announce when we do that.
> > Thanks,
> >
> > Dustin
> >
> >
> > Dustin Moody
> > NIST

> > ------------------------------
> > *From:* pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of
> > Mitchell <berry...@gmail.com>
> > *Sent:* Thursday, October 5, 2023 1:13 PM
> >
> > *To:* pqc-forum <pqc-...@list.nist.gov>
> > *Cc:* Paul Hoffman <paul.h...@icann.org>; pqc-forum <pqc-...@list.nist.gov>;
> > Mitchell <berry...@gmail.com>
> > *Subject:* Re: [Ext] [pqc-forum] Known Answer Tests for ML-KEM

> >
> > I'm still waiting for an official set of known answers. If you are
> > honestly putting your hand up in lieu of the Kyber team then bravo and good
> > on you for trying, but I will still wait for something a bit more legit
> > before publishing anything myself.
> > The silence here is deafening. Where's the actual KATs for ML-KEM?
> > On Friday, 6 October 2023 at 01:55:57 UTC+11 Paul Hoffman wrote:
> >
> > On Oct 5, 2023, at 07:52, Mitchell <berry...@gmail.com> wrote:
> > >
> > > > not final yet
> > > And yet everyone is coalescing around it, likely with no changes in the
> > final design.
> >
> > This is not true, at least from what I see in the IETF. Many developers
> > are being responsible in their early testing, including choosing naming
> > that will clearly indicate that they are using the pre-standard algorithm
> > now.
> >
> > The development environment you are in might be doing it less carefully,
> > but please don't assume that "everyone" is doing so.
> >
> > --Paul Hoffman
> >
> > --
> > 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/ade6e5d3-e456-424a-8ddd-153541ff5718n%40list.nist.gov

> > <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/ade6e5d3-e456-424a-8ddd-153541ff5718n%40list.nist.gov?utm_medium=email&utm_source=footer>
> > .

> >
>
> --
> 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/ccc1f175-df26-45ca-98bd-251a1197a395n%40list.nist.gov.

[Mitchell]

That's great Peter, thanks, do appreciate it, along with the additional comments. 

Strongly agree with the need for negative tests, but this is an excellent starting point for vectors.

Cheers,

    Mitchell

[John Mattsson]

Hi,

I strongly agree with the necessity of including negative test vectors. Negative test vectors are very important for catching bugs that might have security implications. I think all future algorithm and protocols standards should have negative test vectors.

I recently created negative test vectors for the EDHOC protocol, which immediately uncovered bugs in several of the implementations.
https://datatracker.ietf.org/doc/draft-ietf-lake-traces/

Cheers,
John

 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAO%2BHxbD6r5i%2BLK1h%2BZKjU7nTpVAU1GUUcT4Zr-9Q8YyO8gM2BQ%40mail.gmail.com.

[Simon Hoerder]

On 10 Oct 2023, at 11:24, 'John Mattsson' via pqc-forum <pqc-...@list.nist.gov> wrote:



Hi,

I strongly agree with the necessity of including negative test vectors. Negative test vectors are very important for catching bugs that might have security implications. I think all future algorithm and protocols standards should have negative test vectors.

+1 

Best,

Simon

[Paul Hoffman]

On Oct 10, 2023, at 02:23, John Mattsson <john.m...@ericsson.com> wrote:
>
> I strongly agree with the necessity of including negative test vectors. Negative test vectors are very important for catching bugs that might have security implications. I think all future algorithm and protocols standards should have negative test vectors.
>
> I recently created negative test vectors for the EDHOC protocol, which immediately uncovered bugs in several of the implementations.

> https://datatracker.ietf.org/doc/draft-ietf-lake-traces/ [datatracker.ietf.org]

Note that this thread started with a complaint that NIST should have produced these vectors already, and a demand that they do so as soon as possible. What has followed is a set of non-NIST people that have published interesting and useful sets of test vectors.

It's fine if NIST produces such vectors, in their own time. The developer community probably has more leeway in creating useful sets of vectors than NIST does, particularly for edge cases. Let's continue to support interoperability with informal sets of test vectors that become vetted and, if need be, corrected.

Please see <https://github.com/ietf-wg-pquip/state-of-protocols-and-pqc>. If you want to add your set of test vectors to this public list, please open an issue in the tracker.

--Paul Hoffman

[Robin Larrieu]

Dear all,

I wanted to draw your attention on a possible minor mismatch between the
ML-KEM draft standard and the implementation by the pq-crystals team,
more specifically in how the KeyGen procedure consumes randomness.

On the one hand, the FIPS 203 draft dated 2023-08-24 specifies
> K-PKE.KeyGen() {
>     d <- B^32
>     [snip]
> }
>
> ML-KEM.KeyGen() {
>     z <- B^32
>     (ekPKE, dkPKE) <- K-PKE.KeyGen()
>     [snip]
> }

On the other hand, examining files kem.c and indcpa.c from
https://github.com/pq-crystals/kyber/tree/4ecce06d584a4e7cecc42f141aadae39b8431b06
(latest commit in branch "standard" at the time of writing) shows a
slightly different implementation. With the same notations as above,
this would correspond to
> K-PKE.KeyGen(d) {
>     [snip]
> }
>
> ML-KEM.KeyGen() {
>     (d,z) <- B^64
>     K-PKE.KeyGen(d)
>     [snip]
> }

Even if the difference has no impact on security or interoperability,
the two solutions lead to different test vectors.
But maybe I missed something. Could NIST or the pq-crystals team clarify
the situation ?

As a side note, I noticed that the pq-crystal implementation of ML-DSA
(https://github.com/pq-crystals/dilithium/tree/918af1a6eaedcedf9fdd8aaaca6c1fccd5a7a51f)
uses deterministic signing by default, while the FIPS 204 draft
recommends the "hedged" version by default. To avoid any confusion for
someone just pulling the repository, I think that the macro
DILITHIUM_RANDOMIZED_SIGNING should be defined by default.

Robin Larrieu

[Bobby McGee]

The Kyber test vectors for the 3rd round submission (v3.02) sample randomness from AES_CTR_DRBG in an order different from that listed in the specs for key generation.  In particular, the order of sampling (d,z,m) is different from specs (kyber.ccakem.keygen() alg. 7) where it looks like it should be (z,d,m).  I don't know if this is well-known so thought I'd mention it here.

[Kris Kwiatkowski]

Hello,

Over recent days we worked with Roderic Chapman from AWS on two separate MLKEM
implementations that precisely follow the FIPS-203 draft, to make sure we have the
same understanding of the draft (one of those implementations can be formally
verified). We got to the point where both implementations are interoperable. We
only tested Kyber 768.

I was hoping that someone can confirm our results (or prove wrong). That can be
done by running KAT vectors against their own implementation. We used following KATs:
https://github.com/post-quantum-cryptography/KAT/tree/v0.0.1/MLKEM

Note: Those vectors are _just_ a tool to ensure correct understanding of
FIPS-203 draft.

Kind regards,
Kris Kwiatkowski

[Rod Chapman]

To clarify Kris's comment: my implementation currently has an auto-active formal verification of the freedom of undefined behaviour,

plus memory-safety and type-safety, but not functional correctness with respect to any formal statement of the ML-KEM specification.

I am also working on a static verification for worst-case stack usage.

 All the best,

  Rod Chapman, AWS Cryptography

[Robin Larrieu]

Hi Kris, Rod,

I was able to reproduce your test vectors with my implementation.

For anyone else wanting to reproduce the results, notice that the indices are swapped compared to the Kyber spec when expanding the public matrix A from seed rho (and this change is not listed in section "1.3 Differences From the CRYSTALS-KYBER Submission"). Indeed, the draft reads
  Ahat[i,j] <- SampleNTT(XOF(ρ, i, j))
while the Kyber specification reads
  Ahat[i,j] := Parse(XOF(ρ, j, i))

The test vectors published by Kris and Rod are generated using the convention "Ahat[i,j] <- SampleNTT(XOF(ρ, i, j))" as currently written in the draft.
There was a question on this topic last month, and after reviewing the thread, NIST's answers seem to suggest that this change may have been a typo. But it is unclear so I revived the corresponding thread to try to get a more precise answer.

Best regards,
Robin Larrieu

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/9f14de21-1dca-4b8c-88e8-640e3c552953n%40list.nist.gov.

[Peter Schwabe]

'Robin Larrieu' via pqc-forum <pqc-...@list.nist.gov> wrote:
> Hi Kris, Rod,

Dear Robin, dear Kris, dear Rod,

> I was able to reproduce your test vectors with my implementation.

Thank you so much for going through the draft standard and producing
implementations and test vectors!

> For anyone else wanting to reproduce the results, notice that the indices are swapped compared to the Kyber spec when expanding the public matrix A from seed rho (and this change is not listed in section "1.3 Differences From the CRYSTALS-KYBER Submission"). Indeed, the draft reads
> Ahat[i,j] <- SampleNTT(XOF(ρ, i, j))
> while the Kyber specification reads
> Ahat[i,j] := Parse(XOF(ρ, j, i))
>
> The test vectors published by Kris and Rod are generated using the convention "Ahat[i,j] <- SampleNTT(XOF(ρ, i, j))" as currently written in the draft.
> There was a question on this topic last month, and after reviewing the thread, NIST's answers seem to suggest that this change may have been a typo. But it is unclear so I revived the corresponding thread to try to get a more precise answer.

@NIST team: with more and more people working on implementations and
test vectors, it would be great to have a statement which of the two
options you are planning to put into the standard so that we can already
converge in implementations. It really does not matter which one you
pick, just make some choice.

All the best,

Peter

> 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/9f14de21-1dca-4b8c-88e8-640e3c552953n%40list.nist.gov<https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/9f14de21-1dca-4b8c-88e8-640e3c552953n%40list.nist.gov?utm_medium=email&utm_source=footer>.

>
> --
> 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/52468372-92f8-4928-a506-9c646b25dc2f%40cryptonext-security.com.

[Dang, Quynh H. (Fed)]

Hi everyone,

Our intension is to make the PKE in the ML-KEM FIPS to be the same (compatible) with the PKE in the Kyber's third round spec.

As Robin Larrieu, Peter Schwabe, Julius Hermelink and others have suggested, there are a couple of choices that we can make to the draft FIPS.

Option 1:

1) changing XOF(p,i,j) to become XOF(p,j,i) at step 6 in Algorithm 12 in the draft FIPS. (KeyGen).
2) Replace A_hat[i, j] by B_hat[i, j] at Step 6 in Algorithm 13 (Encrypt). Make a note: says that B_hat is the transpose of A_hat in Algorithm 12.
3) Replace A_hat_Transposed by B_hat in step 19 of Algorithm 13.

Make it clear that Index1 in A[index1, index2] and B[index1, index2] is the row index.

Option 2:

a) Do the step (1) above.

b) Add a transpose symbol to A_hat in Step 6 of Algorithm 13 to make it look the same as in the Kyber's 3rd round spec.

c) Make a note at the step 19 of Algorithm 13 to say that A_hat_Transposed is from the step 6; no further transpose happens here.

Make it clear that Index1 in A[index1, index2] is the row index.

Option 2 is the Kyber's third round spec.

Let us know which option you would prefer and/or you have another suggestion. The goal is to make the spec as clear as possible.

Thank you and Regards,
Quynh.

We need your implementation to follow the draft ML-KEM with index1 in A[index1, index2] and B[index1, index2] being the row.

> forum+un...@list.nist.gov>.

> > To view this discussion on the web visit
> https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/9f14de21-
> 1dca-4b8c-88e8-
> 640e3c552953n%40list.nist.gov<https://groups.google.com/a/list.nist.gov/d/
> msgid/pqc-forum/9f14de21-1dca-4b8c-88e8-
> 640e3c552953n%40list.nist.gov?utm_medium=email&utm_source=footer>.
> >
> > --
> > 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/52468372-
> 92f8-4928-a506-9c646b25dc2f%40cryptonext-security.com.
>

> --
> 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/ZTIVta1KC7dn6wij%40disp3269.

[Peter Schwabe]

"Dang, Quynh H. (Fed)" <quynh...@nist.gov> wrote:
> Hi everyone,

Hi Quynh, hi all,

> Our intension is to make the PKE in the ML-KEM FIPS to be the same
> (compatible) with the PKE in the Kyber's third round spec.

Great, thanks for stating this clearly. That's very helpful for
implementations.

> As Robin Larrieu, Peter Schwabe, Julius Hermelink and others have suggested, there are a couple of choices that we can make to the draft FIPS.
>
> Option 1:
>
> 1) changing XOF(p,i,j) to become XOF(p,j,i) at step 6 in Algorithm 12 in the draft FIPS. (KeyGen).
> 2) Replace A_hat[i, j] by B_hat[i, j] at Step 6 in Algorithm 13 (Encrypt). Make a note: says that B_hat is the transpose of A_hat in Algorithm 12.
> 3) Replace A_hat_Transposed by B_hat in step 19 of Algorithm 13.
>
> Make it clear that Index1 in A[index1, index2] and B[index1, index2] is the row index.
>
> Option 2:
>
> a) Do the step (1) above.
>
> b) Add a transpose symbol to A_hat in Step 6 of Algorithm 13 to make it look the same as in the Kyber's 3rd round spec.
>
> c) Make a note at the step 19 of Algorithm 13 to say that A_hat_Transposed is from the step 6; no further transpose happens here.
>
> Make it clear that Index1 in A[index1, index2] is the row index.
>
> Option 2 is the Kyber's third round spec.
>
> Let us know which option you would prefer and/or you have another suggestion. The goal is to make the spec as clear as possible.

Not very surprisingly, I prefer option 2, mostly because I don't see the
reason for introducing an additional name for \hat{A}^T.

However, this is certainly not a strong preference; if anybody thinks
that using the name B for \hat{A}^T helps in some way, please go for it.


All the best,

Peter

[Dang, Quynh H. (Fed)]

Hi Peter and all,

> -----Original Message-----
> From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Peter
> Schwabe
> Sent: Saturday, October 21, 2023 1:40 AM
> To: Dang, Quynh H. (Fed) <quynh...@nist.gov>
> Cc: Peter Schwabe <pe...@cryptojedi.org>; Robin Larrieu
> <robin....@cryptonext-security.com>; pqc-forum <pqc-
> fo...@list.nist.gov>
> Subject: Re: [pqc-forum] Known Answer Tests for ML-KEM
>

[Dang, Quynh H. (Fed)] The disadvantage the option 2 has over the option 1 is the following.

Step 20 in encryption in Kyber's 3rd spec (step 21 in the draft ML-KEM) says that the symbol T is to do a transpose operation on the object mathematically (even though it is not matter in the code).

Looking at step 6 in the encryption function, an implementer might do a transpose on the result matrix from the sampling routine because there is a transpose symbol T there. If the implementer does another transpose at step 19 (because there is a transpose symbol there), then everything is correct and the implementer might realize that it makes no sense to do 2 transpose operations because they cancel themselves out, but the implementer might just think that I don't really know for sure; I am better to follow the spec. So, the 2 transpose operations are wasted.

If the implementer does only 1 transpose operation on the result matrix from the sampling routine at Step 6, call this transposed matrix A_hat_T then use it as is to compute (A_hat_T o r_hat) in step 19, then the result is wrong.

Thank you and Regards,
Quynh.

>

> forum/ZTNkICPnsBW6fCMO%40disp3269.

[Paul Duncan]

Hi Quynh,

Both options are an improvement over the the current ML-KEM draft.

I like Option 2 slighty more than Option 1, because Option 2 seems
easier for the reader to understand (fewer intermediate variables).

Thanks,

> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/MW4PR09MB10059699935AFAD0B564F8DDBF3DBA%40MW4PR09MB10059.namprd09.prod.outlook.com.

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

[Dang, Quynh H. (Fed)]

Hi all,

I discussed the option 1 a bit more inline below.

[Dang, Quynh H. (Fed)] The option 1 is to use the PKE.encryption from the Kyber's third round for the Algorithm 13, K-PKE.Encrypt, in the ML-KEM FIPS 203 with one change: replacing the A_hat_T at steps 6 and 19 by B_hat. Add a comment at the step 6 which says that B_hat is the transpose of A_hat.

The purpose is to not use the transpose symbol T unnecessarily to avoid the potential confusion situation described in the previous email.

> 640e3c552953n%40list.nist.gov<https://gcc02.safelinks.protection.outlook.co
> m/?url=https%3A%2F%2Fgroups.google.com%2Fa%2Flist.nist&data=05%7C0
> 1%7Cquynh.dang%40nist.gov%7C3f6dcc1895c449c5fcc608dbd2247690%7C2a
> b5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C638334826289608549%7CU
> nknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI
> 6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=BmXeZYS0vfZxJey
> oipSUv5MqiqXXWFDMjaVn9H%2B2N1k%3D&reserved=0.

> forum/MW4PR09MB10059CD6BC5398FAE9635C803F3DAA%40MW4PR09MB1
> 0059.namprd09.prod.outlook.com.

[Robin Larrieu]

Hi all,

I also think that option 2 can be confusing because of the transpose
symbol in both lines 6 and 19.
Option 1 reduces the risk of confusion at the cost of introducing a new
notation, that may hide the underlying logic.

As suggested by Quynh, I sent an official comment to
fips-203...@nist.gov; I copied this comment in the other thread
"Question about Ahat_transposed in ML-KEM / Kyber", but I can summarize
it here as well.
In this official comment, I listed 2 additional options:

Option 3:
1) change Algorithm 12 (KeyGen) as in the other 2 options, and
2) change line 6 of Algorithm 13 (Encrypt) from "Ahat[i,j] <-
SampleNTT(XOF(ρ, i, j))" to "Ahat[i,j] <- SampleNTT(XOF(ρ, j, i))"
3) keep line 19 of Algorithm 13 unchanged

Option 4:
1) change Algorithm 12 (KeyGen) as in the other 2 options, and
2) change line 6 of Algorithm 13 (Encrypt) from "Ahat[i,j] <-
SampleNTT(XOF(ρ, i, j))" to "Ahat[i,j] <- SampleNTT(XOF(ρ, j, i))"
3) change line 19 of Algorithm 13 from "u <- NTT^(-1)(Ahat o rhat) + e1"
to "u <- NTT^(-1)(rhat o Ahat) + e1"


Recall that the document already gives formulas to compute the product
yhat = Ahat_transpose * uhat (among other things) in page 10. So the
idea of option 3 is:
- remove the transpose-ambiguity in the matrix sampling, and make it
clear that it is the same matrix as in KeyGen
- the product in line 19 is computed either by transposing the matrix
first, or by using directly the appropriate formula given in page 10.

To emphasize this, the formulas in page 10 could be numbered, e.g.
  (F1) what = Ahat * uhat             what[i] = sum_j [snip]
  (F2) yhat = Ahat_transpose * uhat   yhat[i] = sum_j [snip]
  (F3) zhay = uhat_transpose * vhat   zhat = sum_j [snip]
Then comments in the algorithm description can explicitly reference
which formula to use. For example, the comments in line 19 of Keygen and
Encrypt become "Use (F1); noisy linear system in NTT domain" and "Use
(F2); NTT^(-1) is run k times" respectively.


Option 4 removes the transpose entirely by swapping the operands in the
product. However, this means we are using vectors indiscriminately as
row vectors or column vectors, which can be a minor source of confusion.
Also this implies a more extensive editing work in the rest of the
document to ensure that all the notations and formulas in the text and
algorithm descriptions are consistent with each other.


Note that the formulas in page 10 will need to be adjusted depending on
which option is selected. Typically, F2 is no longer needed with option
1 and 2, and it should become yhat = uhat * Ahat if option 4 is selected.


Best regards,
Robin Larrieu

Le 22/10/2023 à 12:22, 'Dang, Quynh H. (Fed)' via pqc-forum a écrit :
> Hi all,
>
> I discussed the option 1 a bit more inline below.
>
>> -----Original Message-----
>> From: 'Dang, Quynh H. (Fed)' via pqc-forum <pqc-...@list.nist.gov>
>> Sent: Saturday, October 21, 2023 6:57 AM
>> To: Peter Schwabe <pe...@cryptojedi.org>; pqc-forum <pqc-
>> fo...@list.nist.gov>
>> Cc: Robin Larrieu <robin....@cryptonext-security.com>
>> Subject: RE: [pqc-forum] Known Answer Tests for ML-KEM
>>

>> Hi everyone,

>>
>> Our intension is to make the PKE in the ML-KEM FIPS to be the same (compatible) with the PKE in the Kyber's third round spec.
>>

>> As Robin Larrieu, Peter Schwabe, Julius Hermelink and others have suggested, there are a couple of choices that we can make to the draft FIPS.
>>
>> Option 1:
>>
>> 1) changing XOF(p,i,j) to become XOF(p,j,i) at step 6 in Algorithm 12 in the draft FIPS. (KeyGen).
>> 2) Replace A_hat[i, j] by B_hat[i, j] at Step 6 in Algorithm 13 (Encrypt). Make a note: says that B_hat is the transpose of A_hat in Algorithm 12.
>> 3) Replace A_hat_Transposed by B_hat in step 19 of Algorithm 13.
>>
>> Make it clear that Index1 in A[index1, index2] and B[index1, index2] is the row index.
>>
>> Option 2:
>>
>> a) Do the step (1) above.
>>
>> b) Add a transpose symbol to A_hat in Step 6 of Algorithm 13 to make it look the same as in the Kyber's 3rd round spec.
>>
>> c) Make a note at the step 19 of Algorithm 13 to say that A_hat_Transposed is from the step 6; no further transpose happens here.
>>
>> Make it clear that Index1 in A[index1, index2] is the row index.
>>
>> Option 2 is the Kyber's third round spec.
>>

>> Let us know which option you would prefer and/or you have another suggestion. The goal is to make the spec as clear as possible. Hi Peter and all,

[Dang, Quynh H. (Fed)]

Hi Robin,

Thank you for the suggestions.

Hi all,

Robin skipped a few pros/cons of the options to keep the discussion short.

I think it is worth to discuss them. So, I did below inline.

> -----Original Message-----
> From: 'Robin Larrieu' via pqc-forum <pqc-...@list.nist.gov>
> Sent: Monday, October 23, 2023 4:13 AM
> To: pqc-forum <pqc-...@list.nist.gov>
> Subject: Re: [pqc-forum] Known Answer Tests for ML-KEM
>
> Hi all,
>
> I also think that option 2 can be confusing because of the transpose symbol
> in both lines 6 and 19.
> Option 1 reduces the risk of confusion at the cost of introducing a new
> notation, that may hide the underlying logic.

[Dang, Quynh H. (Fed)] With option 2, we would also remove the line for y_hat on page 10. Everything would be fully clear. There is only one dot product between a matrix and a column, so there is no room for using a wrong dot product function.

Option 2 uses a matrix B_hat and makes it clear at the line 6 that B_hat is the transpose of A_hat. This comment would show the underlying logic of the need to transpose the matrix A (from key gen) before computing its dot product with r_hat as (Matrix dot column) in Kyber's encryption.

>
> As suggested by Quynh, I sent an official comment to fips-203-
> comm...@nist.gov; I copied this comment in the other thread "Question

> about Ahat_transposed in ML-KEM / Kyber", but I can summarize it here as
> well.
> In this official comment, I listed 2 additional options:
>
> Option 3:
> 1) change Algorithm 12 (KeyGen) as in the other 2 options, and
> 2) change line 6 of Algorithm 13 (Encrypt) from "Ahat[i,j] <-
> SampleNTT(XOF(ρ, i, j))" to "Ahat[i,j] <- SampleNTT(XOF(ρ, j, i))"
> 3) keep line 19 of Algorithm 13 unchanged

[Dang, Quynh H. (Fed)] This option requires keeping the functions for w_hat and y_hat on page 10. So, it still has room for confusion when one implements line 19. The implementer might do a transpose than use the equation for y_hat, then the result is wrong. The implementer might not do a transpose, then use the equation for w_hat, then the result is also wrong.

In the case of the implementer does the transpose, then use the equation for w_hat, (the result is correct), the disadvantage of this over the option 2 is the unnecessary transpose operation. Option 2 does not do any transpose operation.

Another benefit of option 2 over option 3 is that option 2 looks the same with the Kyber's spec except that 1 change to remove all rooms for confusion. Kyber uses only A_hat_Transposed, option 2 uses only B_hat. Option 3 uses A_hat and A_hat_Transposed.

> Option 4:
> 1) change Algorithm 12 (KeyGen) as in the other 2 options, and
> 2) change line 6 of Algorithm 13 (Encrypt) from "Ahat[i,j] <-
> SampleNTT(XOF(ρ, i, j))" to "Ahat[i,j] <- SampleNTT(XOF(ρ, j, i))"
> 3) change line 19 of Algorithm 13 from "u <- NTT^(-1)(Ahat o rhat) + e1"
> to "u <- NTT^(-1)(rhat o Ahat) + e1"

[Dang, Quynh H. (Fed)] The downside of this option is that it looks fundamentally different from Kyber that has been known even though the result is correct. And we would need to specify one more unnecessarily dot product function and then must prove that the 2 equations (one in this FIPS and one in the Kyber's 3rd round spec) produce the same result. With this option, likely we would receive questions about this from new implementers in the future when they just look at this algorithm and check it against the Kyber's spec.


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/21dd0b2a-
> 2a2a-4dbf-a6a4-557c00fce8b6%40cryptonext-security.com.

[Robin Larrieu]

Hi Quynh,

It seems your response uses "option 2" for "use Bhat" and "option 1" for "use Ahat_transpose", while your initial message was the opposite.
Anyway, I mostly agree with you, but let me expand my line of thought below.

Le 23/10/2023 à 13:09, Dang, Quynh H. (Fed) a écrit :

-----Original Message-----
From: 'Robin Larrieu' via pqc-forum <pqc-...@list.nist.gov>
Sent: Monday, October 23, 2023 4:13 AM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Known Answer Tests for ML-KEM

Hi all,

I also think that option 2 can be confusing because of the transpose symbol
in both lines 6 and 19.
Option 1 reduces the risk of confusion at the cost of introducing a new
notation, that may hide the underlying logic.

[Dang, Quynh H. (Fed)] With option 2, we would also remove the line for y_hat on page 10. Everything would be fully clear. There is only one dot product between a matrix and a column, so there is no room for using a wrong dot product function. 

Option 2 uses a matrix B_hat and makes it clear at the line 6 that B_hat is the transpose of A_hat. This comment would show the underlying logic of the need to transpose the matrix A (from key gen) before computing its dot product with r_hat as (Matrix dot column) in Kyber's encryption.

With option 2 (using Ahat_transpose), implementers may be wondering if they are using the correct access pattern when filling the matrix Ahat_transpose in line 6 and when multiplying in line 19: - when they see "Ahat_transpose[i,j] = ...", they may ask themselves "should I write the coefficient in position [i,j], or in position [j,i] because of the transpose?" (second is wrong) - when they see "Ahat_transpose * rhat", they may ask themselves "should I read column-wise because of the transpose, or row-wise as usual since it was transposed from the beginning ?" (first is wrong). Clearly leaving the formula for yhat would make the confusion worse, so NIST should definitely remove it if this option is selected. For this reason, I prefer option 1 (using Bhat) over option 2.

As suggested by Quynh, I sent an official comment to fips-203-
comm...@nist.gov; I copied this comment in the other thread "Question
about Ahat_transposed in ML-KEM / Kyber", but I can summarize it here as
well.
In this official comment, I listed 2 additional options:

Option 3:
1) change Algorithm 12 (KeyGen) as in the other 2 options, and
2) change line 6 of Algorithm 13 (Encrypt) from "Ahat[i,j] <-
SampleNTT(XOF(ρ, i, j))" to "Ahat[i,j] <- SampleNTT(XOF(ρ, j, i))"
3) keep line 19 of Algorithm 13 unchanged

[Dang, Quynh H. (Fed)] This option requires keeping the functions for w_hat and y_hat on page 10. So, it still has room for confusion when one implements line 19. The implementer might do a transpose than use the equation for y_hat, then the result is wrong. The implementer might not do a transpose, then use the equation for w_hat, then the result is also wrong. 

Maybe I am playing the devil's advocate here, but I think these scenario are less likely than an implementer overlooking the swapped indices in XOF(rho,i,j) compared to the XOF(rho,j,i) that was done in KeyGen, which also leads to a wrong result. Since option 3 does not swap indices, it removes this potential source of confusion, and makes it clear that the matrix is exactly the same as for KeyGen.

In the case of the implementer does the transpose, then use the equation for w_hat, (the result is correct), the disadvantage of this over the option 2 is the unnecessary transpose operation. Option 2 does not do any transpose operation. 
Another benefit of option 2 over option 3 is that option 2 looks the same with the Kyber's spec except that 1 change to remove all rooms for confusion. Kyber uses only A_hat_Transposed, option 2 uses only B_hat. Option 3 uses A_hat and A_hat_Transposed. 

With option 3, the implementer has essentially three ways to go:
- transpose, then do a standard matrix-column product (formula for what)
- do the matrix-column product with an adjusted access pattern (formula for yhat)
- generate Ahat_transpose from the beginning.
The first solution is a plain 1-to-1 implementation of option 3, and the next two are rather straightforward implementation tricks to avoid computing the transpose.

I believe that the pseudo-code description of the algorithm is more useful as an explanation of the underlying logic (hence option 3), but I guess it also makes sense to include micro-optimizations (like options 1 and 2) to help with implementations. So if people prefer option 1 or 2, I am fine with that as well.

Option 4:
1) change Algorithm 12 (KeyGen) as in the other 2 options, and
2) change line 6 of Algorithm 13 (Encrypt) from "Ahat[i,j] <-
SampleNTT(XOF(ρ, i, j))" to "Ahat[i,j] <- SampleNTT(XOF(ρ, j, i))"
3) change line 19 of Algorithm 13 from "u <- NTT^(-1)(Ahat o rhat) + e1"
to "u <- NTT^(-1)(rhat o Ahat) + e1"

[Dang, Quynh H. (Fed)]  The downside of this option is that it looks fundamentally different from Kyber that has been known even though the result is correct.  And we would need to specify one more unnecessarily dot product function and then must prove that the 2 equations (one in this FIPS and one in the Kyber's 3rd round spec) produce the same result.  With this option, likely we would receive questions about this from new implementers in the future when they just look at this algorithm and check it against the Kyber's spec. 

The idea behind option 4 was to further go in the direction of explaining the underlying logic. When you put KeyGen, Encrypt, and Decrypt side-by-side, I find it easier with option 4 to replace the intermediate results t, u, v, v' by their value to observe the simplifications and understand what is going on. With the current formulation, one has some additional transpositions to do, which is not a big deal when one does the computation but makes it a little bit more obscure at first.
Anyway, I agree that it may be too different from what is currently in place so we can forget about it.


Robin

[Dang, Quynh H. (Fed)]

Hi Robin and all,

 

I apologize I meant option 1 (the one uses B_hat) when I said option 2 at places.  See below.

 

 

From: Robin Larrieu <robin....@cryptonext-security.com>
Sent: Monday, October 23, 2023 9:56 AM
To: Dang, Quynh H. (Fed) <quynh...@nist.gov>; pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [pqc-forum] Known Answer Tests for ML-KEM

 

Hi Quynh,

It seems your response uses "option 2" for "use Bhat" and "option 1" for "use Ahat_transpose", while your initial message was the opposite.
Anyway, I mostly agree with you, but let me expand my line of thought below.

Le 23/10/2023 à 13:09, Dang, Quynh H. (Fed) a écrit :

-----Original Message-----

From: 'Robin Larrieu' via pqc-forum <pqc-...@list.nist.gov>

Sent: Monday, October 23, 2023 4:13 AM

To: pqc-forum <pqc-...@list.nist.gov>

Subject: Re: [pqc-forum] Known Answer Tests for ML-KEM

Hi all,

I also think that option 2 can be confusing because of the transpose symbol

in both lines 6 and 19.

Option 1 reduces the risk of confusion at the cost of introducing a new

notation, that may hide the underlying logic.

[Dang, Quynh H. (Fed)] With option 2, we would also remove the line for y_hat on page 10. Everything would be fully clear. There is only one dot product between a matrix and a column, so there is no room for using a wrong dot product function. 

Option 2 uses a matrix B_hat and makes it clear at the line 6 that B_hat is the transpose of A_hat. This comment would show the underlying logic of the need to transpose the matrix A (from key gen) before computing its dot product with r_hat as (Matrix dot column) in Kyber's encryption.

[Dang, Quynh H. (Fed)] I meant to say option 1 here: the one using B_hat, not option 2. 

With option 2 (using Ahat_transpose), implementers may be wondering if they are using the correct access pattern when filling the matrix Ahat_transpose in line 6 and when multiplying in line 19: - when they see "Ahat_transpose[i,j] = ...", they may ask themselves "should I write the coefficient in position [i,j], or in position [j,i] because of the transpose?" (second is wrong) - when they see "Ahat_transpose * rhat", they may ask themselves "should I read column-wise because of the transpose, or row-wise as usual since it was transposed from the beginning ?" (first is wrong). Clearly leaving the formula for yhat would make the confusion worse, so NIST should definitely remove it if this option is selected. For this reason, I prefer option 1 (using Bhat) over option 2.

[Dang, Quynh H. (Fed)] Yes, I also prefer option 1.

As suggested by Quynh, I sent an official comment to fips-203-

comm...@nist.gov; I copied this comment in the other thread "Question

about Ahat_transposed in ML-KEM / Kyber", but I can summarize it here as

well.

In this official comment, I listed 2 additional options:

Option 3:

1) change Algorithm 12 (KeyGen) as in the other 2 options, and

2) change line 6 of Algorithm 13 (Encrypt) from "Ahat[i,j] <-

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

3) keep line 19 of Algorithm 13 unchanged

[Dang, Quynh H. (Fed)] This option requires keeping the functions for w_hat and y_hat on page 10. So, it still has room for confusion when one implements line 19. The implementer might do a transpose than use the equation for y_hat, then the result is wrong. The implementer might not do a transpose, then use the equation for w_hat, then the result is also wrong. 

Maybe I am playing the devil's advocate here, but I think these scenario are less likely than an implementer overlooking the swapped indices in XOF(rho,i,j) compared to the XOF(rho,j,i) that was done in KeyGen, which also leads to a wrong result. Since option 3 does not swap indices, it removes this potential source of confusion, and makes it clear that the matrix is exactly the same as for KeyGen.

[Dang, Quynh H. (Fed)] True. It has this advantage over the option 1.  But, people must follow the standard as written, the order of input is matter. If  i||j is coded as j||i, the result would be different.  

In the case of the implementer does the transpose, then use the equation for w_hat, (the result is correct), the disadvantage of this over the option 2 is the unnecessary transpose operation. Option 2 does not do any transpose operation. 

Another benefit of option 2 over option 3 is that option 2 looks the same with the Kyber's spec except that 1 change to remove all rooms for confusion. Kyber uses only A_hat_Transposed, option 2 uses only B_hat. Option 3 uses A_hat and A_hat_Transposed. 

[Dang, Quynh H. (Fed)] Again, I meant option 1 when I said option 2 over here. 

With option 3, the implementer has essentially three ways to go:
- transpose, then do a standard matrix-column product (formula for what)
- do the matrix-column product with an adjusted access pattern (formula for yhat)
- generate Ahat_transpose from the beginning.
The first solution is a plain 1-to-1 implementation of option 3, and the next two are rather straightforward implementation tricks to avoid computing the transpose.

I believe that the pseudo-code description of the algorithm is more useful as an explanation of the underlying logic (hence option 3), but I guess it also makes sense to include micro-optimizations (like options 1 and 2) to help with implementations. So if people prefer option 1 or 2, I am fine with that as well.

Option 4:

1) change Algorithm 12 (KeyGen) as in the other 2 options, and

2) change line 6 of Algorithm 13 (Encrypt) from "Ahat[i,j] <-

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

3) change line 19 of Algorithm 13 from "u <- NTT^(-1)(Ahat o rhat) + e1"

to "u <- NTT^(-1)(rhat o Ahat) + e1"

[Dang, Quynh H. (Fed)]  The downside of this option is that it looks fundamentally different from Kyber that has been known even though the result is correct.  And we would need to specify one more unnecessarily dot product function and then must prove that the 2 equations (one in this FIPS and one in the Kyber's 3rd round spec) produce the same result.  With this option, likely we would receive questions about this from new implementers in the future when they just look at this algorithm and check it against the Kyber's spec. 

The idea behind option 4 was to further go in the direction of explaining the underlying logic. When you put KeyGen, Encrypt, and Decrypt side-by-side, I find it easier with option 4 to replace the intermediate results t, u, v, v' by their value to observe the simplifications and understand what is going on. With the current formulation, one has some additional transpositions to do, which is not a big deal when one does the computation but makes it a little bit more obscure at first.
Anyway, I agree that it may be too different from what is currently in place so we can forget about it.


Robin

[Dang, Quynh H. (Fed)] Regards, Quynh.