One-round sublinear cPIR ⇒ CRHF

Standard model · IKO05

Statement

A perfectly correct, one-round single-server PIR scheme with communication $p(\lambda )\cdot n^c$ for a polynomial $p$ and a constant $c<1$, that is, a one-round sublinear one, yields a collision-resistant hash function family — IKO05.

Sketch

The key is a tuple of queries for uniform indices, and the hash of an input is the tuple of answers on an encoding of it as a database, shorter than the input. By perfect correctness, two colliding databases agree at every queried index, so a collision reveals positions that were not queried, and a collision finder becomes a query-privacy distinguisher — IKO05.

Notes

• The hash outputs $t=\omega (\log k)$ answers to independent queries on an encoding of its $k$-bit input, so it compresses only when $t\cdot \beta (n)<k$ for answer length $\beta (n)$ — IKO05. Interactive schemes, and schemes in which the server sends $n-o(n)$ bits such as the trapdoor-permutation construction, do not meet the hypothesis — KO00.
• Collision resistance does not follow from one-way permutations by relativizing constructions (No relativizing reduction from OWP to CRHF) — Sim98.
• The same paper derives collision-resistant hashing from homomorphic encryption: homomorphic encryption ⇒ CRHF — IKO05.