LWE to LWE Key Switching

This article is a detailed walkthrough of the key concepts for converting LWE-to-LWE under a different secret. The design is described in this paper.

LWE-to-LWE key switching is essential in several cryptographic settings:

1. Fully homomorphic encryption: After computing on encrypted data, you often need to switch keys — either to refresh ciphertexts, change encryption parameters, or allow a different party to decrypt.
2. Private information retrieval: key switching enables efficient database queries where the server doesn't learn what the client is searching for.
3. Multi-party computation: When encrypted data needs to be handed off between parties with different keys.

The key insight is that rather than performing the expensive key switch directly in LWE space, you convert the LWE ciphertext to RLWE first. This enables an asymptotically faster key switch. You then convert back to LWE, encrypted under the new secret.

Pre-requisites

• LWE Ciphertext: A pair $(b, a) \in \mathbb{Z}_q \times \mathbb{Z}_q^N$ that encrypts a value $\mu$. Decryption computes $\mu = b + \langle a, s \rangle \pmod{q}$. (Note: some papers use the opposite sign convention $\mu = b - \langle a, s \rangle$; we follow the convention from the referenced paper.)

• RLWE Ciphertext: A pair $(b_p, a_p) \in R_q \times R_q$ that encrypts a polynomial $\mu$. Decryption computes $\mu = b_p + a_p \cdot s \pmod{q}$.

• Negacyclic ring property: In $\mathbb{Z}[X]/(X^N + 1)$, we have $X^N = -1$, so $X^{-1} = -X^{N-1}$.

Notation

Overview

Given an LWE ciphertext $(b, a)$ encrypting $\mu_0$ under secret $s$, we want to convert it to a new LWE ciphertext $(b', a')$ encrypting the same value $\mu_0$ under a different secret $s'$.

Why convert to RLWE? The polynomial embedding (described below) enables fast key switching via NTT-accelerated polynomial multiplication, reducing runtime from $\tilde{O}(N^2)$ to $\tilde{O}(N)$.¹ The naive LWE approach requires $N$ scalar-times-vector operations.

Algorithm:

1. Embed into Ring: Convert vector $a$ into polynomial $a(X) = \sum_{i=0}^{N-1} a_i \cdot X^i$.
2. Secret Embedding: Convert $s$ to polynomial $s(X) = \sum_{i=0}^{N-1} s_i \cdot X^{-i}$ using the negacyclic property $X^{-1} = -X^{N-1}$.
3. Key Switching: Apply RLWE key-switching to switch from $s(X)$ to $s'(X)$.
4. Extract: Read coefficients from the resulting RLWE ciphertext to get your new LWE ciphertext under $s'$.

Polynomial Embedding

Polynomial embedding is a technique that converts LWE (vector-based) operations into RLWE (polynomial-based) operations.

The key insight is that an LWE inner product can be computed as the constant term of the product of the LWE ciphertext and the secret.

We'll demonstrate this with $N=4$: the constant term of $a(X) \cdot s(X)$ will equal the inner product $\langle a, s \rangle$.

Let $a = [a_0, a_1, a_2, a_3]$ and $s = [s_0, s_1, s_2, s_3]$.

Define polynomials:

• $a(X) = a_0 + a_1 X + a_2 X^2 + a_3 X^3$
• $s(X) = s_0 + s_1 X^{-1} + s_2 X^{-2} + s_3 X^{-3}$

The LWE inner product $\langle a, s \rangle$ is then given by the constant term of the product $a(X) \cdot s(X)$.

$a(X) \cdot s(X) = (a_0 + a_1 X + a_2 X^2 + a_3 X^3) \cdot (s_0 + s_1 X^{-1} + s_2 X^{-2} + s_3 X^{-3})$

$= a_0 s_0$

$\quad + a_0 s_1 X^{-1} + a_0 s_2 X^{-2} + a_0 s_3 X^{-3}$

$\quad + a_1 X (s_0 + s_1 X^{-1} + s_2 X^{-2} + s_3 X^{-3})$

$\quad + a_2 X^2 (s_0 + s_1 X^{-1} + s_2 X^{-2} + s_3 X^{-3})$

$\quad + a_3 X^3 (s_0 + s_1 X^{-1} + s_2 X^{-2} + s_3 X^{-3})$

$= a_0 s_0$

$+ a_0 s_1 X^{-1} + a_0 s_2 X^{-2} + a_0 s_3 X^{-3}$

$+ a_1 s_0 X + a_1 s_1 X^{0} + a_1 s_2 X^{-1} + a_1 s_3 X^{-2}$

$+ a_2 s_0 X^2 + a_2 s_1 X^{1} + a_2 s_2 X^{0} + a_2 s_3 X^{-1}$

$+ a_3 s_0 X^3 + a_3 s_1 X^2 + a_3 s_2 X^1 + a_3 s_3 X^{0}$

