Abstract
We explore how Private Information Retrieval (PIR) can help users keep their sensitive information from being leaked in an SQL query. We show how to retrieve data from a relational database with PIR by hiding sensitive constants contained in the predicates of a query. Experimental results and microbenchmarking tests show our approach incurs reasonable storage overhead for the added privacy benefit and performs between 7 and 480 times faster than previous work.
An extended version of this paper is available [22].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aguilar-Melchor, C., Gaborit, P.: A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol. Cryptol. ePrint Arch., Report 446 (2007)
Arge, L., Procopiuc, O., Vitter, J.S.: Implementing I/O-efficient Data Structures Using TPIE. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 88–100. Springer, Heidelberg (2002)
Beimel, A., Stahl, Y.: Robust Information-Theoretic Private Information Retrieval. J. Cryptol. 20(3), 295–321 (2007)
Bethencourt, J., Song, D., Waters, B.: New Techniques for Private Stream Searching. ACM Trans. Inf. Syst. Secur. 12(3), 1–32 (2009)
Botelho, F.C., Reis, D., Ziviani, N.: CMPH: C minimal perfect hashing library on SourceForge, http://cmph.sourceforge.net/
Botelho, F.C., Ziviani, N.: External perfect hashing for very large key sets. In: ACM CIKM, pp. 653–662 (2007)
Chaum, D.L.: Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 24(2), 84–90 (1981)
Chor, B., Gilboa, N., Naor, M.: Private information retrieval by keywords. Technical Report TR CS0917, Dept. of Computer Science, Technion, Israel (1997)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: FOCS, October 1995, pp. 41–50 (1995)
Crescenzo, G.D.: Towards Practical Private Information Retrieval. In: Achieving Practical Private Information Retrieval (Panel @ Securecomm 2006) (August 2006)
Department of Computer Science at Duke University. The TPIE (Templated Portable I/O Environment), http://madalgo.au.dk/Trac-tpie/
Dingledine, R., Mathewson, N., Syverson, P.: Tor: the second-generation onion router. In: USENIX Security Symposium, p. 21 (2004)
Goldberg, I.: Percy++ project on SourceForge, http://percy.sourceforge.net/
Goldberg, I.: Improving the Robustness of Private Information Retrieval. In: IEEE Symposium on Security and Privacy, pp. 131–148 (2007)
Hacigümüş, H., Iyer, B., Li, C., Mehrotra, S.: Executing sql over encrypted data in the database-service-provider model. In: ACM SIGMOD, pp. 216–227 (2002)
Hore, B., Mehrotra, S., Tsudik, G.: A privacy-preserving index for range queries. In: VLDB, pp. 720–731 (2004)
ICANN Security and Stability Advisory Committee (SSAC). Report on Domain Name Front Running (February 2008)
Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: FOCS, p. 364 (1997)
Mishra, S.K., Sarkar, P.: Symmetrically Private Information Retrieval. In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 225–236. Springer, Heidelberg (2000)
Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: ACM Symposium on Theory of Computing, pp. 245–254 (1999)
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: ACM-SIAM SODA, pp. 448–457 (2001)
Olumofin, F., Goldberg, I.: Privacy-preserving Queries over Relational Databases. Technical report, CACR 2009-37, University of Waterloo (2009)
Reardon, J., Pound, J., Goldberg, I.: Relational-Complete Private Information Retrieval. Technical report, CACR 2007-34, University of Waterloo (2007)
Sassaman, L., Cohen, B., Mathewson, N.: The Pynchon Gate: a Secure Method of Pseudonymous Mail Retrieval. In: ACM WPES, pp. 1–9 (2005)
Shi, E., Bethencourt, J., Chan, T.-H.H., Song, D., Perrig, A.: Multi-Dimensional Range Query over Encrypted Data. In: IEEE SSP, pp. 350–364 (2007)
Silberschatz, A., Korth, H.F., Sudarshan, S.: Database System Concepts, 5th edn. McGraw-Hill, Inc., New York (2005)
Sion, R., Carbunar, B.: On the Computational Practicality of Private Information Retrieval. In: Network and Distributed Systems Security Symposium (2007)
Sun Microsystems. MySQL, http://www.mysql.com/
Transaction Processing Performance Council. Benchmark C, http://www.tpc.org/
Vengroff, D.E., Scott Vitter, J.: Supporting I/O-efficient scientific computation in TPIE. In: IEEE Symp. on Parallel and Distributed Processing, p. 74 (1995)
Williams, P., Sion, R.: Usable PIR. In: Network and Distributed System Security Symposium. The Internet Society (2008)
Wong, M., Thomas, C.: Database Test Suite project on SourceForge, http://osdldbt.sourceforge.net/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Olumofin, F., Goldberg, I. (2010). Privacy-Preserving Queries over Relational Databases. In: Atallah, M.J., Hopper, N.J. (eds) Privacy Enhancing Technologies. PETS 2010. Lecture Notes in Computer Science, vol 6205. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14527-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-14527-8_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14526-1
Online ISBN: 978-3-642-14527-8
eBook Packages: Computer ScienceComputer Science (R0)