Shaped Rounding: Trading Empty Slots for Precision

At ring degree $N = 2^{15}$, a CKKS ciphertext holds $16384$ complex numbers. Some computations only need a handful of them, but the ring degree is set by security and by the size of the modulus, so it cannot shrink to match the batch. The empty slots are computed on anyway.

My new paper, Fully Homomorphic Encryption for Small Batches of Complex Numbers, puts those slots to work as a guard band that absorbs rounding error in place of the slots that carry data. The data slots then get much more precision at the same scaling factor: in leveled computation, a $20$-bit scaling factor can carry more than $48$ bits of precision. They can also get the same precision at a much smaller scaling factor, which means more levels per bootstrapping.

In FHE, for computing on a few real or complex numbers, the usual choices each miss something. TFHE is built for latency, but on bits and small integers. CKKS has approximate arithmetic, but is built for throughput on thousands of values. This scheme brings the arithmetic of CKKS to small batches, where latency matters more than throughput:

The idea is simple once you see it as a change of basis in the ring, which is what this post is about.

Two coordinate systems

An element of $\mathcal{R} = \mathbb{Z}[X]/(X^N + 1)$ has two natural sets of coordinates. Its coefficients are what we store and round. Its slots $\sigma_t(a) = a(\zeta^{5^t})$ are what CKKS decodes and computes on (vector of complex numbers). The canonical embedding $\sigma$ converts between the two.

Ciphertexts must have integer coefficients, so every rescaling and keyswitching ends by dividing by an integer $r$ and rounding each coefficient. The remainder lies in a cube $[-\tfrac12, \tfrac12]^N$ in coefficient coordinates. Seen in slot coordinates, that cube is rotated and scaled, and the error comes out roughly the same size in every slot. When only a few slots carry data, that even spread is wasteful. We would rather push the error out of the data slots for better precision, while still producing integer ciphertexts.

Rounding in another basis

Rounding each coefficient means rounding to a lattice point in one particular basis, $1, X, \dots, X^{N-1}$. But the lattice $\mathcal{R}$ has many other bases. Rounding in any of them still lands on a lattice point, so the result is still a valid ciphertext component. What changes is the shape of the tile of points that round to each lattice point, and so the region the error falls in.

Take the basis $g, gX, \dots, gX^{N-1}$ for a unit $g$, an element whose inverse also has integer coefficients. Rounding $a/r$ in that basis means:

1. change coordinates by $g^{-1}$,
2. round coefficientwise as usual,
3. change back by $g$.

The result is $g \cdot \lfloor g^{-1} a / r \rceil$, which the paper calls shaped rounding. Its error is $g$ times an ordinary rounding error. In slot coordinates, multiplying by $g$ just scales slot $t$ by $\sigma_t(g)$. You can then choose $g$ small on the data slots, and the error there becomes small too.

The smallest example fits in the plane. The ring $\mathbb{Z}[\sqrt 2]$ (the real part of $\mathbb{Z}[Y]/(Y^4+1)$, with $\sqrt 2 = Y - Y^3$) has two slots, $a + b\sqrt 2 \mapsto (a + b\sqrt2,\ a - b\sqrt2)$. It contains the unit $U = 1 + \sqrt 2$, with slot values $2.414$ and $-0.414$. Call the first slot “data”, the second “guard”, and round with $g = U^{-k}$:

Shaping polynomial $g=1$ $g=U^{-1}$ $g=U^{-2}$

Click or drag to move the point x. It rounds to the lattice point at the center of its tile (circled), and the arrow is the rounding error.

Each tile

data width

guard height

area

Rounding error of x

on the data slot

on the guard slot

The lattice points never move: $U$ is a unit, so every basis shown spans the same lattice. Only the tiles change shape, and their area stays fixed.

The lattice points never move. The tiles are squeezed along the data axis and stretched along the guard axis, and their area stays the same.

The same thing happens in a full ring. Below, $N = 64$, one slot in four carries data, and $g$ is a unit found by the search described in the paper:

Plain rounding Shaped rounding New sample Rotate by 1 Rotate by $R$

Coefficients

Slots (log scale)

data slot guard slot data slot holding a guard's error

In coefficient coordinates, the shaped error looks worse. In slot coordinates, it is about nine bits smaller on the data and three bits larger on the guards.

A polynomial scaling factor

Use shaped rounding everywhere the scheme rounds (rescaling, keyswitching, encoding), and sample encryption errors as $ge$. Every phase then reads

$$\mu = \Delta m + g e \quad\Longleftrightarrow\quad g^{-1}\mu = (g^{-1}\Delta)\, m + e .$$

In the $g^{-1}$ coordinates this is ordinary CKKS with a polynomial scaling factor $g^{-1}\Delta$, worth $\Delta / |\sigma_t(g)|$ in slot $t$. With the paper’s unit and $\Delta = 2^{20}$, the data slots see an effective scaling factor of about $2^{66}$, while each level still consumes only $20$ bits of modulus. With $g = 1$ we are back to CKKS.

This decouples precision from the scaling factor. In CKKS, you cannot keep more bits than you scale by. Here, $\Delta$ only needs to keep the guards under control (see below), and $g$ adds precision on top. At $N = 2^{15}$ and $\Delta = 2^{20}$, sixteen products by fresh operands keep $48.3$ bits of precision, against $5.2$ bits for CKKS at the same scaling factor.

