Parse Algorithm in Kyber Specification

Question

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!

Answer 1

I will try to answer as best I can, but I am no expert on the topic.

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$.