1
$\begingroup$

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:

enter image description 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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.
$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – TreeBook1
    Nov 16 at 9:46
  • 1
    $\begingroup$ @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. $\endgroup$
    – honzaik
    Nov 16 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.