microsoft
Suggestions for NTT implementation details
Thank you very much for opening the SEAL library, and we have learned a lot from it, including homomorphic encryption, implementation details, and so on. When I read the source code of NTT, there are some details that confuse me a lot. In the following equations, we will use $p$ to represent the prime modulus number, use $N$ as the poly degree, $g$ as the primitive root, $\gamma$ and $w$ as the $2Nth$ and $Nth$ root, respectively.
- In the implementation details of finding the primitive root, the definition of primitive root is misused. Primitive root is usually used as the $(p-1)th$ root of the prime number $p$, what the code finds is actually the $2Nth$ root. In more detail, In line 313 of numth.cpp, the function is_primitive_root is defined,, according to the implementation details, it checks for $$root^{degree/2} \equiv root^N \equiv -1(mod p)$$ where degree is $2N$ can be found in line 253 of ntt.cpp, so the function checked if root was the $2Nth$ root instead of the primitive root. The same question also arises from the function try_primitive_root, which is defined in line 340 of numth.cpp, this function generates a random 64 bit number firstly, we denote is as $r$, and then calculates $$r^{\frac{p-1}{2N}}$$ the result was stored in destination in line 380 of numth.cpp, then the function is_primitive_root is called to check if it's a $2Nth$ root(not primitive root, see above for details, the $2N$ in $\frac{p-1}{2N}$ also shows it's a $2Nth$ root); the two steps will loop until a $2Nth$ root is found or 100 attemps are used up.
- We confuse why a minimum $2Nth$ root is needed. In line 386 of numth.cpp, the function try_minimal_primitive_root will calculates all the values of the following set $$\gamma, \gamma^3, \gamma^5, \cdots, \gamma^{2N - 1}$$ and find the minimum of it. As we know, all the elements in this set can be regraded as generators which are used to calculate root_powers_ and inv_root_powers_ in NTT table, and according to our experiments, different generators used for NTT will only affect the order in NTT result, and the result will be the same after INTT. So we wonder what is the reason for finding a minimum generator. We think there might be an explanation that, because the $2Nth$ root is found randomly, so the minimum $2Nth$ root is used to make sure that, for a given prime number, a certain NTT table can be generated; if this stands, there is a more convenient way, in the function is_primitive_root, instead of guessing the number randomly, we can try from $1$ to $100$, for example(maybe a larger number), because the primitive root is small in most of the time, this can also result in a certain NTT table.
- Using 2N root can avoid doubling the polynomial length, checkout https://eprint.iacr.org/2016/504.pdf page 2
I think my description of this question wasn't clear enough. Our question isn't about the $2Nth$ root, but about why a minimal $2Nth$ root is needed.
Before writing this issue, our research has covered various modular reduction methods, including the recommanded paper and the issue #331, and so on. According to our research result, the $2Nth$ root is used to implement negtively wrapped convolution, which will result in mod polynomial $x^N + 1$ of the multiplication result.
In SEAL's implemention, first a random $2Nth$ root is found, then it's used as a generator to find the smallest $2Nth$ root, and the second step will requires a lot of computation.
We think there are two other possibilities:
-
The random $2Nth$ root can be used directly to perform NTT, which introduces uncertainty into the intermediate results between NTT and INTT.
This uncertainty can be eliminated in the second step, which finds the smallest $2Nth$ root, but the second step will result in a large computational overhead.
-
When finding the $2Nth$ root, we can try from $1$ to $100$ (maybe a larger value), this will not only give a certain result but also save the computational overhead of finding the smallest $2Nth$ root.