Abstract
While storing documents on the cloud can be attractive, the question remains whether cloud providers can be trusted with storing private documents. Even if trusted, data breaches are ubiquitous. To prevent information leakage one can store documents encrypted. If encrypted under traditional schemes, one loses the ability to perform simple operations over the documents, such as searching through them. Searchable encryption schemes were proposed allowing some search functionality while documents remain encrypted. Orthogonally, research is done to find attacks that exploit search and access pattern leakage that most efficient schemes have. One type of such an attack is the ability to recover plaintext queries. Passive query-recovery attacks on single-keyword search schemes have been proposed in literature, however, conjunctive keyword search has not been considered, although keyword searches with two or three keywords appear more frequently in online searches.
We introduce a generic extension strategy for existing passive query-recovery attacks against single-keyword search schemes and explore its applicability for the attack presented by Damie et al. (USENIX Security ’21). While the original attack achieves up to a recovery rate of \(85\%\) against single-keyword search schemes for an attacker without exact background knowledge, our experiments show that the generic extension to conjunctive queries comes with a significant performance decrease achieving recovery rates of at most \(32\%\). Assuming a stronger attacker with partial knowledge of the indexed document set boosts the recovery rate to \(85\%\) for conjunctive keyword queries with two keywords and achieves similar recovery rates as previous attacks by Cash et al. (CCS ’15) and Islam et al. (NDSS ’12) in the same setting for single-keyword search schemes.
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
Similar content being viewed by others
Notes
- 1.
- 2.
Note: \(d = 1\) refers to a single-keyword search scheme.
- 3.
\(A^T\) denotes the transpose of matrix A.
- 4.
Our code is available at https://github.com/marcowindt/passive-ckws-attack.
- 5.
\(\mathsf {logit}(x) = \mathsf {log}(\frac{x}{1 - x})\).
References
Abadi, M., et al.: TensorFlow: a system for large-scale machine learning. In: 12th \(\{\)USENIX\(\}\) Symposium on Operating Systems Design and Implementation (\(\{\)OSDI\(\}\) 2016) (2016)
Blackstone, L., Kamara, S., Moataz, T.: Revisiting leakage abuse attacks. IACR Cryptol. ePrint Arch. 2019, 1175 (2019)
Cash, D., Grubbs, P., Perry, J., Ristenpart, T.: Leakage-abuse attacks against searchable encryption. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (2015)
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). https://doi.org/10.1007/978-3-642-40041-4_20
Clement, J.: U.S. online search query size in 2020, August 2020. https://www.statista.com/statistics/269740/number-of-search-terms-in-internet-research-in-the-us/
Damie, M., Hahn, F., Peter, A.: A highly accurate query-recovery attack against searchable encryption using non-indexed documents. In: 30th USENIX Security Symposium (USENIX Security 21). USENIX Association, August 2021
Fairouz, S.A., Lu, S.F.: Symmetric key encryption with conjunctive field free keyword search scheme. J. Adv. Math. Comput. Sci. 16(6), 1–11 (2016)
Golle, P., Staddon, J., Waters, B.: Secure conjunctive keyword search over encrypted data. In: Jakobsson, M., Yung, M., Zhou, J. (eds.) ACNS 2004. LNCS, vol. 3089, pp. 31–45. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24852-1_3
Hu, C., et al.: Forward secure conjunctive-keyword searchable encryption. IEEE Access 7, 35035–35048 (2019)
Islam, M.S., Kuzu, M., Kantarcioglu, M.: Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: NDSS, vol. 20. Citeseer (2012)
Jho, N.S., Hong, D.: Symmetric searchable encryption with efficient conjunctive keyword search. KSII Trans. Internet Inf. Syst. 7(5), 1328–1342 (2013)
Klimt, B., Yang, Y.: Introducing the Enron corpus. In: CEAS (2004)
Lai, S., et al.: Result pattern hiding searchable encryption for conjunctive queries. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (2018)
Liu, C., Zhu, L., Wang, M., Tan, Y.A.: Search pattern leakage in searchable encryption: attacks and new construction. Inf. Sci. 265, 176–188 (2014)
Ning, J., Xu, J., Liang, K., Zhang, F., Chang, E.C.: Passive attacks against searchable encryption. IEEE Trans. Inf. Forensics Secur. 14(3), 789–802 (2018)
Oya, S., Kerschbaum, F.: Hiding the access pattern is not enough: exploiting search pattern leakage in searchable encryption. In: 30th \(\{\)USENIX\(\}\) Security Symposium (\(\{\)USENIX\(\}\) Security 21) (2021)
Patranabis, S., Mukhopadhyay, D.: Forward and backward private conjunctive searchable symmetric encryption. Cryptology ePrint Archive (2020)
Poddar, R., Wang, S., Lu, J., Popa, R.A.: Practical volume-based attacks on encrypted databases. In: 2020 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE (2020)
Poon, H.T., Miri, A.: An efficient conjunctive keyword and phase search scheme for encrypted cloud storage systems. In: 2015 IEEE 8th International Conference on Cloud Computing. IEEE (2015)
Porter, M.F.: An algorithm for suffix stripping. Program (1980)
Pouliot, D., Wright, C.V.: The shadow nemesis: inference attacks on efficiently deployable, efficiently searchable encryption. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (2016)
Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: Proceeding 2000 IEEE Symposium on Security and Privacy, S&P 2000. IEEE (2000)
Sun, W., Liu, X., Lou, W., Hou, Y.T., Li, H.: Catch you if you lie to me: efficient verifiable conjunctive keyword search over large dynamic encrypted cloud data. In: 2015 IEEE Conference on Computer Communications (INFOCOM). IEEE (2015)
Wang, S., Poddar, R., Lu, J., Popa, R.A.: Practical volume-based attacks on encrypted databases. IACR Cryptol. ePrint Arch. 2019, 1224 (2019)
Wang, Y., Wang, J., Sun, S., Miao, M., Chen, X.: Toward forward secure SSE supporting conjunctive keyword search. IEEE Access 7, 142762–142772 (2019)
Wu, Z., Li, K.: VBTree: forward secure conjunctive queries over encrypted data for cloud computing. VLDB J. 28(1), 25–46 (2018). https://doi.org/10.1007/s00778-018-0517-6
Zhang, L., Zhang, Y., Ma, H.: Privacy-preserving and dynamic multi-attribute conjunctive keyword search over encrypted cloud data. IEEE Access 6, 34214–34225 (2018)
Zhang, Y., Katz, J., Papamanthou, C.: All your queries are belong to us: the power of file-injection attacks on searchable encryption. In: 25th \(\{\)USENIX\(\}\) Security Symposium (\(\{\)USENIX\(\}\) Security 16) (2016)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Dijkslag, M., Damie, M., Hahn, F., Peter, A. (2022). Passive Query-Recovery Attack Against Secure Conjunctive Keyword Search Schemes. In: Ateniese, G., Venturi, D. (eds) Applied Cryptography and Network Security. ACNS 2022. Lecture Notes in Computer Science, vol 13269. Springer, Cham. https://doi.org/10.1007/978-3-031-09234-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-09234-3_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-09233-6
Online ISBN: 978-3-031-09234-3
eBook Packages: Computer ScienceComputer Science (R0)