Electronics Guide

Secure Multi-Party Computation

Secure Multi-Party Computation (MPC) is a subfield of cryptography that enables multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other. First proposed by Andrew Yao in the 1980s, MPC has evolved from theoretical curiosity to practical technology deployed in financial services, healthcare, government, and private industry.

The fundamental promise of MPC is profound: parties can collaborate on computations as if they had pooled their data, yet each party learns nothing beyond the final result. This capability addresses scenarios where data sharing is impossible due to privacy regulations, competitive concerns, or legal restrictions, yet collaborative analysis would benefit all participants. Modern MPC protocols combine sophisticated cryptographic techniques with optimized implementations to achieve practical performance for increasingly complex computations.

Foundational Concepts

Understanding secure multi-party computation requires familiarity with its theoretical foundations, security models, and the fundamental building blocks from which practical protocols are constructed.

Security Models and Definitions

MPC protocols are analyzed under different security models that capture various adversarial capabilities:

  • Semi-Honest (Passive) Security: Adversaries follow the protocol specification but attempt to learn additional information from the messages they receive. This model is appropriate when parties are trusted to execute correctly but curious about others' data, common in scenarios involving business partners or regulated entities.
  • Malicious (Active) Security: Adversaries may deviate arbitrarily from the protocol, sending incorrect messages or aborting computation. Achieving security against malicious adversaries requires additional cryptographic mechanisms and typically increases computational overhead.
  • Covert Security: An intermediate model where cheating is detected with some probability, deterring rational adversaries who wish to avoid detection. Offers a practical trade-off between security guarantees and performance.
  • Honest Majority vs. Dishonest Majority: Protocols differ based on assumptions about the number of corrupted parties. Some efficient protocols require an honest majority, while others achieve security even when all but one party is corrupted.
  • Composition and Universal Composability: Security definitions ensuring protocols remain secure when composed with other protocols or executed concurrently, essential for real-world deployments.

Computational vs. Information-Theoretic Security

MPC protocols achieve security through different mechanisms with distinct properties:

  • Computational Security: Based on cryptographic assumptions (e.g., hardness of factoring or discrete logarithm). Security holds against computationally bounded adversaries. Most practical protocols use computational security for efficiency.
  • Information-Theoretic Security: Security is unconditional, holding even against adversaries with unlimited computational power. Typically requires honest majority assumptions and multiple communication rounds but provides stronger guarantees.
  • Hybrid Approaches: Many practical protocols combine information-theoretic techniques in the online phase with computational assumptions in preprocessing, balancing security strength with efficiency.

Garbled Circuits

Garbled circuits, introduced by Andrew Yao, provide a general method for secure two-party computation. The technique transforms a boolean circuit computing the desired function into an encrypted form that can be evaluated without revealing intermediate values.

Garbling Procedure

The garbling process creates an encrypted circuit that computes correctly while hiding all intermediate values:

  • Wire Label Assignment: Each wire in the circuit is assigned two random cryptographic labels, one representing the value 0 and one representing 1. The association between labels and values is known only to the garbler.
  • Gate Garbling: For each gate, a garbled gate table is created containing encryptions of output labels under input labels. The table is permuted so the evaluator cannot determine which entry corresponds to which input combination.
  • Point-and-Permute Optimization: Each wire label includes a "select bit" that directly indexes the garbled table, eliminating the need to try all decryptions. This reduces evaluation to a single decryption per gate.
  • Free XOR Technique: By choosing labels with a global offset, XOR gates require no cryptographic operations or communication, dramatically improving efficiency for circuits with many XOR gates.
  • Half-Gates Optimization: Reduces AND gate cost to two ciphertexts (down from four), currently the most efficient known garbling scheme for AND gates.

Evaluation and Communication

After garbling, the circuit is evaluated through a specific protocol:

  • Circuit Transmission: The garbler sends the garbled circuit to the evaluator along with their own input labels. Circuit size scales with the number of gates, making bandwidth a key consideration.
  • Oblivious Transfer for Input: The evaluator obtains labels for their inputs through oblivious transfer, learning only the labels corresponding to their actual input bits without revealing those bits to the garbler.
  • Sequential Evaluation: The evaluator processes gates in topological order, using input labels to decrypt output labels from garbled tables. Each gate evaluation reveals only the output label, not the underlying bit value.
  • Output Revelation: After evaluation, output wire labels are decoded to reveal the computation result. Depending on the protocol, outputs may be revealed to one or both parties.

