Efficient Multi-Key Homomorphic Encryption with Packed Ciphertexts with Application to Oblivious Neural Network Inference¶
Authors: Hao Chen; Wei Dai; Miran Kim; Yongsoo Song
Year: 2019
Venue: CCS 2019
type: scheme collection: catalogue, schemes status: auto
Links: DOI · ePrint 2019/524 · Semantic Scholar
Visual lesson: Multi-key CKKS / BFV (CDKS19) · Scheme table row: Multi-key CKKS / BFV (CDKS19)
Summary¶
Auto-extracted summary (unreviewed)
Presents multi-key variants of BFV and CKKS with packed ciphertexts, new simpler and faster relinearization algorithms than Chen et al. (TCC 2017), and multi-key bootstrapping. A proof-of-concept in Microsoft SEAL 3.2 performs a four-party multi-key multiplication plus relinearization in about 116 ms (BFV) or 67 ms (CKKS) at ring dimension 8192, and classifies an encrypted MNIST image with a model encrypted under a different key (one conv + two FC layers) in about 1.8 s.
Abstract¶
Homomorphic Encryption (HE) is a cryptosystem which supports computation on encrypted data. L´opez-Alt et al. (STOC 2012) proposed a generalized notion of HE, called Multi-Key Homomorphic Encryption (MKHE), which is capable of performing arithmetic operations on ciphertexts encrypted under different keys. In this paper, we present multi-key variants of two HE schemes with packed ciphertexts. We present new relinearization algorithms which are simpler and faster than previous method by Chen et al. (TCC 2017). We then generalize the bootstrapping techniques for HE to obtain multi-key fully homomorphic encryption schemes. We provide a proof-of-concept implementation of both MKHE schemes using Microsoft SEAL. For example, when the dimension of base ring is 8192, homomorphic multiplication between multi-key BFV (resp. CKKS) ciphertexts associated with four parties followed by a relinearization takes about 116 (resp. 67) milliseconds. Our MKHE schemes have a wide range of applications in secure computation between multiple data providers. As a benchmark, we homomorphically classify an image using a pre-trained neural network model, where input data and model are encrypted under different keys. Our implementation takes about 1.8 seconds to evaluate one convolutional layer followed by two fully connected layers on an encrypted image from the MNIST dataset.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Multi-key BFV and multi-key CKKS with packed (RLWE) ciphertexts | llm | 0.90 |
| contribution | New relinearization algorithms simpler and faster than prior MKHE | llm | 0.90 |
| contribution | Multi-key bootstrapping generalizing single-key techniques | llm | 0.90 |
| contribution | First experimental results for MKHE with packed ciphertexts (SEAL-based) | llm | 0.90 |
| contribution | Oblivious neural network inference with data and model under different keys | llm | 0.90 |
| schemes | multi-key HE | llm | 0.90 |
| schemes | BFV | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| libraries | SEAL | llm | 0.90 |
| models | CNN (1 convolutional + 2 fully connected layers) | llm | 0.90 |
| datasets | MNIST | llm | 0.90 |
| tasks | oblivious neural network inference | llm | 0.90 |
| tasks | image classification | llm | 0.90 |
| tasks | secure computation among multiple data providers | llm | 0.90 |
| hardware | Intel Xeon E-2176M @ 4.00 GHz, single thread, 32 GB (ThinkPad P1) | llm | 0.90 |
| security level | 128-bit | llm | 0.90 |
| threat model | multi-party: input data and model encrypted under different keys, evaluated by a cloud server | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/keras-team/keras (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/Microsoft/SEAL (URL found in the full text) | regex | 0.50 |
| limitations | Multiplication cost grows quadratically in the number of parties | llm | 0.90 |
| limitations | Decryption and ciphertext addition take (k+1)/2 times longer than single-key HE | llm | 0.90 |
| llm relevance | medium | llm | 0.90 |
| key result | multi-key multiplication + relinearization latency: ~116 ms (BFV), ~67 ms (CKKS) (4 parties, ring dimension 8192, single thread) | llm | 0.90 |
| key result | inference latency: ~1.8 s (MNIST CNN (conv + 2 FC), image and model under different keys, multi-key CKKS) | llm | 0.90 |
Scheme card: Multi-key CKKS / BFV (CDKS19)¶
| Group | 6. Multi-party FHE (threshold and multi-key) |
| Kind | Scheme |
| Hardness assumption | RLWE |
| Plaintext type | Approximate or exact |
| SIMD packing | Yes |
| Bootstrapping | Yes |
| Post-quantum | Yes |
| Status | Active |
| Fit for LLM inference | Client and model owner each keep their own key, and inference runs on their joint ciphertexts. |
| Follow-ups | MK-FHE without setup in the plain model (CRYPTO 2026, 2026/322). |
| Follow-up papers in the archive | Multi-key Fully Homomorphic Encryption with Non-Interactive Setup in the Plain Model |
System card: Multi-key CKKS¶
| Group | 2. CKKS core and variants |
| Family | Multi-key RLWE |
| Arithmetic | Approximate (CKKS) and exact (BFV) |
| Interaction | Non-interactive, multiple key owners |
| Model scale | Small CNN |
| Status | Niche |
| Relation to the SoK | Lets client and model owner encrypt under different keys. |
| Note | Enables protecting both inputs and weights. Ciphertext size grows with the number of parties. |
| Code | https://github.com/SNUCP/MKHE-KKLSS |
| Systems page | Multi-key CKKS |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Multi-key HE 152 [p.1], CKKS 66 [p.1], BFV 38 [p.1], MPC 19 [p.1], GSW 8 [p.2], BGV 5 [p.2], TFHE 3 [p.4], Leveled / somewhat HE 3 [p.12]
- library: Microsoft SEAL 7 [p.1], HElib 3 [p.22], MP-SPDZ 2 [p.21]
- model: CNN 13 [p.3], Logistic regression 4 [p.21], Linear regression 1 [p.21]
- dataset: MNIST 10 [p.1]
- hardware: Intel Xeon 1 [p.15]
- technique: Relinearization 61 [p.1], Bootstrapping 23 [p.1], Rotations 19 [p.13], RNS 17 [p.4], Convolution 16 [p.1], Key switching 14 [p.3], Rescaling 14 [p.12], SIMD packing 8 [p.2], Modulus switching 3 [p.10], Square activation 3 [p.17], NTT 2 [p.15]
- assumption: RLWE 22 [p.1], LWE 9 [p.1], IND-CPA 5 [p.7], Lattice-based 2 [p.21]
- task: Medical / healthcare 3 [p.21], Genomics 2 [p.21]
- topic: Homomorphic encryption 55 [p.1], Benchmark 4 [p.1], Open source 2 [p.21]
Related papers¶
- Multi-key Fully Homomorphic Encryption with Non-Interactive Setup in the Plain Model follow up of this paper — follow-up listed for scheme "Multi-key CKKS / BFV (CDKS19)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/2-027_efficient-multi-key-homomorphic-encryption-with-packed-ciphe.pdf |
catalogue | 30 | 903.3 KB | 9807c5d474d1 |
|
references/schemes/s37-0_efficient-multi-key-homomorphic-encryption-with-packed-ciphe.pdf |
schemes | 30 | 903.3 KB | 9807c5d474d1 |
byte-identical to references/catalogue/2-027_efficient-multi-key-homomorphic-encryption-with-packed-ciphe.pdf |
Database key: efficient-multi-key-homomorphic-encryption-with-packed-ciphertexts-with · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set efficient-multi-key-homomorphic-encryption-with-packed-ciphertexts-with COLUMN VALUE