[docs]
class NTT:
def __init__(self, parameter: dict[str, int]):
self.N = parameter["N"]
self.q = parameter["q"]
self.d = parameter["d"]
self.ZETAS = [
0, 4808194, 3765607, 3761513, 5178923, 5496691, 5234739, 5178987,
7778734, 3542485, 2682288, 2129892, 3764867, 7375178, 557458, 7159240,
5010068, 4317364, 2663378, 6705802, 4855975, 7946292, 676590, 7044481,
5152541, 1714295, 2453983, 1460718, 7737789, 4795319, 2815639, 2283733,
3602218, 3182878, 2740543, 4793971, 5269599, 2101410, 3704823, 1159875,
394148, 928749, 1095468, 4874037, 2071829, 4361428, 3241972, 2156050,
3415069, 1759347, 7562881, 4805951, 3756790, 6444618, 6663429, 4430364,
5483103, 3192354, 556856, 3870317, 2917338, 1853806, 3345963, 1858416,
3073009, 1277625, 5744944, 3852015, 4183372, 5157610, 5258977, 8106357,
2508980, 2028118, 1937570, 4564692, 2811291, 5396636, 7270901, 4158088,
1528066, 482649, 1148858, 5418153, 7814814, 169688, 2462444, 5046034,
4213992, 4892034, 1987814, 5183169, 1736313, 235407, 5130263, 3258457,
5801164, 1787943, 5989328, 6125690, 3482206, 4197502, 7080401, 6018354,
7062739, 2461387, 3035980, 621164, 3901472, 7153756, 2925816, 3374250,
1356448, 5604662, 2683270, 5601629, 4912752, 2312838, 7727142, 7921254,
348812, 8052569, 1011223, 6026202, 4561790, 6458164, 6143691, 1744507,
1753, 6444997, 5720892, 6924527, 2660408, 6600190, 8321269, 2772600,
1182243, 87208, 636927, 4415111, 4423672, 6084020, 5095502, 4663471,
8352605, 822541, 1009365, 5926272, 6400920, 1596822, 4423473, 4620952,
6695264, 4969849, 2678278, 4611469, 4829411, 635956, 8129971, 5925040,
4234153, 6607829, 2192938, 6653329, 2387513, 4768667, 8111961, 5199961,
3747250, 2296099, 1239911, 4541938, 3195676, 2642980, 1254190, 8368000,
2998219, 141835, 8291116, 2513018, 7025525, 613238, 7070156, 6161950,
7921677, 6458423, 4040196, 4908348, 2039144, 6500539, 7561656, 6201452,
6757063, 2105286, 6006015, 6346610, 586241, 7200804, 527981, 5637006,
6903432, 1994046, 2491325, 6987258, 507927, 7192532, 7655613, 6545891,
5346675, 8041997, 2647994, 3009748, 5767564, 4148469, 749577, 4357667,
3980599, 2569011, 6764887, 1723229, 1665318, 2028038, 1163598, 5011144,
3994671, 8368538, 7009900, 3020393, 3363542, 214880, 545376, 7609976,
3105558, 7277073, 508145, 7826699, 860144, 3430436, 140244, 6866265,
6195333, 3123762, 2358373, 6187330, 5365997, 6663603, 2926054, 7987710,
8077412, 3531229, 4405932, 4606686, 1900052, 7598542, 1054478, 7648983]
[docs]
def NTT (self, coefficient_list: list[int]) -> list[int]:
"""
Algorithm 41
Computes the NTT.
Args:
coefficient_list (``list[int]``): ``list`` of integers representing polynomial coefficients.
Returns:
w_hat (``list[int]``): ``list`` of integers representing ``NTT`` transformed polynomial coefficients.
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.
"""
# # --- Input checks ---
if len(coefficient_list) != self.N:
raise ValueError(f"Expected 256 elements, got {len(coefficient_list)}")
# line 1 to 5: initialize w_hat, m and len.
w_hat = coefficient_list[:] # make a copy of the input so that it remains unchanged.
q = self.q
zetas = self.ZETAS
m = 0
length = 128
# line 6 to 8: start 2 loops and initialize 'start'.
while length >= 1:
start = 0
len_times_2 = length << 1
while start < 256:
# line 9: increment m.
m = m + 1
# line 10: assign zetas value to z where zetas are precomputed.
z= zetas[m]
# line 11 to 15: butterfly operation.
limit = start + length
for j in range(start, limit):
j_len = j + length
t = (z * w_hat[j_len]) % q
w_hat[j_len] = (w_hat[j] - t) % q
w_hat[j] = (w_hat[j] + t) % q
# line 16: increment 'start' by left shifted 'length'.
start += len_times_2
# line 18: update length. ( 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1 )
length >>= 1
# line 20: return w_hat
return w_hat
[docs]
def inv_NTT(self, coefficient_list: list[int]) -> list[int]:
"""
Algorithm 42
Computes the inverse of the NTT.
Args:
coefficient_list (``list[int]``): ``list`` of integers representing polynomial coefficients in ``NTT`` domain.
Returns:
w (``list[int]``): ``list`` of integers representing polynomial coefficients.
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.
"""
# input checks
if len(coefficient_list) != self.N:
raise ValueError(f"Input list must have exactly {self.N} coefficients.")
m = 256
length = 1
while length < 256:
start = 0
len_times_2 = length << 1
while start < 256:
m = m - 1
z = (-1 * self.ZETAS[m] + self.q) % self.q
for j in range (start, start + length):
j_len = j + length
t = coefficient_list[j]
coefficient_list[j] = (t + coefficient_list[j_len]) % self.q
val = (t - coefficient_list[j_len]) % self.q
coefficient_list[j_len] = (z * val) % self.q
start = start + len_times_2
length <<= 1 # Bitwise shift
f = 8347681 # modular inverse of 256 in Zq
return [(x * f) % self.q for x in coefficient_list]
# Algorithm 43 is skipped as zeta values are precomputed.
[docs]
def AddNTT(self, a_vec: list[int], b_vec: list[int]) -> list[int]:
"""
Algorithm 44
Computes the sum ``a_vec + b_vec`` of the two elements ``a_vec``, ``b_vec`` belong to ``Tq``
Args:
a_vec (``list[int]``): first polynomial in ``NTT`` domain.
b_vec (``list[int]``): second polynomial in ``NTT`` domain.
Returns:
c (``list[int]``): resulting polynomial in ``NTT`` domain after addition.
Raises:
TypeError: If the inputs are not ``lists`` or ``tuples``.
ValueError: If the input lists are ``not of equal size``.
"""
if len(a_vec) != len(b_vec):
raise ValueError(f"both lists must be of equal size to perform NTT multiplication.")
c = [0 for _ in range(self.N)]
for i in range(self.N):
c[i] = (a_vec[i] + b_vec[i]) % self.q
return c
[docs]
def SubNTT(self, a_vec: list[int], b_vec: list[int]) -> list[int]:
"""
Algorithm 44 modified
Computes the sum ``a_vec - b_vec`` of the two elements ``a_vec``, ``b_vec`` belong to ``Tq``
Args:
a_vec (``list[int]``): first polynomial in ``NTT`` domain.
b_vec (``list[int]``): second polynomial in ``NTT`` domain.
Returns:
c (list): resulting polynomial in ``NTT`` domain after subtraction.
"""
if len(a_vec) != len(b_vec):
raise ValueError(f"both lists must be of equal size to perform NTT multiplication.")
c = [0 for _ in range(self.N)]
for i in range(self.N):
c[i] = (a_vec[i] - b_vec[i]) % self.q
return c
[docs]
def MultiplyNTT(self, a_vec: list[int], b_vec: list[int]) -> list[int]:
"""
Algorithm 45
Computes the product ``a_vec * b_vec`` of two elements ``a_vec``, ``b_vec`` belong to ``Tq``.
Args:
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:
c (``list[int]``): list of integers representing ``NTT`` multiplied polynomial coefficients.
Raises:
TypeError: If the inputs are ``not lists`` or ``tuples``.
ValueError: If the input lists are ``not of equal size``.
"""
if len(a_vec) != len(b_vec):
raise ValueError(f"both lists must be of equal size to perform NTT multiplication.")
q = self.q
return [(a_vec[i] * b_vec[i]) % q for i in range(self.N)]
[docs]
def ScalarVectorNTT(self, vector: list[list[int]], polynomial: list[int]) -> list[list[int]]:
"""
Algorithm 47
Computes the product polynomial * vector of a scalar polynomial and a vector over Tq.
Args:
polynomial (``list[int]``): A polynomial in ``NTT`` domain.
vector (``list[list[int]]``): A ``vector`` of polynomials in ``NTT`` domain.
Returns:
result (``list[list[int]]``): The resulting vector of polynomials after multiplication in ``NTT`` domain.
Raises:
TypeError: If the inputs are ``not lists`` or ``tuples``.
ValueError: If the ``dimensions`` of the polynomial and vector are incompatible.
"""
if len(vector) == 0 or len(vector[0]) != len(polynomial):
raise ValueError("Incompatible dimensions for polynomial-vector multiplication.")
result = [[0] * self.N for _ in range(len(vector))] # initialize product of poly and vector
for j in range(len(vector)):
element_product = self.MultiplyNTT(polynomial, vector[j])
for i in range(self.N):
result[j][i] = element_product[i] % self.q
return result
[docs]
def MatrixVectorNTT(self, matrix: list[list[list[int]]], vector: list[list[int]]) -> list[list[int]]:
"""
Algorithm 48
Computes the product matrix * vector of a matrix and a vector v over Tq.
Args:
matrix (``list[list[list[int]]]``): A ``matrix`` of polynomials in ``NTT`` domain.
vector (``list[list[int]]``): A ``vector`` of polynomials in ``NTT`` domain.
Returns:
result (``list[list[int]]``): The resulting vector of polynomials after multiplication in NTT domain.
Raises:
TypeError: If the inputs are ``not lists`` or ``tuples``.
ValueError: If the dimensions of the matrix and vector are incompatible.
"""
if len(matrix) == 0 or len(matrix[0]) != len(vector):
raise ValueError("Incompatible dimensions for matrix-vector multiplication.")
result = [[0] * self.N for _ in range(len(matrix))] # initialize product of A_cap and NTT(s1)
for i in range(len(matrix)):
for j in range(len(vector)):
element_product = self.MultiplyNTT(matrix[i][j], vector[j])
result[i] = self.AddNTT(result[i], element_product)
return result