PaperlayerView exact revision on arXiv

Source-linked AI summary

Conclave: secure multi-party computation on big data (extended TR)

Nikolaj Volgushev, Malte Schwarzkopf, Ben Getchell, Mayank Varia, Andrei Lapets, Azer Bestavros

arXiv:1902.06288v1cs.CR

TL;DR

MPC enables joint computation over private data, but poor scaling makes large relational analytics impractical. Conclave compiles queries into local cleartext processing and smaller MPC steps, adding hybrid protocols when partial trust permits. It scales to inputs several orders of magnitude beyond standalone MPC frameworks and outperforms SMCQL, with limitations in threat models, supported backends, and large-scale resources.

  • Problem

    Existing MPC algorithms and frameworks scale poorly with data size, limiting practical joint analytics over large private data sets.

  • Method

    Conclave analyzes and rewrites relational queries into local cleartext processing, secure MPC steps, and optional hybrid protocols using coarse-grained data annotations.

  • Results

    Conclave scales queries to inputs orders of magnitude larger than existing MPC frameworks support alone, while annotated hybrid protocols speed joins and aggregations by 7× or more versus Sharemind.

  • Takeaways & Limitations

    Conclave makes secure analytics on big data accessible through generated code that combines scalable local processing with secure MPC backends.

  • Takeaways & Limitations

    The prototype defends only against passive adversaries, supports only Obliv-C and Sharemind, and lacked resources to evaluate the full larger SMCQL data set.

Abstract

from arXiv · show

Secure Multi-Party Computation (MPC) allows mutually distrusting parties to run joint computations without revealing private data. Current MPC algorithms scale poorly with data size, which makes MPC on "big data" prohibitively slow and inhibits its practical use. Many relational analytics queries can maintain MPC's end-to-end security guarantee without using cryptographic MPC techniques for all operations. Conclave is a query compiler that accelerates such queries by transforming them into a combination of data-parallel, local cleartext processing and small MPC steps. When parties trust others with specific subsets of the data, Conclave applies new hybrid MPC-cleartext protocols to run additional steps outside of MPC and improve scalability further. Our Conclave prototype generates code for cleartext processing in Python and Spark, and for secure MPC using the Sharemind and Obliv-C frameworks. Conclave scales to data sets between three and six orders of magnitude larger than state-of-the-art MPC frameworks support on their own. Thanks to its hybrid protocols, Conclave also substantially outperforms SMCQL, the most similar existing system.

1 Introduction

Conclave addresses the poor scalability and accessibility of MPC for large private relational analytics by compiling queries into local cleartext processing and smaller secure MPC steps. Its hybrid protocols and generated code substantially improve scalability while preserving security guarantees under passive adversaries.

  • Motivation: Conclave targets joint analytics over private data sets, which existing systems cannot efficiently combine because sharing is restricted by law and privacy concerns.Such analytics could support illness measurement, systemic-risk assessment, and antitrust analysis without revealing private inputs.
  • Approach: Conclave compiles relational queries into efficient local processing and secure MPC steps, enabling near-interactive responses on inputs several orders of magnitude larger than existing systems support.Analysts write queries as though they could access all parties’ data in cleartext.
  • Approach: Its query analysis and transformations reduce the MPC workload while preserving security guarantees, and optional coarse-grained annotations enable hybrid cleartext–MPC protocols for joins and grouped aggregations.These transformations may shift additional local work to individual parties.
  • Implementation: Conclave generates code combining Python and Spark processing with Sharemind and Obliv-C secure computation backends.This combines scalable data-parallel systems with secure but slower cross-party MPC systems.
  • Results: With minimal annotations and basic optimizations, Conclave scales queries to inputs orders of magnitude larger than existing MPC frameworks support alone.With specific input-column annotations, its hybrid protocols speed joins and aggregations by 7× or more versus Sharemind.
  • Limitations: Conclave’s prototype defends only against passive adversaries and supports only Obliv-C and Sharemind, limiting MPC steps to two or three parties.The authors state that stronger threat models are compatible with the approach and that adding further frameworks requires modest effort.

2 Motivation and background

