D-2.10 Application: Matrix Multiplication

BFV has no clean way to do a homomorphic dot product between two vectors (i.e., ${\overrightarrow{v}}_1\cdot {\overrightarrow{v}}_2$), because the last step of a vector dot product requires summation of all slot-wise intermediate values (i.e., $v_{1,1}{v}_{2,1}+v_{1,2}{v}_{2,2}+\cdots +v_{1,n}{v}_{2,n}$). However, each slot in BFV’s batch encoding is independent from each other, which cannot be simply added up across slots (i.e., input vector elements). Instead, we need $n$ copies of the multiplied ciphertexts and properly align their slots by many rotation operations before adding them up. Meanwhile, the homomorphic input vector slot rotation scheme can be effectively used when we homomorphically multiply a plaintext matrix with an encrypted vector. Remember that given a matrix $A$ and vector $\overrightarrow{x}$ (Definition A-10.3 in §A-10.3):

$A=\left[\begin{array}{ccccc}\hfill a_{⟨0,0⟩}\hfill & \hfill a_{⟨0,1⟩}\hfill & \hfill a_{⟨0,2⟩}\hfill & \hfill \cdots \hfill & \hfill a_{⟨0,n-1⟩}\hfill \\ \hfill a_{⟨1,0⟩}\hfill & \hfill a_{⟨1,1⟩}\hfill & \hfill a_{⟨1,2⟩}\hfill & \hfill \cdots \hfill & \hfill a_{⟨1,n-1⟩}\hfill \\ \hfill a_{⟨2,0⟩}\hfill & \hfill a_{⟨2,1⟩}\hfill & \hfill a_{⟨2,2⟩}\hfill & \hfill \cdots \hfill & \hfill a_{⟨2,n-1⟩}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill a_{⟨m-1,0⟩}\hfill & \hfill a_{⟨m-1,1⟩}\hfill & \hfill a_{⟨m-1,2⟩}\hfill & \hfill \cdots \hfill & \hfill a_{⟨m-1,n-1⟩}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill {\overrightarrow{a}}_{⟨0,\ast ⟩}\hfill \\ \hfill {\overrightarrow{a}}_{⟨1,\ast ⟩}\hfill \\ \hfill {\overrightarrow{a}}_{⟨2,\ast ⟩}\hfill \\ \hfill ⋮\hfill \\ \hfill {\overrightarrow{a}}_{⟨m-1,\ast ⟩}\hfill \end{array}\right],\overrightarrow{x}=(x_0,x_1,\cdots ,x_{n-1})$

The result of $A\cdot \overrightarrow{x}$ is an $m$-dimensional vector computed as:

$A\cdot \overrightarrow{x}=({\overrightarrow{a}}_{⟨0,\ast ⟩}\cdot \overrightarrow{x},{\overrightarrow{a}}_{⟨1,\ast ⟩}\cdot \overrightarrow{x},\cdots ,{\overrightarrow{a}}_{⟨m-1,\ast ⟩}\cdot \overrightarrow{x})=\left(\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_{0,i}\cdot x_i,\sum _{i=0}^{n-1}{a}_{1,i}\cdot x_i,\cdots ,\sum _{i=0}^{n-1}{a}_{m-1,i}\cdot x_i\right)$

Let’s define $\rho (\overrightarrow{v},h)$ as the rotation of $\overrightarrow{v}$ by $h$ positions to the left. And remember that the Hadamard dot product (Definition A-10.1 in §A-10.1) is defined as slot-wise multiplication of two vectors:

$\overrightarrow{a}\odot \overrightarrow{b}=(a_0{b}_0,a_1{b}_1,\cdots ,a_{n-1}{b}_{n-1})$

Let’s define $n$ distinct diagonal vector ${\overrightarrow{u}}_i$ extracted from matrix $A$ as follows:

${\overrightarrow{u}}_i={\{a_{⟨jmodm,i+jmodn⟩}\}}_{j=0}^{n-1}$

Then, the original matrix-to-vector multiplication formula can be equivalently constructed as follows:

$A\cdot \overrightarrow{x}={\overrightarrow{u}}_0\odot \rho (\overrightarrow{x},0)+{\overrightarrow{u}}_1\odot \rho (\overrightarrow{x},1)+\cdots +{\overrightarrow{u}}_{n-1}\odot \rho (\overrightarrow{x},n-1)$

, whose computation result is equivalent to $A\cdot \overrightarrow{x}$. The above formula is compatible with homomorphic computation, because BFV supports Hadamard dot product between input vectors as a ciphertext-to-plaintext multiplication between their polynomial-encoded forms (§D-3.6), and BFV also supports $\rho (\overrightarrow{v},h)$ as homomorphic input vector slot rotation (§D-3.9). After homomorphically computing the above formula, we can consider only the first $m$ (out of $n$) resulting input vector slots to store the result of $A\cdot \overrightarrow{x}$.