Security does not change. The public bijection $(a, b) \mapsto (ga, gb)$ turns Ring-LWE samples with error $e$ into samples with error $ge$, and back, so the usual CKKS parameters apply as they are.

Volume is conserved

The tiles kept their area because units have norm one:

$$\prod_{t} |\sigma_t(g)| = 1 .$$

Every bit of suppression on the data must be paid for by amplification on the guards. With one data slot in every $R$, a bit of guard amplification buys at most $R - 1$ bits of data precision. The best units spread the cost evenly over the guards. The paper’s unit, for $R = 16$, suppresses the data by $46$ bits, and no guard is amplified by more than $4.6$ bits.

This unit lies in $\mathbb{Z}[X^{N/(2R)}]$, so its slot values repeat every $R$ slots. Rotations by multiples of $R$ therefore keep the error profile aligned with the data. Rotating by $1$ instead, as in the figure above, moves guard errors onto the data.

Keeping the guards in check

Guards are never decoded, but they are still part of the phase. If they grow too large, the phase wraps around the modulus and the data is lost too. Squaring is the simplest case to analyze. A guard bounded by $b$ becomes bounded by $b^2 + c$, where $c$ is the error injected on the guards:

injected error $c$ initial bound $b_0$

attracting $b^{\ast }$

escape $b^{+}$

after 21 squarings

For $c \le 1/4$, guards that start small enough settle below $1/2$ and stay there. Since $c \approx M E / \Delta$, where $M$ is the largest guard magnitude of $g$ and $E$ the size of a rounding remainder, the scaling factor only has to satisfy

$$\Delta \;\ge\; 4 M E .$$

This replaces the usual rule. In CKKS, $\Delta$ must cover the target precision plus the rounding error. Here it only has to keep the guards stable, which at $N = 2^{15}$ gives $20$-bit levels, and the precision comes from $g$. When other operations would let the guards grow, a multiplication by a mask that zeroes them resets them, and it can often be folded into an existing plaintext-ciphertext product.

Bootstrapping

Bootstrapping follows the CKKS blueprint, with one constraint: bring the data back without importing the guards. The linear transforms are built so that their exact maps never read a guard slot, and they write zeros back on the guards. The constants of the modular reduction are masked so that they do not repopulate the guards. The same transforms also convert to and from CKKS with shared keys, so a CKKS computation can hand a small subcircuit to the new scheme and take the result back.

Results

The implementation is built on poulpy. With parameters targeting 128-bit security and batches of $16$ or $64$ values, bootstrapping at $N = 2^{15}$ restores $21$ levels of $20$ bits, with at least $22.6$ bits of precision after $21$ products. At that ring degree, sparse CKKS restores only four levels. To get $16$, it has to move to $N = 2^{16}$:

$k = 16$ values, single thread	Ring degree	Levels	Min. precision	Bootstrapping time
Sparse CKKS	$2^{16}$	$16$	$19.9$ bits	$3.77$ s
This work	$2^{15}$	$16$	$22.9$ bits	$0.75$ s
This work	$2^{15}$	$21$	$22.8$ bits	$0.86$ s

For $16$ and $64$ values, that is about $5$ times faster on one thread and $3.6$ to $3.7$ times faster on $18$ cores. The gap narrows for large batches. At $1024$ values, sparse CKKS still fits $N = 2^{15}$ for one or two levels and is then about $1.1$ times faster. From four levels on, this work is about twice as fast.

Concurrent work

Two independently developed works appeared on ePrint after this paper, and both cite it: GCKKS by Ma, Liu, Wang and Wang, and Focused CKKS by Cheon and Lee. Both share the core idea: multiply the errors by a public polynomial that is small on the data slots, chosen in a subring so that it commutes with the rotations acting on the data. Three groups arriving at it independently is a good sign that it is the natural idea.

The change-of-coordinates view makes the relation precise. When the shaping polynomial is a unit, the three leveled schemes are related by a public change of coordinates under which encryption, rescaling and products coincide. The focused rounding of Cheon and Lee is the shaped rounding above, and GCKKS stores $g^{-1}c$ in place of $c$ and multiplies by $g$ at decryption. All three are bounded by the same norm limit.

The differences lie in what is built around the idea, and in their focus:

	This work	GCKKS	Focused CKKS
Main focus	Low latency for small batches	High precision	High precision
Bootstrapping	Implemented	Announced	Described
Conversions to and from CKKS	Yes	No	Within bootstrapping
Guard analysis	General circuits	Products, linear maps	Products, linear maps
Public code	Yes	No link given	No

The other works also bring ideas this one does not. GCKKS allows non-unit shaping polynomials and reports leveled precision beyond $1000$ bits. The bootstrapping of Focused CKKS masks the integer lift, which cuts the modulus cost of CoeffsToSlots at high precision for larger batches, and should combine well with the transforms here for larger batches and higher precisions. They also adapt high precision CKKS bootstrapping.

The takeaway

CKKS rounds in the coefficient basis because it is the obvious basis, not because it is the best one for precision. A unit $g$ gives another basis of the same lattice, with the same ciphertexts, keys, and security, and it lets you choose where the rounding error goes.

The construction, proofs, error analysis, bootstrapping algorithm, CKKS conversions and benchmarks are fully described in my paper.