Paper 2026/1163

SWIFT: Shallow and SIMD-Aware CKKS Functional Bootstrapping for Low-Latency

Abstract

Functional bootstrapping combines ciphertext refreshing with the evaluation of a target function, and has become a central tool for evaluating non-linear functions in homomorphic encryption. In the CKKS scheme, functional bootstrapping typically represents the target function as a trigonometric polynomial over the exponential basis generated by the bootstrapping procedure. Existing CKKS functional bootstrapping methods then evaluate this polynomial using standard baby-step giant-step techniques, whose multiplicative depth grows logarithmically with the polynomial degree. As a result, non-smooth function evaluations or high-degree lookup tables require a large modulus budget and often a larger ring degree, leading to higher evaluation latency. This is especially inefficient for applications that require only hundreds of parallel evaluations, where the large SIMD capacity of CKKS is not fully utilized. We present \textsf{SWIFT}, a shallow and SIMD-aware functional bootstrapping framework for CKKS. The key idea is to exploit the exponential map \(h(x)=\exp(2\pi i x)\) used in CKKS bootstrapping, which satisfies \(h(\ell x)=h(x)^\ell\) for $\ell\in \mathbb Z$. Thus, the powers required for trigonometric polynomial evaluation can be obtained directly as \(h(\ell x)\) during bootstrapping, rather than generated by homomorphic multiplications after bootstrapping. To realize this idea efficiently, \textsf{SWIFT} packs the scaled inputs \(\ell x\) into SIMD slots and evaluates the exponential map on them in parallel. It then reconstructs the target trigonometric polynomial from the resulting powers. As a result, the multiplicative depth of polynomial evaluation becomes independent of the polynomial degree and can be reduced to constant depth, even depth one. This shallow structure reduces the required modulus budget and enables high-degree polynomial evaluation at smaller ring degrees. It also lowers the key-switching cost from the standard \(\Theta(\sqrt d)\) cost to \(\Theta(\log d)\) or \(\Theta(d^{1/4})\), depending on our parameter regime. Our implementation shows that computations previously requiring \(\log N=16\) or \(\log N=17\) can be performed at \(\log N=15\). For lookup tables, \textsf{SWIFT} achieves up to a \(38.1\times\) latency improvement over prior CKKS functional bootstrapping methods at batch size \(128\). For ReLU evaluation at batch size \(256\), it achieves a \(5.21\times\) latency improvement over the previous method. These results demonstrate that CKKS functional bootstrapping can be made latency-efficient for batch sizes on the order of hundreds by using SIMD capacity as a computational resource rather than only as a batching mechanism.