PaperlayerView exact revision on arXiv

Source-linked AI summary

ASTRA: High Throughput 3PC over Rings with Application to Secure Prediction

Harsh Chaudhari, Ashish Choudhury, Arpita Patra, Ajith Suresh

arXiv:1912.02592v1cs.CRcs.LG

TL;DR

ASTRA addresses the concrete-efficiency challenges of 3PC over rings with one corruption, motivated by ring computation’s fit to real-world architectures. It presents efficient semi-honest and malicious protocols and applies them to secure prediction, with theoretical improvements backed by extensive benchmarking.

  • Problem

    Existing 3PC protocols either lack efficient ring support or rely on slower large-field computation, motivating more concrete-efficient input-dependent computation over rings.

  • Method

    The paper develops 3PC protocols tolerating one corruption and applies them to linear regression, linear SVM regression, logistic regression, and linear SVM classification.

  • Results

    The protocols improve on state-of-the-art constructions in theory and extensive benchmarking, including 2.25× lower malicious online communication and better secure-prediction performance than existing constructions.

  • Takeaways & Limitations

    The constructions provide efficient ring-based 3PC and secure prediction for multiple regression and classification functions in semi-honest and malicious settings.

  • Takeaways & Limitations

    The techniques are tailored to 3PC with one corruption and extending them to arbitrary Q(2) adversary structures remains open.

Abstract

from arXiv · show

The concrete efficiency of secure computation has been the focus of many recent works. In this work, we present concretely-efficient protocols for secure $3$-party computation (3PC) over a ring of integers modulo $2^{\ell}$ tolerating one corruption, both with semi-honest and malicious security. Owing to the fact that computation over ring emulates computation over the real-world system architectures, secure computation over ring has gained momentum of late. Cast in the offline-online paradigm, our constructions present the most efficient online phase in concrete terms. In the semi-honest setting, our protocol requires communication of $2$ ring elements per multiplication gate during the {\it online} phase, attaining a per-party cost of {\em less than one element}. This is achieved for the first time in the regime of 3PC. In the {\it malicious} setting, our protocol requires communication of $4$ elements per multiplication gate during the online phase, beating the state-of-the-art protocol by $5$ elements. Realized with both the security notions of selective abort and fairness, the malicious protocol with fairness involves slightly more communication than its counterpart with abort security for the output gates {\em alone}. We apply our techniques from $3$PC in the regime of secure server-aided machine-learning (ML) inference for a range of prediction functions-- linear regression, linear SVM regression, logistic regression, and linear SVM classification. Our setting considers a model-owner with trained model parameters and a client with a query, with the latter willing to learn the prediction of her query based on the model parameters of the former. The inputs and computation are outsourced to a set of three non-colluding servers. Our constructions catering to both semi-honest and the malicious world, invariably perform better than the existing constructions.

1 INTRODUCTION

ASTRA targets concrete efficiency in three-party secure computation over rings, focusing on faster online phases and secure prediction. Its protocols reduce online communication and improve throughput for 3PC and several machine-learning inference tasks.

  • Motivation: The offline-online design shifts input-independent work earlier so repeated computations can have fast input-dependent online phases.The offline phase generates reusable raw material for online computation.
  • Motivation: 3PC over rings targets practical computation matching 32- and 64-bit system architectures, avoiding slower field-based computation.Ring computation models CPU-word arithmetic, while field libraries can be 10×-100× slower than real-world system architectures.
  • 3PC protocols: 2 online ring elements per multiplication give each semi-honest party less than one element, achieved for the first time in 3PC.The protocol uses asymmetric sharing so only two parties communicate for online multiplication while the third party is handled offline.
  • 3PC protocols: 4 online elements per multiplication improve on the 9-element state of the art for malicious 3PC, while fairness adds cost only at output reconstruction.The fair reconstruction uses proof of origin rather than a broadcast channel.
  • Secure prediction: Secure prediction covers linear regression, linear SVM regression, logistic regression, and linear SVM classification in a three-server outsourced setting.The protocols use secure comparison for classification and achieve constant-round classification online computation unlike ABY3's log ℓ+1 rounds.
  • Evaluation: 1.05×-1.51× higher 3PC online throughput and 1.02×-2.93× higher secure-prediction throughput are reported across tested settings.For WAN 3PC, the improvement corresponds to 1.44-4.39 million additional AND gates per second; prediction gains span regression and classification.

2 PRELIMINARIES AND DEFINITIONS

The protocols model three parties over a synchronous network with private authenticated channels, assigning one party to preprocessing and two to online evaluation. They use arithmetic or Boolean rings and pre-shared PRF keys for efficient randomness generation.

  • System model: Three parties communicate over pairwise private, authentic channels in a synchronous network while evaluating a public circuit over Z2^ℓ.The circuit contains two-input addition and multiplication gates, with multiplicative depth and gate counts explicitly defined.
  • System model: P0 acts as a distributor during preprocessing, while P1 and P2 evaluate the circuit online.Superscripts distinguish semi-honest and malicious protocols, and Boolean-ring variants replace addition and multiplication with XOR and AND.
  • Shared-key setup: A one-time setup establishes pairwise and all-party PRF keys to reduce communication during protocol execution.The keys are shared by each party pair and jointly by all parties.
  • Shared-key setup: Parties sample shared randomness non-interactively by evaluating the PRF with locally advanced counters.The setup is modeled by Fsetup and can be realized using any secure MPC protocol.

