PaperlayerView exact revision on arXiv

Source-linked AI summary

A New Approach to Practical Active-Secure Two-Party Computation

Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, Sai Sheshank Burra

arXiv:1202.3052v1cs.CR

TL;DR

The paper addresses whether OT-based two-party computation can achieve practical active security, beyond prior practical protocols based on garbled circuits. It combines OT extension with new techniques for relating OT inputs and outputs, and reports an implementation achieving 21,623 gates per second for amortized total time and 1,083,885 online gates per second.

  • Problem

    Practical two-party computation had been based on garbled circuits, while the practicality of OT-based computation remained to be established.

  • Method

    The protocol extends a few seed OTs into many active-secure OT-like primitives and relates OT inputs and outputs using information-theoretic tags and authenticated bits.

  • Results

    21,623 gates per second are handled at best amortized total time, while online evaluation reaches 1,083,885 gates per second.

  • Takeaways & Limitations

    The implementation shows that OT-based two-party computation can be practical, with active security costing about a factor of 10 over the passive-secure protocol at full capacity.

  • Takeaways & Limitations

    The underlying authenticated-OT construction admits a selective failure attack unless LaOTs are randomly partitioned and combined.

Abstract

from arXiv · show

We propose a new approach to practical two-party computation secure against an active adversary. All prior practical protocols were based on Yao's garbled circuits. We use an OT-based approach and get efficiency via OT extension in the random oracle model. To get a practical protocol we introduce a number of novel techniques for relating the outputs and inputs of OTs in a larger construction. We also report on an implementation of this approach, that shows that our protocol is more efficient than any previous one: For big enough circuits, we can evaluate more than 20000 Boolean gates per second. As an example, evaluating one oblivious AES encryption (~34000 gates) takes 64 seconds, but when repeating the task 27 times it only takes less than 3 seconds per instance.

1 Introduction

The paper develops a practical active-secure two-party computation approach based on oblivious transfer extension rather than the garbled-circuit techniques used by almost all prior practical implementations. It introduces techniques for efficient active-secure OT extension and for relating OT inputs and outputs, then reports implementations with strong performance on oblivious AES.

  • Motivation: OT extension turns a small number of seed OTs into many OTs using O(ℓ) hash-function invocations, making OT-based 2PC potentially practical.The approach starts from passive-secure OT extension and passive-secure 2PC, using OT extension to amortize the seed OTs.
  • Contributions: The paper introduces an active-secure OT-extension technique with the same asymptotic complexity as prior work but much smaller practical constants.Its protocol is only a small factor slower than the passive-secure OT-extension protocol it builds on.
  • Contributions: 500,000 OTs per second are generated by the first implementation of the active-secure OT-extension idea.This demonstrates that applications requiring large numbers of OTs can be practical.
  • Contributions: Information-theoretic tags relate OT inputs and outputs, yielding a committed-OT-like primitive that uses symmetric cryptography.Combined with the new OT-extension technique, this enables efficient extension of committed OT.
  • Overview of the approach: The protocol addresses the insecurity of passive-secure computation against malicious adversaries by authenticating bits with MACs and constructing authenticated ANDs.The construction uses authenticated bits, authenticated local ANDs, and authenticated OTs, with proofs and combiners handling consistency and leakage.

2 Preliminaries and Notation

The preliminaries establish notation and security assumptions for the protocol, including random-oracle hashing, oblivious transfer, equality checks, and leakage-secure global keys.

  • κ denotes the security parameter, and adversaries are required to break the protocol with probability at most poly(κ)2^-κ.
  • The UC Framework: Security is proved for static active adversaries in the UC framework, using hash functions modeled as random oracles.
  • The protocol uses OT(τ, ℓ), where a receiver obtains one selected ℓ-bit message without learning the other message or additional information.
  • Equality Check: EQ(ℓ) checks whether two ℓ-bit strings are equal, leaking both strings if they differ; in practice, exchanged hash values implement it in the random-oracle model.
  • Leakage Functions: The leakage framework models attacks that may reveal selected bits of a random τ-bit secret while possibly being detected.
  • Leakage Functions: A leakage class is κ-secure when at least κ bits remain effectively hidden, limiting any adversary’s winning probability to 2^-κ.

3 The Two-Party Computation Protocol

