3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As a final remark, the value of $l_{w,q}$ should be $3$. $\endgroup$ – Hilder Vítor Lima Pereira Jul 19 '16 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 Jul 19 '16 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$ – Hilder Vítor Lima Pereira Jul 19 '16 at 1:31
  • $\begingroup$ Why do you think it should be $3$, is it because $a$ has three terms? $\endgroup$ – caesar Jul 19 '16 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$ – Hilder Vítor Lima Pereira Jul 19 '16 at 2:17
7
$\begingroup$

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

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 correctness of the decryption under the original private key (and also to manage the noise growth). I suggest that you read the section 5 of the original YASHE paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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