NTT

Ntt module

class fips.FIPS204.ntt.NTT(parameter)

Bases: object

Parameters:

parameter (dict[str, int])

NTT(coefficient_list)

Algorithm 41

Computes the NTT.

Parameters:

coefficient_list (list[int]) – list of integers representing polynomial coefficients.

Returns:

list of integers representing NTT transformed polynomial coefficients.

Return type:

list[int]

Raises:

• TypeError – If the input is not a list or tuple, or if any coefficient is not an integer.

• ValueError – If the input list does not contain exactly 256 elements.

inv_NTT(coefficient_list)

Algorithm 42

Computes the inverse of the NTT.

Parameters:

coefficient_list (list[int]) – list of integers representing polynomial coefficients in NTT domain.

Returns:

list of integers representing polynomial coefficients.

Return type:

list[int]

Raises:

• TypeError – If the input is not a list or tuple, or if any coefficient is not an integer.

• ValueError – If the input list does not contain exactly 256 elements.

AddNTT(a_vec, b_vec)

Algorithm 44

Computes the sum a_vec + b_vec of the two elements a_vec, b_vec belong to Tq

Parameters:

• a_vec (list[int]) – first polynomial in NTT domain.

• b_vec (list[int]) – second polynomial in NTT domain.

Returns:

resulting polynomial in NTT domain after addition.

Return type:

list[int]

Raises:

• TypeError – If the inputs are not lists or tuples.

• ValueError – If the input lists are not of equal size.

SubNTT(a_vec, b_vec)

Algorithm 44 modified

Computes the sum a_vec - b_vec of the two elements a_vec, b_vec belong to Tq

Parameters:

• a_vec (list[int]) – first polynomial in NTT domain.

• b_vec (list[int]) – second polynomial in NTT domain.

Returns:

resulting polynomial in NTT domain after subtraction.

Return type:

list[int]

MultiplyNTT(a_vec, b_vec)

Algorithm 45

Computes the product a_vec * b_vec of two elements a_vec, b_vec belong to Tq.

Parameters:

• a_vec (list[int]) – list of integers representing polynomial coefficients in NTT domain.

• b_vec (list[int]) – list of integers representing polynomial coefficients in NTT domain.

Returns:

list of integers representing NTT multiplied polynomial coefficients.

Return type:

list[int]

Raises:

• TypeError – If the inputs are not lists or tuples.

• ValueError – If the input lists are not of equal size.

ScalarVectorNTT(vector, polynomial)

Algorithm 47

Computes the product polynomial * vector of a scalar polynomial and a vector over Tq.

Parameters:

• polynomial (list[int]) – A polynomial in NTT domain.

• vector (list[list[int]]) – A vector of polynomials in NTT domain.

Returns:

The resulting vector of polynomials after multiplication in NTT domain.

Return type:

list[list[int]]

Raises:

• TypeError – If the inputs are not lists or tuples.

• ValueError – If the dimensions of the polynomial and vector are incompatible.

MatrixVectorNTT(matrix, vector)

Algorithm 48

Computes the product matrix * vector of a matrix and a vector v over Tq.

Parameters:

• matrix (list[list[list[int]]]) – A matrix of polynomials in NTT domain.

• vector (list[list[int]]) – A vector of polynomials in NTT domain.

Returns:

The resulting vector of polynomials after multiplication in NTT domain.

Return type:

list[list[int]]

Raises:

• TypeError – If the inputs are not lists or tuples.

• ValueError – If the dimensions of the matrix and vector are incompatible.