Paper 2025/1786

Leveraging Discrete CKKS to Bootstrap in High Precision

Abstract

The CKKS fully homomorphic encryption (FHE) scheme enables computations on vectors of approximate complex numbers. A moderate precision of $\approx 20$ bits often suffices but, in many applications, a higher precision is required for functionality and/or security. Indeed, to obtain IND-CPA-D security [Li-Micciancio; Eurocrypt'21], secure threshold-FHE [Asharov et al; Eurocrypt'12] and circuit privacy [Gentry; STOC'09], all known approaches require a precision that supports noise flooding. This may lead to a precision of $\approx 80$ bits, or more. High-precision CKKS is hard to achieve, notably because of bootstrapping. The main difficulty is modulus consumption: every homomorphic multiplication consumes some, out of an overall modulus budget. Unfortunately, in high precision, most known bootstrapping algorithms consume so much modulus that one needs to increase the parameters to increase the budget. The state-of-the-art approach, Meta-BTS [Bae et al; CCS'22], performs moderate-precision bootstrapping several times to enable high-precision bootstrapping, with similar modulus consumption as the base bootstrapping it builds upon. It however damages latency. We introduce a new approach for high-precision CKKS bootstrapping, whose cost is almost independent of the precision (as opposed to Meta-BTS) and whose modulus consumption increases significantly more slowly than with classical bootstrapping algorithms. Our design relies on the EvalRound bootstrapping [Kim et al; Asiacrypt'22], which we improve in the high-precision context by leveraging and improving recent techniques for handling discrete data with CKKS. We obtain for the first time a non-iterative 80-bit precise bootstrapping algorithm which can be run in ring degree $N=2^{16}$, with 494 bits of remaining modulus for computations. In terms of throughput, and for 80-bit precision, our implementation shows an acceleration of 64\% compared to Meta-BTS.