PaCo: Bootstrapping for CKKS via Partial CoeffToSlot¶
Authors: J.-S. Coron; T. Seur´e
Year: 2025
Venue: IACR ePrint
type: technique collection: catalogue, schemes, sok-references status: auto
Links: ePrint 2025/886
Visual lesson: PaCo bootstrapping · Scheme table row: PaCo bootstrapping
Summary¶
Auto-extracted summary (unreviewed)
PaCo is a new CKKS bootstrapping procedure that rewrites the decryption equation in terms of blind rotations and modular additions, simulating modular additions via the complex circle group and performing blind rotations in alternative ring structures obtained through a partial CoeffToSlot transform. The method has zero failure probability and complexity logarithmic in the number of slots, supports a parallelised all-slot variant, and a proof-of-concept implementation is 1.5-2.6x faster than original CKKS bootstrapping with up to a further 2x from 32 processors.
Abstract¶
We introduce PaCo, a novel and efficient bootstrapping procedure for the CKKS homomorphic encryption scheme, where PaCo stands for (Bootstrapping via) Partial CoeffToSlot. At a high level, PaCo reformulates the CKKS decryption equation in terms of blind rotations and modular additions. This reformulated decryption circuit is then evaluated homomorphically within the CKKS framework. Our approach makes use of the circle group in the complex plane to simulate modular additions via complex multiplication, and utilizes alternative polynomial ring structures to support blind rotations. These ring structures are enabled by a variant of the CoeffToSlot operation, which we call a partial CoeffToSlot. This yields a new bootstrapping approach within CKKS, achieving a computational complexity which is logarithmic in the number of complex slots. We further introduce a parallelized variant that enables bootstrapping over all CKKS slots with enhanced throughput, highlighting PaCo’s suitability for practical and large-scale homomorphic applications. In addition to the bootstrapping technique itself, we develop several supporting tools — particularly in the context of bit-reversing and alternative ring structures for CKKS — which can be of independent interest to the community. Finally, a proof-of-concept implementation confirms that PaCo achieves performance competitive with state-of-the-art methods for CKKS bootstrapping.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | PaCo bootstrapping via partial CoeffToSlot | llm | 0.85 |
| contribution | reformulation of CKKS decryption using blind rotations and modular additions | llm | 0.85 |
| contribution | circle-group simulation of modular additions | llm | 0.85 |
| contribution | parallelised variant bootstrapping all slots | llm | 0.85 |
| contribution | supporting tools for bit-reversal and alternative ring structures in CKKS | llm | 0.85 |
| contribution | open-source proof-of-concept implementation | llm | 0.85 |
| schemes | CKKS | llm | 0.85 |
| tasks | CKKS bootstrapping | llm | 0.85 |
| hardware | CPU, up to 32 processors | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://github.com/se-tim/PaCo-Implementation.git (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/se-tim/PaCo-Implementation | llm | 0.85 |
| limitations | requires a structured secret key | llm | 0.85 |
| limitations | proof-of-concept without RNS optimisation | llm | 0.85 |
| limitations | bootstrapping all N coefficients without parallelisation left open | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | bootstrapping speed-up: 1.5x to 2.6x (vs original CKKS bootstrapping, single processor) | llm | 0.85 |
| key result | parallel speed-up: up to additional 2x (32 processors in parallel) | llm | 0.85 |
Scheme card: PaCo bootstrapping¶
| Group | 1. CKKS and its variants |
| Kind | Variant |
| Hardness assumption | RLWE |
| Plaintext type | Approximate real/complex |
| SIMD packing | Yes |
| Bootstrapping | Yes, about 0.25 GB keys |
| Post-quantum | Yes |
| Status | Active SOTA |
| Fit for LLM inference | Small bootstrapping keys address the memory wall the SoK highlights. |
| Follow-ups | Sub-10 ms CKKS bootstrapping on GPU (2026/2119). |
| Follow-up papers in the archive | CKKS Bootstrapping in less than 10ms |
System card: PaCo bootstrapping¶
| Group | 3. CKKS bootstrapping and operation advances |
| Family | CKKS bootstrapping |
| Arithmetic | - |
| Interaction | - |
| Model scale | - |
| Status | Active SOTA |
| Relation to the SoK | Small-key bootstrapping (about 0.25 GB keys). |
| Note | SoK highlights it as appealing for LLM inference because key memory is a key bottleneck. |
| Systems page | PaCo bootstrapping |
SoK reference [101]¶
J.-S. Coron and T. Seur´e, “Paco: Bootstrapping for ckks via partial coefftoslot,” in Advances in Cryptology – ASIACRYPT 2025, G. Hanaoka and B.-Y. Yang, Eds. Singapore: Springer Nature Singapore, 2026, pp. 36–67.
Listed on the reference page of the site.
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 62 [p.1], BFV 2 [p.1], BGV 2 [p.1], TFHE 2 [p.2], FHEW 2 [p.2]
- library: HElib 1 [p.31], Concrete (Zama) 1 [p.30]
- hardware: Apple silicon 1 [p.27]
- technique: Bootstrapping 103 [p.1], Rotations 31 [p.1], Rescaling 5 [p.2], Polynomial approximation 3 [p.2], Matrix multiplication 3 [p.2], SIMD packing 2 [p.5], RNS 2 [p.30]
- assumption: RLWE 5 [p.1], Lattice-based 5 [p.1], LWE 2 [p.31]
- task: Language modeling / generation 3 [p.2]
- topic: Homomorphic encryption 10 [p.1], Open source 2 [p.8]
Related papers¶
- CKKS Bootstrapping in less than 10ms follow up of this paper — follow-up listed for scheme "PaCo bootstrapping"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/3-043_paco-bootstrapping-for-ckks-via-partial-coefftoslot.pdf |
catalogue | 35 | 1.0 MB | 74e4295a2d7c |
|
references/schemes/s09-0_paco-bootstrapping-for-ckks-via-partial-coefftoslot.pdf |
schemes | 35 | 1.0 MB | 74e4295a2d7c |
byte-identical to references/catalogue/3-043_paco-bootstrapping-for-ckks-via-partial-coefftoslot.pdf |
references/sok-references/101_paco-bootstrapping-for-ckks-via-partial-coefftoslot.pdf |
sok-references | 35 | 1.0 MB | 74e4295a2d7c |
byte-identical to references/catalogue/3-043_paco-bootstrapping-for-ckks-via-partial-coefftoslot.pdf |
Database key: paco-bootstrapping-for-ckks-via-partial-coefftoslot · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set paco-bootstrapping-for-ckks-via-partial-coefftoslot COLUMN VALUE