3 SHARING SEMANTICS

ASTRA uses two secret-sharing variants over arithmetic and Boolean rings: two-party additive sharing and a three-party asymmetric sharing scheme. Their linearity lets parties evaluate affine operations locally.

  • Sharing variants: Both sharing variants operate over arithmetic Z2^ℓ and Boolean Z2^1 rings.The schemes provide the sharing semantics used throughout the protocols.
  • [·]-sharing: [·]-sharing splits v between P1 and P2 as v = v1 + v2.Each evaluator holds one additive share of the value.
  • ⟦·⟧-sharing: ⟦·⟧-sharing represents v as m_v − λ_v, with P0 holding two λ shares and each evaluator holding m_v plus one λ share.The representation is distributed asymmetrically across the distributor and evaluators.
  • Linearity: Linearity lets parties locally compute shared c1x + c2y from shared x and y and public constants.The property extends to both [·]-sharing and ⟦·⟧-sharing, supporting local addition and multiplication by public constants.

4 OUR 3PC PROTOCOL

The paper presents semi-honest and malicious 3PC protocols over Z2^ℓ using offline-online computation, with specialized sharing, multiplication, consistency, and reconstruction procedures. The malicious construction adds product-relation checks and hashing while preserving low online communication and latency.

  • 4.1 3PC with semi-honest security: The semi-honest protocol evaluates additions locally and computes multiplication outputs online through the evaluators after preprocessing output masks.Input sharing, circuit evaluation, and output reconstruction are organized across offline and online phases.
  • 4.2 3PC with malicious security: The malicious protocol addresses distinct attacks against the designated party and evaluators by checking product relations of a shared multiplication triple.The construction uses padded masked values for evaluator checks and reduces product-relation checking to two instances of the malicious multiplication protocol.
  • 4.2 3PC with malicious security: The malicious protocol detects inconsistent or incorrect values and makes honest parties output ⊥ under the described corruption scenarios.The checks cover corrupted preprocessing by the designated party and incorrect evaluator behavior during online reconstruction.
  • 4.2 3PC with malicious security: Fair reconstruction replaces the abort-oriented reconstruction protocol, requiring four rounds and amortized online communication of at most 2 commitments and 6 openings.The fair reconstruction protocol requires four offline commitments in amortized communication.

5 PRIVACY PRESERVING MACHINE LEARNING

The paper applies its 3PC techniques to secure server-aided ML prediction, outsourcing shared inputs to three non-colluding servers. It develops efficient protocols for dot products, comparisons, and four regression or classification functions.

  • 5 PRIVACY PRESERVING MACHINE LEARNING: The protocols support linear regression, logistic regression, linear SVM regression, and linear SVM classification for outsourced prediction.A model-owner supplies trained parameters, while a client supplies a query; three non-colluding servers compute on shared inputs.
  • 5 PRIVACY PRESERVING MACHINE LEARNING: A 64-bit fixed-point representation uses 13 fractional bits and 50 integral bits for values in Z_2^64.Products expand the fractional precision to 26 bits while retaining 37 bits for the integer part.
  • 5 PRIVACY PRESERVING MACHINE LEARNING: The semi-honest dot-product protocol reduces communication to one ring element offline and two ring elements online, independent of vector dimension.It shares the aggregate product of masks offline and reconstructs the aggregate product online rather than each component separately.
  • 5 PRIVACY PRESERVING MACHINE LEARNING: The malicious dot-product protocol communicates 21d ring elements offline and 2d + 2 ring elements online.The online optimization combines component products and verifies the aggregate with hashes.
  • 5 PRIVACY PRESERVING MACHINE LEARNING: Secure comparison reduces checking u < v to extracting the most significant bit of the shared difference a = u − v.The semi-honest protocol masks a with a random value, reconstructs the masked value to one party, and recovers sign(a) by XORing sign bits.
  • 5 PRIVACY PRESERVING MACHINE LEARNING: BitExt uses 2ℓ + 2 online bits in the semi-honest setting and 6ℓ + 1 online bits in the malicious setting.The corresponding protocols require two and three online rounds, respectively.

6 IMPLEMENTATION AND BENCHMARKING

