# 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$. 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. 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... Jul 19 '16 at 1:31
• Why do you think it should be $3$, is it because $a$ has three terms? 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$. 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) (b\cdot w^0, ..., b\cdot w^\ell) & \\ &= \sum_{i=0}^\ell a_i b w^i & (\text{By defn. of dot product}) \\ &= b \sum_{i=0}^\ell a_i w^i & (\text{Since } b \text{ doesn't depend on } i)\\ &= b a & (\text{With the above equality}) \end{align}