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]$.

The keys are succinct: there is a polynomial $p$ such that $|k_0|,|k_1|\le p(\lambda ,\log N,\log |\mathbb{G}|)$ — GI14, BGI15. Without this bound, sharing the truth table is a DPF for every polynomial-size domain: $k_0\stackrel{\$}{\leftarrow }{\mathbb{G}}^N$, $k_1:=(f_{\alpha ,\beta }(x){)}_{x\in [N]}-k_0$ and $\mathsf{Eval}(b,k_b,x):=k_b[x]$ are correct, perfectly hiding and efficient — standard.

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 a function class $\mathcal{F}$ whose members $f$ are given by descriptions $\hat{f}$: $\mathsf{Gen}(1^{\lambda },\hat{f})$ runs in time $\mathrm{poly}(\lambda ,|\hat{f}|)$ and outputs shares $(k_0,k_1)$ of $f$, such that each key evaluates the function’s additive share, and each key hides $f$ individually. As for DPFs, the keys are succinct: for a polynomial $p$, the keys for $f\in \mathcal{F}$ have length at most $p(\lambda ,|\hat{f}|)$ — BGI15. Here $\mathcal{F}$ contains every point function $f_{\alpha ,\beta }:[N]\to \mathbb{G}$, described by $(\alpha ,\beta )$, so $|{\hat{f}}_{\alpha ,\beta }|=O(\log N+\log |\mathbb{G}|)$. Without this requirement FSS holds with no assumption and need not give a DPF: FSS for $\mathcal{F}=\{0\}$ is trivial, and for all functions $[N]\to \mathbb{G}$ described by their truth tables, additive shares of the table are correct, perfectly hiding and of length $|\hat{f}|$ — standard.

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