Advanced Garbling Techniques

Research has produced numerous optimizations extending garbled circuit capabilities:

  • Row Reduction: Techniques to reduce the number of ciphertexts per garbled gate, saving bandwidth and improving evaluation speed.
  • Garbled Gadgets: Specialized garbled constructions for common operations (addition, comparison, multiplication) that are more efficient than naive boolean circuit representations.
  • Streaming Garbling: Generates and transmits garbled gates on-demand rather than creating the entire circuit upfront, reducing memory requirements for large circuits.
  • Reusable Garbled Circuits: Schemes allowing a single garbled circuit to be evaluated multiple times, amortizing garbling cost across many executions.
  • Authenticated Garbling: Extensions providing security against malicious adversaries while maintaining efficiency close to semi-honest protocols.

Secret Sharing

Secret sharing is a fundamental cryptographic primitive enabling distribution of a secret among multiple parties such that only authorized subsets can reconstruct it. In MPC, secret sharing provides the foundation for protocols involving three or more parties.

Shamir Secret Sharing

Shamir's scheme uses polynomial interpolation to create threshold secret sharing:

  • Share Generation: A degree t-1 polynomial is constructed with the secret as the constant term and random coefficients. Each party receives the polynomial evaluated at a unique point, creating n shares where any t can reconstruct the secret.
  • Lagrange Interpolation: Given t shares, the secret is recovered by interpolating the polynomial at zero using Lagrange coefficients. These coefficients can be precomputed for known evaluation points.
  • Threshold Properties: A (t,n)-threshold scheme ensures any t parties can reconstruct while fewer than t parties learn nothing about the secret. Common configurations include (n,n) requiring all parties and (n/2+1,n) requiring honest majority.
  • Linear Operations: Addition of shared values requires only local computation: parties add their shares. This property is fundamental to efficient secret-sharing-based MPC.
  • Multiplication Complexity: Multiplying shared values increases the polynomial degree, requiring degree reduction protocols that involve communication. This makes multiplication the dominant cost in many MPC protocols.

Additive Secret Sharing

Additive sharing offers simplicity and efficiency for specific scenarios:

  • XOR Sharing: For binary values, the secret is split into random shares that XOR to the original value. Simple and efficient but requires all shares for reconstruction.
  • Arithmetic Sharing: Over finite fields or rings, shares are random elements summing to the secret. Commonly used in two-party and three-party protocols.
  • Replicated Secret Sharing: Each party holds multiple shares from an additive scheme, enabling protocols with different trade-offs between communication and computation.
  • Packed Secret Sharing: Embeds multiple secrets in a single polynomial, enabling SIMD-style parallel computation on vectors of shared values.

Secret Sharing MPC Protocols

Secret sharing enables efficient multi-party protocols with various properties:

  • BGW Protocol: The foundational information-theoretically secure protocol using Shamir sharing. Achieves security with honest majority through verifiable secret sharing and degree reduction.
  • GMW Protocol: Uses additive sharing with oblivious transfer for multiplication, achieving security against dishonest majority but with computational assumptions.
  • SPDZ Protocol: Combines additive sharing with message authentication codes for malicious security. Uses preprocessing to generate multiplication triples, enabling fast online computation.
  • ABY Framework: Supports arithmetic, boolean, and Yao sharing with efficient conversions, allowing computations to use the most efficient representation for each operation.

Oblivious Transfer

Oblivious Transfer (OT) is a fundamental cryptographic primitive where a sender transfers one of several pieces of information to a receiver, but remains oblivious as to which piece was transferred. OT serves as a building block for virtually all MPC protocols.

Basic OT Variants

Different OT formulations address various requirements:

  • 1-out-of-2 OT: The sender has two messages; the receiver obtains exactly one based on their choice bit, learning nothing about the other message. The sender learns nothing about which message was chosen.
  • 1-out-of-n OT: Generalization where the sender has n messages and the receiver selects one. Useful when inputs come from larger domains.
  • k-out-of-n OT: The receiver obtains k of the sender's n messages, with the sender unaware of which were selected.
  • String OT: Transfers strings rather than single bits, achieved by running bit OT in parallel or using more efficient constructions.
  • Random OT: Both sender's messages and receiver's choice are random. Can be generated in preprocessing and later "programmed" with actual values.

