# XII. Homomorphic Rotation

[TOC]

## Introduction
This is the twelveth chapter of our [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. This chapter shows the way to rotate the encoded vector under ciphertextsa which is a crucial building block for homomorphic linear transformation.

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

## **The High-Level Concept**

In schemes like CKKS (HEAAN), data is packed into a vector (e.g., `[10, 20, 30, 40]`). However, the encryption scheme doesn't understand vectors; it only understands **polynomials**.

Rotation works by exploiting a mathematical link between the polynomial variable $X$ and the position of data in the vector. By changing $X$ to $X^k$ (a substitution), we force the values in the vector to swap places cyclically.

There are two steps to a rotation:
- **Permutation:** Apply a substitution $X \mapsto X^k$ to the ciphertext polynomials.
- **Key Switching:** The substitution breaks the secret key structure. We use a **Rotation Key** $rk$ to fix it so the ciphertext can be decrypted with the original key.

## **The Setup: "Slots" vs. "Polynomials"**

Let's use a small, concrete example.
* **Ring Dimension $N$:** 8. (This means polynomials have degree up to 7).
* **Modulus $M$:** 16 (usually $M=2N$)
* **Number of Slots:** $N/2 = 4$

#### **The Mapping**
The data is stored in "Slots". Each slot corresponds to evaluating the polynomial $m(X)$ at a specific power of a root of unity $\zeta$.
The indices of the slots follow the powers of 5 modulo 16:
* **Slot 0:** Associated with index $5^0 = 1 \pmod{16}$.
* **Slot 1:** Associated with index $5^1 = 5 \pmod{16}$.
* **Slot 2:** Associated with index $5^2 = 25 \equiv 9 \pmod{16}$.
* **Slot 3:** Associated with index $5^3 = 125 \equiv 13 \pmod{16}$.

If we have a message polynomial $m(X)$, the vector values are:
$$
\text{Vector} = [m(\zeta^1), m(\zeta^5), m(\zeta^9), m(\zeta^{13})]
$$

## Example of Homomorphic Rotation

Recall that the polynomial ring we use is $\mathbb{Q}[X]/(X^N+1)$, and $X^N+1$ is the 2N-cyclotomic polynomial. The roots of $X^N+1$ are $\{\zeta, \zeta^2, ... \zeta^{2N-1}\}$. In the following example, we let $N=8$ and roots of $X^N+1$ are $\{\zeta, \zeta^2, ... \zeta^{15}\}$

### **Step 1: The Initial State**
Let $\vec{m}=[10, 20, 30, 40]$ be our plaintext message. Encode $\vec m=m(X)$ by using the [encoding scheme](https://hackmd.io/xugoXjx5QSeDfwheZ-R4Sg). We don't need to know the complex coefficients of $m(X)$ for this example. We know the evaluation $$[m(\zeta^1), m(\zeta^5), m(\zeta^9), m(\zeta^{13})]=[10,20,30,40]$$

### **Step 2: The Transformation (Galois Automorphism)**
To rotate left by 1 slot, we substitute every instance of $X$ in the polynomial with $X^5$.
$$m_{new}(X) = m(X^5)$$

Let's see what is inside the slots of this **new** polynomial $m_{new}(X)$ by evaluating it at the standard slot locations.

- Check New Slot 0 (Location $\zeta^1$):
$$\text{Value} = m_{new}(\zeta^1) = m((\zeta^1)^5) = m(\zeta^5)=20$$

- Check New Slot 1 (Location $\zeta^5$), and $({\zeta^5})^5 = \zeta^{25 \pmod{16}} = \zeta^9$.
$$\text{Value} = m_{new}(\zeta^5) = m((\zeta^5)^5) = m(\zeta^{25})=m(\zeta^9)=30$$

- Check New Slot 2 (Location $\zeta^9$):
$$\text{Value} = m_{new}(\zeta^9) = m((\zeta^9)^5) = m(\zeta^{45})=m(\zeta^{13})=40$$

- Check New Slot 3 (Location $\zeta^{13}$):
$$\text{Value} = m_{new}(\zeta^{13}) = m((\zeta^{13})^5) = m(\zeta^{65})= m(\zeta^1)=10$$

The Final Vector: $[20, 30, 40, 10]$

## Key Switching (Handling the Encryption)
### Ciphertext Rotation
Now let's make rotation work on ciphertext. Let **ciphertext** $ct = (c_0, c_1)$ which encrypts $m(X)$ under a secret key $s(X)$.
$$c_0(X) + c_1(X) \cdot s(X) \approx m(X)$$

When we apply the substitution $X \to X^5$ to the ciphertext polynomials $c_0, c_1$, we get:
$$c_0(X^5) + c_1(X^5) \cdot s(X^5) \approx m(X^5)$$

The new ciphertext is valid, but now it is encrypted with a new secret key: $s(X^5)$ instead of $s(X)$. If we want to decrypt it by using the original secret key $s(X)$, we have to switch the key back.

### Key Switching
Recall the Key Switching algorithm in chapter [X. Relinearization](https://hackmd.io/A-Cz0U64Qxu2jkuCFQppyA). We use a **Key Switching Key** (specifically a Rotation Key). This key is essentially an encryption of the $s(X^5)$ by using the origin key $s(X)$.
- Generates a special key: $rk = \text{Enc}_{s(X)}(s(X^5))$.
- We homomorphically multiply $c_1(X^5)$ by this key.
- The result is a new ciphertext pair $(c'_0, c'_1)$ that encrypts the rotated message $m(X^5)$ but is decryptable by the normal $s(X)$.

## Reference
[Bootstrapping for Approximate Homomorphic Encryption](https://eprint.iacr.org/2018/153)