Skip to content

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]

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