DCR ⇒ One-round sublinear cPIR

Standard model · Cha04 · security loss: polynomial

Statement

If DCR is hard, there is a perfectly correct, one-round single-server PIR scheme, built from Paillier’s cryptosystem, whose server-side communication is logarithmic in the database size $n$ and whose client-side communication is $O(n^{\epsilon }\log n)$ for a constant $\epsilon <1$, the factors polynomial in $\lambda$, so a one-round sublinear one — Cha04.

Sketch

View the database as a $\sqrt{n}\times \sqrt{n}$ matrix with target entry $(a,b)$: the client sends Paillier encryptions $c_j\leftarrow \mathsf{Enc}(\mathsf{pk},[j=b])$ for $j\le \sqrt{n}$ under a modulus $N$, and for each row $r$ the server computes $z_r:={\prod }_j{c}_j^{D[r,j]}\mathrm{mod}{N}^2$, an encryption of $D[r,b]$ by the additive homomorphism. Instead of returning the $z_r$, the server reads them, each written as $O(1)$ plaintexts of a second level of Paillier encryption, as a $\sqrt{n}$-entry database and selects $z_a$ the same way with an encrypted unit vector for $a$, and the client decrypts the second level, then the first; the query is $O(\sqrt{n})$ ciphertexts and public keys and the answer $O(1)$ ciphertexts, each of $\mathrm{poly}(\lambda )$ bits, which meets the bounds above with $\epsilon =1/2$ — Cha04. Semantic security of Paillier’s scheme under DCR, through a hybrid over the query ciphertexts, hides $(a,b)$ — Pai99.