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

What it is

RDK-CKKS is a preprint (ePrint 2026/2575, received 21 October 2026) by Taeyeong Noh, Aimad Chabounia, Guillaume Hanrot and Alain Passelègue, with contact addresses at CryptoLab. It targets two gaps in CKKS error analysis. Worst-case bounds are rigorous but far from measured error. Average-case bounds rely on heuristics that are too weak for security arguments.

How it works

Randomization keys (RDKs) are encryptions of zero injected at key-switching and rescaling steps. They make the error of each elementary operation amenable to rigorous probabilistic bounds. The error of a whole circuit then follows from standard numerical error propagation. The abstract says the resulting bounds are comparable to heuristic ones and closely match empirical measures.

Preconditions / Affected

The RDKs are extra evaluation material that only the secret key holder can generate. The authors name two settings where a precise error bound is needed:

• noise flooding in IND-CPA^D or threshold settings, where the computation error must be hidden at decryption;
• statistical correctness with discrete data and a single decryptor.

What to do

For bootstrapping, the abstract gives these costs and results:

• Communication overhead is 27% over the bootstrapping keys for a single evaluation, and a further 8% for each additional evaluation.
• When a circuit is evaluated repeatedly, most RDKs can be reused across evaluations.
• The paper gives a complete rigorous analysis of binary CKKS bootstrapping and a full rigorous parameter set for the bootstrap-and-clean technique.
• Against a Gaussian-type heuristic approach, the parameters need a modulus increase of about 3% for bootstrapping.

Caveats

This is a preprint. Only the abstract was available, so the concrete parameter values, the proofs and any implementation or benchmark details are not covered here.