Source-linked AI summary
Secure Arithmetic Computation with No Honest Majority
Yuval Ishai, Manoj Prabhakaran, Amit Sahai
TL;DR
The paper addresses the efficiency of securely evaluating arithmetic circuits over finite rings without reducing them to inefficient Boolean circuits. It develops black-box protocols with varying efficiency, generality, and computational assumptions, including constant amortized cryptographic cost in important settings.
Problem
Securely evaluating arithmetic computations over large finite rings requires efficient protocols that avoid the inefficiency of Boolean-circuit reductions.
Method
The paper constructs arithmetic-circuit protocols using black-box ring operations and cryptographic primitives, including product-sharing and noisy-code techniques.
Results
The protocols achieve constant amortized communication per multiplication gate in one efficient construction and require only O(k) malicious-secure OTs independently of circuit size.
Takeaways & Limitations
The results extend secure arithmetic computation to stateless and reactive settings, supporting efficient transitions between arithmetic and non-arithmetic operations.
Takeaways & Limitations
General-purpose protocols retain round complexity that grows with circuit multiplicative depth, and some efficiency results rely on decoding-hardness assumptions over large fields.
Abstract
from arXiv · showhide
We study the complexity of securely evaluating arithmetic circuits over finite rings. This question is motivated by natural secure computation tasks. Focusing mainly on the case of two-party protocols with security against malicious parties, our main goals are to: (1) only make black-box calls to the ring operations and standard cryptographic primitives, and (2) minimize the number of such black-box calls as well as the communication overhead. We present several solutions which differ in their efficiency, generality, and underlying intractability assumptions. These include: 1. An unconditionally secure protocol in the OT-hybrid model which makes a black-box use of an arbitrary ring $R$, but where the number of ring operations grows linearly with (an upper bound on) $\log|R|$. 2. Computationally secure protocols in the OT-hybrid model which make a black-box use of an underlying ring, and in which the number of ring operations does not grow with the ring size. These results extend a previous approach of Naor and Pinkas for secure polynomial evaluation (SIAM J. Comput., 35(5), 2006). 3. A protocol for the rings $\mathbb{Z}_m=\mathbb{Z}/m\mathbb{Z}$ which only makes a black-box use of a homomorphic encryption scheme. When $m$ is prime, the (amortized) number of calls to the encryption scheme for each gate of the circuit is constant. All of our protocols are in fact UC-secure in the OT-hybrid model and can be generalized to multiparty computation with an arbitrary number of malicious parties.
1 Introduction
The paper asks how to securely evaluate arithmetic circuits over finite rings while using only black-box ring and cryptographic operations and keeping communication and operation counts low. It presents protocols spanning unconditional and computational security, arbitrary rings or fields, and homomorphic encryption, with differing efficiency and assumptions.
- Motivation: The central problem is securely evaluating an arithmetic circuit C over a finite ring R without incurring the inefficiency of Booleanizing large-ring operations.Arithmetic circuits use ring elements as inputs and outputs and addition, subtraction, and multiplication as gates; Boolean multiplication circuits already exceed linear growth in element length.
- Goals and model: The paper targets black-box feasibility and low overhead for two-party computation with malicious parties, primarily in the OT-hybrid model.Black-box access hides the correspondence between ring elements and identifiers, while the stated goals are to minimize black-box calls and communication.
- Protocols: The unconditionally secure protocol works for any finite ring R, but its ring operations and communicated ring elements grow linearly with an upper bound on log |R|.For each circuit gate, the number of ring operations is poly(k) · log |R|.
- Protocols: Computationally secure noisy-encoding protocols support arbitrary fields with per-gate operation counts bounded by a fixed polynomial in k, independently of |F|.Their security relies on intractability assumptions related to decoding noisy random linear codes, extending the Naor–Pinkas approach.
- Efficiency: The most efficient field protocol uses constant amortized communication per multiplication gate and O(log k) amortized field operations per gate under a super-polynomial field-size assumption.Relative to the cited constant-overhead Boolean-circuit protocol, it has better communication and a better-studied assumption but is asymptotically worse by O(log k) computationally in the Boolean model.
- Extensions and security: For Z_m, the homomorphic-encryption protocol uses a constant amortized number of ciphertexts and encryption calls per circuit gate when m is prime, and the protocols extend to matrix rings.The protocols are UC-secure in the OT-hybrid model, generalize to any number of malicious parties, and support adaptive adversaries when honest parties erase data.
2 Preliminaries
The preliminaries define black-box ring families, arithmetic circuits, their MPC functionality, and complexity measures for secure evaluation. They also formalize secure black-box realization and note that arithmetic complexity can be independent of ring size.
- A ring oracle supports addition, subtraction, multiplication, sampling, and element identifiers under a concrete mapping for each ring family.
- The framework includes ring families with inverses, field families, pseudo-field families, and examples such as Z_m and matrix rings.
- An arithmetic circuit uses ring inputs and outputs with addition, subtraction, and multiplication gates, and induces an annotated MPC functionality.
- Security is defined in the UC framework, with protocols considered under static or adaptive corruption and, for the final protocols, adaptive corruption with erasures.
- Arithmetic computation complexity counts ring-oracle calls, while communication complexity counts ring-element labels in the transcript.
- A secure black-box realization must securely evaluate the circuit for each ring family with complexity bounded by a polynomial in k and |id| independently of R.
3 Noisy Encodings
The paper develops noisy encodings that hide ring or field elements while permitting decoding with auxiliary noise information. It gives a generic construction and instantiates it using statistical or computational hiding with field and arbitrary-ring code families.
- Noisy encodings randomly pad a message, apply a linear code, and add noise so decoding is possible with noise information while the public encoding hides the message otherwise.
- The paper uses statistically hiding encodings for unconditional security and computationally hiding encodings under different concrete assumptions.
- Statistically Hiding Noisy Encoding: The simple encoding samples vectors (v0,v1) conditioned on a hidden vector u and outputs them with a pattern σ that enables decoding.
- Statistically Hiding Noisy Encoding: Removing σ statistically hides x from the first encoding part, with the proof relying on the Leftover Hash Lemma.
- Statistically Hiding Noisy Encoding: For the simple encoding, when n > log |R| + k, the statistical distance from uniform is bounded by 2^-Ω(n−log |R|).
- Generic Encoding: The generic computational encoding uses G, H, and L, with a padded vector u, a noisy vector v, and public output (G,v).
- Random Code Based Instantiation: The random-code instantiation applies to fields and chooses a random subset L whose submatrix G|L is nonsingular, then computes H satisfying HG|L = I.
- Ring Code Based Instantiation: The ring-code instantiation applies to arbitrary rings, choosing n = 2k, ℓ = k, triangular matrices, and a subset L that yields an efficiently computable inverse H.
4 Product-Sharing Secure Against Passive Corruption
The section develops OT-hybrid protocols for securely sharing products, progressing from statistical security with size-dependent cost to computational and amortized constructions. It also connects these shared-product protocols to homomorphic-encryption approaches for rings and matrices.
- The functionality gives A and B random additive shares zA and zB of the product ab.
- n > log(|R|) + k yields a statistically secure OT protocol for product sharing against static passive corruption.
- A linear-code protocol removes explicit dependence on the underlying ring size, assuming computational security for the code generation scheme.
- Packed encoding realizes t coordinate-wise product sharings over fields with security under Assumption 3(c), while polynomial processing costs O(k log^2 k) generally or O(k log k) with suitable evaluation points.
- Controlled-ring homomorphic encryption directly supplies product sharing with correctness and privacy inherited from the encryption definition.
- For uncontrolled-ring encryption, statistical masking supports computing m degree-2 functions over n variables with O(m+n) ciphertexts, including matrix product sharing with O(n^2) ciphertexts.
5 General Arithmetic Computation against Active Corruption
The paper composes outer protocols tolerating active server corruption with inner OT-hybrid protocols for secret-shared server state to obtain black-box arithmetic computation. The resulting constructions trade generality and assumptions for ring-size-independent arithmetic or encryption complexity.
- The general compiler combines an outer MPC protocol using k auxiliary servers with an inner passive-secure protocol for reactive secret-shared server computations.
- A statistically secure protocol for arbitrary rings has arithmetic communication growing linearly with an upper bound on log |R|.
- Under Assumption 3(a), field-family protocols have arithmetic complexity poly(k) · |C| independently of the field family or identifier length.
- Under Assumption 3(b), the same poly(k) · |C| arithmetic bound extends to computationally efficient ring families.
- Under Assumption 3(c), field protocols achieve communication O(|C| + k · depth(C)), computation O(log^2 k) · (|C| + k · depth(C)), and O(depth(C)) rounds.
- The computational overhead can fall from O(log^2 k) to O(log k) under specialized Reed–Solomon fields and evaluation points, without black-box field representation.
- Controlled-ring encryption yields poly(k) · |C| invocations for arbitrary rings, while fields admit O(|C| + k · depth(C)) invocations and ciphertext-dominated communication.
- Uncontrolled-ring encryption supports standard-representation Z_M computations with poly(k) · |C| invocations, and matrix instantiations incur quadratic dependence on matrix dimension.
A Security Against Adaptive Passive Corruption, with Erasures
The section presents a transformation from protocols with simpler passive security to adaptive passive security with erasures. It builds the transformed protocol by using random-input executions, erasing local computations, and communicating corrections.
- The transformation calls the basic protocol on random inputs, erases local computations, and communicates corrections to obtain adaptive passive security with erasures.
- The resulting protocol eπOT has passive adaptive security with erasures and can provide an efficiency advantage when preprocessing interaction is available.
A.1 Special Simulation Security Against Passive Corruption
This appendix defines special simulation security for passive corruption on random inputs. The simulator forwards corrupt inputs, samples indistinguishable honest-party randomness correlated with ideal outputs, and aborts if the simulated corrupt outputs disagree.
- A random-input environment supplies independent random inputs to each party according to a specified distribution.
- A special simulator sends corrupt inputs to the functionality and receives its outputs before choosing simulated honest inputs and random tapes.
- The simulator may correlate its random choices with functionality outputs while keeping them jointly indistinguishable from the specified distribution given corrupt inputs.
- The simulator aborts unless the corrupt parties produce the functionality’s outputs, then reports their simulated view to the environment.
- A protocol securely realizes the functionality on random inputs when every random-input environment cannot distinguish real execution from ideal execution with such a simulator.
A.2 Special Simulation Security to Security Against Adaptive Corruption with Erasures
The section transforms a protocol secure under passive corruption with special simulation into one secure against adaptive passive corruption with erasures. The construction uses random masking and erasure to maintain indistinguishable simulated states.
- Protocol construction: The protocol first runs πOT on random inputs, erases its working memory, and then exchanges masked input differences to produce additive shares of ab.The outputs satisfy zA + zB = ab.
- Security transformation: Lemma 5 states that eπOT securely realizes Fpdt-shr against adaptive passive corruption with erasures when πOT is secure on random inputs with special simulation.Statistical security is preserved when the underlying security is statistical.
- Simulation: The simulator obtains zA from the ideal functionality, chooses random c and rA, and sets sA := zA − ac before invoking the special simulator for πOT.This preserves the distribution required by the simulation of the random-input subprotocol.
- Adaptive corruption: If B is corrupted after step 4, its state can be explained using b, rB := b − c, and sB := rArB − sA after B has erased its πOT state.The resulting pair remains consistent with the product-sharing functionality.
- Security proof: The indistinguishability argument relies on special simulation and indistinguishable static-corruption simulation for πOT on random inputs.The same property supports the security of the composed protocol.
- Instantiation: Protocols πOT, σOT, τOT, θ, and ψ satisfy the required special-simulation property, so composing them with eπOT yields adaptive-passive security with erasures.The result applies to the listed underlying protocols, including those based on homomorphic encryption.
B Extension to Multi-Party Computation
The paper extends its inner protocol to multiparty computation by combining it with multiparty outer protocols. The resulting construction preserves correctness and perfect privacy against passive corruptions.
- Extension strategy: The multiparty extension follows by extending the inner protocol while using outer protocols that already support an arbitrary number of parties.This yields corresponding extensions of all the paper’s results.
- Outer computation: The outer protocol’s nontrivial server computation forms random shares ci satisfying Σici = (Σixi)(Σiyi).Each party Pi sends xi and yi and receives ci as output.
- Product sharing: The product-sharing step uses an Fpdt-shr instance for every ordered pair of distinct parties.This generalizes the binary construction to the multiparty setting.
- Security: The resulting protocol is correct and provides perfect privacy against passive corruptions.The paper describes this as analogous to the binary case from GMW87.
C An Efficient Outer MPC Protocol
The outer MPC protocol uses clients and servers to achieve statistically UC-secure computation against adaptive corruption, while allowing security with abort. Its arithmetic and round complexity depend on circuit size, depth, and statistical security.
- Security model: The protocol is statistically UC-secure against an adaptive adversary corrupting any number of clients and a constant fraction of servers.Only clients have inputs and outputs, and the protocol may provide security with abort rather than guaranteed output delivery.
- Randomness assumption: The protocol assumes common access to an oracle broadcasting random field elements, which are excluded from the communication count.The paper notes that this oracle can instead be emulated or generated by clients in the final protocol.
- Efficiency: O(s + kd) arithmetic communication and O(d) rounds suffice for a circuit of size s, multiplicative depth d, and statistical security parameter k.The stated bounds assume n = O(k) and a constant number of clients.
- Scope: The exposition focuses on two clients, while extending to more clients is described as straightforward.The circuit presentation also assumes layered circuits, with arbitrary structures incurring an additive O(nd) cost.
C.1 Building Blocks
The building blocks combine secret sharing, linear-space membership proofs, and local block arithmetic. Their efficiency includes an additive O(kd) term, while correctness, soundness, and zero knowledge support robust shared computation.
- Secret sharing: Shamir secret sharing distributes a secret as evaluations of a random degree-δ polynomial over a field with |F| > n.In a black-box field, interpolation points can be chosen at random.
- Block arithmetic: Shared blocks add locally, multiply coordinatewise, and require degree reduction before products can be reused in later computations.The multiplication follows the Shamir-sharing approach used in BGW.
- Efficiency caveat: The outer protocol has arithmetic communication complexity O(s + kd), and the additive O(kd) term is not optimized in the paper.A careful implementation is suggested to make this term small enough for practical purposes.
- Security properties: The membership protocol provides completeness, soundness, and zero knowledge for distributed vectors.For a corrupted dealer, outputs are either rejected or close to a vector in the target linear space.
- Membership proofs: Membership proofs distribute vectors and blinding vectors, derive a random linear combination, broadcast the blinded combination, and check consistency before outputting shares.A complaint or invalid linear-space membership causes the protocol to abort.
- Adaptive analysis: Adaptive soundness is analyzed with a union bound, while a tighter analysis applies when the field size is superpolynomial in the security parameter.Except with negligible probability, either the protocol aborts or most honest shares are consistent with a valid codeword.
C.2 The Protocol
The protocol evaluates arithmetic circuits layer by layer on secret-shared blocks, using local linear operations and verified procedures for multiplication and block rearrangement. Polynomial consistency checks, blinding, and output validation provide security with abort, while communication and computation are bounded by circuit depth and block size.
- Sharing inputs: Inputs are secret-shared into replicated blocks, with clients proving low-degree polynomial consistency and the required replication pattern.Boolean inputs can additionally be checked by revealing 1 − a · a for each block.
- Layer evaluation: The protocol evaluates each of the d circuit layers in a separate phase using blocks arranged for parallel arithmetic operations.Multiplication, addition, and subtraction are applied coordinate-wise to pairs of blocks.
- Layer evaluation: Addition and subtraction are performed locally, while multiplication uses blinding, polynomial degree checks, and rearrangement into blocks for the next layer.Alice checks that interpolation points lie on a polynomial of degree at most 2δ; Bob supplies consistent unblinding polynomials.
- Verification: Degree restrictions and consistency checks detect corrupted codewords or invalid replicated blocks, causing the protocol to abort when cheating is detected.The code structure provides distance-based protection against undetected corruption.
- Output delivery: Outputs are reconstructed by clients from server shares after checking that each block agrees with a degree-d polynomial.Inconsistent shares cause the client to abort.
- Efficiency: Communication overhead is O(nd), while block secret sharing and reconstruction require O(ℓlog^2 ℓ) arithmetic operations, reducible to O(ℓlog ℓ) with structured evaluation points.The communication bound accounts for narrow layers and wires between non-adjacent layers.