Score:2

In dilithium (post quantum signature algorithm), how have the authors precomputed the table of zetas for NTT?

no flag

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

kodlu avatar
sa flag
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.
Score:3
cn flag

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.

ijaz khalid avatar
no flag
Thank you Sir. This is the exact solution that I was looking for.
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.