Skip to content

BLEACH: Cleaning Errors in Discrete Computations over CKKS

Authors: Drucker, Moshkowich, Pelleg, Shaul
Year: 2024
Venue: J. Cryptology 2024

type: scheme collection: catalogue, schemes status: auto

Links: ePrint 2022/1298

Visual lesson: Discrete CKKS (BLEACH) · Scheme table row: Discrete CKKS (BLEACH)

Summary

Auto-extracted summary (unreviewed)

BLEACH shows that the approximate CKKS scheme can execute unbounded-depth circuits over binary and small-integer values by applying step-function approximations as periodic 'clean-up' utilities, while exploiting CKKS SIMD packing and mixing with fixed-point real arithmetic. Demonstrated on Conway's Game of Life with HeLayers, a 128x128 board runs at about 6 minutes per iteration and is an order of magnitude faster than TFHE (Concrete) implementations for boards larger than roughly 80x80.

Abstract

Approximated homomorphic encryption (HE) schemes such as CKKS are commonly used to perform computations over encrypted real numbers. It is commonly assumed that these schemes are not “exact” and thus they cannot execute circuits with unbounded depth over discrete sets, such as binary or integer numbers, without error overflows. These circuits are usually executed using BGV and B/FV for integers and TFHE for binary numbers. This artificial separation can cause users to favor one scheme over another for a given computation, without even exploring other, perhaps better, options. We show that by treating step functions as “clean-up” utilities and by leveraging the SIMD capabilities of CKKS, we can extend the homomorphic encryption toolbox with efficient tools. These tools use CKKS to run unbounded circuits that operate over binary and small-integer elements and even combine these circuits with fixed-point real numbers circuits. We demonstrate the results using the Turing-complete Conway’s Game of Life. In our evaluation, for boards of size 128×128, these tools achieved an order of magnitude faster latency than previous implementations using other HE schemes. We argue and demonstrate that for large enough real-world inputs, performing binary circuits over CKKS, while considering it as an “exact” scheme, results in comparable or even better performance than using other schemes tailored for similar inputs.
Source: pdf

Extracted details

Field Value Source Confidence
contribution clean-up utilities (step-function approximations) that keep CKKS errors bounded in discrete computations llm 0.85
contribution binary and small-integer circuits of unbounded depth over CKKS, combinable with fixed-point real circuits llm 0.85
contribution Lagrange-interpolation based equality check for small integer ranges llm 0.85
contribution Game of Life implementation with interleaved tile-tensor packing in HeLayers llm 0.85
contribution empirical comparison showing CKKS can beat TFHE for wide binary circuits llm 0.85
schemes CKKS llm 0.85
schemes TFHE llm 0.85
libraries HeLayers llm 0.85
libraries Concrete llm 0.85
tasks Conway's Game of Life llm 0.85
tasks encrypted binary circuit evaluation llm 0.85
tasks mixed integer / fixed-point computation llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/zama-ai/fhe_game_of_life (URL found in the full text) regex 0.50
limitations TFHE reference timings were measured only for boards up to 20x20 and extrapolated quadratically llm 0.85
limitations the clean-up method itself is not fast; the advantage relies on high SIMD parallelism llm 0.85
llm relevance low llm 0.85
key result latency per iteration: 6:08 min (128x128 board, CKKS with Lagrange CheckEqual) llm 0.85
key result latency per iteration: 12:00 min (256x256 board, CKKS with Lagrange CheckEqual) llm 0.85
key result latency per iteration: 22:12 min / 39:40 min (128x128 / 256x256 board, general CheckEqual_1) llm 0.85
key result speed-up of Lagrange CheckEqual over general CheckEqual: 3.6x / 3.3x (128x128 / 256x256 boards) llm 0.85
key result speed-up over TFHE reference: about 10x (boards larger than ~80x80, TFHE timings extrapolated) llm 0.85

Scheme card: Discrete CKKS (BLEACH)

Group 1. CKKS and its variants
Kind Variant
Hardness assumption RLWE
Plaintext type Bits and small integers inside CKKS
SIMD packing Yes
Bootstrapping Yes
Post-quantum Yes
Status Active
Fit for LLM inference Exact logic and comparisons inside CKKS, for example for argmax and sampling, without switching schemes.
Follow-ups XBOOT free-XOR gates (TCHES 2025, 2025/074); faster logical operations (2026/732).
Follow-up papers in the archive XBOOT: Free-XOR Gates for CKKS with Applications to Transciphering
Faster Logical Operations from Discrete CKKS

System card: BLEACH (discrete CKKS)

Group 2. CKKS core and variants
Family CKKS with error cleaning
Arithmetic Discrete values via CKKS
Interaction Non-interactive
Model scale -
Status Niche
Relation to the SoK Runs exact integer/boolean logic inside CKKS.
Note Periodically cleans CKKS noise with polynomial maps. Avoids scheme switching.
Systems page BLEACH (discrete CKKS)

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: CKKS 137 [p.1], TFHE 37 [p.1], BGV 13 [p.1], Scheme switching 4 [p.8], MPC 3 [p.2], BFV 2 [p.8]
  • library: HELayers 6 [p.2], Concrete (Zama) 5 [p.8], HEaaN (library) 4 [p.8], OpenFHE 3 [p.8], Zama 2 [p.8], nGraph-HE 2 [p.2], HElib 1 [p.33], ABY / ABY3 1 [p.35], EzPC / CrypTFlow 1 [p.35]
  • model: Decision tree 2 [p.6], Gradient boosting / XGBoost 2 [p.29], CNN 1 [p.34]
  • hardware: Intel Xeon 1 [p.9]
  • technique: Bootstrapping 40 [p.2], SIMD packing 13 [p.1], ReLU 5 [p.2], Rescaling 4 [p.13], Polynomial approximation 4 [p.5], Minimax approximation 2 [p.10], Remez 2 [p.11], Convolution 2 [p.17], Lookup table 2 [p.6], Non-interactive 2 [p.2]
  • assumption: RLWE 2 [p.9], LWE 2 [p.9]
  • topic: Homomorphic encryption 47 [p.1], Open source 3 [p.31], Benchmark 2 [p.5]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/2-030_bleach-cleaning-errors-in-discrete-computations-over-ckks.pdf catalogue 39 1.7 MB ece74a91a30f
references/schemes/s10-0_bleach-cleaning-errors-in-discrete-computations-over-ckks.pdf schemes 39 1.7 MB ece74a91a30f byte-identical to references/catalogue/2-030_bleach-cleaning-errors-in-discrete-computations-over-ckks.pdf

Database key: bleach-cleaning-errors-in-discrete-computations-over-ckks · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set bleach-cleaning-errors-in-discrete-computations-over-ckks COLUMN VALUE