MPC provides privacy-preserving joint computation, but current techniques scale poorly for large relational data, especially for joins and aggregations. This motivates Conclave’s strategy of limiting cryptographic MPC to the portions of queries that require it while using scalable local processing elsewhere.

  • MPC background: MPC lets parties jointly compute over private data without a trusted party while protecting inputs and intermediate data beyond what the final output reveals.The paper discusses applications including tax-fraud detection, auctions, employment analysis, and gender-pay-gap evaluation.
  • Applications: Large-data MPC could support applications such as jointly measuring health outcomes, estimating geographic credit scores, and assessing market concentration without exposing private records.These applications involve parties holding complementary sensitive data.
  • Scalability: Existing MPC frameworks scale poorly for aggregations and joins, unlike Spark, which runs common relational operators on tens of millions of records in seconds.The comparison uses a log-scale record-count axis and contrasts secure frameworks with plaintext Spark execution.
  • Security models: MPC performance depends on the adversary model: passive security is cheaper than active security, while computational-assumption techniques can work with a single honest party.The paper focuses on scaling to large data with a fixed, small number of parties.
  • MPC techniques: Garbled circuits encode bit-level computation, whereas secret sharing splits integer inputs among parties so additions are local and multiplications require interaction.These are the two dominant MPC techniques discussed in the paper.
  • Scalability: Sharemind takes 200s to sort 16,000 elements, while DJoin takes an hour to join 15,000 records; joins and aggregations are especially consequential because they occur in over 60% and over 34% of privacy-sensitive queries, respectively.These results motivate avoiding cryptographic MPC unless it is necessary.

3 Conclave overview

Conclave minimizes computation under MPC while preserving the backend’s security guarantees, and optionally uses explicitly authorized cleartext processing by a selectively trusted party for better performance. Its security scope remains tied to semi-honest execution, backend tolerances, and assumptions about information leakage from rewritten data sizes.

  • Security-preserving computation placement: Conclave moves operations outside MPC when local inputs, public data, or reversible operations suffice without compromising end-to-end security.The compiler seeks to do as little as possible under MPC while retaining the backend’s guarantees.
  • Security model: Conclave supports semi-honest security and assumes parties faithfully execute the protocol and submit valid inputs.Malicious-adversary security is discussed only as a possible extension.
  • Security model: Conclave inherits its MPC backend’s security guarantees and collusion threshold while hiding private data and metadata such as value frequencies.The compiler generates code for external MPC systems and must uphold their guarantees.
  • Information leakage: Rewrites are safe when new MPC input sizes are data-independent; data-dependent sizes may leak information after operations move outside MPC.The supplied passage states the risk but does not include the complete boundary for data-dependent rewrites.
  • Hybrid protocols: Hybrid protocols let an explicitly authorized selectively trusted party process selected data in cleartext, trading some security for better performance.Only one selectively trusted party can assist an execution, and the rewrite must be authorized by input annotations.

4 Specifying Conclave queries

Conclave lets analysts specify distributed relational queries declaratively, while the compiler tracks data locations and trust annotations to generate an execution DAG across local and MPC backends. This abstracts away much of the distribution and security bookkeeping required by lower-level MPC languages.

  • Query compilation: Conclave compiles relational queries into executable directed acyclic graphs of operators that run on one or more backend systems.Its rewrite rules must preserve MPC security guarantees, unlike ordinary plaintext-only query compilers.
  • Query specification: Conclave accepts queries that compile to operator DAGs and supports SQL- or LINQ-style relational specifications.Listings use a DryadLINQ-like language, and compound relations can be formed by concatenating per-party inputs.
  • Query specification: Analysts write queries as if all parties’ data were in one trusted database, while input relations identify their storing parties through owner annotations.The owner information helps Conclave locate data and determine where operations combine inputs.
  • Interface design: Conclave’s declarative interface avoids the fine-grained intermediate-variable security annotations commonly required by Turing-complete MPC frameworks.This makes the query interface closer to relational analytics systems than to low-level MPC programming.
  • Trust annotations: Optional trust annotations identify parties authorized to learn particular input columns in cleartext for more efficient processing.The annotations are coarse-grained and can reflect column-level differences in sensitivity.

5 Query compilation

