Bivariate CKKS

CKKS is usually presented over RNS: pick a chain of NTT-friendly primes $q_0, q_1, \dots, q_L$, store every polynomial as its CRT residues, and let level be the unit of homomorphic budget. The recent paper of Belorgey, Carpov, Gama, Guasch and Jetchev, Revisiting Key Decomposition Techniques for FHE: Simpler, Faster and More Generic, keeps the scheme but throws out the prime chain entirely. In its place sits the bivariate representation: one cyclotomic axis, one multi-precision axis, and a free parameter $K$ that has nothing to do with primes.

This article walks through CKKS as it is implemented in poulpy-ckks on top of that representation. It is meant as a bridge between the rather abstract setting of the paper (Section 3 introduces the representation in full generality, with gadget decompositions and external products as the main motivation) and what actually runs on a CPU when you call ckks_add_into or ckks_mul_into. Some familiarity with CKKS is assumed, deep RNS expertise is not.

API note (16 August 2026): the code and naming below were checked against poulpy 139a3cd, the tip of main at the time of this update.

1. The bivariate representation, math first

Fix the cyclotomic ring

$$\mathcal{R} = \mathbb{Z}[X]/\langle X^N + 1\rangle, \qquad N \text{ a power of two},$$

and let $\mathbb{T} = \mathbb{R}/\mathbb{Z}$ be the real torus. CKKS encrypts elements of the real torus polynomial ring

$$\mathbb{T}_N[X] \;=\; \mathbb{R}[X]/\langle X^N+1\rangle \bmod \mathbb{Z}.$$

Pick an integer $K \in [10, 60]$, the limb size. In poulpy this is called base2k. A typical value is $K = 52$ for the NTT4x30 backend family. The bivariate representation describes an element $Q \in \mathbb{T}_N[X]$ by a bivariate integer polynomial

$$P(X, Y) \;=\; \sum_{i=0}^{N-1} \sum_{j \geq 1} a_{i,j}\, X^{i}\, Y^{j} \;\in\; \mathbb{Z}[X, Y]/\langle X^N + 1\rangle,$$

with $a_{i,j} \in [-2^{K-1}, 2^{K-1})$ (the paper calls such a polynomial $K$-normalized and reduced), together with the evaluation map

$$\varphi_K : \mathbb{R}[X, Y]/\langle X^N+1\rangle \;\longrightarrow\; \mathbb{R}[X]/\langle X^N+1\rangle, \qquad P(X, Y) \;\longmapsto\; P(X,\, 2^{-K}).$$

We require $\varphi_K(P) \equiv Q \pmod{\mathbb{Z}}$. The picture splits into two independent axes:

• the $X$-axis carries the cyclotomic structure: a length-$N$ vector of integer coefficients per limb, handled by an FFT over $\mathbb{R}$ or an NTT modulo a single large prime;
• the $Y$-axis carries the multi-precision structure: $\ell$ limbs in $[-2^{K-1}, 2^{K-1})$, with carry propagation playing the role of arithmetic over $\mathbb{Z}$.

Two structural consequences worth highlighting up front.

Limb count is a function of precision, not of primes. The number of limbs $\ell \approx L/K$ depends only on the desired precision $L = -\log_2(\text{noise})$ and on $K$. There is no prime chain, and $K$ is a free parameter rather than a property of some prime family.

Prefix property. A precision-$L$ ciphertext, truncated to its first $\ell' < \ell$ limbs along $Y$, is a valid precision-$L'$ ciphertext of the same plaintext, with $L' = \ell' \cdot K$. Modulus switching becomes a length adjustment on the limb sequence, i.e. a slice, not a computation.

↑ $j$ (multi-precision, $\ell$ limbs)

$j=\ell$

$a_{0,\ell }$

$a_{1,\ell }$

$a_{2,\ell }$

$a_{3,\ell }$

⋯

$a_{N-1,\ell }$

⋮

⋮

⋮

⋮

⋰

⋮

$j=2$

$a_{0,2}$

$a_{1,2}$

$a_{2,2}$

$a_{3,2}$

⋯

