The Privacy Stack: A Practitioner’s Guide to Secure Computation

Part 2: MPC : What It Gives You, What It Costs, and What It Does Not Give You

In Part 0, I framed MPC as the technology for the setting where multiple parties each hold private inputs and want to compute a joint function. In Part 1, I explained the trust axis: MPC can achieve information-theoretic security (no computational hardness assumptions, given secure point-to-point channels) when fewer than one-third of the parties are corrupted, or computational security (relying on hardness assumptions such as oblivious transfer or somewhat-homomorphic encryption) when the adversary may corrupt half or more of the parties.

This post is not a tutorial on how MPC protocols work; Daniel Escudero’s crash course [1] and Evans, Kolesnikov, and Rosulek’s monograph [2] already cover that well. Instead, this post is about the questions a practitioner needs to answer: what exactly does MPC guarantee? What does it cost? And what are the things it explicitly does not give you?

What MPC Gives You

MPC provides three guarantees, all formalized through the real–ideal (simulation) paradigm (see [2], Chapter 2):

1. Privacy. No party learns anything about other parties’ inputs beyond what can be inferred from the output and their own input. This is formalized through a simulator: for each corrupted party, there must exist an algorithm that, given that party’s input and the function’s output, produces a transcript indistinguishable from the party’s actual view of the protocol execution. If such a simulator exists, the protocol leaks nothing beyond what the corrupted party can already compute from its own input together with the output.
2. Correctness. When the protocol terminates, the output is the correct evaluation of the agreed-upon function on the actual inputs. For active (malicious) security, this holds even when corrupted parties deviate arbitrarily from the protocol, with two caveats. First, corrupted parties may substitute their inputs (see “What MPC does not give you” below). Second, in the dishonest-majority setting, the standard guarantee is security with abort: honest parties either receive the correct output or detect the cheating and abort; the adversary can force an abort, but cannot force a wrong answer.
3. No trusted third party. The computation is performed jointly by the parties themselves, with no external party who sees all the inputs. Equivalently: any coalition of corrupted parties up to the threshold learns nothing about honest parties’ inputs beyond what the output reveals. This is the defining advantage of MPC over the “send everything to a trusted server” approach.

These three properties are captured in a single definition: the protocol is secure if no adversary can achieve anything in the real protocol execution that it could not also achieve in an ideal world where a perfectly trusted party collects inputs, computes the function, and returns outputs.

What MPC Costs

Addition is free; multiplication is the bottleneck.

In any secret-sharing-based MPC protocol, including the BGW [5], CCD [6], and SPDZ [7] families, addition of secret-shared values is a purely local operation: each party adds their shares and the result is a valid sharing of the sum. No communication is needed.

Multiplication requires interaction. In modern Shamir-based protocols (honest majority, the BGW [5] descendant typically taught today, sometimes called GRR-style after Gennaro–Rabin–Rabin), multiplication is done by each party locally computing the product of its shares, re-sharing that local product, and applying a public recombination vector to reduce the polynomial degree from 2t back to t. Per-party communication is O(n) field elements per multiplication gate; total communication across all parties is O(n²) per gate (later optimizations such as Beerliová-Trubíniová–Hirt’s hyper-invertible matrices [10] reduce this to amortized O(n) total).

In the SPDZ protocol (dishonest majority), multiplication consumes a preprocessed Beaver triple ([a], [b], [c] with c = ab). Each party locally computes its shares of e = x − a and d = y − b, then broadcasts those shares so that e and d can be reconstructed. Revealing e and d is safe because a and b are uniformly random and unknown to the adversary.

The key cost metric is non-linear gates, not circuit size. In secret-sharing-based protocols, addition is communication-free and only multiplication gates require interaction. In garbled circuits with the free-XOR optimization (Kolesnikov & Schneider, ICALP 2008), XOR gates require no ciphertexts in the garbled table; only AND gates incur communication cost. Either way: when evaluating feasibility, count the non-linear gates in the circuit, not the total gates.

The preprocessing/online split.

Beaver’s circuit randomization technique [8] (CRYPTO 1991) introduced multiplication triples and the now-dominant pattern of consuming them online: separate the protocol into a preprocessing phase (offline, input-independent, only the number of triples depends on the circuit) and an online phase (fast, interactive, input-dependent).

In the preprocessing phase, parties generate multiplication triples, shared values [a], [b], [c] where a and b are uniformly random and c = ab. Nobody knows a, b, or c; they only hold shares. This phase uses heavy cryptographic machinery, somewhat homomorphic encryption in the original SPDZ [7], oblivious transfer (extended from a small public-key base) in MASCOT [9], because it happens before the inputs (and, in the function-independent variant, before the function) are known.

