DPF ⇒ Multi-point functions

Fully-black-box reduction · standard model · folklore · security loss: factor $t$ over the DPF key-indistinguishability advantage (hybrid over the $t$ instances)

Statement

For distinct points ${\alpha }_1,\dots ,{\alpha }_t\in [N]$ and values ${\beta }_1,\dots ,{\beta }_t\in \mathbb{G}$, the multi-point function ${\sum }_{i=1}^t{f}_{{\alpha }_i,{\beta }_i}$ is shared by running the key generation of a DPF independently on each $({\alpha }_i,{\beta }_i)$: party $b$ holds $(k_{b,1},\dots ,k_{b,t})$ and evaluates ${\sum }_{i=1}^t\mathsf{Eval}(b,k_{b,i},x)$. This is a correct multi-point FSS, hiding between any two multi-point functions with the same number $t$ of points if the DPF is hiding: for every efficient $\mathcal{A}$ there is an efficient $\mathcal{B}$ whose DPF hiding advantage is at least a $1/t$ fraction of $\mathcal{A}$‘s — folklore.

Sketch

Correctness is additivity of the shares. Hiding is a hybrid over the $t$ instances that swaps one DPF key at a time; $\mathcal{B}$ picks the swapped instance at random and generates the other $t-1$ keys itself.

Notes

• BCGI18 define multi-point FSS and build it from DPFs via combinatorial batch codes, with full-domain evaluation linear in $N$ rather than the $t$ full-domain DPF evaluations of the construction above.