Song Bian
Beihang University

Yunhao Fu
Beihang University

Ruiyu Shen
Beihang University

Haowen Pan
Beihang University

Anyu Wang
Tsinghua University

Zhenyu Guan
Beihang University

Keywords: homomorphic encryption, CKKS, functional bootstrapping, Fourier extension, approximate arithmetic

Abstract

We introduce a new (amortized) functional bootstrapping framework over the CKKS homomorphic encryption (HE) scheme based on Fourier extension. While approximating the modular reduction function in CKKS bootstrapping through Fourier series is a well-known technique, how such method can be efficiently generalized to functional bootstrapping is less understood. In this work, we show that, by constructing proper Fourier extensions, any function with a bounded domain in the smoothness class C^k can be approximated by a degree-n Fourier series with errors of order O(n^(-k-2)) (except at the singularities), improving on previous results on a global error bound of O(n^(-1)) [AKP2025]. To achieve such bound, we propose a new way of constructing Fourier extensions, such that the extended functions appear as smooth as possible in the sense of a Fourier approximation. By implementing our functional bootstrapping over OpenFHE, we demonstrate that we can improve the data precision by 10--27 bits and reduce the amortized FBS latency by 1.1x--2x over a variety of benchmarking functions.