The protocol realizes Boolean two-party computation from preprocessed authenticated bits, oblivious transfers, and local AND triples. Its construction preserves shared global keys while extending authenticated bits into the resources needed for computation.

  • FDeal supplies authenticated bits, authenticated local AND triples, and authenticated OTs as preprocessing resources for F2PC.
  • The F2PC protocol securely implements Boolean two-party computation in the FDeal-hybrid model with security parameter κ.
  • Authenticated bits store a value, MAC, and local key, with XOR computed componentwise without communication.
  • The protocol computes XOR locally, while AND combines authenticated shares using preprocessing, revealed masked values, and authenticated OTs.
  • Implementing FDeal: FDeal is built in stages for authenticated bits, authenticated OTs, and authenticated local ANDs, while preserving the global keys across these resources.

4 Bit Authentication

The section builds active-secure bit authentication from OT-based primitives by managing leakage in intermediate global keys and authenticated bits. Privacy amplification and local reductions yield secure authenticated bits with costs that can be amortized over many outputs.

  • Protocol outline: The protocol starts by authenticating bits under a global key, then transforms controlled leakage in authenticated bits into leakage in the global key.The construction proceeds through LaBit and WaBit intermediates before producing a fully secure aBit.
  • Protocol outline: WaBitL(ℓ, τ) outputs ℓ authenticated bits with τ-bit keys, while aBit(ℓ, ψ) is the no-leakage special case.The weak-key box is parameterized by a leakage-function class; aBit uses a class that never leaks.
  • Protocol outline: LaBitL(τ, ℓ) outputs τ authenticated bits with ℓ-bit keys while allowing leakage of some authenticated bits, and it reduces to WaBitL.The reduction reverses the direction of authenticated outputs: bits authenticated for B become bits authenticated for A.
  • OT-based construction: Randomly pairing authenticated bits and checking their derived values enforces consistent OT message differences, with cheating detected except with probability 2^-ℓ.Equality checks are performed on batched MAC and key strings; the protocol outputs one bit from each checked pair.
  • Complexity: The LaBit construction securely uses OT(2τ, ℓ) and EQ(τℓ), with communication O(τ^2) and work O(τℓ).The subsequent reduction to aBit has communication O(ψ^2) and work O(ψ^2ℓ), while independent costs can be amortized for large ℓ.

5 Authenticated Oblivious Transfer

Section 5 constructs authenticated oblivious transfers through a leaky intermediate functionality, then removes leakage by randomly bucketing and combining multiple instances. The resulting protocol securely implements aOTs under an explicit bucket-size and security-parameter condition.

  • Construction: Authenticated OTs are built from aBits by first constructing a leaky LaOT functionality and then transforming it into ordinary aOTs.The construction is symmetric; the section presents the case with A as sender and B as receiver.
  • Construction: Hash-derived one-time pads let A transfer x_c to B, who reconstructs the authenticated output using a masked difference.A hashes two possible MAC-key values, while B computes the hash corresponding to the chosen bit and announces d = x_c ⊕ r.
  • Leakage removal: Selective failure attacks let A test B’s choice bit by pairing one correctly authenticated message with one invalid MAC.The protocol later removes this leakage through random partitioning and combination of several LaOTs.
  • Security: Theorem 5 states that the Fig. 15 protocol securely implements LaOT(ℓ) in the (aBit(4ℓ, κ), EQ(2ℓκ))-hybrid model.
  • Security: Theorem 6 states that Fig. 16 securely implements aOT(ℓ) from LaOT(Bℓ) when (log2(ℓ)+1)(B−1) ≥ ψ.The resulting statistical security parameter is ψ.

6 Authenticated local AND

Section 6 constructs authenticated local ANDs through a leaky LaAND functionality and removes leakage by random bucketing and combination. The resulting aAND protocol inherits a security condition analogous to the authenticated-OT construction.

  • Construction: Authenticated local ANDs are constructed by first implementing a leaky LaAND functionality and then applying a leakage-removal transformation.The section presents the construction for authenticated local ANDs for A; the construction for B is symmetric.
  • Construction: The LaAND protocol lets A compute the AND locally and authenticate the result, while leakage of x to B is detectable.
  • Leakage removal: The protocol handles guessed x bits by randomly distributing Bℓ LaANDs into ℓ buckets of size B and combining each bucket.A bucket yields a secure aAND if at least one LaAND in that bucket is not leaky; only x can leak, so amplification is needed once.
  • Protocol: The protocol is parameterized by positive integers B and ℓ and invokes LaAND(ℓ′) with ℓ′ = Bℓ.
  • Security: Theorem 8 states that Fig. 20 securely implements aAND(ℓ) when (log2(ℓ)+1)(B − 1) ≥ ψ.The implementation is in the LaAND(Bℓ)-hybrid model with security parameter ψ.

7 Experimental Results

