One-round sublinear cPIR ⇒ Keyword PIR

Fully-black-box reduction · standard model · CGN98 · security loss: a factor $d$ for a search structure of depth $d$, from a hybrid over its $d$ levels with one PIR query per level

Statement

Any search structure for keywords combines with any single-server PIR scheme into a keyword PIR, without changing how the server maintains the structure: the client walks the structure, retrieving each node it visits with the PIR — CGN98. With a balanced binary search tree over $n$ keywords of $\ell$ bits with $m$-bit values and a one-round sublinear PIR, the walk has $d=\lceil {\log }_2(n+1)\rceil$ rounds and communication $p^{\prime }(\lambda ,\ell ,m)\cdot n^{c^{\prime }}$ for a polynomial $p^{\prime }$ and a constant $c^{\prime }<1$ — standard.

Sketch

Publish level $j$ of a balanced binary search tree on the keywords as a database of $2^j$ entries in heap order, each holding a keyword and its value, padded with dummy entries so that every walk visits all $d$ levels. Starting at the root, the client retrieves one entry per level with the PIR, answering one query on each bit-slice of the level, and descends by comparing $w$ with the retrieved keyword. A hybrid that switches the queried index one level at a time turns any keyword-privacy distinguisher into a PIR query-privacy distinguisher, since the reduction knows the database and both keywords and so can compute every other level’s index — standard.

Notes

• Efficiency: level $j$ costs one PIR query and $\ell +m$ answers on a $2^j$-entry database, so with $|q|+|a|\le p(\lambda )\cdot n^c$ the total communication is $O((\ell +m)\cdot p(\lambda )\cdot n^c\log n)$, and the server’s work is linear in each level — standard.
• With two servers, one-way functions give keyword PIR whose queries have length polynomial in the keyword size, whose answers are single bits, and which never errs — GI14.