# XIV. Homomorphic Matrix-Vector Multiplication

[TOC]

## Introduction
This is the fourteenth chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. Homomorphic Matrix-Vector Multiplication is an important building blocks for CKKS Bootstrapping. Applying homomorphic matrix-vector multiplication is equivalent to applying homomorphic linear transformation. See the next chapter how homomorphic linear transformation is used for Bootstrapping.

(*RNS representation is not used in this chapter for clarity.*)

## Homomorphic Matrix-Vector Multiplication under Plaintext Space
### Setup
Let's define a small problem with dimension $N/2 = 4$ (4 slots).
- **Input Vector $\vec z$:**
$$\vec z = [1, 2, 3, 4]$$
- **Matrix $A$:**
$$A = \begin{bmatrix}
1 & 2 & 3 & 4 \\
5 & 6 & 7 & 8 \\
9 & 10 & 11 & 12 \\
13 & 14 & 15 & 16
\end{bmatrix}$$
- **Goal:** Compute $A \cdot \vec z=[30, 70, 110, 150]$

---
### The Algorithm: Diagonal Method
In homomorphic encryption, we cannot access rows or columns arbitrarily. We can only perform **SIMD operations** (add/multiply whole vectors) and **Rotations**.

The formula used is:
$$A \cdot \vec z = \sum_{j=0}^{3} (u_j \odot \rho(\vec z, j))$$

Where:
* $u_j$ is the $j$-th **Extended Diagonal** of matrix $A$.
* $\rho(\vec z, j)$ is the vector $z$ **rotated left** by $j$.
* $\odot$ is component-wise multiplication.

---
### **Step 1: Precompute the Diagonals ($u_j$)**
We extract diagonals and wrap around when we hit the edge. The diagonal $j$:
$$u_j[i] = A_{i, (i+j) \pmod 4}$$
- Diagonal 0: $u_0=[A_{00}, A_{11}, A_{22}, A_{33}]=[1, 6, 11, 16]$
- Diagonal 1: $u_1=[A_{01}, A_{12}, A_{23}, A_{30}]=[2, 7, 12, 13]$
- Diagonal 2: $u_2=[A_{02}, A_{13}, A_{20}, A_{31}]=[3, 8, 9, 14]$
- Diagonal 3: $u_3=[A_{03}, A_{10}, A_{21}, A_{32}]=[4, 5, 10, 15]$

### **Step 2: Rotate the Vector ($z$)**
We generate 3 rotated versions of the ciphertext $z = [1, 2, 3, 4]$.

* $\rho(\vec z, 0) = [1, 2, 3, 4]$ (No rotation)
* $\rho(\vec z, 1) = [2, 3, 4, 1]$ (Rotate left by 1)
* $\rho(\vec z, 2) = [3, 4, 1, 2]$ (Rotate left by 2)
* $\rho(\vec z, 3) = [4, 1, 2, 3]$ (Rotate left by 3)

### **Step 3: Multiply and Accumulate**
Now we multiply each diagonal by the corresponding rotated vector and sum them up.

**1. Iteration $j=0$:**
$$
\begin{aligned}
\text{Term}_0 &= u_0 \odot \rho(\vec z, 0) \\
&= [1, 6, 11, 16] \times [1, 2, 3, 4] \\
&= [\mathbf{1}, \mathbf{12}, \mathbf{33}, \mathbf{64}]
\end{aligned}
$$

**2. Iteration $j=1$:**
$$
\begin{aligned}
\text{Term}_1 &= u_1 \odot \rho(z; 1) \\
&= [2, 7, 12, 13] \times [2, 3, 4, 1] \\
&= [\mathbf{4}, \mathbf{21}, \mathbf{48}, \mathbf{13}]
\end{aligned}
$$

**3. Iteration $j=2$:**
$$
\begin{aligned}
\text{Term}_2 &= u_2 \odot \rho(z; 2) \\
&= [3, 8, 9, 14] \times [3, 4, 1, 2] \\
&= [\mathbf{9}, \mathbf{32}, \mathbf{9}, \mathbf{28}]
\end{aligned}
$$

**4. Iteration $j=3$:**
$$
\begin{aligned}
\text{Term}_3 &= u_3 \odot \rho(z; 3) \\
&= [4, 5, 10, 15] \times [4, 1, 2, 3] \\
&= [\mathbf{16}, \mathbf{5}, \mathbf{20}, \mathbf{45}]
\end{aligned}
$$

### **Step 4: Final Summation**
Add the four resulting vectors together:

$$
\begin{bmatrix} 1 \\ 12 \\ 33 \\ 64 \end{bmatrix} +
\begin{bmatrix} 4 \\ 21 \\ 48 \\ 13 \end{bmatrix} +
\begin{bmatrix} 9 \\ 32 \\ 9 \\ 28 \end{bmatrix} +
\begin{bmatrix} 16 \\ 5 \\ 20 \\ 45 \end{bmatrix}
$$

