Score:1

Matrix parsing in kyber

ru flag

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?

Score:1
ng flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.