$a_{N-1,2}$

$j=1$

$a_{0,1}$

$a_{1,1}$

$a_{2,1}$

$a_{3,1}$

⋯

$a_{N-1,1}$

$i=0$

$i=1$

$i=2$

$i=3$

$i=N-1$

$\text{each }{a}_{i,j}\in [-2^{K-1},2^{K-1})$

$i$ (cyclotomic, length $N$) →

2. CKKS in poulpy: where the bivariate ring lives

A CKKS ciphertext in poulpy-ckks is a GLWE buffer paired with semantic precision metadata, plus a typestate marker for whether the limb digits are carry-normalized:

pub struct CKKSCiphertext<
    D: Data,
    W: ZnxWord,
    S: CKKSNormalizationState = Normalized,
> {
    pub(crate) inner: GLWE<D, W>,
    pub(crate) meta: CKKSMeta,
    _state: PhantomData<S>,
}

pub struct CKKSMeta {
    pub log_delta: usize,
    pub log_sparsity: usize,
    pub slots: SlotsKind,
}

W names the backend’s coefficient-word layout; user code normally lets the backend-specific alias CKKSCiphertextOwned<BE> fill it in. The S parameter is either Normalized or Unnormalized and tracks the limb invariant the unnormalized arithmetic variants discussed in §5.3 expose at the type level. CKKSMeta stores the scale log_delta, the sparse-packing factor log_sparsity (0 for dense / full packing), and a SlotsKind::{Real, Complex} claim. The last field lets operations preserve a known-real subfield when possible without ever mistaking an unknown value for real.

The remaining homomorphic budget is deliberately not stored in CKKSMeta; it is derived on demand from the wrapped GLWE’s torus width k as $\log\beta = k - \log\Delta$.

These quantities have direct mathematical meaning:

• $\log\Delta$ (log_delta) is the base-$2$ logarithm of the plaintext scaling factor: the encoded message lives at scale $\Delta = 2^{\log\Delta}$.
• $\log\beta$ (log_budget, derived) is the remaining homomorphic capacity in bits: the noise sits at the LSB end of the limb stack, mixed with the lowest bits of the scaled plaintext, and $\log\beta$ is the gap between the noise floor and the message MSB.

Together they define the effective torus width used by the kernels, which is exactly the wrapped GLWE’s torus width k:

$$k_{\mathrm{eff}} \;=\; k \;=\; \log\Delta \;+\; \log\beta.$$

The logical limb count is size() = ceil(k / K). Allocation is separate and fixed: max_size() is the number of limbs the backing buffer can hold, and max_k() = max_size() * K. They agree just after an exact-size allocation, but an operation may reduce k and therefore size() while leaving max_size() and max_k() unchanged. The bits between k and the next limb boundary are padding; any further gap up to max_k is unused capacity.

Picturing one ciphertext as a stack of limbs along $Y$, with the most-significant limb on top:

MSB LSB

$\log \beta$ clean bits

$\log \Delta$ encoded message

$\text{noise}$ mixed in LSBs

$k_{\mathrm{eff}}$

$k_{\max }=\lceil k_{\mathrm{eff}}/K\rceil \cdot K$

$\ell \text{ limbs of }K\text{ bits}$

A plaintext is the same shape minus the secret-key half. Unlike RNS, where a plaintext has to live across the full RNS basis to interact with a ciphertext, a bivariate plaintext can be much shorter than the ciphertext it operates on and stored with just enough precision to hold it. Alignment of the two limb stacks is handled inside the kernels to allow operations.

3. The torus is a lie

The torus picture is elegant. It is also, on a finite computer, a representation lie. What we call the torus is $\mathbb{T} = \mathbb{R}/\mathbb{Z}$, a continuous one-dimensional object. What actually lives in RAM, in poulpy, is

$$\widetilde{\mathbb{T}}_K^{(\ell)} \;\simeq\; \prod_{j=1}^{\ell} \big[-2^{K-1},\, 2^{K-1}\big)\;\subset\;\mathbb{Z}^{\ell},$$