Now collect terms by power and convert negative powers using $X^{-k} = -X^{N-k}$ with $N=4$:

• $X^{-1} = -X^{3}$
• $X^{-2} = -X^{2}$
• $X^{-3} = -X^{1}$

The conversion is enabled by the negacyclic ring property $X^{-1} = -X^{N-1}$.

Final result:

$a(X) \cdot s(X) = \underbrace{(a_0 s_0 + a_1 s_1 + a_2 s_2 + a_3 s_3)}_{\text{constant term } = \langle a, s \rangle}$

$+ (a_1 s_0 + a_2 s_1 + a_3 s_2 - a_0 s_3) X$

$+ (a_2 s_0 + a_3 s_1 - a_0 s_2 - a_1 s_3) X^2$

$+ (a_3 s_0 - a_0 s_1 - a_1 s_2 - a_2 s_3) X^3$

Key insight: The constant term of $a(X) \cdot s(X)$ equals the LWE inner product $\langle a, s \rangle$. This is why embedding LWE into RLWE works.

RLWE Key Switching

After embedding the LWE ciphertext into RLWE (via polynomial embedding above), we have an RLWE ciphertext $(b_p, a_p)$ under secret $s(X)$. We now need to switch it to secret $s'(X)$.

Decrypting with $s$ gives the encrypted value: $\mu_0 = b_p + a_p \cdot s \pmod{q}$

Key switching transforms an RLWE ciphertext under secret $s$ to an RLWE ciphertext $(b'_p, a'_p)$ under secret $s'$ while preserving $\mu_0$:

$b'_p + a'_p \cdot s' \approx \mu_0 \pmod{q}$

The challenge: You need to "remove" the $a_p \cdot s$ term and "replace" it with something involving $s'$, but the switching party cannot compute $a_p \cdot s$ directly without knowing $s$.

Insight: Pre-compute an encryption of $s$ under the new secret $s'$, called $\text{Enc}_{s'}(s)$. Then exploit RLWE's homomorphic property — multiplying a ciphertext by a polynomial multiplies the underlying message:

$a_p \cdot \text{Enc}_{s'}(s) \approx \text{Enc}_{s'}(a_p \cdot s)$

This gives you an encryption of $a_p \cdot s$ under $s'$.

