Hello!
Sorry if this is not the place to ask something like this or if a to simple question.
I’m trying to test for my Ph.D. a little bit the NTT of OpenFHE, and I’m a little bit lost…
How can I transform an input, say an std::vector<uint64_t> to a NTT space?
I suppose that first I need to create the NTT tables, how I do that?
You can check the code here, which shows how to invoke NTT for a NativePoly. The file also includes code to perform NTT of a DCRTPoly object (DCRT_ntt).
OpenFHE must be initialized properly (by creating a cryptocontext) before you are able to use NTT. The NTT tables will be created automatically as part of OpenFHE initialization.
I suggest looking at the following unit test: https://github.com/openfheorg/openfhe-development/blob/v1.1.1/src/core/unittest/UnitTestTransform.cpp#L60
Hi a naive question: how shall I set as the type V in the following code?
template <typename V>
void CRT_polynomial_mult(const std::string& msg) {
typename V::Integer primeModulus("113"); // 65537
usint cycloOrder = 8;
usint n = cycloOrder / 2;
typename V::Integer primitiveRootOfUnity = lbcrypto::RootOfUnity(cycloOrder, primeModulus);
ChineseRemainderTransformFTT<V>().PreCompute(primitiveRootOfUnity, cycloOrder, primeModulus);
V a(n, primeModulus);
a.at(0) = typename V::Integer("1");
a.at(1) = typename V::Integer("2");
a.at(2) = typename V::Integer("4");
a.at(3) = typename V::Integer("1");
V b(a);
V A(cycloOrder / 2);
ChineseRemainderTransformFTT<V>().ForwardTransformToBitReverse(a, primitiveRootOfUnity, cycloOrder, &A);
V B(cycloOrder / 2);
ChineseRemainderTransformFTT<V>().ForwardTransformToBitReverse(b, primitiveRootOfUnity, cycloOrder, &B);
V AB = A * B;
V InverseFFTAB(cycloOrder / 2);
ChineseRemainderTransformFTT<V>().InverseTransformFromBitReverse(AB, primitiveRootOfUnity, cycloOrder,
&InverseFFTAB);
V expectedResult(n, primeModulus);
expectedResult.at(0) = typename V::Integer("94");
expectedResult.at(1) = typename V::Integer("109");
expectedResult.at(2) = typename V::Integer("11");
expectedResult.at(3) = typename V::Integer("18");
EXPECT_EQ(expectedResult, InverseFFTAB) << msg << "inverse transform";
}
I wanna copy this code into the src/pke/examples folder to run it and print out ciphertext at eval domain and coef domain, modulus. RootOfUnity, Modulus. Might I seek suggestions on how to do it?
I need these information to make sure my custom NTT implementation matching current OpenFHE NTT.
I think I figure it out, let me know if I do it wrongly
BigInteger primeModulus("113"); // 65537
uint32_t cycloOrder = 8;
uint32_t n = cycloOrder / 2;
uint64_t m = n << 1;
NativeInteger modulusQ(primeModulus);
NativeInteger rootOfUnity = RootOfUnity(m, modulusQ);
DiscreteUniformGeneratorImpl<NativeVector> dug;
NativeVector x = dug.GenerateVector(n, modulusQ);
NativeVector X(n);
ChineseRemainderTransformFTT<NativeVector> crtFTT;
crtFTT.PreCompute(rootOfUnity, m, modulusQ);
std::cout << "x before INTT: " << x << std::endl;
crtFTT.ForwardTransformToBitReverse(x, rootOfUnity, m, &X);
std::cout << "X after INTT: " << X << std::endl;
crtFTT.InverseTransformFromBitReverse(X, rootOfUnity, m, &x);
std::cout << "x after NTT: " << x << std::endl;
Might I ask how shall I understand the value being printed out from here? Should it be the coefficients of the ciphertext?
CycloOrder: 8
rootOfUnity: 18
x after INTT: [1 2 4 1] modulus: 113
X after INTT: [46 62 104 18] modulus: 113
x after INTT: [1 2 4 1] modulus: 113
I get above messages, where 18 is the 2n-th root of unity instead of n-th root of unity for a degree N=4. And the naive NTT following the algorithm (Discrete Fourier transform over a ring - Wikipedia) gives me the result of [8, 95, 2, 12]. Here come the Python code of implementing it. Might I seek suggestions on why am I obtaining a different result?
import math
def bit_reverse_indices(n):
"""
Return a list of indices in bit-reversed order for an array of length n (n must be a power of 2).
"""
bits = n.bit_length() - 1
result = []
for i in range(n):
rev = 0
x = i
for _ in range(bits):
rev = (rev << 1) | (x & 1)
x >>= 1
result.append(rev)
return result
def bit_reverse_permutation(arr):
"""
Reorder the array 'arr' according to the bit-reversal permutation.
"""
n = len(arr)
indices = bit_reverse_indices(n)
return [arr[i] for i in indices]
def ntt_bit_reverse(x, q, omega):
"""
Compute the forward Number Theoretic Transform (NTT) of the input vector x over GF(q)
using the iterative Cooley–Tukey algorithm with bit-reversal reordering.
The NTT is defined as:
X[k] = sum_{j=0}^{N-1} x[j] * omega^(j*k) mod q,
where omega is a primitive N-th root of unity in GF(q).
Parameters:
x : list of integers, length must be a power of 2.
q : prime modulus.
omega : a primitive N-th root of unity in GF(q), where N = len(x).
Returns:
A list of integers representing the NTT of x in natural (standard) order.
"""
n = len(x)
# Step 1: Reorder the input into bit-reversed order.
a = bit_reverse_permutation(x[:]) # copy and reorder
# Step 2: Iteratively perform butterfly updates.
# The algorithm runs in log2(n) stages.
m = 2
while m <= n:
# Compute twiddle factor for this stage:
# In each stage, we need a factor: w_m = omega^(n/m) mod q.
w_m = pow(omega, n // m, q)
# Process blocks of length m.
for k in range(0, n, m):
w = 1
for j in range(m // 2):
t = (w * a[k + j + m//2]) % q
u = a[k + j]
a[k + j] = (u + t) % q
a[k + j + m//2] = (u - t) % q
w = (w * w_m) % q
m *= 2
return a
# Example usage:
if __name__ == '__main__':
# Parameters:
# Let q = 17, N = 8, and omega = 2.
# 2 is a primitive 8-th root of unity modulo 17 since 2^8 = 256 ≡ 1 (mod 17) and no smaller power yields 1.
q = 113
N = 4
omega = 18 ** 2 % q # 98
# Input vector x.
x = [1, 2, 4, 1]
# Compute the NTT using the bit-reverse based iterative algorithm.
X = ntt_bit_reverse(x, q, omega)
print("NTT of x:", X)
Aha I found that I’m implementing the vanilla NTT, which is not for RLWE. The problem goes away after supporting negacyclic NTT via (1) 2n-primitive root and (2) twist input before sending it to NTT and twisted it back after getting the result.