In the online phase, each multiplication gate consumes one triple:

• Open e = x − a and d = y − b (safe: each is masked by a uniformly random share).
• Compute [xy] = [c] + e·[b] + d·[a] + e·d (linear operations on shares, plus a public constant e·d).

The online cost per multiplication gate is two openings. Each party sends its share (one field element) to every other party, for a per-gate total of O(n²) field elements across all parties. The online phase uses only field arithmetic, hash-based commitments, and information-theoretic MAC checks, no public-key cryptography.

Communication complexity. For honest-majority protocols with perfect security against t < n/3 active corruptions, Beerliová-Trubíniová and Hirt[10] achieved an amortized O(n) field elements of communication per multiplication gate (total across all parties), reducing the previously known Ω(n³) cost. This paper received the TCC Test-of-Time Award in 2020 for “introducing hyper-invertible matrices to perfectly secure multiparty computation, thus enabling significant efficiency improvements and, eventually, constructions with minimal communication complexity.”

For dishonest-majority protocols in the SPDZ family, the standard online phase has total communication Ω(n²·|C|) field elements over the full circuit (each of n parties broadcasts a share of each opened value to all n parties, and there are O(|C|) openings). A result by Gordon, Le, and McVicker (CCS 2023 [11]) reduces the total communication to O(n·|C|), matching, asymptotically, the per-gate communication of the honest-majority setting.

For the preprocessing phase, the original SPDZ offline phase based on somewhat homomorphic encryption [7] requires O(n²·κ²) bits of communication per authenticated multiplication triple, where κ is the security parameter (see e.g. Lindell, Pinkas, Smart & Yanai, J. Cryptology 2019, for this complexity analysis). The “Overdrive” variants [12] (HighGear and LowGear) improve this with tighter concrete costs; see [12], Section 5, for benchmarks.

Round complexity.

Protocols in the GMW paradigm, including SPDZ, require a number of communication rounds proportional to the multiplicative depth of the circuit (the longest chain of multiplication gates from input to output). For a circuit of depth D, expect roughly D rounds of online interaction.

Constant-round protocols exist (notably the BMR protocol [13] for the multiparty setting and Yao’s garbled circuits [14] for the two-party setting), but they typically have higher communication or computation costs per gate.

What MPC Does Not Give You

1. MPC does not hide the output. If two parties compute the sum of their salaries, each party learns the other party’s salary by subtracting their own from the sum. Any function whose output reveals an input is unsafe regardless of how the protocol is implemented.
2. MPC does not prevent input manipulation. As Cramer, Damgård, and Nielsen point out in the introductory discussion of Chapter 1 of their textbook [15], a corrupted player can always choose to execute the protocol with any input they like; the security definition cannot rule this out, because the same substitution is available to a corrupted party in the ideal world. In the Danish sugar-beet auction [16], this was handled by economic mechanism design rather than cryptography: the double-auction clearing price was chosen so that truthful bidding was the dominant strategy.
3. Fairness is generally impossible without an honest majority. Cleve (STOC 1986 [17]) proved that for any r-round two-party coin-tossing protocol, an efficient adversary can bias the output by Ω(1/r); fair coin-tossing is therefore impossible to achieve, and the bound extends by a standard reduction to any dishonest-majority multiparty setting. This rules out fully fair MPC for any function that implies coin tossing (e.g., XOR) whenever there is no honest majority.
4. MPC does not scale trivially to very large party counts. Communication per gate typically grows at least linearly in n, and round complexity is at least logarithmic for many protocols. Packed secret sharing, introduced by Franklin and Yung (STOC 1992 [18]), amortizes some of this cost across many parallel evaluations of the same circuit (SIMD-style), but the underlying per-party costs do not vanish.
5. MPC does not hide the function being computed (in the standard setting). All parties typically know the circuit they are evaluating. Yao’s garbled circuits [14] hide the function from the evaluator in two-party computation (because the evaluator sees only an obfuscated circuit), but the garbler knows the function.

What This Series Will Cover

In upcoming posts:

