PaperlayerView exact revision on arXiv

Source-linked AI summary

Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning

Harsh Chaudhari, Rahul Rachuri, Ajith Suresh

arXiv:1912.02631v2cs.LGcs.CRstat.ML

TL;DR

PPML needs efficient, privacy-preserving ML computation for sensitive applications, but existing MPC frameworks incur costly world conversions, truncation, and activation operations. The paper introduces Trident, an actively secure four-party mixed-world framework over rings using the offline-online paradigm. Across ML benchmarks, Trident improves throughput over ABY3, including 23 versus 2.5 NN training iterations per second and 10.46 versus 2 for CNNs.

  • Problem

    Existing MPC protocols are not directly suitable for efficient PPML because different computations favor different worlds and truncation or activation operations remain expensive.

  • Method

    Trident combines an actively secure 4PC protocol tolerating one malicious corruption with offline-online mixed-world computations and PPML-specific conversions over Z2^ℓ.

  • Results

    Trident improves ML training throughput over ABY3, reaching 23 NN iterations per second versus 2.5 and 10.46 CNN iterations versus 2 for MNIST with 784 features and batch size 128.

  • Takeaways & Limitations

    The benchmarks support the paper’s conclusion that an additional honest party can improve actively secure ML protocol performance while reducing total server monetary cost.

Abstract

from arXiv · show

Machine learning has started to be deployed in fields such as healthcare and finance, which propelled the need for and growth of privacy-preserving machine learning (PPML). We propose an actively secure four-party protocol (4PC), and a framework for PPML, showcasing its applications on four of the most widely-known machine learning algorithms -- Linear Regression, Logistic Regression, Neural Networks, and Convolutional Neural Networks. Our 4PC protocol tolerating at most one malicious corruption is practically efficient as compared to the existing works. We use the protocol to build an efficient mixed-world framework (Trident) to switch between the Arithmetic, Boolean, and Garbled worlds. Our framework operates in the offline-online paradigm over rings and is instantiated in an outsourced setting for machine learning. Also, we propose conversions especially relevant to privacy-preserving machine learning. The highlights of our framework include using a minimal number of expensive circuits overall as compared to ABY3. This can be seen in our technique for truncation, which does not affect the online cost of multiplication and removes the need for any circuits in the offline phase. Our B2A conversion has an improvement of $\mathbf{7} \times$ in rounds and $\mathbf{18} \times$ in the communication complexity. The practicality of our framework is argued through improvements in the benchmarking of the aforementioned algorithms when compared with ABY3. All the protocols are implemented over a 64-bit ring in both LAN and WAN settings. Our improvements go up to $\mathbf{187} \times$ for the training phase and $\mathbf{158} \times$ for the prediction phase when observed over LAN and WAN.

I. INTRODUCTION

The paper addresses efficiency barriers in actively secure PPML by introducing Trident, a four-party mixed-world framework that leverages an additional honest party. It reports more efficient conversions, truncation, ML building blocks, and benchmarks than ABY3 across training and prediction.

  • Motivation: Healthcare and other mission-critical ML applications require privacy-preserving training and prediction while maintaining high accuracy and robustness.The paper connects these requirements to substantial training computation and data variance across sources.
  • Challenges: Existing PPML frameworks face costly transitions among Arithmetic, Boolean, and Garbled worlds, while truncation and activation functions can require expensive circuits and rounds proportional to ring size.ABY3 also cannot avoid some expensive Ripple Carry Adder operations in truncation and activation functions.
  • Framework: Trident provides an actively secure 4PC framework over Z2^ℓ, tolerating one malicious corruption and using the offline-online paradigm for mixed-world PPML.The framework targets outsourced computation and supports applications to Linear Regression, Logistic Regression, Neural Networks, and CNNs.
  • 4PC Protocol: 25% lower online communication per multiplication and only three active parties during most of the online phase improve outsourced execution compared with the cited 4PC protocol.The protocol uses 3 ring elements online per multiplication rather than 4, without reducing the total cost.
  • Conversions and Truncation: 7× fewer rounds for B2A conversion and elimination of offline Ripple Carry Adders improve mixed-world computation and truncation efficiency over ABY3.Trident’s truncation adds no online multiplication cost, while its ML building blocks improve round and communication complexity.
  • Evaluation: 23 NN iterations per second versus 2.5 for ABY3 and 10.46 CNN iterations versus 2 demonstrate higher LAN training throughput on MNIST with 784 features and batch size 128.The reported benchmarks cover both training and prediction for four ML algorithms over LAN and WAN.

