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 )$ beyond $[N]$ and $\mathbb{G}$:

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{hide}}_{\mathsf{DPF},\calA,b}(\secpar)$}
\begin{algorithmic}
\State $(\alpha_0, \beta_0, \alpha_1, \beta_1, \stA) \gets \calA(1^\secpar)$; $c \getsr \bits$
\State $(k_0, k_1) \gets \Gen(1^\secpar, \alpha_c, \beta_c)$
\State $c' \gets \calA(k_b, \stA)$
\Return $[c' = c]$
\end{algorithmic}
\end{algorithm}

A DPF $\mathsf{DPF}$ is hiding if for all $b\in \{0,1\}$ and all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{DPF},\mathcal{A},b}^{\mathrm{hide}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{DPF},\mathcal{A},b}^{\mathrm{hide}}(\lambda )=1\right]-1\right|$$

is negligible — GI14, BGI15.

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

• OWF ⇒ PRG
• PRG ⇒ DPF
• DPF ⇒ Computational Multi-server PIR
• DPFs generalize to FSS for richer function classes including intervals, halfspaces, and decision trees — BGI15, BGI16
• For $\beta \ne 0$, correctness makes $(k_0,k_1)$ determine $\alpha$, so $|k_0|+|k_1|\ge \log N$ — folklore

Participates in

Builds on Distributed Point Functions

• DPF ⇒ Computational Multi-server PIR
• DPF ⇒ Multi-point functions
• Function secret sharing (FSS) ⇒ DPF (via Function secret sharing (FSS))

Produces Distributed Point Functions

• DPF ⇒ Multi-point functions (via Multi-point functions)
• Function secret sharing (FSS) ⇒ DPF
• PRG ⇒ DPF