• Part 1: The trust axis , hardware trust, computational trust, and information-theoretic trust. What each one actually means for your system’s security lifecycle.
• Part 2: MPC , what it gives you, what it costs, and what it does not give you. Not a crash course (Escudero already wrote that), but a practitioner’s perspective on where MPC fits and where it breaks down.
• Part 3: FHE, the noise problem, bootstrapping, and what “practical FHE” actually means today.
• Part 4: Zero-knowledge proofs, the distinction between proving and computing, and why the MPC-in-the-head connection matters.
• Part 5: TEEs, the hardware trust tradeoff and the side-channel reality.
• Part 6: The comparison matrix, one problem, four solutions.
• Part 7: Hybrid architectures, why real systems combine everything.
• Part 8: Concrete costs, actual numbers for actual operations.
• Part 9: Open problems that matter for practitioners.
• Part 10: A decision framework for choosing your stack.

This series reflects my perspective as a researcher working on privacy-preserving computation. I have tried to be precise and to avoid overclaiming. If you find errors or disagree with any characterization, I welcome the discussion.

Next: Part 3: FHE.

References:

[1] D. Escudero. “A Crash Course on MPC” (8-part series). The Sugar Beet: Applied MPC, Medium, 2020–2021.

[2] D. Evans, V. Kolesnikov, M. Rosulek. A Pragmatic Introduction to Secure Multi-Party Computation. Foundations and Trends in Privacy and Security, Vol. 2, №2–3, pp. 70–246, 2018. DOI 10.1561/3300000019.

[3] O. Goldreich, S. Micali, A. Wigderson. “How to Play Any Mental Game, or a Completeness Theorem for Protocols with Honest Majority.” STOC 1987, pp. 218–229. ACM Digital Library

[4] R. Canetti. “Universally Composable Security: A New Paradigm for Cryptographic Protocols.” 42nd FOCS, 2001, pp. 136–145. (Updated full version: IACR ePrint 2000/067.) ACM Digital Library

[5] M. Ben-Or, S. Goldwasser, A. Wigderson. “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation.” STOC 1988, pp. 1–10.

[6] D. Chaum, C. Crépeau, I. Damgård. “Multiparty Unconditionally Secure Protocols (Extended Abstract).” STOC 1988, pp. 11–19.

[7] I. Damgård, V. Pastro, N. P. Smart, S. Zakarias. “Multiparty Computation from Somewhat Homomorphic Encryption.” CRYPTO 2012, LNCS 7417, pp. 643–662. Springer, 2012. Springer

[8] D. Beaver. “Efficient Multiparty Protocols Using Circuit Randomization.” CRYPTO 1991, LNCS 576, pp. 420–432. Springer, 1992. Springer

[9] M. Keller, E. Orsini, P. Scholl. “MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer.” ACM CCS 2016, pp. 830–842. ACM Digital Library

[10] Z. Beerliová-Trubíniová, M. Hirt. “Perfectly-Secure MPC with Linear Communication Complexity.” TCC 2008, LNCS 4948, pp. 213–230. Springer, 2008. International Association for Cryptologic ResearchSpringer

[11] S. D. Gordon, P. H. Le, D. McVicker. “Linear Communication in Malicious Majority MPC.” ACM CCS 2023. DOI 10.1145/3576915.3623162. DOI

[12] M. Keller, V. Pastro, D. Rotaru. “Overdrive: Making SPDZ Great Again.” EUROCRYPT 2018, LNCS 10822, pp. 158–189. Springer, 2018. dblpspringer

[13] D. Beaver, S. Micali, P. Rogaway. “The Round Complexity of Secure Protocols (Extended Abstract).” STOC 1990, pp. 503–513. ACM Digital Library

[14] A. C. Yao. “How to Generate and Exchange Secrets (Extended Abstract).” 27th FOCS, 1986, pp. 162–167.

[15] R. Cramer, I. Damgård, J. B. Nielsen. Secure Multiparty Computation and Secret Sharing. Cambridge University Press, 2015. ISBN 978–1–107–04305–3. (See Chapter 1, §1.3 — “Multiparty Computation”, pp. 6–13 — for the discussion of input substitution.) Aarhus Universitet + 2

[16] P. Bogetoft, D. L. Christensen, I. Damgård, M. Geisler, T. Jakobsen, M. Krøigaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. I. Schwartzbach, T. Toft. “Secure Multiparty Computation Goes Live.” FC 2009, LNCS 5628, pp. 325–343. Springer, 2009. Springer

[17] R. Cleve. “Limits on the Security of Coin Flips When Half the Processors Are Faulty (Extended Abstract).” STOC 1986, pp. 364–369.

[18] M. K. Franklin, M. Yung. “Communication Complexity of Secure Computation.” STOC 1992, pp. 699–710.