Function Secret Sharing¶
Authors: Elette Boyle; Niv Gilboa; Yuval Ishai
Year: 2015
Venue: EUROCRYPT 2015
type: scheme collection: schemes status: auto
Links: DOI
Visual lesson: Function secret sharing (FSS) · Scheme table row: Function secret sharing (FSS)
Summary¶
Auto-extracted summary (unreviewed)
Boyle, Gilboa and Ishai introduce function secret sharing (FSS), which splits a function from a class F into p succinct shares that sum to f while any strict subset hides f, generalising distributed point functions (DPF). They give an improved two-party DPF from any PRG with key length O(lambda n) instead of O(lambda n^{log2 3}), the first nontrivial p-party DPF for p >= 3 with a near-quadratic improvement over naive truth-table sharing, PRG-based FSS for interval and partial-matching functions, and a study of general FSS (construction from obfuscation, implausibility from one-way functions, completeness, relation to PRFs).
Abstract¶
Motivated by the goal of securely searching and updating distributed data, we introduce and study the notion of function secret sharing (FSS). This new notion is a natural generalization of distributed point functions (DPF), a primitive that was recently introduced by Gilboa and Ishai (Eurocrypt 2014). Given a positive integer p ≥2 and a class F of functions f : {0, 1}n →G, where G is an Abelian group, a p-party FSS scheme for F allows one to split each f ∈F into p succinctly described functions fi : {0, 1}n →G, 1 ≤i ≤p, such that: (1) p i=1 fi = f, and (2) any strict subset of the fi hides f. Thus, an FSS for F can be thought of as method for succinctly performing an “additive secret sharing” of functions from F. The original definition of DPF coincides with a twoparty FSS for the class of point functions, namely the class of functions that have a nonzero output on at most one input. We present two types of results. First, we obtain efficiency improvements and extensions of the original DPF construction. Then, we initiate a systematic study of general FSS, providing some constructions and establishing relations with other cryptographic primitives. More concretely, we obtain the following main results: – Improved DPF. We present an improved (two-party) DPF construction from a pseudorandom generator (PRG), reducing the length of the key describing each fi from O(λ · nlog2 3) to O(λn), where λ is the PRG seed length. – Multi-party DPF. We present the first nontrivial construction of a p-party DPF for p ≥3, obtaining a near-quadratic improvement over a naive construction that additively shares the truth-table of f. This constrcution too can be based on any PRG. – FSS for simple functions. We present efficient PRG-based FSS constructions for natural function classes that extend point functions, including interval functions and partial matching functions. – A study of general FSS. We show several relations between general FSS and other cryptographic primitives. These include a construction of general FSS via obfuscation, an indication for the Research supported by the European Union’s Tenth Framework Programme (FP10/2010-2016) under grant agreement no. 259426 ERC-CaC. The first and third authors were additionally supported by ISF grants 1361/10 and 1709/14 and BSF grant 2012378. c ⃝International Association for Cryptologic Research 2015 E. Oswald and M. Fischlin (Eds.): EUROCRYPT 2015, Part II, LNCS 9057, pp. 337–367, 2015. DOI: 10.1007/978-3-662-46803-6 12 338 E. Boyle et al. implausibility of constructing general FSS from weak cryptographic assumptions such as the existence of one-way functions, a completeness result, and a relation with pseudorandom functions.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | definition of function secret sharing (FSS) generalising DPF | llm | 0.85 |
| contribution | improved two-party DPF with O(lambda n) key size from any PRG | llm | 0.85 |
| contribution | first nontrivial multi-party (p >= 3) DPF construction | llm | 0.85 |
| contribution | efficient FSS for interval functions and partial matching functions | llm | 0.85 |
| contribution | relations of general FSS to obfuscation, one-way functions and PRFs | llm | 0.85 |
| schemes | function secret sharing | llm | 0.85 |
| schemes | distributed point functions | llm | 0.85 |
| schemes | additive secret sharing | llm | 0.85 |
| schemes | PRG-based constructions | llm | 0.85 |
| tasks | secure search and update of distributed data | llm | 0.85 |
| threat model | p-party; any strict subset of share holders learns nothing about the function | llm | 0.85 |
| interaction | pure MPC | llm | 0.85 |
| limitations | evidence that general FSS cannot be built from weak assumptions such as one-way functions | llm | 0.85 |
| limitations | multi-party DPF improvement is only near-quadratic over the naive construction | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | two-party DPF key length: O(lambda n), down from O(lambda n^{log2 3}) (PRG seed length lambda, input length n) | llm | 0.85 |
| key result | multi-party DPF cost: near-quadratic improvement over naive truth-table sharing (p >= 3 parties, PRG-based) | llm | 0.85 |
Scheme card: Function secret sharing (FSS)¶
| Group | 9. Non-HE cryptographic alternatives to CKKS |
| Kind | Primitive |
| Hardness assumption | PRG / OWF |
| Plaintext type | Fixed point (DPF/DCF gates) |
| SIMD packing | Vectorized |
| Bootstrapping | n/a |
| Post-quantum | Yes |
| Status | Active SOTA |
| Fit for LLM inference | Basis of SIGMA (GPU 2PC GPT inference). Low online rounds but needs a dealer. |
| Libraries | EzPC |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Function secret sharing 155 [p.1], Secret sharing 47 [p.1], PIR 23 [p.3], MPC 18 [p.9], Garbled circuits 10 [p.9], Oblivious transfer 4 [p.4], TFHE 3 [p.5], Functional encryption 2 [p.29]
- technique: Two-party computation 6 [p.1], Bootstrapping 3 [p.28], Semi-honest model 2 [p.26]
- assumption: LWE 5 [p.5], Lattice-based 4 [p.26]
- task: Language modeling / generation 15 [p.6]
- topic: Homomorphic encryption 28 [p.5]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s53-0_function-secret-sharing.pdf |
schemes | 31 | 431.5 KB | 20e7cbbf2904 |
Database key: function-secret-sharing · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set function-secret-sharing COLUMN VALUE