The evaluation benchmarks 3PC and secure-prediction protocols across LAN and WAN settings, comparing latency, communication, and online throughput. Across these experiments, the proposed protocols generally improve throughput and, in several settings, latency relative to competitors.

  • 6.1.1 Results for 3PC.: WAN online latency improves because the protocol can assign the highest-communication party pair to the pair with the lowest round-trip time.The resulting time per round can gain a factor of (maximum rtt)/(minimum rtt) over existing protocols.
  • 6.1.1 Results for 3PC.: Online latency benefits become more visible as multiplicative depth increases because depth determines the number of communication rounds.Figure 14 compares online latency against multiplicative depth for the proposed protocols and competitors.
  • 6.1.1 Results for 3PC.: The proposed 3PC protocol achieves clearly higher online throughput than its competitors in both LAN and WAN benchmarks.The comparison uses AES circuits over LAN and AND gates over WAN; the table reports the throughput results.
  • 6.1.1 Results for 3PC.: A 2.25× reduction in malicious online communication is accompanied by a 1.75× increase in offline communication relative to state-of-the-art protocols.In the semi-honest setting, about 33% of total communication is shifted to the offline phase.
  • 6.1.2 Results for Secure Prediction.: For secure prediction, the malicious regression protocols improve online communication by 4.5× relative to ABY3, boosting throughput.Regression throughput is reported in queries per second for LAN and queries per minute for WAN.
  • 6.1.2 Results for Secure Prediction.: The proposed classification protocol outperforms ABY3 across all tested settings, with the advantage attributed to improved communication and online rounds.For regression, throughput decreases as feature size increases for both protocols, while the proposed protocol remains ahead.

7 CONCLUSIONS

The paper concludes with efficient 3PC protocols tolerating one corruption, applies them to secure machine-learning prediction, and supports the theoretical improvements with extensive benchmarking.

  • The protocols target three-party computation tolerating at most one corruption and support secure prediction for four linear or classification functions.The applications cover Linear Regression, Linear SVM Regression, Logistic Regression, and Linear SVM classification.
  • Extensive benchmarking backs the theoretical improvements over state-of-the-art protocols.
  • The paper leaves extending its techniques beyond the 3PC, one-corruption setting to an arbitrary Q(2) adversary structure as an open problem.

A.1 Instantiating Ftrip

The protocol Πtrip generates private multiplication triples over Z2^ℓ by optimistic generation, cut-and-choose checking, and bucket-based verification, with a later modification postponing verification through shuffling.

  • Πtrip generates N independent random and private multiplication triples over Z2^ℓ in one batch.
  • The protocol opens C triples, randomly buckets the remaining triples, and verifies one candidate per bucket using the others without opening it.
  • Except with error probability at most 1/(N B^(B−1)), an invalid output triple causes the honest parties to abort.
  • A modification postpones offline verification until after multiplication evaluation and randomly shuffles triples before matching them to pending checks.
  • Excluding permutation generation, one triple costs 2B instances of Πrand, B instances of ΠsMul, and B−1 instances of Πprc amortized.

A.2 Properties of Πprc

Πprc detects incorrect multiplication triples through a reconstructed check value while preserving the privacy of the checked inputs.

  • If c differs from ab by a nonzero Δ, every honest party outputs ⊥.
  • Correctness reduces to showing that τ = 0 if and only if Δ = 0.
  • The values ρ and σ reveal nothing about a and b because d and e are random and private, while τ equals Δ independently of a, b, and c.

B 3PC WITH SEMI-HONEST SECURITY

The semi-honest construction securely realizes arithmetic-circuit evaluation over Z2^ℓ in the Fsetup-hybrid model, with simulators covering each possible single-party corruption case.

  • The protocol securely realizes F3pc for arithmetic circuits over Z2^ℓ in the Fsetup-hybrid model.
  • For a corrupt P0, the online circuit evaluation is performed by P1 and P2, whose exchanged messages P0 does not see.
  • For a corrupt P0, the simulator can generate the adversary’s view from the function output and output-wire masks because P0 communicates only during output reconstruction.
  • The simulated and real-world adversary views are computationally indistinguishable for the considered corruption cases.
  • For a corrupt evaluator, the simulator performs honest preprocessing for P0, simulates circuit evaluation with other inputs set to zero, and adjusts output shares to reproduce the function output.

C 3PC WITH MALICIOUS SECURITY

The malicious-security construction securely realizes the intended 3PC functionality against a static adversary corrupting one party. Its proof uses simulators for different corruption cases, with abort behavior represented through an ideal functionality.

  • 3pc securely realizes the standard ideal-world functionality against a static, malicious adversary corrupting one party.
  • The proof establishes security in the {Fsetup, Ftrip}-hybrid model for arithmetic circuits over Z2^ℓ with selective abort.
  • For a corrupted P0, the simulator learns setup keys and masks, extracts masked inputs, and simulates online messages while tracking an abort flag.
  • The simulation concludes by showing that the simulated and real views of the corrupted party are computationally indistinguishable.
  • For a corrupted evaluator, the simulator plays the honest parties, checks message consistency, and sends ⊥ to the abort functionality when a check fails.

D SECURE PREDICTION

The secure-prediction construction uses its multiplication protocol to generate and reconstruct prediction-related values while tolerating aborts. The correctness argument shows that honest parties either obtain the intended values or output ⊥.

  • During the offline phase, honest parties compute r = r1r2 or output ⊥, and during the online phase they obtain sign(ra) or output ⊥.
  • The offline sharing assignments for r1 and r2 generate valid sharings, so multiplication yields r1r2 or ⊥.
  • Online multiplication correctly produces a sharing of ra or ⊥, while reconstruction lets the relevant parties obtain ra or abort under one corruption.
Loading 1912.02592v1…