Number Theoretic Transform (NTT)

The NTT for quotient rings of polynomials often finds specific application in lattice-based cryptography. We do not give a complete introduction here, so for those unfamiliar with the NTT transform, this section is likely not fully understandable.

Full NTT transform

Given a ring \(\mathbb{Z}_q[X]/f(X)\) (assuming that $f$ can be represented as a product of polynomials of degree at most 1 over \(\mathbb{Z}_q\)), there exists an isomorphism (implemented with the NTT) to \(\mathbb{Z}_q^{deg(f)}\). The transform is homomorphic, and addition in the NTT representation remains coefficient-wise, however, the multiplication is also coefficient-wise in the NTT transform, reducing the cost of naïve multiplication from \(deg(f)^2\) to \(deg(f)\) operations.

Instantiation

The NTT algorithm is context dependent, i.e., for a fixed ring, many values can be precomputed using the shared modulus. For instantiation a fixed root of unity needs to be provided, and its powers are precomputed and stored in the context object. We fix these precomputed values with a reference counter in the context modulus object.

use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
use qfall_math::integer_mod_q::PolyOverZq;
use qfall_math::traits::SetCoefficient;

/// Using the ring from Dilithium
pub fn instantiate_ntt_modulus() -> ModulusPolynomialRingZq {
    let n = 256;
    let modulus = 2_i64.pow(23) - 2_i64.pow(13) + 1;

    let mut mod_poly = PolyOverZq::from(modulus);
    mod_poly.set_coeff(0, 1).unwrap();
    mod_poly.set_coeff(n, 1).unwrap();

    // X^{256} + 1 mod 8384017
    let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);

    // 2nth root of unity
    polynomial_modulus.set_ntt_unchecked(1753);
    polynomial_modulus
}

A Dedicated Type

Coefficient-wise arithmetic, especially for matrices over PolynomialRingZq can be tedious to self-implement, so we provide a separate datatype that stores values in the NTT-transform and allows for very basic arithmetic operations. This makes the current state of the program very explicit, and reduces the implementation workload on the developer.

use crate::instantiate_ntt_modulus;
use qfall_math::integer_mod_q::{NTTPolynomialRingZq, PolynomialRingZq};

fn ntt_arithmetic() {
    let modulus = instantiate_ntt_modulus();

    let poly1 = PolynomialRingZq::sample_uniform(&modulus);
    let poly2 = PolynomialRingZq::sample_uniform(&modulus);

    let ntt_poly1: NTTPolynomialRingZq = poly1.ntt();
    let ntt_poly2: NTTPolynomialRingZq = poly1.ntt();

    // normal multiplication
    let normal_mul = poly1 * poly2;

    // ntt multiplication
    let ntt_mul = ntt_poly1 * ntt_poly2;

    assert_eq!(normal_mul, ntt_mul.inv_ntt())
}

Unsupported NTTs

Currently, we only support a full split of positive/negative-wrapped convolutions. Adding other splits (like the one from ML-KEM) is desirable. Refer to the contribution details in case you want to extend the crates.