Hi,

I learned about how LUT (Lookup Table) polynomial rotation works in Zama from this article:

https://www.zama.ai/post/tfhe-deep-dive-part-4

However, I am very confused about why this work…

The purpose of LUT polynomial rotation during bootstrapping is to position the value of the noise-removed plaintext value at the constant term of the LUT polynomial, so that we can extract this coefficient value homomorphically.

To illustrate this, let’s suppose the following example setup:

p = 4 // plaintext space {0, 1, 2, 3}

q = 8 // ciphertext space {0, 1, 2, 3, 4, 5, 6, 7}

m = 3 // a plaintext message

e = 1 // a noise

Delta = 2 // the scale factor, which q / p

The ciphetext is 3 bit, where as the plaintext is 2 bits. Therefore, we scale the plaintext to the left by 1 bit (i.e., multiplying by Delta=4), and reserve the smallest bit for the noise. Thus, when we decrypt the ciphertext, we will simply ignore the last bit and put 0 here (regarding it is a noise).

The following is a mapping between a noisy (Delta-scaled) plaintext and the clean (Delta-scaled) plaintext:

(Delta * m + e, Delta * m)

(0, 0)

(1, 0)

(2, 2)

(3, 2)

(4, 4)

(5, 4)

(6, 6)

(7, 6)

Given this setup, the LUT polynomial should look like this:

V(X) = 0 + X + 2X^2 + 3X^3 + 4X^4 + 5X^5 + 6X^6 + 7X^7

In V(X), each term’s exponent X^i represents the noisy plaintext “Delta * m + e”, and each coefficient c_i represents the noise-removed clean plaintext “Delta * m”.

For each case of noisy plaintext, we rotate V(X) to he left that amount. This gives us the rotation strategy like the following:

**<Delta m + e = 0>**

- V(X) * X^{0} = 0 + 0X + 2X^2 + 2X^3 + 4X^4 + 4X^5 + 6X^6 + 6X^7

=> The constant term’s coefficient is 0 (= Delta * m)

**<Delta m + e = 1>**

- V(X) * X^{-1} = 0 + 2X + 2X^2 + 4X^3 + 4X^4 + 6X^5 + 6X^6 - 0X^7

=> The constant term’s coefficient is 0 (= Delta * m)

**<Delta m + e = 2>**

- V(X) * X^{-2} = 2 + 2X + 4X^2 + 4X^3 + 6X^4 + 6X^5 - 0X^6 - 0X^7

=> The constant term’s coefficient is 2 (= Delta * m)

**<Delta m + e = 3>**

- V(X) * X^{-3} = 2 + 4X + 4X^2 + 6X^3 + 6X^4 - 0X^5 - 0X^6 - 2X^7

=> The constant term’s coefficient is 2 (= Delta * m)

**<Delta m + e = 4>**

- V(X) * X^{-4} = 4 + 4X + 6X^2 + 6X^3 - 0X^4 - 0X^5 - 2X^6 - 2X^7

=> The constant term’s coefficient is 4 (= Delta * m)

**<Delta m + e = 5>**

- V(X) * X^{-5} = 4 + 6X + 6X^2 - 0X^3 - 0X^4 - 2X^5 - 2X^6 - 4X^7

=> The constant term’s coefficient is 4 (= Delta * m)

**<Delta m + e = 6>**

- V(X) * X^{-6} = 6 + 6X - 0X^2 - 0X^3 - 2X^4 - 2X^5 - 4X^6 - 4X^7

=> The constant term’s coefficient is 6 (= Delta * m)

**<Delta m + e = 7>**

- V(X) * X^{-7} = 6 - 0X - 0X^2 - 2X^3 - 2X^4 - 4X^5 - 4X^6 - 6X^7

=> The constant term’s coefficient is 6 (= Delta * m)

So far, all things are good, because rotated constant term’s coefficient value exactly matches our expected (Delta-scaled) plaintext. This rotation works if the number of rotation positions is between 0 and 7.

However, things start to break if we rotate more than 7 positions. During the actual blind (homomorphic) rotation of LUT, we will probably end up rotating V(X) more than N(=8) times back and forth while we perform homomorphic MUX logic. Therefore, we need to ensure that the LUT works even when we rotate the table more than 8 times.

The followings are the results if we rotate V(X) between 8 and 15 positions:

**8 Rotations: <Delta m + e = 0>**

- V(X) * X^{-8} = -0 - 0X - 2X^2 - 2X^3 - 4X^4 - 4X^5 - 6X^6 - 6X^7

=> The constant term’s coefficient is -0 =**0 (= Delta * m = 0)**

**9 Rotations: <Delta m + e = 1>**

- V(X) * X^{-9} = -0 - 2X - 2X^2 - 4X^3 - 4X^4 - 6X^5 - 6X^6 + 0X^7

=> The constant term’s coefficient is -0 =**0 (= Delta * m = 0)**

**10 Rotations: <Delta m + e = 2>**

- V(X) * X^{-10} = -2 - 2X - 4X^2 - 4X^3 - 6X^4 - 6X^5 + 0X^6 + 0X^7

=> The constant term’s coefficient is -2 ≡**6 mod 8 (≠ Delta * m = 2)**

**11 Rotations: <Delta m + e = 3>**

- V(X) * X^{-11} = -2 - 4X - 4X^2 - 6X^3 - 6X^4 + 0X^5 + 0X^6 + 2X^7

=> The constant term’s coefficient is -2 ≡**6 mod 8 (≠ Delta * m = 2)**

**12 Rotations: <Delta m + e = 4>**

- V(X) * X^{-12} = -4 - 4X - 6X^2 - 6X^3 + 0X^4 + 0X^5 + 2X^6 + 2X^7

=> The constant term’s coefficient is -4 ≡**4 mod 8 (= Delta * m = 4)**

**13 Rotations: <Delta m + e = 5>**

- V(X) * X^{-13} = -4 - 6X - 6X^2 + 0X^3 + 0X^4 + 2X^5 + 2X^6 + 4X^7

=> The constant term’s coefficient is -4 ≡**4 mod 8 (= Delta * m = 4)**

**14 Rotations: <Delta m + e = 6>**

- V(X) * X^{-14} = -6 - 6X + 0X^2 + 0X^3 + 2X^4 2X^5 + 4X^6 + 4X^7

=> The constant term’s coefficient is -6 ≡**2 mod 8 (≠ Delta * m = 6)**

**15 Rotations: <Delta m + e = 7>**

- V(X) * X^{-15} = -6 + 0X + 0X^2 + 2X^3 + 2X^4 + 4X^5 + 4X^6 + 6X^7

=> The constant term’s coefficient is -6 ≡**2 mod 8 (≠ Delta * m = 6)**

As you can see above, half of the rotation cases give a wrong constant-term coefficient value for Delta * m. We get this problem because V(X) is a negacyclic polynomial, flipping its coefficient signs whenever they wrap around the X^0 and X^n boundary. We wouldn’t have this problem if the signs didn’t flip…

I don’t know how to come up with a Lookup Table that works. Maybe I have a wrong understanding about how we should create the mappings among the LUT polynomial’s exponents & coefficients, and the space of noisy ciphertext & plaintext?

If so, what should be the correct LUT polynomial look like in this case?

I would really appreciate it if someone come up and clarify my misconception… Thanks a lot.