OT Extension

OT extension protocols generate many OTs from a small number of base OTs:

  • IKNP Extension: The foundational OT extension protocol using a small number of base OTs (typically 128) and symmetric-key operations to generate millions of OTs efficiently. Communication cost is essentially two hash function outputs per OT.
  • Silent OT Extension: Generates OT correlations with sublinear communication using pseudorandom correlation generators. Dramatically reduces bandwidth for large-scale OT generation.
  • Correlated OT: Produces OTs where messages have a known correlation, enabling more efficient protocols. The receiver gets either a random value or that value XORed with a global correlation.
  • Vector OT: Extends to vector-valued choices and messages, supporting operations over larger fields.

OT-Based Protocols

Many MPC protocols are constructed primarily from oblivious transfer:

  • GMW from OT: The GMW protocol implements AND gates using 1-out-of-4 OT, with parties XOR-sharing wire values. Linear gates are computed locally.
  • Multiplication from OT: Beaver multiplication triples can be generated using correlated OT, enabling efficient secret-sharing-based computation.
  • Private Set Operations: OT extension enables efficient private set intersection and related operations through specialized protocols.
  • Circuit Evaluation: OT is essential for garbled circuit evaluation, providing the evaluator's input labels without revealing their inputs.

Private Set Intersection

Private Set Intersection (PSI) allows two parties to compute the intersection of their sets without revealing elements outside the intersection. PSI is one of the most practically deployed MPC applications, with uses in contact discovery, ad measurement, and threat intelligence sharing.

PSI Protocols

Various approaches achieve PSI with different trade-offs:

  • OT-Based PSI: Uses oblivious transfer extension and hashing techniques. Achieves excellent performance for large sets with efficient communication through cuckoo hashing and polynomial interpolation.
  • DH-Based PSI: Employs Diffie-Hellman key exchange properties. Each party exponentiates their elements, shuffles, and re-exponentiates, with matching elements producing equal values. Simple but computationally intensive.
  • Circuit-Based PSI: Implements set intersection as a boolean or arithmetic circuit, enabling additional computations on the intersection. More flexible but often less efficient than specialized protocols.
  • PSI-Cardinality: Reveals only the size of the intersection, not the elements themselves. Useful when knowing overlap is sufficient.
  • Labeled PSI: Associates payloads with set elements; the receiver learns payloads for intersecting elements. Enables private database queries.

PSI Optimizations

Practical PSI deployment requires numerous optimizations:

  • Cuckoo Hashing: Maps set elements to hash table positions with constant lookup time, reducing comparison complexity. Multiple hash functions ensure all elements can be placed.
  • OPRF-Based PSI: Uses oblivious pseudorandom functions to compare encrypted element representations without circuit evaluation, achieving linear complexity.
  • Polynomial-Based Techniques: Encodes sets as polynomial roots, enabling intersection through polynomial operations. Efficient for certain size ratios.
  • Multi-Party PSI: Extends protocols to three or more parties, with specialized techniques for different party counts and security requirements.
  • Unbalanced PSI: Optimized protocols for scenarios where one set is much larger than the other, common in server-client applications.

Secure Comparison Protocols

Secure comparison allows parties to determine the ordering relationship between their private values without revealing the values themselves. Comparison is fundamental to many applications including auctions, benchmarking, and database queries.

Comparison Techniques

Various approaches implement secure comparison with different trade-offs:

  • Garbled Circuit Comparison: Implements a comparison circuit (typically a subtractor followed by sign bit extraction) using garbled circuits. Efficient for small bit widths but scales with input size.
  • Bit Decomposition: Converts shared arithmetic values to shared binary representations, enabling efficient comparison through boolean operations. The conversion itself requires careful protocol design.
  • DGK Protocol: An efficient comparison protocol using homomorphic encryption, particularly suited for integration with other homomorphic computations.
  • Millionaires' Problem Solutions: Specialized protocols for the two-party comparison problem, the original MPC problem posed by Yao.
  • Prefix Computation: Computes comparison through parallel prefix circuits, reducing circuit depth and enabling more parallelism.

