Skip to content

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