But what does $\text{Enc}_{s'}(s)$ actually mean? It's an RLWE ciphertext $(b_p, a_p)$ where:

$b_p = -a_p \cdot s' + s + e'$

When you decrypt with $s'$: $\quad b_p + a_p \cdot s' = s + e' \approx s$

Gadget Decomposition

The key switching technique above has a critical flaw: $a_p$ can be as large as $q$, and multiplying by it causes a major noise blowup.

To solve this, we can use gadget decomposition. This is a technique for decomposing a large number into a vector of smaller numbers under a pre-computed basis $B$:

$g = (1, B, B^2, \ldots, B^{d-1})$

Gadget Decomposition $g^{-1}$

For any $a_p$, compute: $g^{-1}(a_p) = (a_p^{(0)}, a_p^{(1)}, \ldots, a_p^{(d-1)})$

where:

• Each $a_p^{(i)}$ is a small polynomial (coefficients in $[0, B)$).
• $\sum_{i=0}^{d-1} a_p^{(i)} \cdot B^i = a_p$ (reconstruction)

Example with $B = 256$ and $d = 4$:

If a coefficient of $a_p$ is 0x12345678:

• $a_p^{(0)} = \texttt{0x78}$ (least significant byte)
• $a_p^{(1)} = \texttt{0x56}$
• $a_p^{(2)} = \texttt{0x34}$
• $a_p^{(3)} = \texttt{0x12}$

So $g^{-1}(\texttt{0x12345678}) = (\texttt{0x78}, \texttt{0x56}, \texttt{0x34}, \texttt{0x12})$.

Key Switching Key

Following the gadget decomposition, the key switching key $K$ consists of $d$ RLWE ciphertexts instead of just one encryption of $s$:

$K[0] = \text{Enc}_{s'}(s \cdot B^0) = \text{Enc}_{s'}(s)$

$K[1] = \text{Enc}_{s'}(s \cdot B^1) = \text{Enc}_{s'}(s \cdot B)$

$K[2] = \text{Enc}_{s'}(s \cdot B^2)$

$K[3] = \text{Enc}_{s'}(s \cdot B^3)$

Now, instead of computing $a_p \cdot s$ (huge multiplier), we can:

1. Decompose $a_p$ into $a_p^{(0)}, a_p^{(1)}, \ldots, a_p^{(d-1)}$
2. Combine using the pre-computed keys:

$a_p^{(0)} \cdot K[0] + a_p^{(1)} \cdot K[1] + a_p^{(2)} \cdot K[2] + a_p^{(3)} \cdot K[3] \pmod{q}$

3. This equals (homomorphically):

$a_p^{(0)} \cdot (s \cdot B^0 + e_0) + a_p^{(1)} \cdot (s \cdot B^1 + e_1) + a_p^{(2)} \cdot (s \cdot B^2 + e_2) + a_p^{(3)} \cdot (s \cdot B^3 + e_3) \pmod{q}$

$= s \cdot (a_p^{(0)} \cdot B^0 + a_p^{(1)} \cdot B^1 + a_p^{(2)} \cdot B^2 + a_p^{(3)} \cdot B^3) + (a_p^{(0)} \cdot e_0 + a_p^{(1)} \cdot e_1 + a_p^{(2)} \cdot e_2 + a_p^{(3)} \cdot e_3) \pmod{q}$

$= s \cdot a_p + \underbrace{\sum_{i=0}^{d-1} a_p^{(i)} \cdot e_i}_{\text{total noise}}$

Noise growth analysis:

Without gadget decomposition, computing $a_p \cdot \text{Enc}_{s'}(s)$ directly would give noise $\sim a_p \cdot e$, where $a_p$ can be as large as $q$ — catastrophic for correctness.

With gadget decomposition, the total noise is $\sum_{i} a_p^{(i)} \cdot e_i$. Since each $a_p^{(i)} < B$ and we have $d = \lceil \log_B q \rceil$ digits:

$|\text{noise}| \leq d \cdot B \cdot |e|_{\max}$

Trade-off: Larger $B$ means fewer digits $d$, but larger multipliers. Smaller $B$ means more digits but smaller multipliers. The optimal choice balances $d \cdot B$.

Example

With $B = 256$ and $d = 4$:

$a_p = \texttt{0x12345678}$

$g^{-1}(\texttt{0x12345678}) = (\texttt{0x78}, \texttt{0x56}, \texttt{0x34}, \texttt{0x12})$

$a_p^{(0)} \cdot K[0] = \texttt{0x78} \cdot \text{Enc}_{s'}(s \cdot 1)$

$a_p^{(1)} \cdot K[1] = \texttt{0x56} \cdot \text{Enc}_{s'}(s \cdot 256)$

$a_p^{(2)} \cdot K[2] = \texttt{0x34} \cdot \text{Enc}_{s'}(s \cdot 65536)$

$a_p^{(3)} \cdot K[3] = \texttt{0x12} \cdot \text{Enc}_{s'}(s \cdot 16777216)$

Summing all terms:

$\sum_{i=0}^{3} a_p^{(i)} \cdot K[i] \approx \text{Enc}_{s'}(s \cdot a_p)$

The maximum noise multiplier is $\max(a_p^{(i)}) = \texttt{0x78} = 120$, compared to $a_p = \texttt{0x12345678} \approx 305{,}419{,}896$ without decomposition — a 2.5 million× reduction in noise growth.

Extracting the LWE Ciphertext

Recall, by now you have an RLWE ciphertext $(b'_p, a'_p)$ under secret $s'$.

The constant term of the result polynomial contains the original encrypted value $\mu_0$.

Recall the Polynomial Embedding step: the new LWE ciphertext $(b', a')$ is constructed by reading coefficients from the RLWE ciphertext:

• $b'$ equals the constant term of $b'_p$
• $a'$ comes from the coefficients of $a'_p$, with appropriate negation due to the negacyclic structure:
  • $a_0'$ is coefficient 0 of $a'_p$
  • $a_i'$ for $i > 0$ is -(coefficient $N - i$) of $a'_p$

The negation arises because we embedded $s$ using negative powers of $X$ (i.e., $s(X) = \sum_{i=0}^{N-1} s_i \cdot X^{-i}$), which map to negated coefficients under the negacyclic property $X^{-k} = -X^{N-k}$. When extracting back to LWE form, we must "undo" this transformation, hence the negation for indices $i > 0$.

You now have an LWE ciphertext $(b', a')$ encrypting the same value $\mu_0$ under secret $s'$.

Putting It All Together

We have shown how to convert an LWE ciphertext to an RLWE ciphertext and back by following these steps:

1. Embed LWE → RLWE via polynomial embedding
2. Key-switch RLWE using gadget decomposition for noise control
3. Extract coefficients to get new LWE ciphertext

The key insight is that the constant term of the result polynomial contains the original encrypted value $\mu_0$, and the new LWE ciphertext is constructed by reading coefficients from the RLWE ciphertext.

This conversion has enabled us to reduce the LWE Key Switching runtime from $\tilde{O}(N^2)$ in a naive approach to $\tilde{O}(N)$.

See reference implementation here.

Footnotes

1. The $\tilde{O}$ notation hides logarithmic factors, i.e., $\tilde{O}(f(N)) = O(f(N) \cdot \text{polylog}(N))$. ↩