Comparison Applications

Secure comparison enables numerous privacy-preserving applications:

  • Private Auctions: Determine winning bids without revealing losing bids or the winner's true valuation.
  • Secure Sorting: Sort shared data using comparison networks, enabling order statistics and median computation.
  • Range Queries: Determine if private values fall within specified ranges for access control or filtering.
  • Threshold Functions: Compute functions that depend on whether values exceed thresholds, common in finance and healthcare.

Arithmetic Circuits

Arithmetic circuits compute over finite fields or rings using addition and multiplication gates. They provide natural representations for numerical computations and enable efficient MPC for many applications.

Arithmetic Circuit MPC

Protocols for arithmetic circuit evaluation share common characteristics:

  • Secret Sharing Over Fields: Values are shared over finite fields (commonly large prime fields or extension fields), enabling exact arithmetic without overflow concerns.
  • Linear Operations Free: Addition, subtraction, and scalar multiplication require only local computation on shares, with no communication.
  • Multiplication Protocols: Multiplying shared values requires interaction. Beaver triple-based multiplication is the most common approach, consuming one preprocessed triple per multiplication.
  • Ring-Based Computation: Computing over rings like integers modulo powers of 2 enables efficient representation of machine integers, though some operations (like division) become more complex.
  • Truncation Protocols: Fixed-point arithmetic requires truncation after multiplication to maintain precision, requiring specialized protocols to truncate shared values securely.

Beaver Multiplication Triples

Beaver's technique transforms multiplication into linear operations using preprocessed correlations:

  • Triple Structure: A multiplication triple consists of three shared random values (a, b, c) where c = a * b. Triples can be generated in preprocessing without knowledge of actual inputs.
  • Online Multiplication: To multiply shared x and y, parties open (x-a) and (y-b), then compute shares of xy using the triple without revealing x or y.
  • Triple Generation: Triples are generated using OT, homomorphic encryption, or trusted dealers depending on the security model and efficiency requirements.
  • Verification: For malicious security, triples must be verified before use through cut-and-choose or MAC-based authentication.

Boolean Circuits

Boolean circuits compute using AND, OR, XOR, and NOT gates over binary values. They provide maximum flexibility for arbitrary computation and enable certain operations more efficiently than arithmetic circuits.

Boolean Circuit Representations

Functions are represented as boolean circuits with various characteristics:

  • Circuit Depth vs. Size: Circuits can be optimized for depth (parallel time) or size (total gates). Different MPC protocols benefit from different optimizations.
  • AND Gate Count: In protocols using Free-XOR garbling, only AND gates have significant cost. Circuit optimizers minimize AND gates specifically.
  • Universal Gates: NAND or NOR gates alone can implement any function, simplifying some protocol designs at the cost of circuit size.
  • Circuit Compilers: Tools automatically convert high-level programs to boolean circuits, handling control flow, data types, and optimization.

Boolean vs. Arithmetic Trade-offs

Different circuit types excel at different operations:

  • Comparison and Branching: Boolean circuits naturally express comparison, equality testing, and conditional operations.
  • Arithmetic Operations: Addition and multiplication over large integers are more efficient in arithmetic circuits, avoiding large boolean representations.
  • Bit Manipulation: Shifts, rotations, and bitwise operations are natural in boolean circuits.
  • Cryptographic Operations: Hash functions and block ciphers typically have efficient boolean circuit representations.

Hybrid Protocols

Hybrid protocols combine multiple MPC techniques to leverage the strengths of each approach. Modern MPC frameworks support automatic or programmer-guided selection of the most efficient representation for each computation.

ABY and Mixed-Protocol Frameworks

The ABY framework and its successors enable flexible protocol mixing:

  • Three Sharing Types: ABY supports Arithmetic sharing for field operations, Boolean sharing for bitwise operations, and Yao (garbled circuit) sharing for general computation.
  • Conversion Protocols: Efficient protocols convert between sharing types, enabling computations to switch representations at operation boundaries.
  • Automatic Selection: Advanced frameworks analyze computation graphs to automatically choose optimal representations, balancing conversion costs against operation efficiency.
  • ABY3 and Beyond: Extensions to three parties and malicious security settings, maintaining the mixed-protocol approach with stronger guarantees.

