Skip to content

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