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