# Parse Algorithm in Kyber Specification

In the Kyber specification there is an algorithm "Parse", which receives a byte stream as input and from this the NTT representation $$\hat{a} = \hat{a}_0+\hat{a}_1X + ... + \hat{a}_{n-1}X^{n-1} \in R_q$$ is calculated from $$a \in R_q$$. For the sake of completeness, I have added the algorithm here:

I have a few questions:

1. What exactly is meant here by "NTT representation" of a polynomial? So far I have interpreted the NTT as a special "ring variant" of the DFT. However, I cannot see from the algorithm Parse how the "NTT representation" is calculated here at all.

2. The goal should be that the coefficients of the output polynomial are in $$\mathbb{Z}_q$$. But what exactly are we trying to achieve with the operations $$d_1 := b_i + 256 \cdot (b_{i+1} \text{ mod}^+ 16)$$ and $$d_2 := \lfloor b_{i+1}/16 \rfloor + 16 \cdot b_{i+2}$$? The background to this is not entirely clear to me.

3. Since the parse algorithm plays a role in the calculation of the public key $$\mathbf{A}$$ and the entries of this matrix should be uniformly random, I wonder how this is guaranteed here?

I hope my questions are understandable and meet the requirements of the forum. Thank you in advance and I look forward to your answers!

1. Saying $$\hat f$$ is the NTT representation of $$f$$ is just saying that $$\hat f=\mathsf{NTT}(f)$$.
2. The parse algorithm uses rejection sampling: it takes as input bytes $$b_i\in\{0,\dots,255\}$$ and outputs polynomial coefficients $$\hat a_i\in \mathbb{Z}_q$$ for $$q=3329$$. You could use two bytes $$b_ib_{i+1}$$, interpret it as a number between $$0$$ and $$256^2-1=65535$$ and retry if it is above $$3329$$. But you only need 12 bits to do rejection sampling since $$2^{12}=4096>3329$$, so instead they use 3 bytes $$b_ib_{i+1}b_{i+2}$$ to compute two uniform numbers $$d_1$$ and $$d_2$$ to have two tries at the rejection sampling. $$d_1$$ uses $$b_i$$ and the lower bits of $$b_{i+1}$$ and $$d_2$$ uses $$b_{i+2}$$ and the higher bits of $$b_{i+1}$$.
3. The Parse algorithm outputs a random polynomial $$\hat a$$. The number theoretic transform is a bijection, so if $$\hat a$$ is uniformly random, then so is $$\mathsf{NTT}^{-1}(\hat a)$$, and therefore $$\hat a$$ is the NTT representation of a random polynomial $$a$$.
• Thanks for the great answer! Saying $\hat{f}$ is the NTT representation of $f$ is just saying that $\hat{f}=NTT(f)$. That's exactly how I see it! But: Parse itself does not represent an NTT (as I see it), so I wonder how one can then say that it is an NTT representation. No NTT has been applied yet. You have only generated coefficients that are in $\mathbb{Z}_q$. Commented Nov 16, 2023 at 9:46
• @TreeBook1 I think you are looking at it in a complicated way. Any list of coefficients in $\mathbb{Z}_q$ can be interpreted as a "regular" polynomial in $\mathbb{Z}_q[x]$ OR it can also be interpreted as a polynomial in the NTT domain. See e.g. en.wikipedia.org/wiki/Discrete_Fourier_transform_over_a_ring , that is why FFT is sometimes called a "change of basis" since you are not actually mapping between different rings. The algorithm just generates a set of elements $\mathbb{Z}_q$ that is then interpreted (in other parts of Kyber) as a polynomial in the NTT domain. Commented Nov 16, 2023 at 13:10