On the Computational Practicality of Private Information Retrieval
Radu Sion
Department of Computer Science
Stony Brook University
Abstract
We explore the limits of single-server computational private information
retrieval (PIR) for the purpose of preserving client access patterns
leakage. We show that deployment of non-trivial single server PIR protocols
on real hardware of the recent past would have been orders of magnitude less
time-efficient than trivially transferring the entire database. We stress
that these results are beyond existing knowledge of mere ``impracticality''
under unfavorable assumptions. They rather reflect an inherent limitation
with respect to modern hardware, likely the result of a communication-cost
centric protocol design. We argue that this is likely to hold on
non-specialized traditional hardware in the foreseeable future. We validate
our reasoning in an experimental setup on modern off-the-shelf hardware.