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]
Related papers¶
- XBOOT: Free-XOR Gates for CKKS with Applications to Transciphering follow up of this paper — follow-up listed for scheme "Discrete CKKS (BLEACH)"
- Faster Logical Operations from Discrete CKKS follow up of this paper — follow-up listed for scheme "Discrete CKKS (BLEACH)"
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