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?