Abstract
Private Information Retrieval (PIR) allows a user to retrieve bits from a database while hiding the user’s access pattern. However, the practicality of PIR 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 the cost saving advantages of cloud computing. In this paper, we first examine existing PIR protocols, analyzing their efficiency and practicality in realistic cloud settings. We identify shortcomings and, subsequently, present an efficient protocol (PIRMAP) that is particularly suited to MapReduce, a widely used cloud computing paradigm. PIRMAP focuses especially on the retrieval of large files from the cloud, where it achieves good communication complexity with query times significantly faster than previous schemes. To achieve this, PIRMAP enhance related work to allow for optimal parallel computation during the “Map” phase of MapReduce, and homomorphic aggregation in the “Reduce” phase. To improve computational cost, we also employ a new, faster “somewhat homomorphic” encryption, making our scheme practical for databases of useful size while still keeping communication costs low. PIRMAP has been implemented and tested in Amazon’s public cloud with database sizes of up to 1 TByte. Our evaluation shows that non-trivial PIR such as PIRMAP can be more than one order of magnitude cheaper and faster than trivial PIR in the real-world.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aguilar-Melamine, C., Gaborit, P.: A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol (2007), http://eprint.iacr.org/2007/446.pdf
Amazon. Elastic MapReduce (2010), http://aws.amazon.com/elasticmapreduce/
Blass, E.-O., Di Pietro, R., Molva, R., Önen, M.: PRISM – Privacy-Preserving Search in MapReduce. In: Fischer-Hübner, S., Wright, M. (eds.) PETS 2012. LNCS, vol. 7384, pp. 180–200. Springer, Heidelberg (2012)
Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
Chen, Y., Sion, R.: On securing untrusted clouds with cryptography. In: Workshop on Privacy in the Electronic Society, Chicago, USA, pp. 109–114 (2010)
Chor, B., Goldreich, O., Kushilevitz, E.: Private Information Retrieval. In: Proceedings of Symposium on Foundations of Computer Science (1995)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. In: Proceedings of Symposium on Foundations of Computer Science, pp. 41–50 (1995)
Dean, J., Ghemawat, S.: MapReduce: Simplified Data Processing on Large Clusters. In: Proceedings of Symposium on Operating System Design and Implementation, San Francisco, USA, pp. 137–150 (2004)
Fürer, M.: Faster integer multiplication. In: Proceedings of Symposium on Theory of Computing (1997)
Gartner. Gartner Identifies the Top 10 Strategic Technologies for 2011 (2010), http://www.gartner.com/it/page.jsp?id=1454221
Google. A new approach to China (2010), http://googleblog.blogspot.com/2010/01/new-approach-to-china.html
Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: Proceedings of Symposium on Foundations of Computer Science, pp. 364–373 (1997)
Lipmaa, H.: An Oblivious Transfer Protocol with Log-Squared Communication. In: Zhou, J., López, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 314–328. Springer, Heidelberg (2005)
McClure, D.: GSA’s role in supporting development and deployment of cloud computing technology (2010), http://www.gsa.gov/portal/content/159101
Nasuni: State of Cloud Storage Providers Industry Benchmark Report (2011), http://cache.nasuni.com/Resources/Nasuni_Cloud_Storage_Benchmark_Report.pdf
Olumofin, F., Goldberg, I.: Revisiting the Computational Practicality of Private Information Retrieval. In: Danezis, G. (ed.) FC 2011. LNCS, vol. 7035, pp. 158–172. Springer, Heidelberg (2012)
PIRMAP. Source Code (2012), http://pasmac.ccs.neu.edu
Sion, R., Carbunar, B.: On the Computational Practicality of Private Information Retrieval. In: Proceedings of Network and Distributed Systems Security Symposium, San Diego, USA, pp. 1–10 (2007)
Symantec. State of Cloud Survey (2011), http://www.symantec.com
Trostle, J., Parrish, A.: Efficient computationally private information retrieval from anonymity or trapdoor groups. In: Burmester, M., Tsudik, G., Magliveras, S., Ilić, I. (eds.) ISC 2010. LNCS, vol. 6531, pp. 114–128. Springer, Heidelberg (2011)
Whittaker, Z.: Microsoft admits Patriot Act can access EU-based cloud data (2011), http://www.zdnet.com/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mayberry, T., Blass, EO., Chan, A.H. (2013). PIRMAP: Efficient Private Information Retrieval for MapReduce. In: Sadeghi, AR. (eds) Financial Cryptography and Data Security. FC 2013. Lecture Notes in Computer Science, vol 7859. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39884-1_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-39884-1_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39883-4
Online ISBN: 978-3-642-39884-1
eBook Packages: Computer ScienceComputer Science (R0)