8
$\begingroup$

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:

  1. Initial implementation - round 1 submission is described here and here.
  2. A faster AVX2 implementation is described here.
  3. A more optimized version (with smaller modulus reduced from q = 7681 to q = 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.

Improve this question
$\endgroup$
1
  • $\begingroup$ There are parts of the second paper which are likely more relevant --- in particular see the "Constant-time modular reduction" subsection, which answers why some constants are not reduced mod $q$. It seems to be that the precomputed constants are powers of the root of unity, but in a representation that is more friendly for later modular reductions. $\endgroup$
    – Mark
    Jun 14, 2021 at 20:04

0

Reset to default

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.