a vector of $\ell$ signed $K$-bit integers per cyclotomic coefficient. Reading the limbs $(a_{i,1}, a_{i,2}, \dots, a_{i,\ell})$ as the $X^i$-coefficient of a torus element means evaluating

$$\sum_{j=1}^{\ell} a_{i,j} \cdot 2^{-jK} \pmod{1},$$

which is exactly $\varphi_K$ applied coefficient-wise. The torus has been discretized at resolution $2^{-K\ell}$, and any “real number on the torus” only exists up to that resolution.

From RNS-CKKS to bivariate

For readers more comfortable with the RNS picture: in RNS-CKKS a ciphertext at level $L$ lives in $\mathcal{R}_{Q_L}^2$ with $Q_L = \prod_{j=0}^{L} q_j$, stored as the CRT tuple of residues modulo each $q_j$. The “level” is both a budget and a storage layout: dropping a level (reducing the modulus to $Q_{L-1}$) is itself just discarding the residue at $q_L$, but the useful operation that actually consumes a level, rescaling the ciphertext by dividing it by $q_L$, needs a mod-switch pass on every remaining residue.

In bivariate, the same ciphertext lives in $(\mathbb{Z}[X,Y]/\langle X^N+1\rangle)^2$, $K$-normalized, with $\ell$ limbs along $Y$. The CRT axis is gone. The “level” decouples into three quantities:

Quantity	RNS-CKKS	Bivariate
Budget unit	one prime $q_j$ ($\sim 30$–$50$ bits)	one bit
Storage unit	one RNS residue (one prime)	one limb of $K$ bits
Rescale (consume budget)	divide + mod-switch	bit shift; choose a narrower result k when useful
Modulus	product $Q_L$ of primes	$2^{K\ell}$
Key-switch online NTTs	$O(\ell^2)$	$O(\ell)$
Evaluation key	tied to prime chain	prefix-shared across precisions

The hard part of the migration is not algebra: it is essentially a change of basis at the storage level, but rebuilding the kernels around the semantic pair (log_delta, derived log_budget), the requested logical width k, and the allocation max_k instead of the single fused level. Going from RNS to bivariate looks like a change of representation, but in practice it is mostly a change of bookkeeping, and the bookkeeping is most of CKKS engineering. Bivariate CKKS is also easier to parameterize since instead of having to choose a chain of prime moduli, one can just choose $K$ and $\ell$. Note that Grafting in RNS provides a similar decoupling functionality, but the difference is that what Grafting gets by engineering, you get by design in the bivariate representation.

4. Three independence axes

Once the representation is set, every CKKS operation has to deal with three quantities that may differ between operands and result:

• $\log\Delta$ - the scale at which the message is encoded.
• $\log\beta$ - the bits of clean torus above the message.
• $k_{\max}$ - the fixed physical storage capacity, while the requested logical precision is the derived $k = \log\Delta + \log\beta$.

In RNS-CKKS these collapse into a single state (the level), so reconciling two ciphertexts amounts to “modulus-switch to the lowest common level”. In bivariate they are independent and each has its own primitive.

The $\log\beta$ axis is reconciled by shifting inside the torus. Two ciphertexts at the same scale but with different budgets have their noise floors at different bit positions in the limb stack. A left-shift of the higher-budget operand by the budget difference brings its noise floor down to the lower-budget operand’s, at the cost of consuming the extra budget:

MSB LSB

$a$

$\log {\beta }_a$

$\log \Delta$

$\text{noise}$

$b$

$\log {\beta }_b$

$\log \Delta$

$\text{noise}$

$\text{left-shift }b\text{ by }({\beta }_b-{\beta }_a)\text{ bits to align noise floors}$

$a$

$\log {\beta }_a$

$\log \Delta$

$\text{noise}$

$b^{\prime }$

$\log {\beta }_a$

$\log \Delta$

$\text{noise}$

$\text{matched}$

The $k$ / max_k axis is explicit in the destination. The destination’s k() is the precision requested from an *_into operation; if it is narrower than the natural result, the kernel rounds away the low-order tail and charges the difference to $\log\beta$. max_k() only describes the fixed allocation and does not silently select the arithmetic width. To obtain a physically smaller owned result, allocate the destination at the desired k before the operation.

