The NTT and residues of a polynomial modulo factors of $X^{2^d} + 1$

Sahil Sharma

Paper 2023/1812

The NTT and residues of a polynomial modulo factors of $X^{2^d} + 1$

Sahil Sharma

, Signify

Abstract

The Number Theoretic Transform (NTT) plays a central role in efficient implementations of cryptographic primitives selected for Post Quantum Cryptography. Although it certainly exists, academic papers that cite the NTT omit the connection between the NTT and residues of a polynomial modulo factors of $X^{2^d} + 1$ and mention only the final expressions of what the NTT computes. This short paper establishes that connection and, in doing so, elucidates key aspects of computing the NTT. Based on this, the specific instantiations of the NTT function used in CRYSTALS-Kyber and CRYSTALS-Dilithium are derived.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: NTT Kyber Dilithium Post Quantum Cryptography (PQC)Efficient implementations of PQC
Contact author(s): sahil sharma @ signify com
History: 2023-11-24: approved; 2023-11-23: received; See all versions
Short URL: https://ia.cr/2023/1812
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1812,
      author = {Sahil Sharma},
      title = {The {NTT} and residues of a polynomial modulo factors of $X^{2^d} + 1$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1812},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1812}
}