Usable PIR

In [22] we showed 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√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²n) per query (as compared to e.g., O(log⁴n) for existing approaches). We achieve these novel results by applying new insights based on probabilistic analyses of data shuffling algorithms to Oblivious RAM [17], 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.