On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption¶
Authors: López-Alt, Tromer, Vaikuntanathan
Year: 2012
Venue: STOC 2012
type: scheme collection: schemes status: auto
Links: ePrint 2013/94 · link
Visual lesson: LTV (NTRU multi-key FHE) · Scheme table row: LTV (NTRU multi-key FHE)
Summary¶
Auto-extracted summary (unreviewed)
Introduces on-the-fly MPC, where an untrusted cloud non-interactively evaluates dynamically chosen functions over data of arbitrary user sets, with users involved only when uploading encrypted data and in a final joint decryption phase. The paper realises this via a new primitive, multikey FHE, constructed from NTRU (also giving the first FHE from NTRU), and shows that the decryption-phase interaction is unavoidable because removing it would imply program obfuscation.
Abstract¶
We propose a new notion of secure multiparty computation aided by a computationallypowerful but untrusted “cloud” server. In this notion that we call on-the-fly multiparty computation (MPC), the cloud can non-interactively perform arbitrary, dynamically chosen computations on data belonging to arbitrary sets of users chosen on-the-fly. All user’s input data and intermediate results are protected from snooping by the cloud as well as other users. This extends the standard notion of fully homomorphic encryption (FHE), where users can only enlist the cloud’s help in evaluating functions on their own encrypted data. In on-the-fly MPC, each user is involved only when initially uploading his (encrypted) data to the cloud, and in a final output decryption phase when outputs are revealed; the complexity of both is independent of the function being computed and the total number of users in the system. When users upload their data, they need not decide in advance which function will be computed, nor who they will compute with; they need only retroactively approve the eventuallychosen functions and on whose data the functions were evaluated. This notion is qualitatively the best possible in minimizing interaction, since the users’ interaction in the decryption stage is inevitable: we show that removing it would imply generic program obfuscation and is thus impossible. Our contributions are two-fold: 1. We show how on-the-fly MPC can be achieved using a new type of encryption scheme that we call multikey FHE, which is capable of operating on inputs encrypted under multiple, unrelated keys. A ciphertext resulting from a multikey evaluation can be jointly decrypted using the secret keys of all the users involved in the computation. 2. We construct a multikey FHE scheme based on NTRU, a very efficient public-key encryption scheme proposed in the 1990s. It was previously not known how to make NTRU fully homomorphic even for a single party. We view the construction of (multikey) FHE from NTRU encryption as a main contribution of independent interest. Although the transformation to a fully homomorphic system deteriorates the efficiency of NTRU somewhat, we believe that this system is a leading candidate for a practical FHE scheme. 1 Contents
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | notion of on-the-fly multiparty computation on the cloud | llm | 0.80 |
| contribution | definition of multikey fully homomorphic encryption | llm | 0.80 |
| contribution | multikey FHE construction from NTRU | llm | 0.80 |
| contribution | first fully homomorphic encryption scheme from NTRU | llm | 0.80 |
| contribution | impossibility result: removing decryption interaction implies generic program obfuscation | llm | 0.80 |
| schemes | multikey FHE | llm | 0.80 |
| schemes | NTRU | llm | 0.80 |
| schemes | FHE | llm | 0.80 |
| tasks | cloud-assisted secure multiparty computation | llm | 0.80 |
| threat model | untrusted cloud server and mutually distrusting users with independent keys | llm | 0.80 |
| interaction | interactive (HE+MPC) | llm | 0.80 |
| limitations | transformation to a fully homomorphic system deteriorates NTRU efficiency somewhat | llm | 0.80 |
| limitations | user interaction in the decryption stage is inevitable | llm | 0.80 |
| llm relevance | low | llm | 0.80 |
Scheme card: LTV (NTRU multi-key FHE)¶
| Group | 5. Earlier and other FHE constructions |
| Kind | Scheme |
| Hardness assumption | NTRU |
| Plaintext type | Bits |
| SIMD packing | Limited |
| Bootstrapping | Yes |
| Post-quantum | Weakened (overstretched NTRU) |
| Status | Foundational |
| Fit for LLM inference | First multi-key FHE. Overstretched-NTRU attacks limit its parameters. |
| Follow-ups | YASHE (2013/075), also affected. |
| Follow-up papers in the archive | Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: MPC 94 [p.1], Multi-key HE 45 [p.1], Leveled / somewhat HE 45 [p.2], Zero-knowledge proofs 43 [p.2], NTRU 41 [p.1], Threshold HE 7 [p.13], Paillier 2 [p.13], ElGamal 2 [p.13], Secret sharing 2 [p.5], PIR 2 [p.51]
- technique: Non-interactive 40 [p.1], Malicious model 33 [p.3], Bootstrapping 32 [p.2], Relinearization 18 [p.6], Semi-honest model 15 [p.10], Key switching 6 [p.13], Compiler 6 [p.22], Modulus switching 4 [p.13]
- assumption: RLWE 20 [p.2], LWE 16 [p.2], Lattice-based 13 [p.7]
- topic: Homomorphic encryption 153 [p.1]
Related papers¶
- Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme follow up of this paper — follow-up listed for scheme "LTV (NTRU multi-key FHE)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s32-0_on-the-fly-multiparty-computation-on-the-cloud-via-multikey.pdf |
schemes | 73 | 545.3 KB | 32022e4c0294 |
Database key: on-the-fly-multiparty-computation-on-the-cloud-via-multikey-fully · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set on-the-fly-multiparty-computation-on-the-cloud-via-multikey-fully COLUMN VALUE