Accelerating HE Operations from Key Decomposition Technique¶
Authors: Kim, Lee, Seo, Song
Year: 2023
Venue: CRYPTO 2023
type: technique collection: catalogue status: auto
Links: ePrint 2023/413
Summary¶
Auto-extracted summary (unreviewed)
The paper introduces a new external-product algorithm for lattice-based HE in which the expensive gadget decomposition over a large modulus is refactored into cheap operations over an integer ring with a small bound, reducing the number of NTTs from quadratic to linear in the ciphertext level without extra noise growth. Applied to CKKS key switching on top of Lattigo, the new method is 1.2x to 2.3x faster for ring dimension 2^15 and 2.1x to 3.3x faster for 2^16 than the previous full-RNS key switching, with the largest gains for small digit lengths and high levels.
Abstract¶
Lattice-based homomorphic encryption (HE) schemes are based on the noisy encryption technique, where plaintexts are masked with some random noise for security. Recent advanced HE schemes rely on a decomposition technique to manage the growth of noise, which involves a conversion of a ciphertext entry into a short vector followed by multiplication with an evaluation key. Prior to this work, the decomposition procedure turns out to be the most time-consuming part, as it requires discrete Fourier transforms (DFTs) over the base ring for efficient polynomial arithmetic. In this paper, an expensive decomposition operation over a large modulus is replaced with relatively cheap operations over a ring of integers with a small bound. Notably, the cost of DFTs is reduced from quadratic to linear with the level of a ciphertext without any extra noise growth. We demonstrate the implication of our approach by applying it to the key-switching procedure. Our experiments show that the new key-switching method achieves a speedup of 1.2–2.3 or 2.1–3.3 times over the previous method, when the dimension of a base ring is 215 or 216, respectively.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | new external product algorithm based on key decomposition | llm | 0.90 |
| contribution | reduction of DFT/NTT cost from quadratic to linear in ciphertext level without extra noise | llm | 0.90 |
| contribution | new key-switching method for RNS-based CKKS | llm | 0.90 |
| contribution | open-source implementation on Lattigo with experimental evaluation | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| libraries | Lattigo | llm | 0.90 |
| tasks | homomorphic key switching | llm | 0.90 |
| tasks | gadget decomposition / external product | llm | 0.90 |
| hardware | Intel Xeon Platinum 8268 2.90 GHz CPU, 192 GB RAM, single thread | llm | 0.90 |
| security level | 128-bit | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/SNUCP/fast-ksw (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/ldsec/lattigo (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/SNUCP/fast-ksw | llm | 0.90 |
| limitations | previous key-switching method remains faster for small levels combined with large digit length r | llm | 0.90 |
| limitations | hardware/GPU implementation left for future work | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | key-switching speed-up: 1.2x to 2.3x (ring dimension N = 2^15) | llm | 0.90 |
| key result | key-switching speed-up: 2.1x to 3.3x (ring dimension N = 2^16) | llm | 0.90 |
| key result | key-switching speed-up: 3.3x (log N = 16, level 48, digit length r = 1) | llm | 0.90 |
| key result | key-switching speed-up: 2.2x (log N = 16, level 48, digit length r = 4) | llm | 0.90 |
| key result | key-switching time: 1.181 s -> 0.451 s (2.6x) (log N = 16, level 32, r = 1, single thread) | llm | 0.90 |
System card: KLSS key switching¶
| Group | 3. CKKS bootstrapping and operation advances |
| Family | Key switching |
| Arithmetic | - |
| Interaction | - |
| Model scale | - |
| Status | Active SOTA |
| Relation to the SoK | Asymptotically faster key switching for large parameters. |
| Note | Reduces NTT count in key switching. Relevant to rotation-heavy linear layers. |
| Systems page | KLSS key switching |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 18 [p.1], TFHE 2 [p.1], FHEW 2 [p.1], GSW 2 [p.1], RSA 2 [p.16], Multi-key HE 2 [p.6]
- library: Lattigo 4 [p.11], HElib 1 [p.16]
- model: Logistic regression 1 [p.16]
- hardware: GPU 5 [p.2], FPGA 2 [p.17], Intel Xeon 1 [p.11]
- technique: Key switching 77 [p.1], NTT 66 [p.5], RNS 39 [p.1], Bootstrapping 13 [p.2], Relinearization 4 [p.3]
- assumption: RLWE 9 [p.1], Lattice-based 7 [p.1], LWE 6 [p.1]
- topic: Homomorphic encryption 52 [p.1], Benchmark 2 [p.12], Open source 2 [p.11]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/3-039_accelerating-he-operations-from-key-decomposition-technique.pdf |
catalogue | 17 | 261.6 KB | b7450a61769b |
Database key: accelerating-he-operations-from-key-decomposition-technique · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set accelerating-he-operations-from-key-decomposition-technique COLUMN VALUE