2
$\begingroup$

As far as I know, given two $n$-dimensional vectors $\mathbf{a},\mathbf{b} $, tensor product $\mathbf{a} \otimes \mathbf{b} $ produces $n\times n$ matrix.

However in Ring-LWE based homomorphic encryption, tensor product on two 2-dimensional ring elements $c_0=(c_{00}, c_{01}),c_1 =(c_{10}, c_{11}) \in (Z_q[X]/f(x))^2$ where $q$ is an integer and $f(x)$ is a monic irreducible polynomial of degree $n$, produces three ring elements of the form $c_0 \otimes c_1 = (c_{00} \cdot c_{10},c_{01} \cdot c_{10} +c_{00} \cdot c_{11}, -c_{01} \cdot c_{11} )$ as shown in Appendix B.5 (line no. 4 of Mult.) in https://eprint.iacr.org/2012/099.pdf .

Why does this hold instead of producing $2 \times 2=4$ ring elements?

$\endgroup$
  • 1
    $\begingroup$ It’s not really a tensor product, it’s multiplication of linear (degree-1) polynomials where the polynomial coefficients belong to $Z_q[X]/f(X)$. This produces a quadratic (degree-2) polynomial, which has three coefficients. As compared with the tensor product, the two values representing the “cross terms” collapse into one, by commutativity. $\endgroup$ – Chris Peikert Apr 21 '18 at 11:51

Your Answer

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

Browse other questions tagged or ask your own question.