Rich Queries on Encrypted Data: Beyond Exact Matches
We extend the searchable symmetric encryption (SSE) protocol of [Cash et al., Crypto’13] adding support for range, substring, wildcard, and phrase queries, in addition to the Boolean queries supported in the original protocol. Our techniques apply to the
- PDF / 644,532 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 181 Views
Abstract. We extend the searchable symmetric encryption (SSE) protocol of [Cash et al., Crypto’13] adding support for range, substring, wildcard, and phrase queries, in addition to the Boolean queries supported in the original protocol. Our techniques apply to the basic singleclient scenario underlying the common SSE setting as well as to the more complex Multi-Client and Outsourced Symmetric PIR extensions of [Jarecki et al., CCS’13]. We provide performance information based on our prototype implementation, showing the practicality and scalability of our techniques to very large databases, thus extending the performance results of [Cash et al., NDSS’14] to these rich and comprehensive query types.
1
Introduction
Searchable symmetric encryption (SSE) addresses a setting where a client outsources an encrypted database (or document/file collection) to a remote server E such that the client, which only stores a cryptographic key, can later search the collection at E while hiding information about the database and queries from E. Leakage to E is to be confined to well-defined forms of data-access and query patterns while preventing disclosure of explicit data and query plaintext values. SSE has been extensively studied [4–7,9,11–14,16–19,24], particularly in last years due to the popularity of clouds and data outsourcing, focusing almost exclusively on single-keyword search. Recently, Cash et al. [5] and Pappas et al. [19] presented the first SSE solutions that go well beyond single-keyword search by supporting Boolean queries on multiple keywords in sublinear time. In particular, [4,5] build a very scalable system with demonstrated practical performance with databases containing indexes in the order of tens of billions document-keyword pairs. In this work we extend the search capabilities of the system from [5] (referred to as the OXT protocol) by supporting range queries (e.g., return all records of people born between two given dates), substring queries (e.g., return records with textual information containing a given pattern, say ‘crypt’), wildcard queries (combining substrings with one or more single-character wildcards), and phrase queries (return records that contain the phrase “searchable encryption”). Moreover, by preserving the overall system c Springer International Publishing Switzerland 2015 G. Pernul et al. (Eds.): ESORICS 2015, Part II, LNCS 9327, pp. 123–145, 2015. DOI: 10.1007/978-3-319-24177-7 7
124
S. Faber et al.
design and optimized data structures of [4], we can run any of these new queries in combination with Boolean-search capabilities (e.g., combining a range and/or substring query with a conjunction of additional keywords/ranges/substrings) and we can do so while preserving the scalability of the system and additional properties such as support for dynamic data. We also show how to extend our techniques to the more involved multi-client SSE scenarios studied by Jarecki et al. [12]. In the first scenario, denoted MCSSE, the owner of the data, D, outsources its data to a remote server E in e
Data Loading...
