2
$\begingroup$

I am trying to understand the design rationale of in place NTT in Dilithium. I know that how the splitting of polynomials is done but I cant seem to map this approach to the precomputed table of zetas that is present in the authors code. I have attached the array of values as well. Specifically speaking, is there a way to calculated these values by ourselves? If yes, then how can this be done? Any help regarding this would be very very helpful.enter image description here

$\endgroup$
1
  • $\begingroup$ please give a link to a definition of zeta or explain it. same for NTT. it is a good idea to make your questions detailed and complete. $\endgroup$
    – kodlu
    Aug 24, 2023 at 12:13

1 Answer 1

3
$\begingroup$

I did not try to implement the algorithm myself but those values are powers of $\zeta = 1753 \in \mathbb{Z}_q$ (as hinted by the name) in the Montgomery form where $q = 8380417$ and the elements of $\mathbb{Z}_q$ are represented not as $\{0,\dots, 8380416\}$ but as $\{-\frac{8380416}{2},\dots,0,\dots, \frac{8380416}{2}\}$. Montgomery form is calculated by multiplying by $2^{32}$ and reducing $\mod q$.

Source: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf (Section 8.5 mainly)

In more detail, each value is $\zeta_k = \zeta^{\text{brv}(k)}\mod q$. Where $\text{brv}()$ is the bit reversal operation (see the specification for definition), e.g., $\text{brv}(1)=128,\text{brv}(2)=64$. This corresponds with the values listed.

$\zeta_1 = \zeta^{\text{brv}(1)}=\zeta^{128} \mod q = 4808194$

Now we convert to Montgomery representation and the $\mathbb{Z}_q$ representation.

$4808194\cdot 2^{32} \mod q = 25847$. We get the second value. Similarly,

$\zeta_2 = \zeta^{\text{brv}(2)}=\zeta^{64} \mod q = 3765607$

$3765607\cdot 2^{32} \mod q = 5771523$. This is bigger than $\frac{8380416}{2}$ so we need to reduce.

We need to find a number $\alpha$ in $\{-\frac{8380416}{2},\dots,0,\dots, \frac{8380416}{2}\}$ s.t. $\alpha = 5771523 \mod q$ which is $5771523-q=-2608894$ which is the third value in the array.

The first value in the array ($0$) seems to be just a placeholder to properly index the array (since you want to access elements at indices $1-255$ and not $0-254$. Since in the code they do pre-increment https://github.com/pq-crystals/dilithium/blob/master/ref/ntt.c#L56.

$\endgroup$
1
  • $\begingroup$ Thank you Sir. This is the exact solution that I was looking for. $\endgroup$ Aug 25, 2023 at 9:38

Your Answer

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

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