The $\log\Delta$ axis is tracked by the kernels too. Ciphertext addition and multiplication accept unequal scales and stamp the result with $\min(\log\Delta_a, \log\Delta_b)$; multiplication absorbs $\max(\log\Delta_a, \log\Delta_b)$ bits. MultiplicationPrecisionUnderflow means the available budget cannot pay that cost, not merely that the input scales differ. Plaintext operands declare both their CKKS metadata and their encoded integer width; an impossible ciphertext–plaintext alignment produces PlaintextAlignmentImpossible.

All fallible CKKS operation traits now return CKKSResult<T>. Recoverable conditions such as the two above live under CKKSError::Composition(CKKSCompositionError), while backend or invariant failures are carried as CKKSError::Internal.

5. Bivariate CKKS operations

5.1 Encoding and decoding

Encoding follows the standard CKKS slot map. A complex slot vector $\mathbf{z} \in \mathbb{C}^{N/2}$ is placed at the canonical embedding positions and inverse-FFT’d to yield a real-coefficient polynomial. In current poulpy the transform runs through a backend-resident planar [re | im] CKKSEncodingBuffer, at either f64 or portable binary128 Quad precision:

$$\mathbf{z} \in \mathbb{C}^{N/2} \;\xrightarrow{\;\text{slot map}\;}\; m(X) \in \mathbb{R}[X]/\langle X^N+1\rangle.$$

This step is identical to RNS-CKKS: the canonical embedding obviously does not care how the underlying ring is stored, as it is just a ring homomorphism.

The interesting step is the next one: turning $m(X)$ into the bivariate representation at scale $\Delta = 2^{\log\Delta}$. We want an integer polynomial $\tilde m(X) \in \mathbb{Z}[X]/\langle X^N+1\rangle$ such that $\tilde m \approx \Delta \cdot m$, then we want to spread $\tilde m$ across the $Y$-axis so that the limbs of each coefficient encode the integer $\tilde m_i$ in base $2^K$, with the message lying in the lowest $\log\Delta$ bits of the limb stack - its lowest bits being where the encryption noise sits - and the $\log\beta$ bits above it left clean for noise growth:

MSB LSB

$0$ clean

$m_i(\Delta \text{-scaled})$ integer bits

$0$ clean

$\text{noise sits at the LSBs and grows upward as ops accumulate}$

In RNS this same operation requires representing $\tilde m$ modulo each prime $q_j$, which forces the encoder to carry around the full prime chain. In poulpy the module’s encoding operation writes into limbs of $K$ bits, with $K$ chosen freely. The slot map is unchanged, but the quantization-to-storage is done so that the integer $\tilde m_i$ lands in the right limbs with the right alignment, and so that subsequent kernels see the limb stack the way they expect.

There is a single plaintext type, CKKSPlaintext, which lives in the ZNX (integer-limb torus) domain:

pub struct CKKSPlaintext<D: Data, W: ZnxWord> {
    pub(crate) inner: GLWEPlaintext<D, W>,
    pub(crate) meta: CKKSMeta,
}

The old host-side Encoder object is gone. Encoding is now an operation family on Module<BE>: CKKSEncodingOps works entirely on backend buffers, while CKKSEncodingHostOps provides explicit host-slice adapters. The common path allocates the plaintext, presets its metadata, and supplies the caller’s scratch arena:

let mut pt = module.ckks_pt_vec_alloc(base2k, k);
pt.set_meta(CKKSMeta {
    log_delta,
    log_sparsity: 0,
    slots: SlotsKind::Complex,
});
module.ckks_encode_reim_into(&mut pt, &re, &im, &mut scratch)?;

This one call stages [re | im] into the backend arena, applies the slot-to-coefficient transform, scales by $\Delta = 2^{\log\Delta}$, rounds to the appropriate integer width, and decomposes the coefficients into base-$2^K$ limbs. Backends cache their own transform plans, so there is no encoder or FFT table for user code to construct. Raw coefficient paths are also available through ckks_encode_coeffs_into and ckks_encode_coeffs_host_into.

