Beyond Approximate Arithmetic: Efficient Homomorphic Computation with Discrete CKKS
Abstract
Fully homomorphic encryption (FHE) allows computations to be performed directly on encrypted sensitive data without decrypting it. Modern FHE schemes expose different computational models. CKKS distinguishes itself by supporting approximate arithmetic on packed complex values. Despite its high throughput, the absence of a homomorphic error-reduction mechanism long confined it to applications that tolerate approximation, such as privacy-preserving machine learning. This PhD research tackles this issue and extends CKKS to support efficient computation over discrete data while satisfying the correctness conditions required for security. We first show that, in the IND-CPAD security model, failure probabilities above 2-λ can invalidate λ-bit security, even for exact FHE schemes. We address the correctness challenge of discrete CKKS through three complementary approaches: (1) Functional Bootstrapping allows arbitrarily deep computations on packed small integers and achieves over two orders of magnitude higher throughput for lookup-table evaluation on 8-bit integers than the reported TFHE-rs baseline. (2) Digit Decomposition cuts modulus consumption for high-precision integer cleaning, also improving the throughput of high-precision approximate bootstrapping. (3) Character-Block Encodings provide lower error growth and constant-depth cleaning but consume more slots per integer. Building on functional bootstrapping, we also provide an extension of discrete CKKS to arithmetic over finite extension fields of small characteristic and large extension degree. This research project explores the regimes in which approximate arithmetic enables efficient homomorphic computation over discrete data.