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$.

  • $\begingroup$ As a final remark, the value of $l_{w,q}$ should be $3$. $\endgroup$ Commented Jul 19, 2016 at 0:20
  • $\begingroup$ 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. $\endgroup$
    – caesar
    Commented Jul 19, 2016 at 1:04
  • $\begingroup$ 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... $\endgroup$ Commented Jul 19, 2016 at 1:31
  • $\begingroup$ Why do you think it should be $3$, is it because $a$ has three terms? $\endgroup$
    – caesar
    Commented Jul 19, 2016 at 1:41
  • $\begingroup$ 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$. $\endgroup$ Commented Jul 19, 2016 at 2:17

1 Answer 1


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$


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} $$

About your other issue:

why it is better than school-book polynomial multiplication followed by modular reduction.

I think you have miss understood SEAL's manual... Those two functions are used in the relinearization step (called KeySwitch on the original paper), and they are not used to increase the efficiency of the multiplication, they are used to guarantee the correctness of the decryption under the original private key (and also to manage the noise growth). I suggest that you read section 5 of the original YASHE paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.