Φ-Hiding ⇒ cPIR

Standard model · CMS99

Statement

Under the Φ-hiding assumption, there is a 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)$, which by Φ-hiding 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 variant of Φ-hiding yields single-database PIR with constant communication rate — GR05.