1. bookVolume 2022 (2022): Issue 1 (January 2022)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Forward and Backward-Secure Range-Searchable Symmetric Encryption

Published Online: 20 Nov 2021
Page range: 28 - 48
Received: 31 May 2021
Accepted: 16 Sep 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

Dynamic searchable symmetric encryption (DSSE) allows a client to query or update an outsourced encrypted database. Range queries are commonly needed. Previous range-searchable schemes either do not support updates natively (SIGMOD’16) or use file indexes of many long bit-vectors for distinct keywords, which only support toggling updates via homomorphically flipping the presence bit. (ESORICS’18).

We propose a generic upgrade of any (inverted-index) DSSE to support range queries (a.k.a. range DSSE), without homomorphic encryption, and a specific instantiation with a new trade-off reducing client-side storage. Our schemes achieve forward security, an important property that mitigates file injection attacks. Moreover, we identify a variant of injection attacks against the first somewhat dynamic scheme (ESORICS’18). We also extend the definition of backward security to range DSSE and show that our schemes are compatible with a generic upgrade of backward security (CCS’17).

We comprehensively analyze the computation and communication overheads, including implementation details of client-side index-related operations omitted by prior schemes. We show high empirical efficiency for million-scale databases over a million-scale keyword space.

Keywords

[1] G. Amjad, S. Kamara, and T. Moataz. Breach-resistant structured encryption. PoPETs, (1):245–265, 2019. Search in Google Scholar

[2] A. Boldyreva, N. Chenette, and A. O’Neill. Order-preserving encryption revisited: Improved security analysis and alternative solutions. In CRYPTO, 2011. Search in Google Scholar

[3] R. Bost. ∑oφoς: Forward secure searchable encryption. In CCS, 2016. Search in Google Scholar

[4] R. Bost, B. Minaud, and O. Ohrimenko. Forward and backward private searchable encryption from constrained cryptographic primitives. In CCS, 2017. Search in Google Scholar

[5] D. Cash, J. Jaeger, S. Jarecki, C. S. Jutla, H. Krawczyk, M. Rosu, and M. Steiner. Dynamic searchable encryption in very-large databases: Data structures and implementation. In NDSS, 2014. Full version at Crypto. ePrint 2014/853. Search in Google Scholar

[6] D. Cash, S. Jarecki, C. S. Jutla, H. Krawczyk, M. Rosu, and M. Steiner. Highly-scalable searchable symmetric encryption with support for boolean queries. In CRYPTO Part I, 2013. Search in Google Scholar

[7] J. G. Chamani, D. Papadopoulos, C. Papamanthou, and R. Jalili. New constructions for forward and backward private symmetric searchable encryption. In CCS, 2018. Search in Google Scholar

[8] M. Chase and S. Kamara. Structured encryption and controlled disclosure. In ASIACRYPT, 2010. Search in Google Scholar

[9] I. Demertzis, D. Papadopoulos, C. Papamanthou, and S. Shintre. SEAL: attack mitigation for encrypted databases via adjustable leakage. In USENIX Security, 2020. Search in Google Scholar

[10] I. Demertzis, S. Papadopoulos, O. Papapetrou, A. Deligiannakis, and M. N. Garofalakis. Practical private range search revisited. In SIGMOD, 2016. Search in Google Scholar

[11] S. Faber, S. Jarecki, H. Krawczyk, Q. Nguyen, M. Rosu, and M. Steiner. Rich queries on encrypted data: Beyond exact matches. In ESORICS Part II, 2015. Search in Google Scholar

[12] P. Grubbs, M. Lacharité, B. Minaud, and K. G. Paterson. Pump up the volume: Practical database reconstruction from volume leakage on range queries. In CCS, 2018. Search in Google Scholar

[13] P. Grubbs, K. Sekniqi, V. Bindschaedler, M. Naveed, and T. Ristenpart. Leakage-abuse attacks against order-revealing encryption. In SP, 2017. Search in Google Scholar

[14] F. Hahn and F. Kerschbaum. Searchable encryption with secure and efficient updates. In CCS, 2014. Search in Google Scholar

[15] S. Kamara and T. Moataz. SQL on structurally-encrypted databases. In ASIACRYPT Part I, 2018. Search in Google Scholar

[16] S. Kamara and T. Moataz. Computationally volume-hiding structured encryption. In EUROCRYPT, 2019. Search in Google Scholar