Protocol Composition

Complex MPC applications compose multiple protocol components:

  • Preprocessing and Online Phases: Most efficient protocols separate computation into data-independent preprocessing (generating triples, garbled circuits) and fast online execution.
  • Specialized Subprotocols: Custom protocols for specific operations (comparison, equality, maximum) can be integrated with general-purpose frameworks.
  • Security Composition: Care is required to ensure composed protocols maintain security, typically through universal composability frameworks.
  • Performance Modeling: Choosing between protocol options requires understanding of network latency, bandwidth, and computational capabilities of all parties.

Communication Optimization

Communication cost often dominates MPC performance, particularly in wide-area networks. Reducing communication rounds and total bandwidth is essential for practical deployment.

Round Complexity

Minimizing communication rounds reduces latency-induced delays:

  • Constant-Round Protocols: Garbled circuits achieve constant rounds regardless of circuit depth, advantageous over high-latency networks.
  • Depth-Dependent Protocols: Secret sharing protocols typically require rounds proportional to circuit depth, favoring shallow circuits.
  • Round-Optimal Constructions: Theoretical constructions achieve minimal rounds but often with impractical constants or assumptions.
  • Preprocessing Trade-offs: Moving computation to preprocessing can reduce online rounds at the cost of preprocessing complexity.

Bandwidth Reduction

Techniques for reducing total data transmitted:

  • Silent Preprocessing: Generates correlations with sublinear communication using pseudorandom generators and learning with errors assumptions.
  • Function-Dependent Preprocessing: Some protocols allow function-specific preprocessing that reduces online communication.
  • Compression Techniques: Network coding and compression reduce effective bandwidth requirements.
  • Batching and Amortization: Processing multiple inputs together amortizes fixed costs and enables vectorized operations.

Network Topology Considerations

Protocol efficiency depends on network characteristics:

  • Point-to-Point vs. Broadcast: Different protocols assume different communication patterns; some require broadcast channels while others use only point-to-point.
  • Star vs. Full Mesh: Architectures with a central coordinator can reduce total connections but create bottlenecks.
  • Asynchronous Protocols: Protocols tolerating message delays and reordering handle unreliable networks but typically with overhead.
  • Geographic Distribution: Placing computation close to data sources can reduce wide-area communication for distributed datasets.

Real-World Deployments

Secure multi-party computation has moved from academic research to production deployment across multiple industries. Real-world systems balance theoretical security guarantees with practical engineering constraints.

Financial Services Applications

Finance represents one of the most active MPC deployment areas:

  • Inter-Bank Analytics: Banks compute aggregate statistics over combined customer data for fraud detection and risk assessment without sharing individual records.
  • Dark Pools and Private Matching: MPC enables private order matching in financial markets, preventing information leakage about trading intentions.
  • Credit Scoring: Multiple data sources contribute to credit decisions without centralizing sensitive financial data.
  • Regulatory Compliance: MPC enables regulatory reporting and auditing while maintaining customer privacy and competitive confidentiality.
  • Cryptocurrency Custody: Threshold signatures using MPC distribute private key control, eliminating single points of compromise.

Healthcare and Life Sciences

Healthcare applications leverage MPC to enable collaborative research:

  • Multi-Site Clinical Studies: Hospitals analyze combined patient data for clinical research without transferring protected health information.
  • Genomic Analysis: MPC enables collaborative genomic studies across institutions, computing on sensitive genetic data while maintaining patient privacy.
  • Drug Discovery: Pharmaceutical companies can jointly analyze proprietary compound libraries and patient response data.
  • Rare Disease Research: Aggregating data across institutions is essential for studying rare conditions where no single site has sufficient cases.

Technology Industry Deployments

Major technology companies deploy MPC at scale:

  • Private Contact Discovery: Messaging applications use PSI to determine which contacts use the service without uploading full contact lists.
  • Privacy-Preserving Analytics: Aggregate usage statistics are computed without accessing individual user data.
  • Ad Measurement: Advertisers measure campaign effectiveness by computing on combined data from publishers without sharing user-level information.
  • Federated Machine Learning: MPC techniques secure aggregation in federated learning systems, protecting model updates from honest-but-curious servers.

