Peter Williams, Radu Sion. Usable PIR. Proceedings of the 2008 Network
and Distributed System Security Symposium (NDSS) 2008.

Abstract

We have previously shown that existing single-server computational
private information retrieval (PIR) protocols for the purpose of
preserving client access patterns leakage are orders of magnitude
slower than trivially transferring the entire data sets to the
inquiring clients. We thus raised the issue of designing efficient PIR
mechanisms in practical settings.

In this paper we introduce exactly such a technique, guaranteeing
access pattern privacy against a computationally bounded adversary, in
outsourced data storage, with communication and computation overheads
orders of magnitude better than existing approaches. In the presence
of a small amount (O(sqrt n), where n is the size of the database) of
temporary storage, clients can achieve access pattern privacy with
communication and computational complexities of less than O(log^2 n)
per query (as compared to e.g., O(log^4 n) for existing approaches).

We achieve these novel results by applying new insights based on
probabilistic analyses of data shuffling algorithms to Oblivious RAM,
allowing us to significantly improve its asymptotic complexity.  This
results in a protocol crossing the boundary between theory and
practice and becoming generally applicable for access pattern privacy.
We show that on off the shelf hardware, large data sets can be queried
obliviously orders of magnitude faster than in existing work.