The post-quantum lattice-based cryptosystem CRYSTALS-KYBER which has made it to the second round of NIST PQC includes two implementations: 1) a baseline reference implementation in C and 2) an optimized AVX2 implementation. The code repository can be found here.
The AVX2 implementation includes some precomputed constants in consts.c
such as _ZETAS_EXP
and _ZETAS_INV_EXP
. I understand that these precomputed constants are used in Number Theoretic Transform (NTT) and its inverse. I also understand how their counterparts - found in the reference implementation -
have been generated thanks to this question. However, I am not able to understand how they have been generated in the AVX2 implementation? And why some of them are not even reduced modulo q
in [0, q-1]
?
I read the following papers (listed below) in order to understand that, but I could not find detailed information related to my questions. The only information that might be relevant can be found in Section 4 in 3, which I include below for convenience:
Precomputed roots. Instead of loading single precomputed roots and populating the vector registers with broadcast and various shuffling instructions, which is slow, we precompute vectors of roots that can be loaded into a vector register with one aligned load instruction vmovdqa only.
The following papers describe the initial development of Kyber and how it has evolved:
- Initial implementation - round 1 submission is described here and here.
- A faster AVX2 implementation is described here.
- A more optimized version (with smaller modulus reduced from
q = 7681
toq = 3329
) uses some ideas from this paper.
I appreciate if someone could explain or refer to other sources which can help understand how these constants are generated.