III. OUR 4PC PROTOCOL

The protocol defines several linear secret-sharing schemes and evaluates arithmetic circuits through input sharing, gate evaluation, and output reconstruction. Its multiplication protocol and delayed hash verification achieve the stated communication efficiency while preserving correctness.

  • Sharing Semantics: The protocol uses [·]-, ⟨·⟩-, and J·K-sharing over arithmetic and Boolean rings.[·]-sharing distributes additive shares among P1, P2, and P3; ⟨·⟩-sharing gives each party two shares; J·K-sharing combines a mask with a publicly known masked value for P1, P2, and P3.
  • Sharing Semantics: Linearity lets parties evaluate additions and public-constant multiplications locally without interaction.For public constants c1 and c2, shares of c1x + c2y are computed directly from shares of x and y.
  • Stages of the 4PC Protocol: Input sharing generates J·K-shares, evaluation maintains J·K-shared wire values, and output reconstruction recovers each output.The protocol Π4PC consists of input sharing, topological circuit evaluation, and output reconstruction.
  • Stages of the 4PC Protocol: Multiplication masks products in the offline phase and reconstructs a verified masked intermediate during the online phase.Parties compute shares of γxy = λxλy offline, then use mz = z + λz and reconstruct mz − mxmy before locally obtaining mz.
  • Stages of the 4PC Protocol: Delaying multiplication-gate hash exchange until output reconstruction reduces total communication to 3 ring elements.Corresponding values are appended and hashed collectively rather than exchanged separately for every multiplication gate.
  • Correctness and Communication: Π4PC is correct and uses one-round offline preprocessing plus online communication proportional to inputs, multiplications, and outputs.The online evaluation uses D rounds and amortized communication of 3M ring elements; input and output stages use at most 3I and 3O elements, respectively.

D. Achieving Fairness

The fairness layer prevents selective aborts during reconstruction, while the garbled-world construction supports verified Boolean sharing and cross-checking among garblers and the evaluator.

  • Fair Reconstruction: Fair reconstruction propagates abort decisions so parties do not selectively continue after failed multiplication verification.P1, P2, and P3 report continue or abort to P0, which broadcasts abort if any report indicates failure; the parties then exchange P0’s response.
  • Fair Reconstruction: After the fairness check, parties exchange missing shares together with hashes and abort if the received abort messages form a majority.The reconstruction sends masked values or shares through designated party pairs and uses hashes for consistency checking.
  • The Garbled World: The garbled world uses P1, P2, and P3 as garblers and P0 as the sole evaluator, with hash-based cross-verification.P1 sends the garbled circuit to P0 while P2 sends a hash; P0 may receive its inputs from only P1 and P2.
  • The Garbled World: J·K-sharing represents a masked value whose mask is known to the garblers while P0 holds mask shares and the masked value is shared among the parties.For Boolean values, the scheme uses a global offset and supports bitwise representation for ring elements.
  • The Garbled World: Garbled-world XOR is local, whereas AND uses a garbled table sent by one garbler and hash-checked by another.Sharing can split P0’s input into two parts, generate their garbled sharings, and combine them with free XOR; one component may be offloaded offline.

B. Building Blocks

