DPF ⇒ Computational Multi-server PIR

Fully-black-box reduction · standard model · GI14 · security loss: tight: one oracle call, advantage-preserving

Statement

A DPF for domain $[N]$ and range ${\mathbb{Z}}_2$ yields a 2-server computational PIR for an $N$-bit database $D$ in which each query is one DPF key and each answer one bit: the client sends $(k_0,k_1)\leftarrow \mathsf{Gen}(1^{\lambda },i,1)$, one key to each server; server $b$ returns $a_b={\sum }_{j\in [N]}D[j]\cdot \mathsf{Eval}(b,k_b,j)$; and $D[i]=a_0+a_1$ — GI14.

Sketch

Correctness: $a_0+a_1={\sum }_{j}D[j]\cdot f_{i,1}(j)=D[i]$ by DPF correctness. Privacy: server $b$‘s entire view of a query is $k_b$, so a distinguisher between queries for $i$ and $i^{\prime }$ is an adversary against DPF hiding for key $k_b$ with the same advantage.

\begin{algorithm}
\algname{Algorithm}
\caption{$\Query(i)$}
\begin{algorithmic}
\State $(k_0, k_1) \gets \Gen(1^\secpar, i, 1)$
\Return $(k_0, k_1)$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Answer(b, k_b, D)$}
\begin{algorithmic}
\State $a_b \gets \sum_{j \in [N]} D[j] \cdot \Eval(b, k_b, j)$
\Comment{sum in $\ZZ_2$}
\Return $a_b$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Recon(i, a_0, a_1)$}
\begin{algorithmic}
\Return $a_0 + a_1$
\end{algorithmic}
\end{algorithm}

Notes

• With the PRG-based DPF of GI14 (PRG ⇒ DPF), each query has length $O(\lambda \cdot (\log N{)}^{{\log }_{2}3})$, polylogarithmic in $N$ when $\lambda =\mathrm{polylog}(N)$, as a strong one-way function allows, and each server’s computation is comparable to applying a symmetric encryption scheme to the entire database — GI14.
• For every constant $\epsilon >0$ there is a one-round two-server computational PIR with communication $O(n^{\epsilon })$, built from pseudorandom generators and storing the database unencoded — CG97; with one-bit answers its queries have length $2^{O(\sqrt{\log n})}$, against the polylogarithmic queries here — GI14. Two-server information-theoretic PIR has communication $n^{O(\sqrt{\log \log n/\log n})}=n^{o(1)}$ — DG15 — so the $O(n^{\epsilon })$ bound no longer needs an assumption.