Paper 2026/1023

Faster CoeffToSlot and SlotToCoeff for Sparsely Packed Ciphertexts with Application to CKKS Bootstrapping

Abstract

CKKS bootstrapping is a central tool for restoring the available modulus budget of approximate ciphertexts, thereby enabling homomorphic computations beyond a fixed leveled circuit. A key component is the pair of linear transformations CoeffToSlot and SlotToCoeff, which move data to the slot representation for homomorphic modular reduction and then back to the coefficient representation. In the sparse packing setting of Cheon et al. (EUROCRYPT 2018), the useful data occupy a short effective slot vector that is repeated across the full slot space. Existing methods for this setting mainly use the smaller effective dimension, whereas our approach exploits the repetition pattern itself to obtain simpler and cheaper transformations. This paper use the repeated slot pattern to improve the efficiency of both CoeffToSlot and SlotToCoeff. Each transform keeps multiplicative depth \(1\) and uses fewer homomorphic operators. Let \(N\) be the ring dimension, let the packed vector have length \(n/2\), and write \(r=N/n\) for the repetition factor. For each transform, when \(n\le r/2\), the cost is one plaintext-ciphertext multiplication and \(O(\log n)\) rotations. When \(n>r/2\), the cost is \(2n/r\) plaintext-ciphertext multiplications and \(O(\sqrt{2n/r}+\log r)\) rotations. We also analyze the auxiliary slots produced by the new \textsf{CoeffToSlot} layout and prove that they satisfy the same sub-Gaussian range bound as the desired coefficient slots. Hence the \textsf{EvalMod} approximation range only needs the usual logarithmic margin from a union bound. We implement the proposed transforms in OpenFHE and evaluate them as part of the CKKS bootstrapping pipeline. For \(N=2^{16}\) and the tested sparse dimensions \(n/2\le 1024\), our transforms are \(3.53\times\) to \(7.95\times\) faster than OpenFHE's depth \(1\) sparse linear transforms in the sparse secret key setting. This gives a \(1.71\times\) to \(5.28\times\) speedup for the whole bootstrapping procedure. Similar gains are observed in the uniform secret key setting. The gains are largest for \(n/2\le 512\), where our method is also competitive with the depth \(3\) OpenFHE baseline while using four fewer levels. Overall, the results show that slot repetition can be used to reduce the practical cost of CKKS bootstrapping in the sparse packing setting.