Skip to content

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