Skip to content

Breaking the Circuit Size Barrier for Secure Computation Under DDH

Authors: Boyle, Gilboa, Ishai
Year: 2016
Venue: CRYPTO 2016

type: scheme collection: schemes status: auto

Links: ePrint 2016/585

Visual lesson: Homomorphic secret sharing (HSS) · Scheme table row: Homomorphic secret sharing (HSS)

Summary

Auto-extracted summary (unreviewed)

Under the DDH assumption, constructs a 2-out-of-2 (homomorphic) secret sharing scheme in which shares of an input can be locally evaluated on any branching program of size S, with the two output bits XORing to the result except with failure probability delta, plus a public-key variant for multi-client inputs. This yields, without FHE, secure two-party computation of branching programs and formulas with communication linear in the input size, 2PC for leveled boolean circuits with O(S/log S) communication, function secret sharing for branching programs, and 1-round 2-server PIR for branching-program queries.

Abstract

Under the Decisional Diffie-Hellman (DDH) assumption, we present a 2-out-of-2 secret sharing scheme that supports a compact evaluation of branching programs on the shares. More concretely, there is an evaluation algorithm Eval with a single bit of output, such that if an input w ∈{0, 1}n is shared into (w0, w1), then for any deterministic branching program P of size S we have that Eval(P, w0) ⊕Eval(P, w1) = P(w) except with at most δ failure probability. The running time of the sharing algorithm is polynomial in n and the security parameter λ, and that of Eval is polynomial in S, λ, and 1/δ. This applies as a special case to boolean formulas of size S or boolean circuits of depth log S. We also present a public-key variant that enables homomorphic computation on inputs contributed by multiple clients. The above result implies the following DDH-based applications: • A secure 2-party computation protocol for evaluating any branching program or formula of size S, where the communication complexity is linear in the input size and only the running time grows with S. • A secure 2-party computation protocol for evaluating leveled boolean circuits of size S with communication complexity O(S/ log S). • A 2-party function secret sharing scheme, as defined by Boyle et al. (Eurocrypt 2015), for general branching programs (with inverse polynomial error probability). • A 1-round 2-server private information retrieval scheme supporting general searches expressed by branching programs. Prior to our work, similar results could only be achieved using fully homomorphic encryption. We hope that our approach will lead to more practical alternatives to known fully homomorphic encryption schemes in the context of low-communication secure computation.
Source: pdf

Extracted details

Field Value Source Confidence
contribution DDH-based 2-out-of-2 secret sharing with compact homomorphic evaluation of branching programs llm 0.80
contribution public-key variant enabling homomorphic computation on inputs from multiple clients llm 0.80
contribution 2PC for branching programs and formulas with communication linear in the input size llm 0.80
contribution 2PC for leveled boolean circuits with O(S/log S) communication, breaking the circuit size barrier llm 0.80
contribution 2-party function secret sharing for general branching programs llm 0.80
contribution 1-round 2-server PIR supporting branching-program searches llm 0.80
schemes homomorphic secret sharing llm 0.80
schemes secret sharing llm 0.80
schemes function secret sharing llm 0.80
tasks secure two-party computation llm 0.80
tasks private information retrieval llm 0.80
threat model two-party / two-server secure computation under DDH llm 0.80
interaction pure MPC llm 0.80
limitations evaluation has an inverse-polynomial failure probability delta and running time grows with 1/delta llm 0.80
limitations compact evaluation applies to branching programs / formulas (depth log S circuits), not arbitrary circuits llm 0.80
llm relevance low llm 0.80
key result communication complexity: linear in input size (independent of program size S) (2PC for branching programs or formulas of size S) llm 0.80
key result communication complexity: O(S/log S) (2PC for leveled boolean circuits of size S) llm 0.80
key result evaluation running time: polynomial in S, lambda and 1/delta (Eval with failure probability delta) llm 0.80

Scheme card: Homomorphic secret sharing (HSS)

Group 9. Non-HE cryptographic alternatives to CKKS
Kind Primitive
Hardness assumption DDH (later LWE, DCR)
Plaintext type Small integers / branching programs
SIMD packing No
Bootstrapping n/a
Post-quantum Depends
Status Niche
Fit for LLM inference Two servers evaluate locally on shares with no interaction, a middle ground between FHE and MPC.

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: Secret sharing 101 [p.1], ElGamal 76 [p.4], Function secret sharing 48 [p.1], Homomorphic secret sharing 37 [p.3], MPC 29 [p.1], PIR 25 [p.1], Oblivious transfer 4 [p.28], Multi-key HE 2 [p.4], Threshold HE 2 [p.3], Zero-knowledge proofs 2 [p.27]
  • model: Decision tree 1 [p.44]
  • technique: Two-party computation 15 [p.2], Compiler 4 [p.4], Bootstrapping 2 [p.42], Non-interactive 2 [p.21], Malicious model 2 [p.4]
  • assumption: DDH 55 [p.1], LWE 3 [p.4]
  • task: Language modeling / generation 5 [p.4]
  • topic: Homomorphic encryption 37 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s54-0_breaking-the-circuit-size-barrier-for-secure-computation-und.pdf schemes 47 576.7 KB 97e923acea74

Database key: breaking-the-circuit-size-barrier-for-secure-computation-under-ddh · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set breaking-the-circuit-size-barrier-for-secure-computation-under-ddh COLUMN VALUE