International Association
for Cryptologic Research

Private Information Retrieval (PIR) allows for retrieval of bits from a

database in a way that hides a user\'s access pattern from the server. However, its practicality in a cloud computing setting has recently been questioned. In such a

setting, PIR\'s enormous computation and communication overhead is

expected to outweigh any cost saving advantages of cloud computing.

This paper presents PIRMAP, a practical, highly efficient protocol for

PIR in MapReduce, a widely supported cloud computing API. PIRMAP focuses especially on the retrieval of

large files from the cloud, where it achieves optimal communication

complexity ($O(l)$ for retrieval of an $l$ bit file) with query times significantly faster than previous schemes. To achieve this, PIRMAP arranges files so parallel evaluation can be done during the ``Map\'\' phase

of MapReduce and aggregation can be carried out via an efficient additively

homomorphic encryption scheme in the ``Reduce\'\' phase. PIRMAP has been implemented and tested in Amazon\'s public cloud with total database sizes of up to 1~TByte. Our performance evaluations show that

PIRMAP is more than one order of magnitude cheaper and faster than

``trivial PIR\'\' on Amazon and adds only $20\\%$ overhead to a

theoretical optimal PIR.