Function Secret Sharing (FSS)

The foundational FSS scheme for point functions. A DPF splits a function f(x) that outputs a secret value β only at a specific point α into two keys. Each key individually reveals nothing about α or β, but when evaluated at every point in the domain and XORed together, the secret is recovered only at x=α.

• Key Size: O(λ log N) bits for a domain of size N, where λ is the security parameter
• Evaluation: Each party evaluates their key locally, requiring zero interaction
• Use Case: Private information retrieval (PIR) and secure database queries

An FSS scheme for interval functions where f(x) = β if x < α and 0 otherwise. DCFs enable efficient private comparisons without bit-by-bit circuit evaluation. The construction uses a binary tree representation of the comparison threshold, with shares encoding the path to the boundary.

• Efficiency: Avoids expensive garbled circuit comparisons
• Communication: Only the initial key distribution requires interaction; evaluation is fully non-interactive
• Application: Secure range queries, private decision tree evaluation, and threshold-based analytics

FSS supports a growing taxonomy of efficiently shareable function families beyond point and comparison functions. Each class exploits specific algebraic structure to achieve compact key sizes.

• Splittable Functions: Functions whose truth table can be recursively decomposed
• Decision Trees: Entire tree models can be shared as a collection of DCFs
• Sparse Functions: Functions with few non-zero outputs in a large domain
• Linear Combinations: Multiple FSS shares can be combined to represent more complex functions
• Limitation: Not all functions are efficiently shareable; general circuits still require garbled circuits or full MPC

FSS operates in a two-party model where a dealer generates and distributes keys to two non-colluding servers. Clients send queries to both servers, which evaluate their shares locally and return results. The client XORs the responses to recover the output.

• Trust Assumption: The two servers must not collude
• Client Role: The client is typically the party receiving the result, not contributing input
• Dealer Role: Can be a trusted third party or implemented via a secure distributed setup protocol
• Advantage over Garbled Circuits: Eliminates the need for interactive evaluation for supported function classes

FSS achieves optimal communication for the supported function classes. After the one-time key distribution phase, the online evaluation phase requires only a single round of communication: the client sends a query to each server and receives one response.

• Key Distribution: One-time cost proportional to key size
• Online Phase: 1 round, O(1) or O(λ) bits per query
• Comparison: Garbled circuits require O(κ) bits per AND gate and multiple rounds; FSS eliminates this for point and comparison functions
• Practical Impact: Enables sub-second private queries over billion-entry databases

FSS provides information-theoretic or computational security depending on the construction. Each key individually is uniformly random and reveals no information about the underlying function, threshold, or output value.

• Perfect Secrecy: For DPF with information-theoretic constructions, a single key gives zero information about α or β
• Computational Hiding: Some efficient constructions rely on pseudorandom generators (PRGs) and achieve computational security
• Malicious Security: Standard FSS assumes semi-honest servers; extensions using verifiable secret sharing or MACs can detect cheating
• Composability: FSS can be combined with other MPC primitives while maintaining security under the universal composability framework

The most fundamental and widely-used FSS scheme. A DPF splits a point function f(x) that evaluates to a secret value at a single target point and zero elsewhere. Key properties:

• Compact shares: Each share's size is logarithmic in the domain size, not linear
• Efficient evaluation: Parties locally evaluate their share on every point in the domain
• Applications: Private information retrieval (PIR), secure database queries, and anonymous messaging