Date Added: Oct 2012
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 real-world 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.