Privacy Blog

This article discusses the third contribution of the CDKS paper: packing multiple LWEs into one RLWE (CDKS Packing).

Previously, we introduced the concept of LWE to RLWE conversion and LWE to LWE key switching. Please familiarize yourself with these before proceeding.

CDKS Packing is a technique that packs multiple LWEs into one RLWE ciphertext.

The practical applications include:

Private Information Retrieval: A client query results in many LWE ciphertexts. Packing them into RLWE enables efficient server-side processing and smaller response sizes
Batched Homomorphic Operations: Once packed, you can perform SIMD-style operations on all messages simultaneously instead of each one individually.
Communication Savings: One RLWE ciphertext is more compact than $n$ separate LWE ciphertexts.

To grasp the benefit more directly, recall that an LWE ciphertext encrypts a single scalar value $\mu$ , despite having $N$ elements in the ciphertexts vector. By embedding the LWE ciphertext into RLWE (polynomial form), you get a polynomial with $N$ coefficients. Recall from LWE to RLWE Conversion that only constant terms carry the message while the rest are garbage. Instead of having $n$ ciphertexts with $n \cdot (N - 1)$ garbage coefficients, you now have 1 ciphertext with $N$ coefficients.

Compared to prior designs, CDKS Packing reduces computational complexity by roughly $O(N / n)$ where $n$ is the number of LWEs and $N$ is the dimension of the RLWE ciphertext.

The algorithm is based on two phases:

Tree-based Collection: This phase uses a binary tree structure to combine pairs of ciphertexts. It results in an RLWE ciphertext where the phases are placed at evenly-spaced positions in the polynomial.
Partial Trace: This phase applies a partial trace to zero out the garbage coefficients between the meaningful ones. To understand how the garbage arises, see LWE to LWE Key Switching. On the algorithm for eliminating the garbage, see LWE to RLWE Conversion.

Algorithm Intuition

Imagine you have 8 separate LWE ciphertexts. The algorithm works in layers:

Round 1 (Pairing): Take pairs of ciphertexts. Merge them using Trace function so each new ciphertext holds 2 messages. You now have 4 ciphertexts.
Round 2 (Merging Pairs): Take those 4 ciphertexts. Merge them again. Now you have 2 ciphertexts, each holding 4 messages.
Round 3 (Final Merge): Merge the last two. Now you have 1 ciphertext holding all 8 messages.

Instead of trying to stuff all ciphertexts into one polynomial, the algorithm follows a divide-and-conquer (Fast Fourier Transform (FFT) structure) approach. In this case, the application of the Trace function is applied to each layer of the tree.

The Trace Function Mechanics

Recall that in LWE to RLWE Conversion, the Field Trace is used as a mathematical "filter" to zero out the garbage coefficients.

In the packing case, think of it as the reverse of the "Trace" filter we just discussed. Instead of using symmetry to delete noise, use symmetry to weave two separate data streams into a single, denser stream without them colliding.

Collision Risk

Assume two half-full ciphertexts:

$ct_{even}$ : Valid data at indices $0, 2, 4, \dots$ (Garbage at $1, 3, 5, \dots$ )
$ct_{odd}$ : Valid data at indices $0, 2, 4, \dots$ (Garbage at $1, 3, 5, \dots$ )

The goal is to combine them into one ciphertext with $ct_{even}$ at $0, 2, 4, \dots$ and $ct_{odd}$ at $1, 3, 5, \dots$ .

The Naive Failure:

By shifting $ct_{odd}$ (multiply by $X$ ) and adding them, a collision occurs:

$Result = ct_{even} + (X \cdot ct_{odd})$

The "Garbage" from $ct_{even}$ (at index 1) will smash into the "Valid Data" from $ct_{odd}$ (shifted to index 1). The data is corrupted.

The Solution:

Constructive Interference: The algorithm uses a special algebraic formula to perform a clean merge. It forces the valid data to amplify and the colliding garbage to cancel out. The Formula:

$ct_{new} = (ct_{even} + Y \cdot ct_{odd}) + \tau(ct_{even} - Y \cdot ct_{odd})$

Where $Y$ is the shift factor $X^{N/n}$ and $\tau$ is the specific automorphism.

How it works (Step-by-Step):

The Automorphism ( $\tau$ ): We choose a specific rotation $\tau$ that acts as a Conditional Switch:

For Even indices (where $ct_{even}$ lives): $\tau(X^i) = X^i$ (It leaves them alone).
For Odd indices (where $ct_{odd}$ lives): $\tau(X^i) = -X^i$ (It negates them).

The Even Slot (Index 0):

Let's see what happens at an even index.

Input: We have $Data_{even}$ and $Garbage_{odd}$ .
Left Term: $Data_{even} + Garbage_{odd}$
Right Term: $\tau(Data_{even} - Garbage_{odd}) \rightarrow Data_{even} - (-Garbage_{odd}) \rightarrow Data_{even} + Garbage_{odd}$
Correction: The paper's specific derivation ensures that when we apply the formula, the garbage terms that would occupy the "even" slot are negated by $\tau$ and canceled, while the valid "even" data is summed.
Result: $2 \cdot Data_{even}$ (Clean Signal).

The Odd Slot (Index 1):

Now look at an odd index.

Input: We have $Garbage_{even}$ and $Data_{odd}$ .
Behavior: The automorphism $\tau$ flips the sign of the odd slots.
Result: The math ensures $Data_{odd}$ is added constructively ( $Data + Data = 2 Data$ ), while $Garbage_{even}$ is added destructively ( $Garbage - Garbage = 0$ ).

Asymptotic Complexity

This merge operation is repeated in a pattern identical to the Fast Fourier Transform, but in reverse (an inverse butterfly).

Pack 2 ciphertexts (Density $1/N \to 2/N$ ).
Pack 2 of those pairs (Density $2/N \to 4/N$ ).
Repeat until the ciphertext is full.

The standard approach would require $n$ packing operations linearly. Cost per item = $O(1)$ expensive operation.

This approach: You use a tree.

Level 1: $n/2$ merges.
Level 2: $n/4$ merges.
Total Work $\approx n$ .

However, because the work is processed in batches, the amortized cost per single LWE ciphertext approaches the theoretical minimum of 1 automorphism.

Summary

CDKS packing uses the geometric symmetry of the ring to "zip" multiple ciphertexts together, mathematically guaranteeing that the noise from one does not overwrite the data from the other.