QR ⇒ cPIR (Kushilevitz–Ostrovsky)

Fully-black-box reduction · standard model · KO97 · security loss: a factor 2 at any recursion depth: setting every non-residue of the query to x r_j^2 for the QR challenge x makes each index’s query indistinguishable from the all-residue query

Statement

If QR is hard, then for every constant $\epsilon >0$ there is a perfectly correct, one-round single-server PIR scheme for $n$-bit databases with communication $O(n^{\epsilon })$, the hidden factor polynomial in $\lambda$ for each fixed $\epsilon$, so a one-round sublinear one — KO97. The basic scheme has communication $O(\sqrt{n}\lambda )$.

Sketch

View the database as a $\sqrt{n}\times \sqrt{n}$ matrix and let the client want entry $(a,b)$. The client sends a modulus $N$ and $y_1,\dots ,y_{\sqrt{n}}$ of Jacobi symbol $+1$, with $y_b$ a non-residue and the others residues. For each row $r$ the server returns $z_r:={\prod }_j{w}_{r,j}$, where $w_{r,j}:=y_j^2$ if $D[r,j]=0$ and $w_{r,j}:=y_j$ otherwise, so $z_a$ is a residue iff $D[a,b]=0$, which the client decides with the factorization of $N$. Hiding which $y_j$ is the non-residue is the QR assumption; applying the scheme recursively to the server’s answer, read as a smaller database, lowers the communication to $O(n^{\epsilon })$ — KO97.

Notes

• Efficiency: the server performs $\Theta (n)$ modular multiplications; every single-server PIR scheme without preprocessing must touch every database bit, since an untouched bit reveals that it was not queried — standard.
• Polylogarithmic communication is achieved under Φ-hiding — CMS99 — and, through trapdoor hash functions, under QR and DDH (TDH ⇒ cPIR) — DGI+19. With Paillier encryption the server’s reply alone can be made logarithmic (DCR ⇒ One-round sublinear cPIR) — Cha04.