search

pq-crystals / kyber

Other
782 stars 189 forks source link

Why NTT and INTT use the same zeta array only with different order? and Why signed number is used not unsigned number? #54

Closed lizhirui closed 1 year ago

lizhirui commented 1 year ago

I notice that NTT and INTT use the same(not different) zeta array(ref/ntt.c) since commit.

Why is it effective?

And, in Dilithium implementation, intt also uses the same zeta array with ntt except zeta = -zetas[k--] not zeta = zetas[k--], that's why?

In Kyber and Dilithium implementation, why signed number is used not unsigned number?

cryptojedi commented 1 year ago

The values in the zeta array are the same for forward and inverse NTT, they are just used in a different order. So, using the same array saves some space and keeps the code simpler.

Using signed representation can have a small advantage for lazy-reduction strategies, but if you prefer, you can also use unsigned representation. If you do, you will have to update the modular reduction algorithms then and carefully check where reductions are needed to avoid overflows.