Decoding runs the chain in reverse with module.ckks_decode_reim_into(&pt, &mut re, &mut im, &mut scratch): the bivariate plaintext is collapsed back to a scalar per coefficient, divided by $\Delta$, and mapped through the forward FFT to recover an approximation of the input slot vector. The accuracy of the round-trip is governed by the bits of $\log\beta$ that survived the homomorphic computation.

5.2 Encryption

Encryption is the standard RLWE encryption of the ZNX plaintext into a pair $(a,\, b = a \cdot s + \mathrm{pt} + e)$. CKKSEncryptOps::ckks_encrypt_sk takes the total torus width $k$ from the encryption parameters and stamps

$$\log\Delta_{\mathrm{out}} = \log\Delta_{\mathrm{pt}}, \qquad \log\beta_{\mathrm{out}} = k - \log\Delta_{\mathrm{pt}}.$$

The randomness arguments are ordered (source_xe, source_xa): error first, uniform mask second. Decryption is destination-framed in the current API: ckks_decrypt no longer copies the ciphertext metadata into its output. Allocate with ckks_plaintext_alloc_from_infos(&ct), or otherwise preset the destination’s (log_delta, log_budget) frame, before decrypting.

5.3 Addition

Adding two ciphertexts at the same scale is just GLWE addition, if the budgets and storage widths agree. When they don’t, the kernel reconciles all three axes in a single pass:

1. Compute the natural result width and the destination offset

   $$k_{\mathrm{nat}} = \min(\log\Delta^a, \log\Delta^b) + \min(\log\beta^a, \log\beta^b), \qquad o = \max(0, k_{\mathrm{nat}} - k^{\mathrm{dst}}).$$

2. Left-shift the lower-budget operand by $o$ bits and add the higher-budget operand left-shifted by $(\log\beta^{\text{high}} - \log\beta^{\text{low}}) + o$ bits.

3. Set the result’s metadata: $\log\Delta^{\mathrm{dst}} = \min(\log\Delta^a, \log\Delta^b)$, $\log\beta^{\mathrm{dst}} = \min(\log\beta^a, \log\beta^b) - o$.

The default ckks_add_into returns a Normalized ciphertext: it follows the addition with a carry-propagation pass that brings every limb back into $[-2^{K-1}, 2^{K-1})$. The ckks_add_into_unnormalized variant writes into an UnnormalizedCKKSCiphertext and skips that pass, which is correct for chains of linear operations as long as ct.normalize(&module, &mut scratch) happens before any DFT-domain operation downstream (keyswitching, multiplication, automorphism). The Unnormalized typestate flags a numeric invariant (limbs may hold un-propagated carries and eventually overflow i64 if you keep accumulating), not a memory invariant, and the type system refuses to hand such a value to a kernel that assumes normalized limbs.

Plaintext addition takes a CKKSPlaintext already in the ZNX domain. The ckks_add_pt_vec_* family consumes a full polynomial; ckks_add_pt_const_* consumes one encoded coefficient. The plaintext declares its meaningful k and its integer consuming width encoded_k(), which can be much narrower than the ciphertext’s allocation, and the kernel aligns it inside the ciphertext before adding.

5.4 Multiplication

A product of two CKKS ciphertexts at scales $\Delta_a$ and $\Delta_b$ is a ciphertext at scale $\Delta_a \cdot \Delta_b$. To recover a single-scale result, one factor of $\Delta$ must be absorbed, which costs $\max(\log\Delta_a, \log\Delta_b)$ bits of $\log\beta$:

Let $\log\beta_{\mathrm{nat}} = \min(\log\beta^a, \log\beta^b) - \max(\log\Delta_a, \log\Delta_b)$. Then

$$k_{\mathrm{nat}} = \log\beta_{\mathrm{nat}} + \min(\log\Delta_a, \log\Delta_b), \qquad o = \max(0, k_{\mathrm{nat}} - k^{\mathrm{dst}}),$$ $$\log\beta^{\mathrm{dst}} = \log\beta_{\mathrm{nat}} - o,$$ $$\log\Delta^{\mathrm{dst}} \;=\; \min(\log\Delta_a, \log\Delta_b),$$

