Source-linked AI summary
Think Locally Before Computing Jointly: Efficient Secure Multi-Party Computation via Maximizing Local Processing
Mingfei Yu, Chenglu Jin, Giovanni De Micheli
TL;DR
Conventional GC optimization focuses on minimizing non-linear gates, although gates whose inputs are locally available need not be evaluated jointly. This paper introduces ownership-aware circuit optimization to increase local computation, reporting reduced garbling cost and performance gains on circuits with party-local structure.
Problem
AND-count minimization treats every non-linear gate as cryptographically costly, although gates with inputs available to one party can be evaluated locally outside the GC protocol.
Source: §1 · p. 2, §4.1.1 · p. 9Method
The framework uses node ownership and an ACD-based, gate-level synthesis strategy to restructure circuits and minimize jointly evaluated computation while preserving functionality.
Source: §1 · p. 2, §4.1.1 · p. 9, §5 · p. 12Results
39.25% reduction in garbling cost on a processor-style benchmark; some cases reduce jointly evaluated computation even when MC is unchanged or slightly increases.
Source: §1 · p. 3Takeaways & Limitations
Ownership-aware optimization uncovers cryptographic-cost reductions missed by conventional MC-based approaches and complements existing GC synthesis techniques.
Source: §1 · p. 3, §8 · p. 21Wall-clock evaluation time is an imperfect indicator of intrinsic savings because memory access, data movement, cache locality, and measurement noise can affect it.
Source: §6.4 · p. 21
Abstract
from arXiv · showhide
Secure multi-party computation (MPC) lets parties evaluate a function over private inputs without revealing them. In garbled-circuit (GC) protocols, prior optimization has largely treated the number of non-linear gates, especially AND gates, as a proxy for cryptographic cost, and has focused on minimizing multiplicative complexity. We identify an orthogonal source of savings: a gate need not be garbled when one party knows or can locally compute its inputs; that party can evaluate it outside the secure protocol, even when the gate is non-linear. We introduce ownership-aware optimization for GC-based MPC, which minimizes non-linear gates requiring joint evaluation rather than total non-linear gates. We formalize this objective in a cost model and implement a compiler-integrated, gate-level framework that restructures Boolean circuits to increase party-local computation while preserving secure-computation semantics. The method is automated and general-purpose, and composes with existing multiplicative-complexity optimization. Experiments show that it reduces jointly evaluated computation and improves end-to-end GC performance on circuits with party-local structure, revealing protocol-cost savings missed by conventional GC cost models.
1 Introduction
The paper argues that garbling cost depends on which non-linear gates require joint evaluation, not just how many appear in a circuit. It presents an automated gate-level approach to increase local computation and reports savings beyond conventional AND-count optimization.
1 Introduction
- A non-linear gate can be evaluated locally when one party knows or can locally compute its inputs, so it need not enter the GC protocol.The paper therefore asks how to minimize jointly evaluated non-linear gates rather than total non-linear gates.Source: §1 · p. 2
- Prior work includes application-tailored local-computation designs and automated compilers that reason about party knowledge at whole-operation granularity.The paper positions its gate-level circuit optimization as complementary to these approaches and to conventional GC synthesis.Source: §1 · p. 2
- The automated gate-level framework restructures Boolean circuits to maximize party-local computation and minimize gates requiring joint evaluation without changing target functionality.It operates directly on circuit structure rather than relying on application-specific insights.Source: §1 · p. 2
- 39.25% reduction in garbling cost on a processor-style benchmark with substantial party-local control logic; some cases reduce jointly evaluated computation despite unchanged or slightly increased MC.Across 12 circuits, the framework is integrated with MP-SPDZ to translate circuit-level reductions into system-level savings.Source: §1 · pp. 2–3
2 Preliminaries
This section reviews the cryptographic and logic-synthesis foundations needed for the paper’s work.
2 Preliminaries
- The review covers the GC protocol, its main cost components, and the threat model considered in the paper.It also introduces logic-network concepts used by the gate-level optimization framework.Source: §2 · p. 3
- The logic-synthesis background includes Boolean circuit representations and cuts.These concepts underlie the framework’s circuit-level optimization.Source: §2 · p. 3
- The section also reviews multiplicative complexity and Boolean decomposition as foundations for the optimization approach.Source: §2 · p. 3
2.1 Cryptographic Preliminaries
The preliminaries describe garbled circuits, their cost drivers, and the security setting assumed for the optimization. They distinguish protocol-evaluated non-linear gates from local work and state the scope of the security guarantees.
2.1.1 Garbled Circuits
- In GC, the garbler sends garbled tables and the evaluator processes them using input labels obtained through OT, learning only the prescribed output.The protocol is described for two parties computing over private inputs.Source: §2.1.1 · pp. 3–4
2.1.2 Garbling Cost
- Under free-XOR, XOR gates have negligible cryptographic cost, while non-linear gates evaluated through GC dominate computation and communication costs.OT cost scales with evaluator input bits, but OT extension makes marginal input-label costs small relative to fixed setup.Source: §2.1.2 · p. 4
2.1.3 Threat Model
- The work assumes a semi-honest model and requires optimized circuits to preserve functionality and reveal no more than the surrounding protocol.Use in maliciously secure protocols requires checks such as input consistency and correct garbling; designing those protocols is out of scope.Source: §2.1.3 · pp. 4–5
2.2 Logic Synthesis and Optimization
The section introduces logic networks and cuts, multiplicative complexity as a conventional cost proxy, and Boolean decomposition as a way to factor functions for synthesis.
2.2.1 Logic Networks
- A logic network is a DAG of primary inputs and Boolean operators; a cut isolates a node’s subcircuit behind leaves, with κ-feasible cuts limiting leaf count.The paper uses XAGs, where AND and XOR are nodes and NOT is represented as a complemented edge.Source: §2.2.1 · p. 5
2.2.2 Multiplicative Complexity
- Structural MC counts AND gates in an XAG and serves as a conventional GC cost proxy, while functional MC is the minimum AND count over the stated basis.Functional MC lower-bounds structural MC, but exact computation is hard beyond limited cases, so practical minimization uses heuristic synthesis.Source: §2.2.2 · p. 6
2.2.3 Boolean Decomposition
- Ashenhurst–Curtis decomposition partitions input variables into disjoint bound, shared, and free sets and factors a function into sub-functions plus combining logic.Unlike variable-based decompositions, it partitions the input space and has been used in LUT-network synthesis.Source: §2.2.3 · pp. 6–7
3 Related Works
Prior work reduces GC costs through cryptographic constructions, multiplicative-complexity optimization, and party-knowledge-based locality. This work distinguishes itself with an automated, general-purpose gate-level approach to reducing joint computation.
3.1 Cryptographic Optimizations for GC
- Cryptographic optimizations make XOR gates essentially free and reduce AND-gate costs; this work adds circuit-level efficiency improvements without introducing a new cryptographic construction.The circuit-level approach is complementary to, and naturally combinable with, these cryptographic optimizations.Source: §3.1 · p. 7
3.2 Optimal Garbled Circuit Generation
- Logic-synthesis approaches largely target multiplicative-complexity reduction, treating non-linear gates as equally costly; related MPC tools also optimize metrics such as gate count or depth.Examples include TinyGarble and heuristics such as cut-based rewriting, resubstitution, and structural don’t-cares.Source: §3.2 · p. 7
3.3 Exploiting Party Knowledge in Secure Computation
- Earlier party-knowledge approaches and mixed-mode compilers move computation outside MPC, but decide locality at whole-operation granularity; this work instead restructures individual gates.The framework uses input ownership, while incorporating output-derived knowledge remains a direction for future work.Source: §3.3 · p. 8
3.4 Joint Computation Minimization
- To the best of the authors’ knowledge, this is the first automated, general-purpose gate-level framework for reducing joint computation in Boolean GC-based MPC.It restructures circuits at individual gates, contrasting with application-specific optimizations and compilers that make locality decisions at the level of whole operations.Source: §3.4 · p. 8
4 Overview
The section replaces total AND count as the GC cost proxy with joint multiplicative complexity (JMC), based on whether nodes can be computed locally under input ownership. It outlines a gate-level peephole optimizer and motivates ownership-aligned Boolean decomposition to reduce jointly evaluated computation.
4.1.1 Limitations of MC as a Cost Proxy
- MC can overestimate GC cost because a party can evaluate a gate locally when its inputs are locally available, even if the gate is nonlinear.The cost objective therefore distinguishes locally derivable nodes from jointly derived nodes.Source: §4.1.1 · p. 9
4.1.2 Node Ownership
- A node is locally derivable by a party if it is that party’s input or a gate whose fanins are all locally derivable by that party.Input ownership assigns each primary input to exactly one party; nodes not locally derivable by any single party are jointly derived.Source: §4.1.2 · p. 9
4.1.3 Refined Cost Model
- With the same two AND gates and party ownership, one MC-optimal implementation has JMC = 2, while another has JMC = 1 because B can compute one gate locally.The example illustrates why equal MC does not imply equal garbling cost.Source: §4.1.3 · p. 10, Figure 3 · p. 10
- JMC counts jointly derived AND nodes, which require joint computation, rather than all AND nodes in the network.The framework targets JMC to reduce garbling cost.Source: §4.1.3 · p. 10
4.2 Logic Optimization Framework
- The peephole optimizer resynthesizes bounded-size cuts, screens candidates by local JMC, then checks whole-network JMC before committing the best replacement.Global evaluation accounts for shared substructures.Source: §4.2 · p. 11
4.3 Role of Boolean Decomposition
- Larger cuts expose broader structural relationships, and Ashenhurst–Curtis decomposition aligns variable partitioning with party ownership to make free-set functions local.Unlike Shannon expansion’s ownership-independent selection layer, ACD’s jointly evaluated select-signal count adapts to function structure.Source: §4.3 · pp. 11–12, Figure 4 · p. 12
5 Methodology
The methodology uses ACD-based synthesis to restructure Boolean sub-networks around party-specific input ownership. Its engine combines ownership-aware decomposition, near-MC-minimal function synthesis, and low-MC MUX construction to minimize jointly derived computation.
5.1 Joint Compute-Oriented Decomposition
- ACD expresses the function through BS functions, FS functions, and a top function realized as a MUX; BS and SS variables serve as selector variables.The engine partitions variables and derives FS functions, assigns their encodings and constructs BS functions, then synthesizes the top MUX.Source: §5.1 · pp. 12–13
5.1.1 Variable Partitioning and Free-Set Function Construction
- The partitioning procedure groups exclusively owned leaves into the FS set, discards partitions with at most one FS variable, and derives distinct FS functions by restricting the function for each BS-variable assignment.Figure 5 illustrates the partition xFS = {b1, b2}, xBS = {a1}, yielding two distinct FS functions.Source: §5.1.1 · p. 13, Figure 5 · p. 14
5.1.2 Encoding and Bound-Set Function Derivation
- Each FS function receives a unique code, while code assignments are optimized to minimize the support of the induced BS functions and thus limit joint computation.The number of BS functions is constrained to be minimal while still encoding all FS functions uniquely.Source: §5.1.2 · p. 14
5.1.3 Synthesis of Derived BS and FS Functions
- BS and FS functions are synthesized as XAGs using per-output lookup from a near-MC-minimum database, with structural hashing sharing only structurally identical AND nodes.The per-output approach is reported as within 1% of exact multi-output synthesis for 353 BS instances; FS-side surplus AND gates remain local and do not enter the garbled circuit.Source: §5.1.3 · p. 15
5.2 Low-MC Multiplexer Construction
- The top MUX selects among FS-function outputs using BS-function outputs as selectors; its construction targets MC-optimality because data and select signals entangle at the first logic level.For the running example, its JMC is 1, a 50% reduction relative to the implementation in Fig. 3a.Source: §5.2 · pp. 15–16
5 Methodology
- The resynthesis engine combines joint compute-oriented decomposition, near-MC-minimal synthesis of derived functions, and low-MC MUX construction to minimize jointly derived computation.It is the computational core that replaces sub-networks with optimized XAGs.Source: §5.2 · p. 16
6 Experimental Evaluation
The evaluation tests ownership-aware optimization on diverse two-party circuits at both circuit and system levels. It finds that reducing jointly evaluated computation can complement multiplicative-complexity reduction, with garbled-gate savings outweighing added OT overhead in the reported benchmarks.
6.1 Experimental Setup
- The evaluation covers 12 circuits after high-effort MC preprocessing, measuring circuit-level changes and MP-SPDZ communication and latency across arithmetic, cryptographic, and general-purpose workloads.The two-party benchmark set includes seven arithmetic/comparative circuits and five cryptographic/general-purpose kernels.Source: §6 · p. 16, §6.1 · p. 16, §6.2 · p. 16
6.3 Circuit-Level Evaluation
- Floating-point operators offer more opportunity to reduce joint computation than integer operators, and FP-eq benefits most because much of its case analysis is operand-local.Independent operand preparation and post-processing surround a core that mixes operands; FP-eq’s zeros, infinities, and NaNs often depend on one operand.Source: §6.3 · p. 17
- AES-128 already has locally derivable linear layers, whereas SHA3 exposes essentially no locally derivable AND gates; neither benchmark yields further optimization.Their remaining nonlinear regions are isolated and predominantly jointly derived, leaving little structural flexibility.Source: §6.3 · pp. 17–18
- General-purpose kernels vary in locality: Hamming distance mixes inputs immediately, while LiteMIPS has operand-local instruction decoding and control steering.LiteMIPS models one party supplying the instruction stream and the other supplying data and architectural state.Source: §6.3 · p. 18
- JMC reductions can accompany lower MC, but can also occur with unchanged or slightly increased MC, showing the objectives explore overlapping but distinct design-space regions.INT-div reduces MC by 26 and JMC by 72; FP-eq reduces JMC with unchanged MC, while INT-mul reduces JMC despite a slight MC increase.Source: §6.3 · p. 18
- Results vary non-monotonically with cut-size bound κ; larger cuts can crowd out profitable small cuts, while a larger priority-cut budget improves most benchmarks at higher synthesis time.The default κ = 8 is the largest value the backend exploits fully; using 15 rather than 8 priority cuts at κ = 8 costs 2.9× the synthesis time.Source: §6.3 · p. 18
- Optimization adds at most 100 seconds of one-time synthesis, usually does not increase total AND count, and largely preserves depth.Total AND count grows by three gates only for INT-mul among nine circuits; AND depth changes on three circuits, while total depth grows noticeably only on two smallest circuits.Source: §6.3 · pp. 18–19
6.4 System-Level Evaluation in MPC
- The garbled-gate saving exceeds OT overhead by at least 3.2× and typically by one to two orders of magnitude; Encoder and LiteMIPS reduce both terms.Table 5 summarizes the per-benchmark trade-off between additional evaluator inputs and saved garbled ANDs.Source: §6.4 · p. 20, Table 5 · p. 20
7 Positioning of Contributions
The contribution is orthogonal to per-garbled-AND and AND-count optimizations: it reduces how many AND gates must be garbled by exploiting private ownership at gate granularity.
7 Positioning of Contributions
- The method lowers the number of AND gates that must be garbled, complementing per-garbled-AND cryptographic optimizations and multiplicative-complexity-driven synthesis.The baselines are MC-minimized and use half-gates.Source: §7 · p. 21
- Unlike SkipGate/ARM2GC [SRH+19] and Senate [PKY+21] or Marill, it exploits values privately known to one party automatically at gate granularity across arbitrary Boolean circuits.Source: §7 · p. 21
- Ownership analysis contributes 18.19 percentage points on LiteMIPS and 39.37 on FP-eq, while resynthesis adds 21.06 and 29.84 percentage points, respectively.Source: §7 · p. 21
8 Conclusion
The conclusion presents joint multiplicative complexity as a GC-cost metric and an ownership-aware synthesis framework that reduces it. The evaluation finds opportunities missed by conventional MC optimization, while benchmarks and the instantiated cost model remain two-party.
8 Conclusion
- The framework formalizes node ownership as joint multiplicative complexity (JMC) and uses peephole optimization to reduce it.Its Ashenhurst–Curtis-based engine resynthesizes subnetworks through ownership-aware variable partitioning and low-MC component implementations.Source: §8 · p. 21
- The evaluation finds optimization opportunities missed by conventional multiplicative-complexity approaches, motivating more local work and less joint computation.Source: §8 · p. 21
- The ownership analysis is stated for t parties, but the benchmarks and instantiated cost model are two-party; multi-party extensions and malicious-security variants remain future work.The proposed extension uses a protocol-specific cost function over ownership sets.Source: §8 · p. 21