Section 7 evaluates a Java proof-of-concept implementation using oblivious ECB-AES circuits and reports preprocessing, online, total, and amortized performance. Performance improves substantially when preprocessing is amortized across repeated AES evaluations, with the best reported total-throughput point at ℓ = 54.

  • Implementation: The implementation is a Java proof of concept with SHA256, circuit-independent preprocessing, circuit construction, and a runtime evaluation system.
  • Benchmark: The benchmark uses oblivious ECB-AES encryption, with secret shared keys and a secret ℓ-block message whose ciphertexts are learned by B.The AES circuit comes from [PSSW09].
  • Benchmark: AES was selected as a reasonably sized and structurally complex circuit, while comparisons remain crude because experiments used different setups.
  • Measurements: The timing study records gates, preprocessing time, online time, amortized total time per AES encryption, and gates per second.Ttot = Tpre + Tonl; preprocessing includes generating, communicating, and storing FDeal values, while online time includes circuit generation and evaluation.
  • Security parameters: 640 seed OTs are required at computational security level 120, but their timing is excluded because it depends on the seed-OT implementation.The implementation uses fixed bucket size 4, so statistical security depends on ℓ.
  • Results: The amortized time drops sharply from ℓ = 1 to ℓ = 27 because implementation preprocessing uses fixed-size units and both cases preprocess equally many gates.
  • Results: 21,623 gates per second and 1.6 seconds per AES block are achieved at ℓ = 54 under the best amortized total-time behavior.

A Complexity Analysis

The complexity analysis expresses the protocol’s post-seed cost in cryptographic-hash invocations and derives per-gate costs from the authenticated primitives. The optimized implementation uses fixed buckets of size 4.

  • Overall cost: After an initial ideal call to (OT(4^3 ψ, ψ), EQ(ψ)), the protocol’s per-gate cost consists of cryptographic-hash invocations.The analysis counts total hash calls made by both parties.
  • Primitive costs: An EQ costs 2 hash calls, while each aOT costs 4B aBits, 2B EQ calls, and 6B hash calls.
  • Primitive costs: Each aAND costs 3B aBits, B EQ calls, and 3B hash calls; input gates cost 1 aBit, AND gates cost 2 aOTs, 2 aANDs, and 2 aBits.
  • Optimization: The unoptimized aBit cost is 59 hash calls, reducible to 8 with further optimizations not described in the paper.
  • Final cost: 584 hash calls are required per AND gate in the optimized implementation with bucket size 4.The general optimized expression is 142B + 16 hash calls per AND gate.
  • Trade-off: Deferring MAC checks reduces communication complexity but adds 8B + 20 hash calls to each AND gate.This added cost is unaffected by the aBit optimization.

B Proof of Thm. 1

The proof reduces active security to the claim that an adversary able to produce an inconsistent bit can guess the global key. A sequence of equivalent games removes MAC queries while preserving winning probability and resource bounds.

  • Security reduction: An inconsistent bit can occur only with negligible probability because producing one is equivalent to guessing the global key ∆.The protocol is passively secure, and absent inconsistency the adversary follows the protocol up to input substitution.
  • Game sequence: The proof models MAC and break interactions through a sequence of games that preserve the adversary’s winning probability.The reductions maintain comparable query complexity and running time, formalized by the no-stronger relation.
  • Game sequence: The first reduction replaces MAC queries with sampled messages while passing the global-key side information to the original adversary.This constructs an adversary for the hybrid game with the same number of queries and linear overhead.
  • Game sequence: The second reduction combines stored MAC values and the break message so that a successful break reveals ∆ in the no-MAC-query game.The algebra shows that the transformed break query equals the global key whenever the original adversary wins.
  • Game sequence: Removing MAC queries does not change the winning probability because the final game ignores them.This yields the corollary that every attacker in the original game has an equally successful, no-stronger attacker in the simplified game.

C Proof of Thm. 2

The proof establishes security by showing that the adversary’s view leaves the masked global-key value uniformly random except with negligible probability. This follows from leakage bounds and random linear-algebraic structure.

  • Simulation: The simulator perfectly answers global-key queries by forwarding them to the ideal functionality.These queries therefore do not affect the remaining simulation analysis.
  • Uniformity argument: The proof defines uniformity of ∆A as independence from the adversary’s view and bounds failure through a single event F.The target failure probability is at most 2^2−ψ.
  • Uniformity argument: The event that too many indices are learned has probability at most 2^−ψ.This is Lemma 5’s bound for the event |S| ≥ τ − n and c = 1.
  • Uniformity argument: Leakage security bounds the leaked information by leakL ≤ τ − κ = 1 under the assumed κ-secure leakage class.This bound is used to control the size of the learned index set.
  • Uniformity argument: Random vectors span {0, 1}^ψ except with probability 2^1−ψ, ensuring the masked value ∆A is uniform outside the combined failure event.Combining the two failure bounds gives Pr[F] ≤ 2^2−ψ.