Government and Defense

Government agencies use MPC for sensitive collaborative computation:

  • Intelligence Sharing: Agencies compare information across organizational and national boundaries without revealing sources or methods.
  • Tax and Benefit Administration: Different government databases can be matched for fraud detection without creating centralized records.
  • Census and Statistics: MPC enables detailed statistical analysis while providing differential privacy guarantees.
  • Voting and Elections: MPC-based voting systems can provide verifiable elections without revealing individual votes.

Hardware Acceleration

The computational demands of MPC motivate specialized hardware support, from optimized CPU implementations to custom accelerators.

CPU Optimizations

Modern processors include features beneficial for MPC:

  • AES-NI Instructions: Hardware AES acceleration speeds garbling and other symmetric-key operations by an order of magnitude.
  • SIMD Instructions: Vector instructions enable parallel processing of multiple garbled gates or secret shares.
  • Carry-less Multiplication: CLMUL instructions accelerate polynomial arithmetic in finite fields.
  • SHA Extensions: Hardware SHA support speeds hash-based operations common in OT and commitments.

FPGA and ASIC Acceleration

Custom hardware provides further acceleration:

  • Garbled Circuit Accelerators: FPGAs can generate and evaluate garbled circuits with high throughput, limited primarily by memory bandwidth.
  • OT Extension Hardware: Dedicated OT extension implementations achieve billions of OTs per second.
  • Finite Field Arithmetic: Custom arithmetic units for specific field sizes accelerate secret sharing computations.
  • Network Processing: Hardware offload for protocol message processing reduces CPU overhead.

Trusted Execution Environments

TEEs provide an alternative approach with different trust assumptions:

  • Intel SGX: Enclave-based computation can simplify some MPC scenarios, though with different security assumptions than cryptographic MPC.
  • ARM TrustZone: Provides isolated execution on ARM processors, enabling secure computation on mobile and embedded devices.
  • Hybrid TEE-MPC: Combining TEEs with cryptographic MPC can improve efficiency while maintaining security against some TEE vulnerabilities.

Implementation Considerations

Deploying MPC in production requires careful attention to engineering concerns beyond cryptographic protocol design.

Software Frameworks

Multiple open-source frameworks support MPC development:

  • MP-SPDZ: Comprehensive framework supporting many protocols, security models, and preprocessing approaches.
  • EMP Toolkit: High-performance implementation of garbled circuits and oblivious transfer.
  • ABY/ABY3: Mixed-protocol frameworks supporting multiple sharing types with efficient conversions.
  • Sharemind: Commercial platform with focus on deployment in regulated industries.
  • CrypTen: PyTorch-based framework for privacy-preserving machine learning.

Security Engineering

Secure implementation requires attention to practical security:

  • Side-Channel Resistance: Implementations must avoid timing leaks, cache attacks, and other side channels that could reveal secret data.
  • Randomness Quality: Cryptographic security depends on high-quality random number generation; weak randomness can compromise all guarantees.
  • Input Validation: Malformed inputs can trigger implementation bugs or denial of service; robust parsing is essential.
  • Audit and Verification: Critical deployments require security audits and formal verification of core components.

Deployment Architecture

Production MPC systems require robust operational design:

  • Key Management: Secure generation, storage, and rotation of cryptographic keys across parties.
  • Logging and Monitoring: Auditable logs of protocol executions while maintaining privacy guarantees.
  • Fault Tolerance: Handling party failures, network interruptions, and recovery scenarios.
  • Scalability: Horizontal scaling for high-throughput applications, potentially using multiple parallel protocol instances.

Future Directions

Secure multi-party computation continues to advance on multiple fronts. Research addresses fundamental efficiency improvements, with silent preprocessing and pseudorandom correlation generators dramatically reducing communication requirements. New protocol constructions achieve better trade-offs between security models, round complexity, and computational cost.

The integration of MPC with machine learning drives significant development, with protocols for secure inference and training becoming increasingly practical. Hardware acceleration through custom ASICs and integration with trusted execution environments promises further performance improvements. As privacy regulations tighten and data collaboration becomes more valuable, MPC is positioned to become a fundamental technology for the data economy, enabling computation that would otherwise be impossible due to privacy constraints.