**Calculation:**
* Slot 0: $1 + 4 + 9 + 16 = \mathbf{30}$
* Slot 1: $12 + 21 + 32 + 5 = \mathbf{70}$
* Slot 2: $33 + 48 + 9 + 20 = \mathbf{110}$
* Slot 3: $64 + 13 + 28 + 45 = \mathbf{150}$

Final Result $[30, 70, 110, 150]$ matches the expected result perfectly. This method is efficient because it processes all rows simultaneously using only simple SIMD multiplications and rotations.

## Homomorphic Matrix-Vector Multiplication under Ciphertext Space

The above shows Homomorphic Matrix-Vector Multiplication under plaintext space. However, in fhe scheme we cannot see any plaintext message. We explain the execution under ciphertext space below.

### **Setup (Ciphertext Space)**

- **Ring:** Polynomials modulo $X^N + 1$ (where $N=8$ for the 4-slot example).
- **Decryption Rule:** $\text{Message} \approx c_0(X) + c_1(X) \cdot s(X)$.
- **Input Vector:** $\vec z = [1, 2, 3, 4]$ and $m(X)$ encoding $\vec z$.
- **Input Ciphertext:** $ct = (c_0, c_1)$
---
### **Step 1: Ciphertext Rotation (The Most Complex Part)**

We need to create rotated copies of $ct_{in}$. This step is called [homomorphic rotation](https://hackmd.io/d7HeidPUQ12ig9mYtCWXEQ). Check the link to see how homomorphic rotation works. After rotation, we have ciphertexts $ct, ct_1, ct_2, ct_3$ encrypting messages that encode $\rho(\vec z, 0)=\vec z, \rho(\vec z, 1), \rho(\vec z, 2), \rho(\vec z, 3)$

---
### **Step 2: Encoding the Diagonals (Plaintext Space)**
Recall the plaintext diagonals (from the previous example):
- Diagonal 0: $u_0=[A_{00}, A_{11}, A_{22}, A_{33}]=[1, 6, 11, 16]$
- Diagonal 1: $u_1=[A_{01}, A_{12}, A_{23}, A_{30}]=[2, 7, 12, 13]$
- Diagonal 2: $u_2=[A_{02}, A_{13}, A_{20}, A_{31}]=[3, 8, 9, 14]$
- Diagonal 3: $u_3=[A_{03}, A_{10}, A_{21}, A_{32}]=[4, 5, 10, 15]$

We have to encode these Diagonal vector into polynomials before multiplying. The encoding algorithm is the same as [here](https://hackmd.io/d7HeidPUQ12ig9mYtCWXEQ#Step-1-The-Initial-State). After encoding, we have $U_0(X), U_1(X), U_2(X), U_3(X)$
* $U_i(X)$ is a polynomial where $U_i(\zeta^1)=u_{i,0}, U_i(\zeta^5)=u_{i,1}$, etc.

---
### **Step 3: Homomorphic Multiplication (Scalar Mult)**

Now we multiply the rotated ciphertexts by the encoded diagonals.
We perform this for each diagonal $j=0$ to $3$.

- Operation for $j=0$:
We take the unrotated ciphertext $ct = (c_0, c_1)$ and the encoded diagonal $U_0(X)$.
$$ct' = (c_0 \cdot U_0, \; c_1 \cdot U_0)$$ Now, $ct'$ encrypts $[1, 2, 3, 4] \odot [1, 6, 11, 16] = [1, 12, 33, 64]$.
- Operation for $j=1$:
We take the rotated ciphertext $ct_{1} = (c_{0, r1}, c_{1,r1})$ and encoded diagonal $U_1(X)$.
$$ct_1' = (c_{0,r1} \cdot U_1, \; c_{1,r1} \cdot U_1)$$
Same, $ct_1'$ encrypts $[2, 3, 4, 1] \odot [2, 7, 12, 13] = [4, 21, 48, 13]$.
- Operation for $j=2$: *(ignore ...)*
- Operation for $j=3$: *(ignore ...)*

*(We can simply multiply the ciphertext polynomials by the plaintext polynomial).*

---

### **Step 4: Homomorphic Addition (Accumulation)**

Finally, we sum the four partial ciphertexts. In ciphertext space, addition is the simplest operation: just add the polynomials component-wise.
$$ct_{final} = \sum_{j=0}^{3} ct_j'$$

The resulting pair of polynomials $(c_{0,final}, c_{1,final})$ encrypts the sum of the underlying vectors: $[1, 12, 33, 64] + [4, 21, 48, 13] + ... = [30, 70, 110, 150]$

We finally finish doing Homomorphic Matrix-Vector Multiplication by using the following techiques:
- Vector Encoding Scheme
- Homomorphic Rotation
- Homomorphic Multiplication
- Key Switching
- Rescaling (since Homomorphic Multiplication needs to drop one modulus)
- Homomorphic Addition