The $\min/\max$ pair handles the common case (equal scales: $\min = \max = \log\Delta$, so the subtraction is just $-\log\Delta$) as well as genuinely different input scales. MultiplicationPrecisionUnderflow is the bivariate counterpart of “out of levels”: multiplication is impossible when $\min(\log\beta^a, \log\beta^b) < \max(\log\Delta_a, \log\Delta_b)$. If dst.k() is below the natural result width, the kernel additionally rounds the low bits to the requested precision and charges $o$ bits of budget.

Pictorially, for two operands at the same scale $\Delta$ and budgets $\beta_a \leq \beta_b$:

MSB LSB

$a$

$\log {\beta }_a$

$\log \Delta$

$\text{noise}$

$b$

$\log {\beta }_b$

$\log \Delta$

$\text{noise}$

$\text{tensor product }a\cdot b\text{ at scale }{\Delta }^2\text{: message extends upward by }\log \Delta \text{ into the budget}$

$a\cdot b$

${\beta }_{\min }$

$\log \Delta$ upper

$\log \Delta$ lower

$\text{noise}$

$m_a\cdot m_b\text{ at scale }{\Delta }^2$

$\text{rescale by }\log \Delta \text{: drop the lower }\log \Delta \text{ bits, noise climbs into the message, budget shrinks}$

$a\cdot b$

${\beta }^{\prime \prime }$

$\log \Delta$

$\text{noise}$

${\beta }^{\prime \prime }={\beta }_{\min }-\log \Delta$

The rescale brings the noise floor up by $\log\Delta$ bits relative to the message, closing the gap by that much: the budget after the multiplication is $\beta'' = \min(\beta_a, \beta_b) - \log\Delta$.

The kernel produces the tensor product of the two ciphertexts under the appropriate shift, then relinearizes using a precomputed tensor key. Current gadget-key layouts are parameterized by decomposition count dnum, digit width dsize, and an auxiliary guard k_aux, rather than by a caller-supplied total k:

$$k_{\mathrm{key}} = \mathrm{dnum}\cdot\mathrm{dsize}\cdot K + k_{\mathrm{aux}}.$$

The key-switching operation derives its working width from the input ciphertext and this key layout. One sufficiently wide tensor key therefore serves computations at lower ciphertext precisions without a circuit-specific prime schedule.

Plaintext multiplication is dramatically cheaper. A constant multiplication consumes only the plaintext’s $\log\Delta$ bits of budget, with no factor of the ciphertext’s scale, and skips relinearization entirely. A small constant such as $3 / 2^{8}$ consumes exactly $8$ bits, instead of forcing an entire prime drop as it would in RNS without Grafting.

5.5 Rescale and the prefix property

Re-anchoring the message inside the limb stack is exposed through CKKSPow2Ops, poulpy’s multiply/divide-by-a-power-of-two primitives. ckks_mul_pow2_into / ckks_mul_pow2_assign left-shift the torus polynomial by bits positions, so the encrypted value becomes $\mathrm{message}\cdot 2^{\mathrm{bits}}$ at the same scale $\log\Delta$. The in-place variant leaves metadata unchanged, so the caller is responsible for ensuring the larger value still fits the nominal headroom.

ckks_div_pow2_into / ckks_div_pow2_assign right-shift the polynomial. They are the precision-aware rescale and transfer bits from the budget into the scale,

$$\log\Delta \;\leftarrow\; \log\Delta + \mathrm{bits}, \qquad \log\beta \;\leftarrow\; \log\beta - \mathrm{bits}.$$

Division rejects a request that would push $\log\beta$ below zero with InsufficientHomomorphicCapacity: there is no equivalent to “negative levels”. An *_into call may consume further budget when dst.k() is narrower than the source; multiplying by a power of two only reports this error for that destination-width charge, not for bits itself.

