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.