Abstract
Two sets of privacy requirements need to be fulfilled when a company’s accounting data is audited by an external party: the company needs to safeguard its data, while the auditors do not want to reveal their investigation methods. This problem is usually addressed by physically isolating data and auditors during the course of an audit. This approach however no longer works when auditing is performed remotely.
In this paper we present an efficient construction for a searchable encryption scheme for outsourcing data analytics. In this scheme the data owner needs to encrypt his data only once and ship it in encrypted form to the data analyst. The data analyst can then perform a series of queries for which he must ask the data owner for help in translating the constants in the queries.
Our searchable encryption scheme extends previous work by the ability to re-use query results as search tokens (query-result reusability) and the ability to perform range queries. It is efficient with O(log2 n) work for a range query and is semantically secure relying only on Diffie-Hellman assumptions (in the random oracle model).
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.
References
Ateniese, G., Blanton, M., Kirsch, J.: Secret Handshakes with Dynamic and Fuzzy Matching. In: Proceedings of Network and Distributed System Security Symposuim (2007)
Boneh, D., Goh, E., Boyen, X.: Hierarchical Identity Based Encryption with Constant Size Ciphertext. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 440–456. Springer, Heidelberg (2005)
Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public-key Encryption with Keyword Search. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004)
Boneh, D., Franklin, M.: Identity-based Encryption from the Weil Paring. SIAM Journal of Computing 32(3) (2003)
Boneh, D., Kushilevitz, E., Ostrovsky, R., Skeith, W.: Public Key Encryption That Allows PIR Queries. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 50–67. Springer, Heidelberg (2007)
Boneh, D., Waters, B.: Conjunctive, Subset, and Range Queries on Encrypted Data. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 535–554. Springer, Heidelberg (2007)
Cachin, C., Micali, S., Stadler, M.: Computationally Private Information Retrieval with Polylogarithmic Communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, p. 402. Springer, Heidelberg (1999)
Camenisch, J., Kohlweiss, M., Rial, A., Sheedy, C.: Blind and Anonymous Identity-Based Encryption and Authorised Private Searches on Public Key Encrypted Data. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 196–214. Springer, Heidelberg (2009)
Chang, Y., Mitzenmacher, M.: Privacy Preserving Keyword Searches on Remote Encrypted Data. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 442–455. Springer, Heidelberg (2005)
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private Information Retrieval. In: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (1995)
Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions. In: Proceedings of ACM Conference on Computer and Communications Security (2006)
Evdokimov, S., Günther, O.: Encryption Techniques for Secure Database Outsourcing. In: Biskup, J., López, J. (eds.) ESORICS 2007. LNCS, vol. 4734, pp. 327–342. Springer, Heidelberg (2007)
Goh, E.: Secure Indexes. Cryptology ePrint Archive: Report 2003/216 (2003), http://eprint.iacr.org/2003/216/
Goldreich, O.: Secure Multi-party Computation (2002), http://www.wisdom.weizmann.ac.il/~oded/pp.html
Goldreich, O., Ostrovsky, R.: Software Protection and Simulation on Oblivious RAMs. Journal of ACM 43(3) (1996)
Kerschbaum, F., Vayssiere, J.: Privacy-Preserving Data Analytics as an Outsourced Service. In: Proceedings of the ACM Secure Web Services Workshop (2008)
Kushilevitz, E., Ostrovsky, R.: Replication is not needed: Single Database Computationally Private Information Retrieval. In: Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (1997)
Shi, E., Bethencourt, J., Chan, H., Song, D., Perrig, A.: Multi-Dimensional Range Query over Encrypted Data. In: Proceedings of IEEE Symposium on Security and Privacy (2007)
Sion, R., Carbunar, B.: On the Computational Practicality of Private Information Retrieval. In: Proceedings of Network and Distributed System Security Symposium (2007)
Waters, B.: Efficient Identity-Based Encryption Without Random Oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005)
Yang, Z., Zhong, S., Wright, R.: Privacy-Preserving Queries on Encrypted Data. In: Gollmann, D., Meier, J., Sabelfeld, A. (eds.) ESORICS 2006. LNCS, vol. 4189, pp. 479–495. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kerschbaum, F., Sorniotti, A. (2011). Searchable Encryption for Outsourced Data Analytics. In: Camenisch, J., Lambrinoudakis, C. (eds) Public Key Infrastructures, Services and Applications. EuroPKI 2010. Lecture Notes in Computer Science, vol 6711. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22633-5_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-22633-5_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22632-8
Online ISBN: 978-3-642-22633-5
eBook Packages: Computer ScienceComputer Science (R0)