Abstract
Searchable symmetric encryption (SSE) has been widely applied in the encrypted database for queries in practice. Although SSE is powerful and feature-rich, it is always plagued by information leaks. Some recent attacks point out that forward security which disallows leakage from update operations, now becomes a basic requirement for any newly designed SSE schemes. Many forward secure searchable symmetric encryption (FSSE) schemes supporting single-keyword search have been proposed. Only a few SSE schemes can satisfy forward security and support conjunctive-keyword search at the same time, which are realized by adopting inefficient or complicated cryptographic tools. In this paper, we use an efficient cryptographic tool, Shamir threshold secret sharing scheme, to design an efficient and secure conjunctive-keyword FSSE scheme. Our scheme achieves sub-linear efficiency, and can easily be used in any single-keyword FSSE scheme to obtain a conjunctive-keyword FSSE scheme. Compared with the current conjunctive-keyword FSSE scheme, our scheme has a better update and search efficiency.
Supported by National Natural Science Foundation of China (No: 62072240) and The National Key Research and Development Program of China (No. 2020YFB1804604).
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
References
Bost, R.: \(\sum \)o\(\varphi \)o\(\varsigma \): forward secure searchable encryption. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016, pp. 1143–1154. ACM (2016)
Bost, R., Minaud, B., Ohrimenko, O.: Forward and backward private searchable encryption from constrained cryptographic primitives. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1465–1482 (2017)
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
Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. J. Comput. Secur. 19(5), 895–934 (2011)
Goh, E.J., et al.: Secure indexes. IACR Cryptology ePrint Archive 2003, 216 (2003)
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
Guo, Y., Zhang, C., Jia, X.: Verifiable and forward-secure encrypted search using blockchain techniques. In: 2020 IEEE International Conference on Communications, ICC 2020, Dublin, Ireland, 7–11 June 2020, pp. 1–7. IEEE (2020)
Hu, C., et al.: Forward secure conjunctive-keyword searchable encryption. IEEE Access 7, 35035–35048 (2019)
Kamara, S., Papamanthou, C.: Parallel and dynamic searchable symmetric encryption. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 258–274. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39884-1_22
Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, pp. 965–976 (2012)
Katz, J., Lindell, Y.: Introduction to Modern Cryptography, 2nd edn. CRC Press, Boca Raton (2014)
Kim, K.S., Kim, M., Lee, D., Park, J.H., Kim, W.: Forward secure dynamic searchable symmetric encryption with efficient updates. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, 30 October–03 November 2017, pp. 1449–1463. ACM (2017)
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, pp. 745–762 (2018)
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, pp. 44–55. IEEE (2000)
Song, X., Dong, C., Yuan, D., Xu, Q., Zhao, M.: Forward private searchable symmetric encryption with optimized I/O efficiency. IEEE Trans. Dependable Secure Comput. 17, 912–927 (2018)
Stefanov, E., Papamanthou, C., Shi, E.: Practical dynamic searchable encryption with small leakage. In: NDSS, vol. 71, pp. 72–75 (2014)
Vo, V., Lai, S., Yuan, X., Sun, S., Nepal, S., Liu, J.K.: Accelerating forward and backward private searchable encryption using trusted execution. CoRR abs/2001.03743 (2020)
Wang, Y., Wang, J., Sun, S., Miao, M., Chen, X.: Toward forward secure sse supporting conjunctive keyword search. IEEE Access 7, 142762–142772 (2019)
Wei, Y., Lv, S., Guo, X., Liu, Z., Huang, Y., Li, B.: FSSE: forward secure searchable encryption with keyed-block chains. Inf. Sci. 500, 113–126 (2019)
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), pp. 707–720 (2016)
Zhang, Z., Wang, J., Wang, Y., Su, Y., Chen, X.: Towards efficient verifiable forward secure searchable symmetric encryption. In: Sako, K., Schneider, S., Ryan, P.Y.A. (eds.) ESORICS 2019. LNCS, vol. 11736, pp. 304–321. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-29962-0_15
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Li, L., Xu, C., Liu, Z., Mei, L. (2020). Forward Secure Conjunctive-Keyword Searchable Symmetric Encryption Using Shamir Threshold Secret Sharing Scheme. In: Batina, L., Li, G. (eds) Applications and Techniques in Information Security. ATIS 2020. Communications in Computer and Information Science, vol 1338. Springer, Singapore. https://doi.org/10.1007/978-981-33-4706-9_2
Download citation
DOI: https://doi.org/10.1007/978-981-33-4706-9_2
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-33-4705-2
Online ISBN: 978-981-33-4706-9
eBook Packages: Computer ScienceComputer Science (R0)