Conclave compiles relational queries by automatically identifying which operators require MPC, moving eligible work into local cleartext processing, and inserting hybrid protocols where partial trust permits. These transformations reduce MPC work while preserving security subject to explicitly authorized leakage.

  • Query analysis and trust propagation: Conclave propagates ownership and column-level trust through the query DAG to determine which operators and intermediate columns can be processed outside MPC.A column is trusted only when a party has enough authorized input data to derive it in cleartext; trust sets propagate through operator dependencies.
  • Reducing oblivious operations: Conclave favors extra local work when it reduces expensive oblivious computation, including repeated local joins or redundant sorting that can improve execution time.The system uses data-parallel local processing and hybrid operators to reduce the amount of computation performed under MPC.
  • Security: The compiler’s trust propagation maintains an invariant that a column is revealed only to a party authorized to derive it from input columns.The appendix states that hybrid operators preserve simulation-based MPC security modulo their specified leakage.
  • Query rewriting: The compiler rewrites an initially all-MPC plan into local operators surrounding a smaller MPC clique, pushing the MPC frontier down and pulling reversible work upward.The resulting plan can include local preprocessing, cleartext operators at roots and leaves, and fewer operators under MPC.
  • Security: Push-down transformations may reveal data-dependent MPC input lengths, so Conclave requires party consent when rewritten cardinalities depend on private data.The formal security result identifies leaked input-length information as the only security implication of changing the MPC frontier.
  • Hybrid operators: Conclave uses hybrid protocols to perform selected join and aggregation work in cleartext at a selectively trusted party, then reconstruct results with MPC operations.For hybrid joins, parties shuffle inputs, reveal authorized key columns, perform enumeration and joining at the STP, and use oblivious indexing under MPC to recover joined rows.

6 Implementation

Conclave is implemented as a query compiler with cleartext and MPC backends, supporting core relational analytics operations. Its current operator support covers many practical queries and standard MPC algorithms for joins and aggregations.

  • Prototype architecture: The prototype integrates Python and Spark as cleartext backends with Sharemind and Obliv-C as MPC backends.The implementation comprises 8,000 lines of Python, and its generic interfaces allow other backends to be added with modest effort.
  • Query support: Conclave supports table schemas, joins, aggregates, projections, filters, enumeration, and arithmetic on columns and scalars.This query support appears sufficient to express 88% of 8M sensitive realworld queries at Uber.
  • MPC operators: The implementation includes the same standard Cartesian-product join and aggregation MPC algorithms in both Sharemind and Obliv-C.These algorithms provide the MPC backends for the supported join and aggregation operators.

7 Evaluation

Conclave’s evaluation shows that query rewrites, hybrid MPC-cleartext operators, and suitable MPC backends let it process substantially larger private datasets than pure MPC and SMCQL. The gains are strongest for workloads dominated by joins and aggregations, while unsupported operators and backend scope remain boundaries.

  • Evaluation setup: The evaluation measures runtime scaling, trust annotations and hybrid operators, and performance against SMCQL using three-party experiments.Each party runs a four-node cluster with Spark and Sharemind VMs.
  • Market concentration query: Conclave completes the market concentration query in under 20 minutes for 1B input records, whereas Sharemind cannot scale past 10k records.Conclave pushes the MPC frontier past per-party aggregations, leaving only a few records for final MPC.
  • Hybrid operator performance: Conclave’s hybrid join and aggregation operators substantially improve scalability by moving data-intensive work outside MPC.The hybrid join replaces O(n^2) non-linear MPC operations with O((n + m) log (n + m)) operations, while hybrid aggregation replaces sorting-network comparisons with an oblivious shuffle.
  • Credit card regulation query: Conclave processes 300k records in under 25 minutes on the credit card regulation query, while pure Sharemind fails beyond 3,000 total records.The query requires hybrid operators because its first operation is a join, preventing frontier pushdown from avoiding full MPC execution.
  • Comparison with SMCQL: At 40k rows, Conclave finishes aspirin count in 3.7 seconds versus 14.3 minutes for SMCQL, and Conclave processes 4M records in 8 minutes.The improvement comes from combining a public join with slicing and eliminating the sort from MPC.
  • Comparison with SMCQL: Conclave scales to 200k total rows while SMCQL takes over an hour at 20k rows, but the advantage is lower for comorbidity because aggregation and order-by remain in MPC.The comparison attributes the improvement to Conclave’s Sharemind backend when both systems apply the same optimizations.

8 Related Work

This section situates Conclave among work on mixed-mode computation, query rewriting, secure-query scalability, and inference privacy. It contrasts Conclave’s distributed setting and annotation approach with related systems and research directions.

  • The related-work survey covers mixed-mode operations, query rewriting, query scalability, and privacy-preserving inference.It explicitly omits MPC algorithms, frameworks, and deployments discussed earlier.
  • Mixed mode operation: Wysteria combines MPC and local computation but requires programmers to manually annotate MPC and local blocks.Its annotations are finer-grained than Conclave’s input annotations and require MPC proficiency.
  • Query rewriting and MPC alternatives: Prior systems optimize MPC through query rewriting at the circuit level or relational-algebra level, including SMCQL and Opaque.Circuit-level rewriting can reduce operations such as multiplications through algebraic transformations.
  • Protected databases and scalability: Protected-database research scales secure query execution to gigabyte-to-terabyte datasets, but generally targets a single protected database rather than Conclave’s distributed scenario.The surveyed work includes Boolean keyword search and broad relational-algebra subsets.
  • Inference and privacy: MPC protects data during computation but does not prevent sensitive inputs from being inferred from outputs, motivating combinations of MPC with differential privacy.Differential privacy provides a formal output-privacy guarantee but often relies on a trusted curator.

