Paper 2012/398

PIRMAP: Efficient Private Information Retrieval for MapReduce

Travis Mayberry, Erik-Oliver Blass, and Agnes Hui Chan

Abstract

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 close to optimal communication complexity with query times significantly faster than previous schemes. To achieve this, PIRMAP uses a special case of Lipmaa's PIR protocol that allows for optimal parallel computation during the "Map" phase of MapReduce, and homomorphic aggregation in the "Reduce" phase. To improve computational cost, we also use newer, faster homomorphic encryption which makes our scheme practical for databases of useful size, while keeping the communication costs low. 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Financial Cryptography 2013
Keywords
private information retrievalcloud computingmap reduce
Contact author(s)
travism @ ccs neu edu
History
2013-09-03: last of 6 revisions
2012-07-23: received
See all versions
Short URL
https://ia.cr/2012/398
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/398,
      author = {Travis Mayberry and Erik-Oliver Blass and Agnes Hui Chan},
      title = {PIRMAP: Efficient Private Information Retrieval for MapReduce},
      howpublished = {Cryptology ePrint Archive, Paper 2012/398},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/398}},
      url = {https://eprint.iacr.org/2012/398}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.