Paper 2023/1812 Original: eprint.iacr.org/2023/1812 ↗
The NTT and residues of a polynomial modulo factors of $X^{2^d} + 1$
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.
- History
- 2023-11-23: last updated
- 2023-11-23: published
- Short URL
- https://ia.cr/2023/1812
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}