I would like to know if there is a way to multiply two NativePoly with classical polynomial multiplication.
If you use the function Times, the multiplication is done coefficients by coefficients.
OpenFHE natively supports only the polynomial multiplication in the EVALUATION (NTT) representation. The main motivation is that the cost of direct polynomial multiplication in COEFFICIENT representation is O(N^2), where N is the ring dimension, while it is O(N \log N) when NTTs are used. If needed, you can add your own implementation (I could point you where).
BTW, why do you need to use the classical polynomial multiplication algorithm? If you just need to multiply two polynomials in COEFFICIENT representation, you can convert them to NTT by using SetFormat(Format::EVALUATION), do Times, and then go back to COEFFICIENT by calling SetFormat(Format::COEFFICIENT). This is much faster than doing it using the classical polynomial multiplication algorithm.
Thank you for your answer.
I would like to implement the RLWE scheme for TFHE. Therefore, I need to do multiplication between polynomials for encryption and decryption.
I made tests and it seems that Times works only if the modulus of the polynomials is prime. Except that in the RLWE scheme, q is not a prime number.
When I use Times between two polynomials with a non prime modulus, the result is the scalar product between their coefficients.
I don’t know much about the NTT so I don’t know if there is a way to use it with non prime modulus.
Therefore, is there any other solution than add a classical polynomial multiplication function ?
OpenFHE currently supports both TFHE for LWE with with power-of-two moduli and functional CKKS bootstrapping (think of it as vectorized TFHE) for RLWE with power-of-two (arbitrary) moduli. For polynomial multiplications, we switch the moduli to NTT-friendly ones and do polynomial multiplication using NTT (we never use classical polynomial multiplication as it is too slow). The high level idea is you can always call modulus switching to go from an NTT-unfriendly modulus (like power of two) to an NTT-friendly one (and back if needed). This introduces modulus switching noise, which is typically quite small.
Probably the “easiest” example to study is functional bootstrapping using CKKS. First, get familiar with the paper General Functional Bootstrapping using CKKS and look specifically at Algorithm 1 there (note the ModSwitch calls). Then, look at the examples at openfhe-development/src/pke/examples/functional-bootstrapping-ckks.cpp at v1.4.0 · openfheorg/openfhe-development · GitHub Probably the most useful function is ModSwitch in openfhe-development/src/pke/lib/schemelet/rlwe-mp.cpp at main · openfheorg/openfhe-development · GitHub Note that the RLWE schemelet provides the basic RLWE functionality and it may be useful for your application.
1 Like
Thanks a lot for your response