The prefix property the paper highlights still costs no basis conversion, but its API expression has changed. Compact and SetSize have been removed. An owned ciphertext now has a fixed allocation (max_size, max_k) and a logical precision (k, with size() = ceil(k/K)). Budget-consuming operations lower the logical k; kernels work over that logical limb prefix while the backing allocation stays put. If memory must shrink too, the caller allocates the destination at the smaller k before an *_into operation.

The picture, in the storage layout the kernels actually manipulate (limbs indexed $j = 1, \dots, \ell$ as in §1, with $a_j$ carrying weight $2^{(\ell-j) \cdot K}$ on the buffer integer, so $a_1$ is the high half, $a_\ell$ the low half):

MSB LSB

$\text{fresh}$

$a_1$ K bits

$a_2$ K bits

$a_3$ K bits

$a_4$ K bits

$k:4K\to 3K\text{ after a budget-consuming op; }\text{size()}:4\to 3$

$\text{same allocation}$

$a_1$ logical

$a_2$ logical

$a_3$ logical

$a_4$ unused capacity

$\text{allocate the next destination at }k=3K\text{ to shrink memory too}$

$\text{narrow destination}$

$a_1$ K bits

$a_2$ K bits

$a_3$ K bits

The logical view uses the high-weight prefix $a_1, \dots, a_{\ell'}$. A narrower destination represents the same plaintext at lower precision, with the kernel performing the required value-preserving rounding; it does not require a CRT lift or reprojection.

Evaluation keys and plaintexts inherit the same structural advantage. Key operations derive the necessary prefix from the operand and the key’s decomposition/k_aux coverage, while plaintext operations bound the integer polynomial by encoded_k().

5.6 Keyswitching, relinearization, and automorphisms

Relinearization, slot rotations, and conjugation all reduce to the same primitive: a keyswitch, where a ciphertext is rewritten under a different secret. In poulpy the underlying kernel is glwe_keyswitch from poulpy-core, wrapped at the CKKS level by ckks_rotate_into, ckks_conjugate_into, and the relinearization step inside ckks_mul_into.

A keyswitch evaluates $\sum_i A_i(X) \cdot B_i(X)$ where the $A_i$ are the gadget decomposition of one ciphertext polynomial and the $B_i$ are the key. In RNS-CKKS the operands have to be raised to an auxiliary modulus before the elementwise products, and that base extension dominates the online cost. In bivariate the $A_i$ are already polynomials over $\mathcal{R}$ in the same ring: the online phase is one NTT per limb, the products, and a carry-propagation pass: no base extension, no CRT reprojection.

The prefix property carries over to key material: a relinearization, automorphism, or generic keyswitching key with sufficient decomposition and k_aux coverage works for lower-precision operands too. The current core API derives the working width from the operand and key; it no longer accepts a separate output/working-size argument.

6. Why this is cool: a worked example

The runnable example at poulpy-cpu-ref/examples/ckks_poly2.rs evaluates a degree-$31$ Chebyshev approximation of $\sin$ on encrypted complex slots,

$$\sin(x) \;\approx\; \sum_{i=0}^{31} c_i\, T_i(x), \qquad x \in [-1, 1],$$

encoded in Baby-Step/Giant-Step form and evaluated homomorphically with ckks_eval_poly_real_const_coeffs_from_power_basis over a Chebyshev PowerBasis. Build and run it with:

cargo run -p poulpy-cpu-ref --features enable-ckks --example ckks_poly2

The parameters are $N = 1024$ (so $512$ slots), $K = 52$ (base2k), and a ciphertext width $k^{\mathrm{ct}} = 300$, giving $k_{\max} = \lceil 300/52\rceil \cdot 52 = 312$ (six limbs). The message is encoded at $\log\Delta = 45$.

The per-phase trace tells the bivariate story compactly. The columns are the metadata accessors: log_delta, log_budget, the logical torus width k, its derived size() in limbs, and the allocated max_k:

encoded plaintext x   log_delta=45 log_budget=  5 k= 50 limbs= 1 max_k= 52
ciphertext x          log_delta=45 log_budget=255 k=300 limbs= 6 max_k=312
sin(x)                log_delta=45 log_budget= 30 k= 75 limbs= 2 max_k=312
max |have − sin(x)| = 0.000000000075357

The freshly encrypted $\mathrm{ct}_x$ has $\log\Delta = 45$ and $\log\beta = 255$ bits of clean headroom above the scaled message, so its torus width $k = 300$ fills all six $52$-bit limbs ($k_{\max} = 312$, $12$ bits of padding). The plaintext it was encrypted from needed only a single limb ($k = 50$): a bivariate plaintext is stored with just enough precision to hold its value and gets aligned to the ciphertext inside the kernels.

Then the whole degree-$31$ polynomial is evaluated, and the budget falls from $255$ to $30$ bits: $225$ bits consumed across all the Chebyshev recurrences, baby-step products, and giant-step multiplications. The result’s logical width falls from six limbs to two ($k = 75 \Rightarrow \lceil 75/52\rceil = 2$), while its fixed backing allocation remains max_k=312. This is a metadata/view change, not an automatic compaction or reallocation. Decrypting the result recovers $\sin(-1) = -0.8414709849\ldots$ with a maximum slot error of about $7.6 \times 10^{-11}$ in the current deterministic example.

The headline observation is that the budget falls in bits, not in levels. A degree-$31$ evaluation that under RNS-CKKS would burn a discrete chain of primes, one whole prime per rescale with each consumption rounded up to $\sim 30$ to $50$ bits, here spends exactly the bits each step needs and lands on a two-limb logical value with $75$ surviving bits. A caller that also wants a two-limb allocation requests that k when allocating the destination.

For a polynomial whose coefficients are mostly small fractions, those roundings compound: dozens of bit-sized consumptions versus dozens of full-prime drops. The practical consequence is fewer bootstrappings for the same circuit.

$\text{RNS-CKKS}$

$q_0$

$q_1$

$q_2$

$q_3$

$q_4$

$\text{each op consumes a whole prime, even if only a few bits were needed}$

$\text{Bivariate}$

$\text{each op consumes exactly the bits it needs (down to one bit of granularity)}$

7. Conclusion and what’s next

The bivariate representation keeps the CKKS scheme intact and replaces the way ciphertexts are stored and operated on. Polynomials become bivariate (a cyclotomic axis $X$ of length $N$ and a multi-precision axis $Y$ of length $\ell \approx L/K$), the limb size $K$ is a free parameter, and the prefix property turns modulus switching into a length adjustment. The torus picture remains a useful piece of mathematical scaffolding, but it is honest to say that the working object is a stack of $K$-bit signed integers and that every operation is, ultimately, integer arithmetic on those stacks.

In poulpy-ckks this materializes as word-generic ciphertexts and plaintexts carrying a CKKSMeta { log_delta, log_sparsity, slots } alongside their GLWE storage, with $\log\beta$ derived from the logical torus width k; backend-resident encoding operations on Module<BE>; arithmetic kernels that reconcile mismatched scales, budgets and requested result widths through offsets and shifts; fixed allocations separated from the logical limb prefix; and typed, bit-granular composition errors where RNS-CKKS would have signalled “out of levels”.

Much of what this foundation was built for has since landed in poulpy: bit-granular polynomial evaluation (including reusable minimax approximation planning), linear transforms (the homomorphic DFT, slot rotations, and matrix-vector products), and several bootstrapping paths. Those now include the standard and S2C-first CKKS pipelines, functional bootstrapping, and the native PaCo and SHIP families, all parameterized by precision rather than by a fixed prime chain.

Still coming next:

• Discrete CKKS - variants of the scheme where the plaintext space is integer rather than real, sharing the bivariate plumbing with the standard real-valued CKKS, with functional bootstrapping.
• Faster backends - as poulpy was designed to work with any hardware, it is relatively easy to add a new backend hardware acceleration. Poulpy already ships AVX2 + FMA, AVX512 (with an IFMA variant), and ARM (NEON/ASIMD, AArch64) backends; a CUDA backend is on the roadmap.

The torus is a lie. The cake, on the other hand, is real.

Thanks to Jean-Philippe Bossuat for pointing out mistakes in an earlier version of this post.