Skip to content

Multi-Key Homomorphic Encryption from TFHE

Authors: Chen, Chillotti, Song
Year: 2019
Venue: ASIACRYPT 2019

type: scheme collection: schemes status: auto

Links: ePrint 2019/116

Visual lesson: Multi-key TFHE · Scheme table row: Multi-key TFHE

Summary

Auto-extracted summary (unreviewed)

The paper generalizes TFHE gate bootstrapping to the multi-key setting, giving an MKHE scheme that evaluates a binary gate on ciphertexts encrypted under different keys followed by bootstrapping; its core tool is a hybrid product between a single party's RGSW bootstrapping key and a multi-key RLWE ciphertext, for which two algorithms are given (an improved Mukherjee-Wichs ciphertext extension and a new approach with better storage, complexity and noise growth). Ciphertext length grows linearly and gate cost quadratically in the number of parties, and the first reported MKHE implementation (MK-TFHE, built on the TFHE library) performs a bootstrapped NAND in 0.27 s for 2 parties up to 7.16 s for 8 parties on a single-threaded laptop at over 110-bit security.

Abstract

In this paper, we propose a Multi-Key Homomorphic Encryption (MKHE) scheme by generalizing the low-latency homomorphic encryption by Chillotti et al. (ASIACRYPT 2016). Our scheme can evaluate a binary gate on ciphertexts encrypted under different keys followed by a bootstrapping. The biggest challenge to meeting the goal is to design a multiplication between a bootstrapping key of a single party and a multi-key RLWE ciphertext. We propose two different algorithms for this hybrid product. Our first method improves the ciphertext extension by Mukherjee and Wichs (EUROCRYPT 2016) to provide better performance. The other one is a whole new approach which has advantages in storage, complexity, and noise growth. Compared to previous work, our construction is more efficient in terms of both asymptotic and concrete complexity. The length of ciphertexts and the computational costs of a binary gate grow linearly and quadratically on the number of parties, respectively. We provide experimental results demonstrating the running time of a homomorphic NAND gate with bootstrapping. To the best of our knowledge, this is the first attempt in the literature to implement an MKHE scheme.
Source: pdf

Extracted details

Field Value Source Confidence
contribution multi-key generalization of TFHE gate bootstrapping llm 0.90
contribution two hybrid product algorithms multiplying a single-key bootstrapping key with a multi-key RLWE ciphertext llm 0.90
contribution ciphertext length linear and binary-gate cost quadratic in the number of parties, improving prior MKHE llm 0.90
contribution first implementation of an MKHE scheme with concrete timings llm 0.90
schemes TFHE llm 0.90
schemes multi-key FHE llm 0.90
schemes RGSW llm 0.90
libraries TFHE library llm 0.90
libraries LWE Estimator llm 0.90
hardware Intel Core i7-4910MQ 2.90GHz laptop, single thread llm 0.90
security level at least 110-bit llm 0.90
threat model multiple parties with independent keys; common reference string model llm 0.90
interaction non-interactive FHE llm 0.90
code url https://bitbucket.org/malb/lwe-estimator/src/master/18 (URL found in the full text) regex 0.50
code url https://github.com/ilachill/MK-TFHE llm 0.90
limitations requires the CRS model; MKHE without a CRS left as an open problem llm 0.90
limitations computational cost of a gate grows quadratically with the number of parties llm 0.90
limitations each parameter set supports a fixed maximum number of parties (2, 4 or 8) llm 0.90
limitations proof-of-concept code left unoptimized; only gate bootstrapping implemented, advanced TFHE functionalities left for future work llm 0.90
llm relevance low llm 0.90
key result bootstrapped NAND gate time: 0.27 s (parameter set I, 2 parties) llm 0.90
key result bootstrapped NAND gate time: 0.43 s / 1.45 s (parameter set II, 2 / 4 parties) llm 0.90
key result bootstrapped NAND gate time: 0.50 s / 1.90 s / 7.16 s (parameter set III, 2 / 4 / 8 parties) llm 0.90
key result key generation time per party: 1.1-1.3 s (sets I-III) llm 0.90
key result key sizes per party: bootstrapping key 0.62-1.03 MB, key-switching key 70.1 MB (sets I-III) llm 0.90
key result multi-key ciphertext size: 2.19 KB per party (4.38 KB for 2 parties, 17.32 KB for 8) (LWE n = 560, RLWE N = 1024) llm 0.90

Scheme card: Multi-key TFHE

Group 6. Multi-party FHE (threshold and multi-key)
Kind Scheme
Hardness assumption Torus LWE
Plaintext type Bits
SIMD packing No
Bootstrapping Yes
Post-quantum Yes
Status Niche
Fit for LLM inference Multi-key gate bootstrapping for joint data from several parties.
Follow-ups Mukherjee–Wichs two-round MPC (2015/345); Clear–McGoldrick (2014/798); FINALLY (2024/1505).
Follow-up papers in the archive FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE
Two Round Multiparty Computation via Multi-Key FHE
Multi-Identity and Multi-Key Leveled FHE from Learning with Errors

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: Multi-key HE 46 [p.1], TFHE 26 [p.1], GSW 12 [p.2], MPC 11 [p.1], Threshold HE 5 [p.2]
  • technique: Bootstrapping 46 [p.1], Key switching 31 [p.3], Lookup table 3 [p.18]
  • assumption: LWE 69 [p.2], RLWE 68 [p.1], Lattice-based 4 [p.20]
  • topic: Homomorphic encryption 22 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s38-0_multi-key-homomorphic-encryption-from-tfhe.pdf schemes 26 411.0 KB 7d7973266b6e

Database key: multi-key-homomorphic-encryption-from-tfhe · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set multi-key-homomorphic-encryption-from-tfhe COLUMN VALUE