Multiparty Computation from Somewhat Homomorphic Encryption¶
Authors: Damgård, Pastro, Smart, Zakarias
Year: 2012
Venue: CRYPTO 2012
type: scheme collection: schemes status: auto
Links: ePrint 2011/535
Visual lesson: Additive secret sharing with SHE triples (SPDZ) · Scheme table row: Additive secret sharing with SHE triples (SPDZ)
Summary¶
Auto-extracted summary (unreviewed)
This is the SPDZ paper: a general MPC protocol for arithmetic circuits over any finite field that is secure against an active adversary corrupting up to n-1 of n players, structured as a function- and input-independent preprocessing phase followed by an unconditionally secure online phase whose total cost is linear in n (previously quadratic) and only a small constant factor above computing in the clear. Preprocessing uses a somewhat homomorphic encryption scheme extended from Brakerski et al. with distributed decryption and packing, needing O(n^2/s) public-key operations per multiplication; in practice a secure 64-bit multiplication for 3 players costs 0.05 ms online and about 13 ms of preprocessing.
Abstract¶
We propose a general multiparty computation protocol secure against an active adversary corrupting up to n−1 of the n players. The protocol may be used to compute securely arithmetic circuits over any finite field Fpk. Our protocol consists of a preprocessing phase that is both independent of the function to be computed and of the inputs, and a much more efficient online phase where the actual computation takes place. The online phase is unconditionally secure and has total computational (and communication) complexity linear in n, the number of players, where earlier work was quadratic in n. Moreover, the work done by each player is only a small constant factor larger than what one would need to compute the circuit in the clear. We show this is optimal for computation in large fields. In practice, for 3 players, a secure 64-bit multiplication can be done in 0.05 ms. Our preprocessing is based on a somewhat homomorphic cryptosystem. We extend a scheme by Brakerski et al., so that we can perform distributed decryption and handle many values in parallel in one ciphertext. The computational complexity of our preprocessing phase is dominated by the public-key operations, we need O(n2/s) operations per secure multiplication where s is a parameter that increases with the security parameter of the cryptosystem. Earlier work in this model needed Ω(n2) operations. In practice, the preprocessing prepares a secure 64-bit multiplication for 3 players in about 13 ms.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | actively secure MPC for dishonest majority (up to n-1 of n corrupted) over any finite field F_{p^k} | llm | 0.80 |
| contribution | preprocessing/online split with an information-theoretic online phase of complexity linear in n | llm | 0.80 |
| contribution | proof that the online overhead is optimal for computation in large fields | llm | 0.80 |
| contribution | SHE-based preprocessing with O(n^2/s) public-key operations per multiplication instead of Omega(n^2) | llm | 0.80 |
| contribution | extension of the Brakerski et al. SHE scheme with distributed decryption and packing of many values per ciphertext | llm | 0.80 |
| schemes | somewhat homomorphic encryption (Brakerski et al.) | llm | 0.80 |
| schemes | secret sharing | llm | 0.80 |
| schemes | zero-knowledge proofs | llm | 0.80 |
| tasks | arithmetic circuit evaluation | llm | 0.80 |
| security level | roughly equivalent to 1024-bit RSA; zero-knowledge error probability 2^-40 | llm | 0.80 |
| threat model | active (malicious) adversary, dishonest majority with up to n-1 of n players corrupted, UC security | llm | 0.80 |
| interaction | pure MPC | llm | 0.80 |
| llm relevance | low | llm | 0.80 |
| key result | online secure 64-bit multiplication: 0.05 ms (3 players) | llm | 0.80 |
| key result | preprocessing per secure 64-bit multiplication: about 13 ms amortized (3 players, s approximately 12000) | llm | 0.80 |
| key result | online complexity: linear in n (earlier work quadratic) (total computation and communication) | llm | 0.80 |
| key result | preprocessing public-key operations per multiplication: O(n^2/s) vs Omega(n^2) in earlier work (s grows with the SHE security parameter) | llm | 0.80 |
Scheme card: Additive secret sharing with SHE triples (SPDZ)¶
| Group | 9. Non-HE cryptographic alternatives to CKKS |
| Kind | Primitive |
| Hardness assumption | SHE (BGV) for preprocessing; information-theoretic online |
| Plaintext type | Fixed point over Z_p / Z_2^k |
| SIMD packing | Vectorized |
| Bootstrapping | n/a |
| Post-quantum | Depends |
| Status | Widely used |
| Fit for LLM inference | Basis of many 2PC/MPC LLM protocols. Needs interaction and non-colluding parties. |
| Libraries | MP-SPDZ, CrypTen |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: MPC 28 [p.1], Zero-knowledge proofs 15 [p.3], Leveled / somewhat HE 15 [p.1], Secret sharing 12 [p.2], Oblivious transfer 4 [p.4], RSA 2 [p.3], Threshold HE 2 [p.4]
- library: Concrete (Zama) 2 [p.13]
- technique: SIMD packing 6 [p.3], Two-party computation 5 [p.16], Bootstrapping 4 [p.2]
- assumption: Lattice-based 14 [p.14], LWE 11 [p.13], IND-CPA 4 [p.9]
- topic: Homomorphic encryption 23 [p.1]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s50-0_multiparty-computation-from-somewhat-homomorphic-encryption.pdf |
schemes | 46 | 649.7 KB | b9f32625d7d9 |
Database key: multiparty-computation-from-somewhat-homomorphic-encryption · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set multiparty-computation-from-somewhat-homomorphic-encryption COLUMN VALUE