2
$\begingroup$

I have been studying about homomorphic encryption (HE) lately, and I am trying to perform simple computations over encrypted data. Specifically, I am interested in the scalar product between two vectors.

I came across this presentation about HElib (an implementation of HE) and on slide 32 there's this particular way of encoding vectors that gives use the scalar product after we multiply the polynomials that represent them:

Given $v=[1, 2, 3]$, $u=[4,5,6]$

If we make two polynomials such as $V(x) = 1 + 2x + 3x^2$, $U(x)=4 + 5x + 6x^2$

But $V(x)U(x) = 4 + 13x + 28x^2 + 27x^3 + 18x^4$

Change a little bit $Û(x) = 6 + 5x + 4x^2$

$V(x)Û(x) = 6 + 17x + 32x^2 + 23x^3 + 12x^4$

$32 = \langle v, u \rangle$

So my question is: How to choose the polynomial encoding of the vectors in order to obtain the scalar product value from a particular coefficient after multiplication? In other words, why inverting the representation of $U(x)$ to $Û(x)$ gave us the scalar product in the third coefficient?

$\endgroup$
2
$\begingroup$

To encode vectors following that technique, you just have to generalize it.

For any two $(d+1)$-dimensional vectors $a = (a_0, a_1, ..., a_d)$ and $b = (b_0, b_1, ..., b_d)$, define the polynomials $a(x) = a_0 + a_1x + ... + a_dx^d$ and $b(x) = b_d + b_{d-1}x + b_{d-2}x^2 + ... + b_0x^d$.

Then, when multiplying $a(x)$ by $b(x)$, among all the coefficients that we multiply, we will multiply $a_0$ by $b_0x^d$, also $a_1x$ by $b_1x^{d-1}$, $a_2x^2$ by $b_2x^{d-2}$, and so on... Notice that all that multiplications are of the form $a_kx^k \cdot b_kx^{d-k}$, which result in $a_kb_kx^d$. Therefore, if we look to the $d$-th coefficient of the product polynomial we will see

$$\left( \sum_{k=0}^d a_kb_k \right) x^d$$

and that summation is exactly the inner product between the vectors $a$ and $b$.

It is worth noting that if this summation is greater than the module of the plaintext ring (usually a parameter $t$ or $p$), than the decoding will not work. Also, that representation is only possible if that value $d$ is smaller than the degree of the polynomial used to define the quotient ring (usually a cyclotomic polynomial).

$\endgroup$
  • $\begingroup$ Thank you very much for the reply! I was having trouble to generalize it, but it is clear now. $\endgroup$ – mshcruz Aug 7 '16 at 6:53
  • 1
    $\begingroup$ You're welcome. By the way, you have to study if this encoding is the best one for your application. If you are going to perform other operations in addition to the inner product, it may be better to encode each component of the vector into a plaintext... $\endgroup$ – Hilder Vítor Lima Pereira Aug 7 '16 at 18:53
2
$\begingroup$

Polynomial multiplication corresponds to convolution of coefficients. Given two polynomials $$U(x)=u_0+u_1 x+\ldots+u_n x^n$$ and $$V(x)=v_0+v_1 x+\ldots+v_m x^m$$ the product $$U(x)V(x)=\sum_{k=0}^n a_k x^k$$ satisfies $$a_s=\sum_{k=0}^s u_k v_{s-k},\quad 0\leq s \leq n+m,$$ making the "reversal" clear.

As you can imagine, thinking formally with no convergence issues which is irrelevant in this case, you can consider $$U(x)V(x) ~mod~ (x^n-1)$$ to obtain a cyclic convolution for two vectors of length $n$ which is useful in some other contexts related to cryptography.

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