Welcome to the resource topic for 2012/398
Title:
PIRMAP: Efficient Private Information Retrieval for MapReduce
Authors: Travis Mayberry, Erik-Oliver Blass, 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.
ePrint: https://eprint.iacr.org/2012/398
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .