Bootstrapping monomial order and negacyclic property

Zama TFHE-rs
1

Hello,

My math knowledge is rusty. Could you elaborate more on the paragraph starting from
Furthermore, the monomial X modulo X^N + 1 has order 2N,

from www.zama.ai/post/tfhe-deep-dive-part-4 Step2 ?

Why is it ordered 2N and not 1?

Thanks a lot for your work,
Vladimir

2

Hello @sh1ng

I think what is meant here is that given a monomial

a*X^b

then for the polynomial ring Z[ X ]/(X^N+1) you have

aX^b . X^(2N) = aX^b

3

Thank you for the fast reply @IceTDrinker!

If I understand correctly the author’s main point is

if the LUT you are evaluating is negacyclic, then you can encode the information by using all p the possible values for the message, otherwise, you can only use p/2.

What is negacyclic LUT? I know about cyclic/negacyclic convolution of polynom multiplication, but that sentence is confusing.

4

hello @sh1ng so the negacyclic LUT is linked to the negacyclic property of the polynomial multiplication

essentially it means that LUT[x + N] = -LUT[ x ] where N is the degree of the polynomial