PRG ⇒ DPF

Fully-black-box reduction · standard model · GI14

Statement

If a PRG with seed length $\lambda$ exists, there is a two-party DPF for domain $[N]$ with keys of length $O(\lambda \cdot (\log N{)}^{{\log }_{2}3})$: the shares satisfy $\mathsf{Eval}(0,k_0,x)\oplus \mathsf{Eval}(1,k_1,x)=f_{\alpha ,\beta }(x)$ for all $x\in [N]$, and the scheme is hiding — GI14. BGI15 reduce the key length to $O(\lambda \log N)$ with a PRG-based tree construction, and BGI16 shrink those keys by roughly a further factor of 4 and reduce the computational cost.