-
FHE for SIMD Arithmetic Logic Units with Amortized O(1) Bootstrapping per Ciphertext
TL;DR: We propose a new CKKS-compatible encoding framework that supports both arithmetic and Boolean operations for a vector of, for example, 64-bit integers. The key idea is using multiple complex slots to represent one integer, with a special ring isomorphism to maintain the desired integer arithmetic. For arithmetic-only workloads, each refreshing requires only two bootstrapping operations for one ciphertext. For Boolean operations, the arithmetic-to-Boolean conversion can batch $O(n)$ ciphertexts, resulting in amortized $O(1)$ bootstrapping per ciphertext. The prototype is available at
-
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.