How the ciphertext*ciphertext multiplication works

[lattice0]

According to the seal manual (https://www.microsoft.com/en-us/research/uploads/prod/2017/11/sealmanual-2-3-1.pdf), before the relinearization,

c0 = [t/q (ct0[0]ct1[0])]_q 

c1 = [t/q(ct0[0]ct1[1]1+ct0[1]ct1[0])]_q

c2 = [t/q(ct0[1]ct1[1])]_q

where the multiplications like ct0[0]ct1[0] or ct0[0]ct1[1] etc, are non modular both in polynomial and in coefficient. So if we have a a degree 4096 ct polynomial the product is going to be degree 24096. The reduction happens only after the product is computed, so in theory I'd have to compute a 24096 degree polynomial. This is not a problem if I use the NTT for degree 2*4096 with a bunch of zeros appended to the end of each 4096 degree polynomial, but still the NTT is going to be modulo q on the coefficients, but we should do the modulo after the multiplication by t/q.

I tried finding how the multiplication is done in SEAL and found this paper https://eprint.iacr.org/2018/589.pdf but I couldn't understand how it's done.

How to do this multiplication efficiently?

[fionser]

• Most of the current RLWE library use the negacyclic convolution NTT which does not double the polynomial degrees. In a words, we only take care 4096 coefficients all the time.
• The t/q should be a divide-then-round operation round(t/q*x) which takes x \in [0, q^2) and the output is also in [0, q)
  • So by math the mul ct0[0] * ct1[1] should not wrap round mod q. Many libraries will use a double precision form for this variable.

[lattice0]

Yes, but the tensor products c0, c1 and c2 require a double degree multiplication, then multiply by t/q, and only then round and reduce the degree and coefficient

-------- Mensagem Original -------- Em 1 de mar. de 2023 22:49, Juhou escreveu:

• Most of the current RLWE library use the negacyclic convolution NTT which does not double the polynomial degrees. In a words, we only take care 4096 coefficients all the time.
• The t/q should be a divide-then-round operation round(t/q*x) which takes x \in [0, q) and the output is also in [0, q)

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you authored the thread.Message ID: @.***>

[fionser]

No need to double the polynomial degree, we can think the negacyclic convolution NTT also work for some Q > p^2. What actually matter is to keep the double precision.

For instance, in SEAL, ct0[i] mod q is first lifted to a larger modulo Q. Then perform the tensor product using neg-NTT i.e, degree-N and modulo Q

The current implementation looks very complicated due to the full RNS form. We do not want to convert to the BigInt form for the divide-then-round operation (and switch back). :) The very ancient version of SEAL does it until the BEHZ algorithm is published .

On the other hand, library that uses the BigInt form will have a very simple divide-then-round operation (eg. the HEAAN library though it is a CKKS not a BFV)

[lattice0]

Ok, so if we have modulus 105 and thus a basis of (3,5,7), we can extend the basis with a 4th member such that 3times5times7timesmember > degree*105^2, because the maximum coefficient a poly product can have is degree sums of modulus-1.

So, we do a product like this:

(1,2,3,4)*(5,6,7,8)

(each coefficient is an RNS number)

is turned into

(1,2,3,4,0,0,0,0)*(5,6,7,8,0,0,0,0)

and we do the NTT in the basis (3,5,7,X) where X is a number such that 3times5times7timesX > degree*105^2. Am I right?

Now, what about the t/q and round? How is it done, or was previously done, without big int and without behz?

[fionser]

• 3*5*7*X > C*q^2 for some constant C. For instance, we can use a heuristic bound C = 2*sqrt{degree}
• For BigInt, we can get a value x \in Z_{3*5*7*x} , then the divde-then-round is simply round(t/q*x) mod q.