Abstract
There has been considerable interest in querying encrypted data, allowing a “secure database server” model where the server does not know data values. This paper shows how results from cryptography prove the impossibility of developing a server that meets cryptographic-style definitions of security and is still efficient enough to be practical. The weaker definitions of security supported by previous secure database server proposals have the potential to reveal significant information. We propose a definition of a secure database server that provides probabilistic security guarantees, and sketch how a practical system meeting the definition could be built and proven secure. The primary goal of this paper is to provide a vision of how research in this area should proceed: efficient encrypted database and query processing with provable security properties.
This material is based upon work supported by the National Science Foundation under Grant No. 0312357.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Hacigumus, H., Iyer, B.R., Li, C., Mehrotra, S.: Executing SQL over encrypted data in the database-service-provider model. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, pp. 216–227 (2002)
Damiani, E., Vimercati, S.D.C., Jajodia, S., Paraboschi, S., Samarati, P.: Balancing confidentiality and efficiency in untrusted relational dbmss. In: Proceedings of the 10th ACM conference on Computer and communications security, Washington D.C, pp. 93–102. ACM Press, New York (2003)
Ozsoyoglu, G., Singer, D.A., Chung, S.S.: Anti-tamper databases: Querying encrypted databases. In: Proceedings of the 17th Annual IFIP WG 11.3 Working Conference on Database and Applications Security. Estes Park, Colorado (2003)
Agrawal, R., Kiernan, J., Srikant, R., Xu, Y.: Order-preserving encryption for numeric data. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, France (2004)
Boneh, D., Boyen, X.: Efficient selective-id secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
Song, D., Wagner, D., Perrig, A.: Search on encrypted data. In: Procedings of IEEE SRSP. IEEE, Los Alamitos (2000)
Ahituv, N., Lapid, Y., Neumann, S.: Processing encrypted data. Communications of the ACM 20, 777–780 (1987)
IBM: IBM PCI cryptographic coprocessor (2004), http://www.ibm.com/security/cryptocards/html/pcicc.shtml
Goldreich, O.: The Foundations of Cryptography, vol. 2. Cambridge University Press, Cambridge (2004)
NIST: Advanced encryption standard (aes). Technical Report NIST Special Publication FIPS-197, National Institute of Standards and Technology (2001), http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. Journal of the ACM 45, 965–981 (1998)
Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. Journal of the ACM 43, 431–473 (1996)
Asonov, D., Freytag, J.C.: Almost optimal private information retrieval. In: Dingledine, R., Syverson, P.F. (eds.) PET 2002. LNCS, vol. 2482, pp. 209–223. Springer, Heidelberg (2003)
Goldreich, O.: General Cryptographic Protocols. In: The Foundations of Cryptography, vol. 2. Cambridge University Press, Cambridge (2004)
Lin, P., Candan, K.S.: Hiding traversal of tree structured data from untrusted data stores. In: Proceedings of Intelligence and Security Informatics: First NSF/NIJ Symposium ISI 2003, Tucson, AZ, USA, p. 385 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 IFIP International Federation for Information Processing
About this paper
Cite this paper
Kantarcıoǧlu, M., Clifton, C. (2005). Security Issues in Querying Encrypted Data. In: Jajodia, S., Wijesekera, D. (eds) Data and Applications Security XIX. DBSec 2005. Lecture Notes in Computer Science, vol 3654. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11535706_24
Download citation
DOI: https://doi.org/10.1007/11535706_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28138-2
Online ISBN: 978-3-540-31937-5
eBook Packages: Computer ScienceComputer Science (R0)