Distributed Point Functions

A distributed point function (DPF) allows one to split the description of a point function $f_{\alpha ,\beta }$ (which outputs $\beta$ on input $\alpha$ and $0$ everywhere else) into two succinct keys $(k_0,k_1)$ such that $k_0$ and $k_1$ individually reveal nothing about $\alpha$ or $\beta$, but any party holding one key can evaluate the function’s share at any point. Introduced by Gilboa and Ishai — GI14.

Syntax

A distributed point function for domain $[N]$ and range $\mathbb{G}$ is a tuple of efficient algorithms $\mathsf{DPF}=(\mathsf{Gen},\mathsf{Eval})$:

• $\mathsf{Gen}(1^{\lambda },\alpha ,\beta )\to (k_0,k_1),$ is a randomized key generation algorithm that takes a special point $\alpha \in [N]$ and output value $\beta \in \mathbb{G}$, and outputs two evaluation keys $k_0,k_1$,
• $\mathsf{Eval}(b,k_b,x)\to y_b\in \mathbb{G},$ is a deterministic algorithm for $b\in \{0,1\}$ that evaluates the $b$-th share of the point function at input $x\in [N]$.

Properties

Correctness

For all $\lambda \in \mathbb{N}$, $\alpha \in [N]$, $\beta \in \mathbb{G}$, and $(k_0,k_1)\leftarrow \mathsf{Gen}(1^{\lambda },\alpha ,\beta )$, the shares sum to the point function: $\mathsf{Eval}(0,k_0,x)+\mathsf{Eval}(1,k_1,x)=f_{\alpha ,\beta }(x)\text{for all }x\in [N],$ where $f_{\alpha ,\beta }(x)=\beta$ if $x=\alpha$ and $0$ otherwise.

Hiding (Security)

For $b\in \{0,1\}$, key $k_b$ reveals nothing about $(\alpha ,\beta )$: for all efficient $\mathcal{A}$, $\left|2\mathrm{Pr}\left[\mathcal{A}(1^{\lambda },k_b)=\alpha \right]-1\right|\le \mathrm{negl}(\lambda ).$

Variations

Function secret sharing (FSS)

DPFs are a special case of function secret sharing (FSS), introduced by Boyle, Gilboa, and Ishai — BGI15, BGI16. FSS generalizes DPFs to arbitrary function classes $\mathcal{F}$: one generates shares $(k_0,k_1)$ of any $f\in \mathcal{F}$, such that each key evaluates the function’s additive share, and each key hides $f$ individually.

Multi-point functions

Distributes a function that is non-zero on multiple points. Can be built by composing multiple DPFs.

Other results

• DPFs can be constructed from OWFs (concretely, from PRGs) with key size $O(\lambda \log N)$ — GI14
• Computational 2-server PIR can be built from DPFs (the query is a DPF key pair, and each server evaluates its share) — GI14
• DPFs generalize to FSS for richer function classes including intervals, halfspaces, and decision trees — BGI15, BGI16
• DPF key size lower bound: any 2-server DPF for $N$-element domain has keys of size $\Omega (\lambda +\log N)$ — standard