[17] S. Kamara, T. Moataz, and O. Ohrimenko. Structured encryption and leakage suppression. In CRYPTO, 2018. Search in Google Scholar

[18] S. Kamara and C. Papamanthou. Parallel and dynamic searchable symmetric encryption. In FC, 2013. Search in Google Scholar

[19] S. Kamara, C. Papamanthou, and T. Roeder. Dynamic searchable symmetric encryption. In CCS, 2012. Search in Google Scholar

[20] G. Kellaris, G. Kollios, K. Nissim, and A. O’Neill. Generic attacks on secure outsourced databases. In CCS, 2016. Search in Google Scholar

[21] F. Kerschbaum and A. Tueno. An efficiently searchable encrypted data structure for range queries. In ESORICS Part II, 2019. Search in Google Scholar

[22] A. Kiayias, S. Papadopoulos, N. Triandopoulos, and T. Zacharias. Delegatable pseudorandom functions and applications. In CCS, 2013. Search in Google Scholar

[23] M. Lacharité, B. Minaud, and K. G. Paterson. Improved reconstruction attacks on encrypted data using range query leakage. In SP, 2018. Search in Google Scholar

[24] R. W. F. Lai and S. S. M. Chow. Structured encryption with non-interactive updates and parallel traversal. In ICDCS, 2015. Search in Google Scholar

[25] R. W. F. Lai and S. S. M. Chow. Parallel and dynamic structured encryption. In SecureComm, 2016. Search in Google Scholar

[26] R. W. F. Lai and S. S. M. Chow. Forward-secure searchable encryption on labeled bipartite graphs. In ACNS, 2017. Search in Google Scholar

[27] E. A. Markatou and R. Tamassia. Mitigation techniques for attacks on 1-dimensional databases that support range queries. In ISC, 2019. Search in Google Scholar

[28] W. Ogata and K. Kurosawa. Efficient no-dictionary verifiable searchable symmetric encryption. In FC, 2017. Search in Google Scholar

[29] F. I. Rusu. Sketches for aggregate estimations over data streams. PhD thesis, University of Florida, 2009. Search in Google Scholar

[30] X. Song, C. Dong, D. Yuan, Q. Xu, and M. Zhao. Forward private searchable symmetric encryption with optimized I/O efficiency. IEEE TDSC, 17(5):912–927, 2020. Search in Google Scholar

[31] E. Stefanov, C. Papamanthou, and E. Shi. Practical dynamic searchable encryption with small leakage. In NDSS, 2014. Search in Google Scholar

[32] J. Wang and S. S. M. Chow. Forward and backward-secure range-searchable symmetric encryption. Cryptology ePrint Archive, Report 2019/497, 2019. Preliminary version of this paper, submitted to ePrint on 14-May-2019. Search in Google Scholar

[33] J. Wang and S. S. M. Chow. Simple storage-saving structure for volume-hiding encrypted multi-maps (A slot in need is a slot indeed). In DBSEC, 2021. Search in Google Scholar

[34] J. Wang and S. S. M. Chow. Omnes pro uno: Practical multi-writer encrypted database. In USENIX Security, 2022. Search in Google Scholar

[35] J. Wang, M. Du, and S. S. M. Chow. Stargazing in the dark: Secure skyline queries with SGX. In DASFAA Part III, 2020. Search in Google Scholar

[36] S. Wu, Q. Li, G. Li, D. Yuan, X. Yuan, and C. Wang. ServeDB: Secure, verifiable, and efficient multidimensional range queries on outsourced database. In ICDE, 2019. Search in Google Scholar

[37] Y. Zhang, J. Katz, and C. Papamanthou. All your queries are belong to us: The power of file-injection attacks on searchable encryption. In USENIX Security, 2016. Search in Google Scholar

[38] C. Zuo, S. Sun, J. K. Liu, J. Shao, and J. Pieprzyk. Dynamic searchable symmetric encryption schemes supporting range queries with forward (and backward) security. In ESORICS Part II, 2018. Search in Google Scholar

[39] C. Zuo, S. Sun, J. K. Liu, J. Shao, J. Pieprzyk, and L. Xu. Forward and backward private DSSE for range queries. IEEE Trans. Dependable Sec. Comput. (TDSC), 2020. Early Access. Also available as Cryptology ePrint Archive: Report 2019/1240, submitted to ePrint on 22-Oct-2019. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo