# SEAL Homomorphic multiplication

In SEAL homomorphic encryption library, there is an internal procedure to decompose a polynomial with large coefficients into a vector of polynomials with smaller coefficients. The procedure is described in pages 3-4 here. I wonder if someone can paraphrase the procedure and provide a simple example to show how polynomial multiplication can be done via that procedure and why it is better than school-book polynomial multiplication followed by modular reduction.

Let $n = 4$, $q = 199$, $w = 16$. This means that $\ell_{w,q}=2$, $\mathbb{Z}_q = \{-99,...,99\}$, and $\mathbb{Z}_w = \{-8,...,7\}$.

Let $a = 70X^2 + 56X+45$ and $b = 61X+31$.

Please show $Dec_{w,q}(a)$ and $Pow_{w,q}(b)$ and how the dot product is equivalent to polynomial multiplication as follows: $\langle Dec_{w,q}(a),Pow_{w,q}(b) \rangle = a.b \pmod q$.

• As a final remark, the value of $l_{w,q}$ should be $3$. – Hilder Vítor Lima Pereira Jul 19 '16 at 0:20
• But it is specified in the paper as: $l_{w,q}=\lfloor \log_{16}^{199}\rfloor + 1$. I think it is correct, cause the vectors you got are 2-dimension. – caesar Jul 19 '16 at 1:04
• Well, it is strange, the original paper (eprint.iacr.org/2013/075.pdf) defines it adding $2$ instead of $1$. Take a look at page 5... But all the other places I have checked define as you said... – Hilder Vítor Lima Pereira Jul 19 '16 at 1:31
• Why do you think it should be $3$, is it because $a$ has three terms? – caesar Jul 19 '16 at 1:41
• No, the number of terms of the polynomial does not matter. I was just thinking that because of the definition that adds $2$ instead of $1$... But it may be a little mistake on the original paper, since we really need at most $\lfloor \log_w(q) \rfloor + 1$ digits to represent an integer from $\mathbb{Z}_q$ in base $w$. – Hilder Vítor Lima Pereira Jul 19 '16 at 2:17

In this answer, I am reducing using that centered representation of $\mathbb{Z}_q$ and $\mathbb{Z}_w$. Also, I am writing $\ell$ instead of $l_{w,q}$ to simplify the notation.

## Concrete examples:

• $Dec_{w,q}(a) = (6x^2 - 8x - 3, 4x^2 + 4x + 3)$

• $Pow_{w,q} = (61x + 31, 61\cdot16x + 31\cdot16) = (61x + 31, -19 x + 98) \pmod q$

Therefore, we have the following dot product:

\begin{align} Dec_{w,q}(a)\cdot Pow_{w,q}(b) &= (6x^2 - 8x - 3) \cdot (61x + 31)+( 4x^2 + 4x + 3) \cdot (-19 x + 98) \\ &= (366 x^3-302 x^2-431 x-93) + (-76x^3+316 x^2+335 x+294)\\ &= 290 x^3+14 x^2-96 x+201 \\ &= 91x^3 + 14x^2 -96x + 2 \end{align}

And the usual product reduced modulo $q$ is:

$a \cdot b = 4270 x^3+5586 x^2+ 4481x+1395 = 91x^3 + 14x^2 + -96x + 2$

## Explanation:

In order to have a simple understanding, think of the integers (or, polynomials with degree equal to zero): in this case it is easy to see that given an integer $a$, we can write $a$ in base $w$ obtaining digits $a_\ell, ..., a_1, a_0$ such that

$$a = \sum_{i=0}^\ell a_i \cdot w^i$$

In particular, if $w = 2$, then this is the binary representation.

The key point now is to understand why it is still valid if $a$ is any polynomial. In fact it is valid because we just write each coefficient in base $w$, obtaining $\ell$ digits for each coefficient and then we define $\ell$ polynomials, with each polynomial $a_i$ having the $i$-th digits of each coefficient...

For instance, let $p(x) = 3x^3 + 2x + 1$, $q = 199$ and $w = 2$, then, write each coefficient in base $w$, obtaining $3 = (1,1)_w$, $2 = (0,1)_w$, and $1 = (1, 0)_w$, thus, we got $$Dec_{w,q}(p) = (\underbrace{1x^3 + 0x + 1}_{\text{First digits}}, \underbrace{1x^3 + 1x + 0}_{\text{Second digits}})$$

So, once we have accepted that the summation above holds for any polynomial $a$, i.e., we can decompose any polynomial writing its coefficients in base $w$, then, understanding why the dot product is equal to the usual product is straightforward.

The function $Pow_{w,q}(b)$ just put the exponents of the decomposition of the summation above in a vector with the polynomial $b$: $Pow_{w,q}(b) = (b\cdot w^0, b\cdot w^1, ..., b\cdot w^\ell)$.

Therefore, we have

\begin{align} Dec_{w,q}(a) \cdot Pow_{w,q}(b) &= (a_0, ..., a_\ell) \cdot (b\cdot w^0, ..., b\cdot w^\ell) & \\ &= \sum_{i=0}^\ell a_i b w^i & (\text{By definition of dot product}) \\ &= b \sum_{i=0}^\ell a_i w^i & (\text{Since } b \text{ does not depend on } i)\\ &= b a & (\text{By the equality described above}) \end{align}