The framework develops verifiable sharing protocols and conversions among arithmetic, Boolean, and garbled worlds for four-party computation. Its building blocks include vector dot products, bit operations, and cross-world transformations.

  • Verifiable Sharing: The verifiable sharing protocols let parties generate arithmetic/Boolean or garbled shares while checking consistency through hashes and commitments.Arithmetic/Boolean sharing uses a helper for verification, while garbled sharing supports key or hash checks between garblers.
  • Dot Product: The dot product protocol computes z = x ⊙ y with communication independent of vector size by locally aggregating multiplication shares before one exchange.This contrasts with malicious-setting protocols whose cost scales with the vector dimension.
  • Sharing Conversions: The framework provides conversions between garbled, Boolean, and arithmetic sharing using XOR, subtraction, and locally reconstructed shares.Examples include G2B, G2A, B2G, A2G, and A2B conversions, with garbled circuits used where required.
  • Sharing Conversions: B2A represents a ring value as a weighted sum of its bits, converts each bit offline, then locally combines arithmetic shares after online verification and sharing.The value representation is v = Σ 2^i · v_i over Z2^ℓ.
  • Bit Injection: Bit injection computes Jb · vK from Boolean and arithmetic shares using a ring identity, followed by local share combination after verification.The protocol uses the identity b · v = x0 − x1y1 + x2y2 + x3y3.

V. PRIVACY PRESERVING MACHINE LEARNING

Privacy-preserving machine learning requires representing decimal intermediate values and efficiently instantiating truncation, secure comparison, and nonlinear activation functions. Trident addresses these components over a ring-based representation.

  • Representation: Decimal intermediate values are represented using signed two’s complement over Z2^ℓ, with the most significant bit indicating sign and the remaining d bits representing the fractional part.This representation is used for privacy-preserving machine-learning computations.
  • Core Components: The framework identifies share truncation, secure comparison, and nonlinear activation functions as three components requiring efficient privacy-preserving instantiations.These components support fixed-point arithmetic and activation operations in machine-learning protocols.

A. Share Truncation

Trident’s truncation protocol precomputes a random value and its truncated form, then opens a masked value to obtain the truncated result. It avoids Boolean circuits in the offline phase.

  • Design: Trident improves on ABY3 truncation by using no Boolean circuits, reducing offline round complexity to a constant.The underlying value is preserved with very high probability, as in the motivating ABY3 approach.
  • Offline Phase: The offline phase generates random r and its truncated value r_t, while parties verify the relation r = 2^d r_t + r_d.Here r_d denotes the last d bits of r.
  • Online Phase: The protocol obtains the truncated value of z by opening and truncating z − r, then adding the result to the precomputed r_t.P0 generates the truncated share, and the other parties check its correctness because P0 cannot be trusted alone.

B. Secure Comparison

Trident instantiates secure comparison and nonlinear activations for machine learning, then benchmarks training across regression, neural-network, and convolutional models against malicious ABY3 in LAN and WAN settings.

  • Secure Comparison: Secure comparison checks x < y by computing x − y and extracting its sign bit from the most significant position.The Bit Extraction protocol outputs Boolean shares of that sign bit from arithmetic shares.
  • Activation Functions: ReLU is implemented by extracting the sign bit, complementing it, and injecting the resulting bit into the arithmetic share of v.This realizes relu(v) = max(0, v) and also supports its derivative.
  • Activation Functions: The sigmoid protocol uses two extracted comparison bits and requires an additional bit extraction, bit multiplication, and bit injection beyond ReLU.The protocol uses the paper’s stated approximation of the sigmoid function.
  • Benchmarking: 4.88× to 251.84× LAN and 2× to 2.83× WAN improvements are reported for linear regression over malicious ABY3.The gains are attributed to feature-independent dot-product communication and truncation reducing online communication from 12 elements to 3.
  • Benchmarking: 5.95× to 67.88× LAN and 2.71× to 2.96× WAN improvements are reported for logistic regression, with sigmoid rounds reduced to constant complexity.For Z2^64, communication is reduced by approximately 80%, from 81 elements to roughly 16.

B. Secure Prediction

