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].
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-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)