PRG ⇒ DPF

Fully-black-box reduction · standard model · GI14 · security loss: polynomial: a factor the number of PRG invocations in key generation, from the hybrid over them

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.

Sketch

In the tree construction of BGI15, in the form given by BGI16, $k_b$ holds a root seed and one $O(\lambda )$-bit correction word per level, common to both keys; $\mathsf{Eval}(b,k_b,x)$ walks a binary tree of depth $\log N$ along the bits of $x$, expanding the current seed with the PRG into a seed and a control bit for each child and applying the level’s correction word iff the parent’s control bit is 1. $\mathsf{Gen}$ chooses the correction words so that the two parties’ seeds and control bits coincide at every node off the path to $\alpha$, while on the path the seeds are pseudorandom and the control bits differ; the evaluations therefore cancel at every leaf $x\ne \alpha$, and a final correction word, applied by the party whose control bit at $\alpha$ is 1, makes them XOR to $\beta$ at $\alpha$. Hiding follows by a hybrid over the levels from the root down: the other party’s on-path seed enters $k_b$ only through its PRG expansion, and replacing that expansion by a uniform string makes the next correction word uniform and the next on-path seed fresh.