An efficiently searchable encrypted data structure for range queries

DOI10.1007/978-3-030-29962-0_17MaRDI QIDQ2167782zbMATH OpenOpenAlexFDO

Authors Florian Kerschbaum, Anselme Tueno

Publication date 25 August 2022

Full work available at URL https://arxiv.org/abs/1709.09314

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Abstract: At CCS 2015 Naveed et al. presented first attacks on efficiently searchable encryption, such as deterministic and order-preserving encryption. These plaintext guessing attacks have been further improved in subsequent work, e.g. by Grubbs et al. in 2016. Such cryptanalysis is crucially important to sharpen our understanding of the implications of security models. In this paper we present an efficiently searchable, encrypted data structure that is provably secure against these and even more powerful chosen plaintext attacks. Our data structure supports logarithmic-time search with linear space complexity. The indices of our data structure can be used to search by standard comparisons and hence allow easy retrofitting to existing database management systems. We implemented our scheme and show that its search time overhead is only 10 milliseconds compared to non-secure search.

Recommendations

• Order-preserving encryption revisited: improved security analysis and alternative solutions
• Order-Preserving Symmetric Encryption
• Practical private range search in depth
• On the security of frequency-hiding order-preserving encryption
• Semi-order preserving encryption

Cited in

(5)

• A multi-client DSSE scheme supporting range queries
• Efficient Fuzzy Search on Encrypted Data
• Efficient Asymmetric Index Encapsulation Scheme for Named Data
• A New Functional Encryption for Multidimensional Range Query (Short Paper)
• Updatable searchable symmetric encryption: definitions and constructions

This page was built for publication: An efficiently searchable encrypted data structure for range queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2167782)