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]
Related papers¶
- Threshold Cryptosystems From Threshold Fully Homomorphic Encryption follow up of this paper — follow-up listed for scheme "Threshold FHE (AJLTVW)"
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