FHE ⇒ cPIR

Fully-black-box reduction · standard model · folklore · security loss: a factor log n, from a hybrid over the encrypted index bits

Statement

A compact fully homomorphic encryption scheme yields a one-round single-server PIR scheme with communication $\mathrm{poly}(\lambda ,\log n)$: the client sends encryptions of the $\log n$ bits of its index $i$, and the server homomorphically evaluates the selection function $i\mapsto D[i]$ and returns one ciphertext — folklore.

Sketch

$\mathsf{Setup}(1^{\lambda },1^n)$ outputs $\mathsf{pp}=(1^{\lambda },n)$; $\mathsf{Query}(\mathsf{pp},i)$ samples $(\mathsf{pk},\mathsf{sk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$, writes $i$ in binary as $x_1\cdots x_{\ell }$ with $\ell =O(\log n)$, and outputs $q=(\mathsf{pk},c_1,\dots ,c_{\ell })$ with $c_j\leftarrow \mathsf{Enc}(\mathsf{pk},x_j)$ and $\mathsf{st}=\mathsf{sk}$; $\mathsf{Answer}(D,q)$ outputs $a=\mathsf{Eval}(\mathsf{pk},f_D,c_1,\dots ,c_{\ell })$ for the selection circuit $f_D(x_1\cdots x_{\ell }):=D[i]$; and $\mathsf{Decode}(\mathsf{st},a):=\mathsf{Dec}(\mathsf{sk},a)$, which equals $D[i]$ with probability $1-\mathrm{negl}(\lambda )$ by correctness of the FHE scheme. Compactness bounds $|a|$ by a polynomial in $\lambda$ independent of $f_D$, so $|q|+|a|\le (\ell +2)\cdot \mathrm{poly}(\lambda )=\mathrm{poly}(\lambda ,\log n)$. Query privacy follows from IND-CPA security by a hybrid that switches the $\ell$ ciphertexts from the bits of $i_0$ to those of $i_1$ one at a time, with a factor $\ell$ loss — standard.

Notes

• Compactness is needed: a scheme whose $\mathsf{Eval}$ returns the circuit together with its input ciphertexts is correct and IND-CPA-secure, but its answer here has $\Omega (n)$ bits — standard.
• Efficiency: communication is polylogarithmic in $n$, while the server evaluates a circuit of size $\Theta (n)$ homomorphically, which dominates the cost — folklore. An LWE-based instantiation has communication $\lambda \cdot \mathrm{polylog}(\lambda )+\log n$ bits for a single-bit database entry — BV11.
• Linear homomorphism already suffices for communication $O(n^{\epsilon })$: additively homomorphic encryption ⇒ cPIR — Ste98.