Skip to content

Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE

Authors: Asharov, Jain, López-Alt, Tromer, Vaikuntanathan, Wichs
Year: 2012
Venue: EUROCRYPT 2012

type: scheme collection: schemes status: auto

Links: ePrint 2011/613

Visual lesson: Threshold FHE (AJLTVW) · Scheme table row: Threshold FHE (AJLTVW)

Summary

Auto-extracted summary (unreviewed)

The paper constructs threshold fully homomorphic encryption (TFHE) from the LWE-based FHE schemes of Brakerski et al. by exploiting their key-homomorphic properties, so that many parties can jointly generate a common public key (and, with one extra round, the evaluation key) with a distributed secret key and jointly decrypt. This yields UC-secure MPC against fully malicious adversaries with any number of corruptions in only 3 broadcast rounds in the CRS model or 2 rounds with a reusable PKI, with communication proportional to input and output size rather than circuit size and with the circuit-dependent computation outsourceable to a single party; efficient Sigma-protocols for LWE languages compiled into NIZKs in the random-oracle model make the approach practical.

Abstract

Fully homomorphic encryption (FHE) provides a simple template for secure computation between two parties (Alice and Bob) where: (I) Alice encrypts her input under her key, (II) Bob homomorphically evaluates the desired function on Alice’s ciphertext and his own input, and sends the encrypted output to Alice. Extending this approach to multiple parties raises the problem of which key to encrypt under; if all parties choose a key on their own, then homomorphic evaluation on ciphertexts under different keys will not be possible, and if a single party chooses the key for everyone then corrupting this party will break privacy for all. In this work, we explore the option of using threshold fully homomorphic encryption (TFHE), allowing many parties to cooperatively generate a common public key whose secret key is shared/distributed among them. Moreover, the parties can cooperatively decrypt a ciphertext without learning anything but the plaintext. We show how to instantiate this approach efficiently using the recent FHE schemes of Brakerski et al. (FOCS ’11, ITCS ’12) based on the learning with errors (LWE) assumption. Our main tool is to exploit the property that such LWE-based encryption schemes are homomorphic over their keys. Using TFHE, we construct multiparty computation (MPC) protocols secure against fully malicious settings, tolerating any number of corruptions, and providing security in the universal composability framework. Our schemes have several benefits over prior templates for MPC. Interaction: We get protocols with only 3 rounds of interaction in the common random string model, or 2 rounds with a reusable public-key infrastructure, improving on prior known results. Communication: The communication in our protocol is only proportional to the input and output size of the function being evaluated and independent of its circuit size. Computation: The only computation that depends on the size of the circuit being computed is a homomorphic evaluation over public ciphertexts. This computation can be performed by a single party or can be outsourced to an external server. Novel Approach: Prior approaches to MPC with a dishonest majority rely in part on some combination of the techniques of Yao (FOCS ’86) and/or Goldreich, Micali and Wigderson (STOC ’87). Our approach is fundamentally different and relies only on the homomorphic properties of LWE-based encryption.
Source: pdf

Extracted details

Field Value Source Confidence
contribution threshold FHE from LWE-based FHE via key-homomorphism, including threshold generation of evaluation keys llm 0.80
contribution 3-round MPC in the CRS model and 2-round MPC in the PKI setting (optimal), UC-secure against malicious adversaries with dishonest majority llm 0.80
contribution communication independent of circuit size; circuit-dependent computation can be outsourced to one party or an external server llm 0.80
contribution semi-malicious security notion that removes the need for coin-flipping llm 0.80
contribution Sigma-protocols for basic LWE languages and efficient UC NIZKs in the random-oracle model llm 0.80
contribution fairness variant for the honest-majority case llm 0.80
schemes threshold FHE llm 0.80
schemes LWE-based FHE (Brakerski et al.) llm 0.80
schemes NIZK / Sigma-protocols llm 0.80
threat model fully malicious, any number of corruptions, static corruption in the UC framework; CRS or PKI setup llm 0.80
interaction interactive (HE+MPC) llm 0.80
limitations key-homomorphism requires common randomness, so a CRS (or PKI) setup is assumed llm 0.80
limitations generating the evaluation key adds an extra round to key generation llm 0.80
limitations outsourcing evaluation in the fully malicious setting additionally requires efficiently verifiable proofs of correctness llm 0.80
llm relevance low llm 0.80
key result round complexity: 3 rounds (CRS model) / 2 rounds (PKI setting) (general MPC, malicious security, UC) llm 0.80
key result communication: proportional to input and output size, independent of circuit size (all MPC variants) llm 0.80

Scheme card: Threshold FHE (AJLTVW)

Group 6. Multi-party FHE (threshold and multi-key)
Kind Scheme
Hardness assumption LWE
Plaintext type Any (scheme-agnostic)
SIMD packing Depends on base scheme
Bootstrapping Yes
Post-quantum Yes
Status Foundational
Fit for LLM inference Splits the decryption key so the model owner and user can jointly control decryption.
Follow-ups Threshold cryptosystems from threshold FHE (Boneh et al., CRYPTO 2018, 2017/956).
Follow-up papers in the archive Threshold Cryptosystems From Threshold Fully Homomorphic Encryption

Keyword mentions

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

  • scheme: MPC 77 [p.1], TFHE 45 [p.1], Zero-knowledge proofs 15 [p.2], Threshold HE 7 [p.1], Secret sharing 7 [p.19], Garbled circuits 2 [p.3], Leveled / somewhat HE 2 [p.18]
  • library: Concrete (Zama) 1 [p.31]
  • technique: Malicious model 48 [p.2], Semi-honest model 12 [p.3], Compiler 12 [p.2], Two-party computation 8 [p.6], Bootstrapping 6 [p.13], Non-interactive 5 [p.4], Modulus switching 2 [p.25]
  • assumption: LWE 49 [p.1], Lattice-based 7 [p.8]
  • topic: Homomorphic encryption 81 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s35-0_multiparty-computation-with-low-communication-computation-an.pdf schemes 48 776.1 KB db54c69bda7d

Database key: multiparty-computation-with-low-communication-computation-and · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set multiparty-computation-with-low-communication-computation-and COLUMN VALUE