Paper 2026/2575

RDK-CKKS: A Framework for Rigorous Error Analysis for CKKS Computation

Abstract

The CKKS scheme allows approximate arithmetic on encrypted data, and has found widespread use in privacy-preserving computation. A rigorous control of its homomorphic error is critical for both precision and security guarantees. In particular, in some settings such as IND-CPA^D or threshold settings, the latter computation error should be hidden at the time of decryption. This is achieved by noise flooding techniques, which require a precise upper bound on the computational error magnitude. When dealing with discrete data and a single decryptor, this is addressed by ensuring statistical correctness, which also requires a precise error management. Yet, current approaches to CKKS error analysis provide either rigorous worst-case bounds that are far off empirical measures, or average-case bounds that rely on various heuristics and do not provide strong enough guarantees for security. In this work, we develop a framework based on so-called randomization keys (RDKs), which are encryptions of zero injected at key-switching and rescaling steps to render the homomorphic error amenable to rigorous probabilistic analysis. Combined with tail bounds, this yields, to our knowledge, the first fully rigorous error analysis framework for CKKS computations. Our framework is modular: RDKs make the error of each elementary operation amenable to rigorous bounds, after which the error of a circuit follows by standard numerical error propagation. Our rigorous bounds are comparable to heuristic ones and closely match empirical measures, but cost additional evaluation material (RDKs) generated by the secret key holder. In the context of rigorous bootstrapping, this induces a communication overhead of 27% over the bootstrapping keys for a single evaluation, and of a further 8% for each additional evaluation. We show that, when a circuit is evaluated repeatedly, most of these keys can be reused across evaluations. As our main application, we derive a complete and rigorous analysis of binary CKKS bootstrapping, and a full, rigorous, parameter set for the bootstrap-and-clean technique. Compared to a standard Gaussian-type heuristic approach, our parameters only require a modulus increase for bootstrapping of $\approx 3\%$, while providing rigorous precision estimates.