Leveled FHE ⇒ PIR with polylogarithmic communication

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

Statement

An IND-CPA-secure leveled fully homomorphic encryption scheme yields a one-round single-server PIR scheme with polylogarithmic communication: the client generates a key pair $(\mathsf{pk},\mathsf{sk})$ for depth $L=O(\log n)$ and sends $\mathsf{pk}$ with encryptions of the $\lceil \log n\rceil$ bits of its index, keeping $\mathsf{sk}$ as its state, and the server homomorphically evaluates the selection circuit $f_D(x):=D[x]$, which has depth $O(\log n)$ — folklore.

Sketch

The protocol is that of FHE ⇒ cPIR with depth bound $L=c\log n$ for a constant $c$ fixed by the depth of $f_D$. The public key, the $\lceil \log n\rceil$ input ciphertexts and the evaluated ciphertext each have length polynomial in $\lambda$ and $L$, so $|q|+|a|=\mathrm{poly}(\lambda ,\log n)$; correctness follows from that of the leveled scheme and query privacy from its IND-CPA security, as in the compact case — folklore.