Matrix parsing in Kyber

Question

In the Kyber specification the parse function (algorithm 1 on page 6) takes as input a non-terminating byte stream. Although unlikely, an unlimited number of bytes from this stream can be used in this function.

In Kyber.CPAPKE.KeyGen (algorithm 4 on page 8) the parse function is called on line 6 using the output of an extensible output function for the byte stream. On page 11 it is stated that SHAKE-128 is used to instantiate this extensible output function.

The NIST FIPS-202 specification of SHAKE-128 in section 6.2 requires that the function be given an output size before output is generated. How can SHAKE-128 be used to generate the (possibly non-terminating) bytes stream of indeterminate length required by the parse function?

Answer 1

How can $\operatorname{SHAKE-128}$ be used to generate the (possibly non-terminating) bytes stream of indeterminate length required by the parse function?

$\operatorname{SHAKE-128}$ has the property that for any message $M$ and any output lengths $d$ and $d'$ with $d<d'$, $\operatorname{SHAKE-128}(M,d)$ is the beginning of $\operatorname{SHAKE-128}(M,d')$.

The internal structure of $\operatorname{Keccak}$ and it's extension to $\operatorname{SHAKE-128}$ makes it possible to make all the computations involving $M$, then an output of length $d$, then dynamically extend the output to whatever $d'>d$ without redoing any of the previous sponge rounds already performed.

Granted, not all APIs to $\operatorname{SHAKE-128}$ allow that. E.g. I don't see how to reuse Python's shake_128 to ask for more output without causing some duplicate work. We don't need to rehash $M$, but we need to recompute the whole output.

Answer 2

Update:

NIST has stated (at the fifth NIST PQC Standardization conference) that they intend to extend the official API to XOF so that an application (such as Kyber) will be able to generate (squeeze) additional outputs as needed (rather than having to tell the XOF how much output to generate up front). I'm not sure if they intend to update FIPS 202, or include that as a part of FIPS 203 (I suspect the latter - updating FIPS 202 would require a public comment period, and NIST wants FIPS 203 to be published "this summer").

With that update, it's easy - you just ask the XOF for more output.

This, of course, assumes that you can use the new not-yet-published NIST-blessed APIs. If you're stuck with an API (such as Python's) which doesn't anticipate this, well, see fgrieu's answer.