D Proof of Thm. 4

The proof connects the LaBit construction to OT and equality testing through three intermediate boxes, each linearly reducible to the next. The resulting OT extension yields essentially unbounded active-secure OTs with amortized work linear in κ.

  • Reduction chain: The simulator maps OT inputs to the authenticated-bit parameters by setting Li = Yi,0 and Γi = Yi,0 ⊕ Yi,1.It then chooses colors and distinct labels so that Γi = Λcol(i), and supplies the resulting values to IB1.
  • Reduction chain: The intermediate boxes preserve the protocol’s outputs by deriving the same pairing, guesses, failure event, and authenticated values.For IB2, the simulator determines the most common color and reconstructs outputs matching IB1 exactly.
  • Reduction chain: IB2 is linearly locally reducible to IB1, and IB3 is linearly locally reducible to IB2.Each implementation calls the preceding box while preserving the relevant failure behavior and outputs.
  • Reduction chain: LaBitL(τ, ℓ) is linearly reducible to OT(2τ, ℓ) and EQ(τℓ).This is the stated reduction obtained after composing the intermediate-box reductions.
  • Efficiency: The OT extension produces an essentially unbounded number of active-secure OTs with amortized work linear in κ per OT.The construction starts from a small number of seed OTs and achieves the stated optimal amortized dependence.

F Proof of Thm. 5

The proof gives simulators for both corruption cases in the LaOT protocol. In each case, simulation is perfect unless the adversary queries the random oracle at a hidden key-dependent point, an event shown negligible.

  • Corrupted A: The protocol securely implements LaOT(ℓ) against corrupted A.The simulator receives A’s dealer inputs, checks consistency through LaOT and EQ interactions, and aborts on the same events as the real protocol.
  • Corrupted A: When the bad event F does not occur, the simulator’s messages are distributed exactly as in the real protocol.The random-oracle masking makes the unchecked ciphertext components uniformly random from A’s view.
  • Corrupted A: The bad event F implies that the adversary can compute the honest receiver’s global key ∆A.Because protocol inputs are independent of ∆A during execution, guessing it succeeds only with negligible probability.
  • Corrupted B: The protocol securely implements LaOT(ℓ) against corrupted B.The simulator forwards dealer inputs to LaOT, samples hidden values, and uses random-oracle programming after outputs are released.
  • Corrupted B: For corrupted B, simulation is perfect unless B queries the random oracle on Kc ⊕ (1 ⊕ c)∆B or Kz ⊕ (1 ⊕ z)∆B.If such a query occurs, a modified adversary can recover ∆B; otherwise the relevant masked values are uniformly random.

G Proof of Thm. 6

The proof establishes security by randomly partitioning leaky OTs into buckets, ensuring each bucket contains a receiver-secure OT with overwhelming probability, then applying an OT combiner.

  • The receiver randomly partitions ℓB leaky OTs into ℓ buckets of size B.
  • The probability that every bucket contains an OT whose choice bit is unknown to the adversary exceeds 1 − (2ℓ)^(1−B).
  • A secure OT in every bucket implies protocol security through a standard OT combiner.

H Proof of Thm. 7

The proof shows that the Fig. 19 protocol securely implements LaAND against either corrupted party, while correctness follows for honest parties from the aBit box.

  • For honest sender and receiver, correctness follows immediately from correctness of the aBit box.
  • The protocol securely implements LaAND against a corrupted sender A.
  • Before outputs are released, the global key ∆A is uniformly random to the environment when B is honest.
  • The simulator samples random U and aborts unless the equality-box response and consistency condition pass.
  • Random-oracle behavior makes simulated and real U values perfectly indistinguishable until both corresponding oracle inputs are queried, an event negligible during the protocol.
  • The protocol securely implements LaAND against a corrupted receiver B.

I Proof of Thm. 8

The proof handles a corrupted receiver by showing that leaky triples are unlikely to fill an entire bucket and that one non-leaky triple per bucket suffices for security under iterative combination.

  • The protocol is correct and secure when both parties are honest or A is corrupted.
  • For corrupted B, security is proved by bounding the probability that B learns every x-bit within a bucket, then simulating when each bucket retains an unknown x-bit.
  • A ball is leaky when B learned its x-bit, and γ denotes the number of leaky balls.
  • The probability that B leaky balls occupy one bucket is bounded by requiring a size-B subset of leaky balls to land there.
  • Assuming each bucket has one non-leaky triple, security follows because combining it with other triples preserves a non-leaky result through subsequent combinations.
Loading 1202.3052v1…