Paper 2026/975

Functional Bootstrapping for a Single LWE Ciphertext with \(\tilde{O}(1)\) Polynomial Multiplications

Hongbo Li, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, University of Chinese Academy of Sciences

Dingkang Wang, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, University of Chinese Academy of Sciences

Abstract

Bootstrapping is the key technique that turns leveled homomorphic encryptionc into fully homomorphic encryption, but it remains a major efficiency bottleneck. Recent work by Z. Liu and Y. Wang (ASIACRYPT 2023) showed how to bootstrap \(N\) LWE ciphertexts with total cost of \(\widetilde{O}(N)\) polynomial multiplications based on the BFV scheme. However, their results achieve \(\widetilde{O}(1)\) complexity only through amortization over large batches, and do not give a genuine non-amortized \(\widetilde{O}(1)\) bound for a single ciphertext. In this paper, we present a BFV-based functional bootstrapping algorithm for arbitrary functions over large plaintext spaces with total cost of \(\widetilde{O}(1)\) polynomial multiplications for one LWE ciphertext. The same construction also supports small and moderate batches, and processes a batch of \(m\) ciphertexts with total cost \(\widetilde{O}(m)\) in the supported parameter range. The main technical ingredient is a sparse-packing polynomial-evaluation method for BFV ciphertexts, which exploits the duplicated-slot structure to evaluate an arbitrary polynomial on \(m\) encrypted inputs with total cost of \(\widetilde{O}(m)\). We implement the scheme in Lattigo using the BFV scheme. At 128 bit security and on a single thread, bootstrapping an arbitrary function takes 3.15 seconds for one ciphertext encrypting a 9-bit plaintext and 3.77 seconds for 128 such ciphertexts in one batched invocation. For 16-bit plaintexts, it takes 10.63 seconds for one ciphertext and 18.07 seconds for 16 ciphertexts. These results show that non-amortized single-ciphertext functional bootstrapping, as well as small and moderate batch bootstrapping, can be practical for arbitrary functions over relatively large plaintext spaces.