-
Faster Bootstrapping for CKKS with Less Modulus Consumption
TL;DR: To improve efficiency and reduce the modulus consumption in standard CKKS bootstrapping, we propose two novel core techniques: level-conserving rescaling (LCR) and aggregated key-switching (AKS), which act on the matrix-vector multiplications in linear transformations and can be further combined into the lossless LCR+AKS. The contributions enable bootstrapping that consumes one fewer modulus level, improves throughput by 20%–35%, and reduces CtS rotation key size by 11.9%–15.2%, while preserving identical precision and failure probability.
-
On the (In)security of Approximate Computation Protocols from CKKS
TL;DR: Recent advances in approximate HE, particularly CKKS, have significantly advanced the practicality of secure computation involving approximate arithmetic. However, the inherent errors introduced by CKKS pose substantial challenges in the security analysis and protocol design. We investigate the correctness and security of existing CKKS-based protocols relying on the noise smudging technique, in which each party independently samples exponentially large noise. We show that these constructions fail to achieve standard simulation-based security. To address this issue, we propose a collaborative sampling approach in which parties jointly generate additive shares of the smudging noise. We present concrete constructions for both asymmetric two-party and symmetric multiparty settings, together with formal ideal functionalities. Furthermore, we provide concrete implementations of round-efficient collaborative sampling protocols. As an alternative perspective, we show that existing protocols satisfy a weaker security notion called liberal security.
-
Modern Construction of Moduli Chain in HEaaN2
TL;DR: Every CKKS computation is built upon a sequence of moduli that predetermines the rescaling amount after each multiplication. A new CKKS library, HEaaN2, generalizes the construction of this parameter with a carefully designed scheme and API set. In this article, we break down the traditional construction of the moduli chain to derive the new one.
-
RadixCKKS: A General Framework for Integer Computation over CKKS
TL;DR: To handle large integers in FHE, a common approach is to decompose an integer into several small pieces, called digits, and perform computations based on them. One such approach is the radix-based approach, which decomposes a large integer into digits in base $B$ and carries out arithmetic on those digits via polynomial operations. However, after arithmetic operations, the resulting representation is no longer unique, which makes it difficult to directly perform non-arithmetic operations such as comparison or bitwise operations. The process of restoring such a disturbed digit representation back to its unique form is commonly called digit carry, and this step inherently requires non-arithmetic processing. In this post, we introduce a two-step homomorphic digit carry algorithm over CKKS. Our algorithm restores the digit representation to its unique form using $O(\log k)$ bootstrappings.
-
Verifiable Computation for CKKS
TL;DR: Homomorphic Encryption (HE) enables computing over encrypted data but, by itself, provides no guarantees that the computation was honestly executed. One can build "Verifiable HE" (vHE) using SNARKs, but efficiently combining HE and SNARKs in practice is a major challenge. This work introduces a blueprint for building verifiable HE schemes and its efficient instantiation for CKKS. Our first step is to introduce a "proof-friendly" version of CKKS, which is more amenable to proof systems, while being only slightly slower than typical RNS CKKS implementations. We then show how the problem of proving correctness of computations for such proof-friendly HE schemes can be reduced to just two sets of arithmetic relations (containing equalities and inequalities). We show that if these are satisfied, it implies the correct execution of the HE evaluation. We design Polynomial Interactive Oracle Proofs (PIOPs) for efficiently proving these relations, and we show how they can be instantiated using standard proof components. Our final construction demonstrates the feasibility of building SNARKs for proving computation of full-fledged HE schemes, opening the path for building practical verifiable HE schemes.