Abstract
We point out the risks of protecting relational databases via Searchable Symmetric Encryption (SSE) schemes by proposing an inference attack exploiting the structural properties of relational databases. We also show that record-injection attacks mounted on relational databases have worse consequences than their file-injection counterparts on unstructured databases. Moreover, we discuss some techniques to reduce the effectiveness of inference attacks exploiting the access pattern leakage existing in SSE schemes.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abdelraheem, M.A., Gehrmann, C., Lindström, M., Nordahl, C.: Executing boolean queries on an encrypted bitmap index. In: Proceedings of the 2016 ACM on Cloud Computing Security Workshop, pp. 11–22. ACM (2016)
Aggarwal, G., Bawa, M., Ganesan, P., Garcia-Molina, H., Kenthapadi, K., Motwani, R., Srivastava, U., Thomas, D., Xu, Y.: Two can keep a secret: a distributed architecture for secure database services. In: CIDR 2005 (2005)
Portuguese banking institution. Bank marketing data set (2014). https://archive.ics.uci.edu/ml/datasets/Bank+Marketing. Accessed June 2017
Bost, R.: \(\sigma \)o\(\varphi \)o\(\varsigma \): forward secure searchable encryption. In: CCS 2016 (2016)
Cash, D., Grubbs, P., Perry, J., Ristenpart, T.: Leakage-abuse attacks against searchable encryption. In: Proceedings of CCS 2015 (2015)
Cash, D., Jaeger, J., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M.-C., Steiner, M.: Dynamic searchable encryption in very-large databases: data structures and implementation. IACR Cryptology ePrint Archive, 2014:853 (2014)
Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Roşu, M.-C., Steiner, M.: Highly-scalable searchable symmetric encryption with support for boolean queries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 353–373. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40041-4_20
Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 577–594. Springer, Heidelberg (2010). doi:10.1007/978-3-642-17373-8_33
Ciriani, V., De Capitani di Vimercati, S., Foresti, S., Jajodia, S., Paraboschi, S., Samarati, P.: Fragmentation and encryption to enforce privacy in data storage. In: Biskup, J., López, J. (eds.) ESORICS 2007. LNCS, vol. 4734, pp. 171–186. Springer, Heidelberg (2007). doi:10.1007/978-3-540-74835-9_12
Ciriani, V., De Capitani di Vimercati, S., Foresti, S., Jajodia, S., Paraboschi, S., Samarati, P.: Keep a few: outsourcing data while maintaining confidentiality. In: Backes, M., Ning, P. (eds.) ESORICS 2009. LNCS, vol. 5789, pp. 440–455. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04444-1_27
Ciriani, V., De Capitani Di Vimercati, S., Foresti, S., Jajodia, S., Paraboschi, S., Samarati, P.: Combining fragmentation and encryption to protect privacy in data storage. ACM Trans. Inf. Syst. Secur. (TISSEC) (2010)
Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: Proceedings of the 13th ACM Conference on Computer and Communications Security, pp. 79–88. ACM (2006)
Center for Machine Learning and Intelligent Systems. University of California, Irvine. https://archive.ics.uci.edu/ml/datasets.html. Accessed June 2017
Islam, M.S., Kuzu, M., Kantarcioglu, M.: Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: NDSS (2012)
Kohavi, R., Becker, B.: Adult data set (1996). https://archive.ics.uci.edu/ml/machine-learning-databases/adult/. Accessed June 2017
Lane, T., Kohavi, R.: Census-income (KDD) data set (2000). https://archive.ics.uci.edu/ml/machine-learning-databases/census-income-mld/. Accessed June 2017
Naveed, M., Kamara, S., Wright, C.V.: Inference attacks on property-preserving encrypted databases. In: Proceedings of CCS 2015 (2015)
Popa, R.A., Redfield, C., Zeldovich, N., Balakrishnan, H.: Cryptdb: protecting confidentiality with encrypted query processing. In: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pp. 85–100. ACM (2011)
Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: 2000 IEEE Symposium on Security and Privacy, S&P 2000, Proceedings, pp. 44–55. IEEE (2000)
van Liesdonk, P., Sedghi, S., Doumen, J., Hartel, P., Jonker, W.: Computationally efficient searchable symmetric encryption. In: Jonker, W., Petković, M. (eds.) SDM 2010. LNCS, vol. 6358, pp. 87–100. Springer, Heidelberg (2010). doi:10.1007/978-3-642-15546-8_7
Zhang, Y., Katz, J., Papamanthou, C.: All your queries are belong to us: the power of file-injection attacks on searchable encryption. Cryptology ePrint Archive, Report 2016/172
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Abdelraheem, M.A., Andersson, T., Gehrmann, C. (2017). Searchable Encrypted Relational Databases: Risks and Countermeasures. In: Garcia-Alfaro, J., Navarro-Arribas, G., Hartenstein, H., Herrera-Joancomartí, J. (eds) Data Privacy Management, Cryptocurrencies and Blockchain Technology. DPM CBT 2017 2017. Lecture Notes in Computer Science(), vol 10436. Springer, Cham. https://doi.org/10.1007/978-3-319-67816-0_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-67816-0_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-67815-3
Online ISBN: 978-3-319-67816-0
eBook Packages: Computer ScienceComputer Science (R0)