Φ-Hiding ⇒ cPIR

Standard model · CMS99

Statement

Under the Φ-hiding assumption, there is a one-round single-server PIR scheme with total communication polylogarithmic in the database size $n$ — CMS99, which introduces the assumption.

Sketch

The client maps each index $j$ to a prime $p_j$ by a shared prime-sequence generator and sends a modulus $m$ with $p_i\mid \varphi (m)$, of bit length $\Theta (\max (\lambda ,\log {\max }_j{p}_j))$ so that every $p_j\le m^{1/4-\epsilon }$ as Φ-hiding requires, which keeps $|m|=\mathrm{poly}(\lambda ,\log n)$ for primes of $\mathrm{poly}(\log n)$ bits; by Φ-hiding $m$ then hides $p_i$, together with an $x\in {\mathbb{Z}}_m^{\ast }$ that is not a $p_i$-th residue. The server returns $x^Q\mathrm{mod}m$ for $Q={\prod }_j{p}_j^{b_j}$, where $b_j$ is the $j$-th database bit; knowing the factorization of $m$, the client tests whether the reply is a $p_i$-th residue, which holds iff $b_i=1$.

Notes

• A simple variant of the Φ-hiding assumption gives single-database PIR with communication $O(k+d)$ for a $d$-bit block and security parameter $k\ge \log n$, hence constant rate on large blocks; the scheme is stated for general groups with hidden smooth subgroups — GR05.