Secure prediction benchmarks compare Trident with malicious ABY3 using online latency and throughput across four machine-learning models in LAN and WAN settings. Trident reports substantial gains, while WAN throughput for simpler models is constrained by limited parallel CPU threads and bandwidth utilization.

  • Evaluation setting: 93%–98.3% prediction accuracy was obtained across linear regression through CNN models on MNIST.The benchmark uses 784 features and batch sizes of 1 and 100; truncation has the same least-significant-bit error as ABY3 and SecureML.
  • Online latency: 3×–126× improvement was reported for Linear Regression, 3×–19.48× for Logistic Regression, 3.05×–74.85× for NN, and 2.71×–68.82× for CNN.These ranges combine LAN and WAN online-latency comparisons against ABY3.
  • Truncation: Trident’s truncation avoids ABY3’s 128-round Ripple Carry Adder circuits, yielding approximately 15× lower communication and 64× fewer rounds.The approach also removes the corresponding offline circuit cost.
  • Throughput: Online throughput is measured as predictions per second over LAN and predictions per minute over WAN using 32 threads across four CPU cores.Each thread handles 100 simultaneous queries without reduced performance.
  • WAN caveat: WAN throughput gains are limited for Linear and Logistic Regression because only 32 CPU threads can run in parallel, leaving bandwidth underutilized.Linear and Logistic Regression reach maximum bandwidth utilization around 1.5 Mbps, whereas NN and CNN use the full bandwidth even at 40 Mbps.
  • Overall consequence: The framework’s additional honest party is associated with improved ML performance and reduced server hiring costs.The conclusion presents this as the overall practical consequence of the framework.

APPENDIX A BUILDING BLOCKS

Appendix A specifies Trident’s four-party building blocks, their communication costs, and the setup mechanisms used to generate sharings and verify protocol values. The protocols separate offline preprocessing from online interaction and provide explicit amortized round and communication bounds.

  • Shared Key Setup: The shared-key setup defines pairwise, three-party, and all-party PRF keys for the four participants.The ideal functionality samples these keys and distributes each party’s corresponding key tuple.
  • Generating Zero Share: ΠZero generates a sharing of zero among P1, P2, and P3, while P0 receives all three component values.The shares A, B, and Γ satisfy A + B + Γ = 0.
  • Arithmetic sharing: ΠSh is noninteractive offline and requires 1 online round with amortized communication of 3ℓ bits.Offline sampling uses the shared-key setup, while online values and hashes are exchanged and amortized across instances.
  • Sharing and reconstruction: ΠaSh requires 1 offline round and 2ℓ amortized communication bits, while ΠRec requires 1 online round and 4ℓ amortized communication bits.The costs arise from distributing and reconstructing missing shares with consistency hashes.
  • Multiplication: ΠMult uses 1 offline round with 3ℓ amortized communication bits and 1 online round with 3ℓ amortized communication bits.The same building-block structure supports multiplication-related sharing and verification.
  • Four-party protocol: Π4PC requires 1 offline round with 3M ring elements and an online input-sharing round, D evaluation rounds, and an output-reconstruction round.The online communication is at most 3I ring elements for input sharing, 3M for evaluation, and 3O elements for reconstruction.

B. Sharing Conversions

Trident’s sharing conversions connect arithmetic, Boolean, and garbled representations with explicit offline-online costs. The framework also provides truncation and bit-extension protocols while reducing or removing expensive circuit use in key operations.

  • Garbled and Boolean conversions: G2B and B2G each require 1 round in both offline and online phases, with G2B costing κ + 1 + |Decode| offline and 3 bits online, and B2G costing κ bits in each phase.These conversions use garbled sharing and decoding information as specified by their protocols.
  • Arithmetic-to-garbled conversion: A2G requires 1 online round and ℓκ online communication, while its offline communication includes ℓκ + |Sub| bits.The conversion is treated as ℓ instances of B2G plus a garbled subtractor circuit.
  • Arithmetic-to-Boolean conversion: A2B requires 1 + log ℓ online rounds and 3ℓlog ℓ + ℓ online communication bits.Its offline cost is 1 round with 3ℓlog ℓ + 2ℓ bits, including a Boolean subtractor circuit.
  • Bit and arithmetic conversions: Bit2A requires 2 offline rounds with 3ℓ + 1 bits and 1 online round with 3ℓ bits, while B2A requires 2 offline rounds with 3ℓ^2 + ℓ bits and 1 online round with 3ℓ bits.B2A applies Bit2A across ℓ instances in the offline phase.
  • Truncation: ΠMultTr requires 2 offline rounds with 6ℓ bits and 1 online round with 3ℓ bits, while detecting incorrect offline sharing by aborting honest evaluators.The offline phase combines multiplication preprocessing with truncated-value sharing and verification.
  • Bit extension: ΠBitExt requires 1 offline round with 4ℓ + 1 bits and 3 online rounds with 5ℓ + 2 bits.The protocol’s displayed construction is accompanied by these communication bounds.

