Additively homomorphic encryption ⇒ cPIR

Fully-black-box reduction · standard model · Ste98 · security loss: a factor 2 per recursion level, from a hybrid through the all-zero query

Statement

A semantically secure additively homomorphic encryption scheme, with fixed-length ciphertexts and perfect correctness, yields for every constant $\epsilon >0$ a perfectly correct, one-round single-server PIR scheme with communication $O(n^{\epsilon })$ ciphertexts, the hidden factor polynomial in $\lambda$ for each fixed $\epsilon$, so a one-round sublinear one — Ste98.

Sketch

For a $\sqrt{n}\times \sqrt{n}$ database, the client sends $c_j\leftarrow \mathsf{Enc}(\mathsf{pk},[j=b])$ for $j\le \sqrt{n}$, and the server returns, for each row $r$, the homomorphic combination ${\sum }_{j}D[r,j]\cdot c_j$, an encryption of $D[r,b]$; semantic security hides $b$. Recursing on the server’s answer, read as a smaller database of ciphertext bits, lowers the communication as in KO97 — Ste98.

Notes

• With Paillier’s scheme, server-side communication logarithmic in $n$ is achievable: DCR ⇒ One-round sublinear cPIR — Cha04.