Polynomial Decomposition

A-6.2 Polynomial Decomposition

This time, suppose we have polynomial $f$ in the polynomial ring $ℤ_{q} [x] ∕ (x^{n} + 1)$ . Therefore, each coefficient $c_{i}$ of $f$ is an integer modulo $q$ . Polynomial decomposition expresses $f$ as a sum of multiple polynomials in base $β$ and level $l$ as follows:

$⟨$ Summary A-6.2 $⟩$ Polynomial Decomposition

Given $f \in ℤ_{q} [z] ∕ (x^{n} + 1)$ , where:

$f = f_{1} \frac{q}{β^{1}} + f_{2} \frac{q}{β^{2}} + \dots + f_{l} \frac{q}{β^{l}}$

We denote the decomposition of the polynomial $f$ into the base $β$ with the level $l$ as follows:

${𝖣𝖾𝖼𝗈𝗆𝗉}^{β, l} (f) = (f_{1}, f_{2}, \dots, f_{l})$

A-6.2.1 Example

Suppose we have the following polynomial in the polynomial ring $ℤ_{16} [x] ∕ (x^{4} + 1)$ :

$f = 6 x^{3} + 3 x^{2} + 14 x + 7 \in ℤ_{16} [x] ∕ (x^{4} + 1)$

Suppose we want to decompose the above polynomial with base $β = 4$ and level $l = 2$ . Then, each degree’s coefficient of the polynomial $f$ is decomposed as follows:

$𝐱^{3}$ : $6 = 1 \cdot \frac{16}{4^{1}} + 2 \cdot \frac{16}{4^{2}}$

$𝐱^{2}$ : $3 = 0 \cdot \frac{16}{4^{1}} + 3 \cdot \frac{16}{4^{2}}$

$𝐱^{1}$ : $14 = 3 \cdot \frac{16}{4^{1}} + 2 \cdot \frac{16}{4^{2}}$

$𝐱^{0}$ : $7 = 1 \cdot \frac{16}{4^{1}} + 3 \cdot \frac{16}{4^{2}}$

The decomposed polynomial is as follows:

$f = 6 x^{3} + 3 x^{2} + 14 x + 7 = (1 x^{3} + 0 x^{2} + 3 x + 1) \cdot \frac{16}{4^{1}} + (2 x^{3} + 3 x^{2} + 2 x + 3) \cdot \frac{16}{4^{2}}$

${𝖣𝖾𝖼𝗈𝗆𝗉}^{4, 2} (6 x^{3} + 3 x^{2} + 14 x + 7) = (1 x^{3} + 0 x^{2} + 3 x + 1, 2 x^{3} + 3 x^{2} + 2 x + 3)$

A-6.2.2 Discussion

Note that after decomposition, the original coefficients of the polynomial got reduced to smaller numbers. This characteristic is importantly used in homomorphic encryption’s multiplication, for reducing the growth rate of the noise. Normally, the polynomial coefficients of ciphertexts are large because they are uniformly random numbers. Reducing such big constants is important to reduce the noise growth during homomorphic multiplication. We will discuss this more in detail in §D-1.6.

[prev][parent][next]