APPENDIX E BENCHMARKING

Appendix E evaluates Trident’s practical efficiency through runtime and monetary-cost comparisons with ABY3 and another 4PC protocol. The benchmarks indicate lower malicious-case runtime and enable shutting down one server during most online evaluation.

  • Cost metric: Monetary cost combines each server’s total running time with the hiring cost determined by server computing power.The comparison therefore accounts for computation as well as communication.
  • Practical implication: The authors argue that lower runtime balances computation and communication to reduce total monetary cost relative to competing protocols.The conclusion links the additional honest party to improved performance and lower server-hiring cost.
  • 4PC activity: P0 need not remain active during online evaluation except for sharing and reconstruction, allowing its server to be shut down during the evaluation phase.This behavior is highlighted in the AES-128 comparison with Gordon et al.
  • ABY3 comparison: Despite using four servers instead of ABY3’s three, Trident has lower total runtime than malicious ABY3 for every evaluated training and prediction algorithm.The benchmarks use batch size 128 for training and 784 features for both training and prediction.

B. Comparison with the ML framework of ABY3 [6] in the semi-honest setting

The framework matches ABY3 for linear regression and increasingly outperforms it on more complex algorithms, especially in online training and prediction. Comparisons use online iterations per second for training, and runtime and throughput for prediction.

  • Linear regression has the same performance as ABY3S because the additional hash cost is amortized.
  • The performance gap increasingly favors this framework as the protocols become more complex.
  • Efficient bit extraction, bit injection, and Bit2A protocols drive the advantage over ABY3S for the other three algorithms.
  • The framework is less efficient than ABY3 in the offline phase but substantially more efficient online for both training and prediction.
  • Online training is compared using iterations per second, while prediction is compared using runtime and queries processed per second.

APPENDIX F SECURITY OF OUR CONSTRUCTIONS

The appendix establishes security for the four-party protocol in the {Fsetup, FZero}-hybrid model using real-world/ideal-world simulation. It treats corruption of P0 and P1 explicitly, with the other evaluator cases handled symmetrically.

  • The proof operates in the {Fsetup, FZero}-hybrid model using the real-world/ideal-world paradigm.
  • The security proof shows that Π4PC securely realizes F4PC against a static malicious adversary corrupting P0.
  • For corrupt P0, the simulator handles the only communication to P0 during online output reconstruction using the function output and circuit-output masks.
  • The cases of corrupt P2 and P3 are treated symmetrically to the explicitly considered evaluator-corruption case.
  • The security proof also shows secure realization against a static malicious adversary corrupting P1.
  • For corrupt P1, the simulator emulates the honest parties and simulates each protocol step before producing the adversary’s output.

A. Security Proof in Detail

This section gives simulation-based security proofs for the sharing, reconstruction, multiplication, dot-product, conversion, truncation, and secure-comparison constructions. The simulators emulate setup, extract or compute required values, check consistency, and reproduce outputs or aborts.

  • The proofs use the real-world/ideal-world paradigm, with simulators acting as honest parties and setting an abort flag when an honest party aborts.
  • Circuit Simulation: For a circuit, the simulator sets honest inputs to 0, extracts the adversary’s input, and computes intermediate values and the circuit output for simulation.
  • Sharing Protocol: The sharing protocol ΠSh is specified through an ideal functionality and simulators for corruption of P0 and P1.
  • Verifiable Arithmetic/Boolean Sharing: The verifiable sharing functionality compares received values, outputs ⊥ on mismatch, and otherwise creates masked arithmetic shares.
  • Reconstruction Protocol: The reconstruction functionality checks shares, reconstructs v as mv − λv,1 − λv,2 − λv,3, and sends ⊥ when its conditions fail.
  • Multiplication: Multiplication and multiplication-with-truncation compute masked products, with truncation producing zt = (xy)t and freshly masked output shares.
  • Secure Comparison: Bit extraction receives an arithmetic share and supports secure comparison through an ideal functionality and corruption-case simulators.
Loading 1912.02631v2…