9 Conclusion and future work

Conclave makes secure MPC on big data more practical by rewriting queries to minimize expensive MPC processing. It runs queries in minutes that previous frameworks found impractical or required specialized expertise to implement.

  • Conclave speeds up secure MPC on big data by rewriting queries to minimize expensive processing under MPC.
  • Conclave runs queries in minutes that were impractical with previous MPC frameworks or required domain-specific implementation knowledge.
  • Future work includes additional MPC backends, automatic protocol selection, verifiable computation, and adaptive padding for relation-size leakage.
  • Conclave is open-source.

A Security analysis

The security analysis proves Conclave’s guarantees by analyzing its push-down, push-up, and hybrid transformations both individually and collectively.

  • Conclave’s security guarantees are analyzed for its push-down, push-up, and hybrid transformations individually and collectively.

A.1 Definitions

The security definition requires correct computation while preventing permissible colluding parties from learning useful information beyond their inputs and permitted output-related information.

  • An adversarial set is permissible when it belongs to the protocol’s adversary structure, which defines the collusions the protocol must withstand.
  • Security requires that a colluding adversary’s view be simulatable from its own inputs and the lengths of honest parties’ inputs.
  • MPC correctness requires the protocol output to equal the computed function over all parties’ inputs.
  • If the adversary includes the receiving party, the simulator also receives the function output because that party is intended to learn it.

A.2 Semi-Honest Security without Hybrid Operators

Without hybrid operators, Conclave splits a computation into local preprocessing, one MPC computation, and local postprocessing. A composition argument preserves semi-honest security while revealing the input lengths of the MPC step rather than the original inputs.

  • Execution structure: Conclave executes local preprocessing, one MPC calculation, and local postprocessing by the receiving party.The postprocessing outputs z = u(y), where u is invertible.
  • Security argument: A standard composition lemma replaces oracle calls to a secure protocol with executions of that protocol, preserving semi-honest security.The composed protocol may reveal the length of the oracle protocol’s input.
  • Security guarantee: Conclave securely computes the transformed function under the same adversary structure, but reveals the input lengths of f rather than those of the original function.The revealed lengths are ℓ_i = |d_i(x_i)|.
  • Scope of the proof: The transformation’s correctness is asserted without proof, with the argument relying mostly on the distributive law.The supplied proof focuses on security rather than correctness.

A.3 Hybrid Operators Stand-Alone Security

Conclave’s hybrid operators provide standalone semi-honest security under a selectively trusted party model, while explicitly accounting for leakage. Their composition preserves security but exposes annotated columns and operator length information within the stated trust assumptions.

  • Trust assumptions: Hybrid-operator security assumes the selectively trusted party operates alone and cannot collude with other participants.The adversary structure includes the STP but excludes sets containing the STP together with other parties.
  • Standalone leakage: Theorem A.3 states that each hybrid operator is standalone secure, while the STP learns the join or aggregation key column and all parties learn input and result row counts.The theorem applies when the backend supports secure oblivious shuffles and indexing.
  • Proof scope: The security proofs focus on simulation and assume correctness is preserved rather than proving correctness directly.This assumption appears both for the standalone hybrid operators and for their composed construction.
  • Hybrid operators: A public join runs entirely in cleartext after all participants disclose their relevant key columns to one another.The aiding server calculates the join in the clear, so this operator entails substantial leakage.
  • Composed construction: Conclave composes local, generic MPC, and hybrid operators by lifting them to operate over shared state, with randomized sharing and reconstruction around the sequence.The operator sequence alternates secure functions f_j and hybrid functions e_j between local preprocessing d and postprocessing u.
  • Composed leakage: The full construction securely computes the composed function subject to leakage of input and output lengths and the contents of columns annotated for the STP.The potential harm depends on the parties’ privacy concerns and the number and type of hybrid operators; annotation propagation bounds intermediate leakage by the columns parties agree to share.
Loading 1902.06288v1…