Searchable Symmetric Encryption
- 26 May 2017
- journal article
- survey
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 50 (3), 1-37
- https://doi.org/10.1145/3064005
Abstract
Searchable Symmetric Encryption (SSE) when deployed in the cloud allows one to query encrypted data without the risk of data leakage. Despite the widespread interest, existing surveys do not examine in detail how SSE’s underlying structures are designed and how these result in the many properties of a SSE scheme. This is the gap we seek to address, as well as presenting recent state-of-the-art advances on SSE. Specifically, we present a general framework and believe the discussions may lead to insights for potential new designs. We draw a few observations. First, most schemes use index table, where optimal index size and sublinear search can be achieved using an inverted index. Straightforward updating can only be achieved using direct index, but search time would be linear. A recent trend is the combinations of index table, and tree, deployed for efficient updating and storage. Secondly, mechanisms from related fields such as Oblivious RAM (ORAM) have been integrated to reduce leakages. However, using these mechanisms to minimise leakages in schemes with richer functionalities (e.g., ranked, range) is relatively unexplored. Thirdly, a new approach (e.g., multiple servers) is required to mitigate new and emerging attacks on leakage. Lastly, we observe that a proposed index may not be practically efficient when implemented, where I/O access must be taken into consideration.Keywords
Funding Information
- Rackspace
- Cloud Technology Endowed Professorship from the 80/20 Foundation
This publication has 83 references indexed in Scilit:
- Toward Practical Searchable Symmetric EncryptionLecture Notes in Computer Science, 2013
- Parallel and Dynamic Searchable Symmetric EncryptionLecture Notes in Computer Science, 2013
- Highly-Scalable Searchable Symmetric Encryption with Support for Boolean QueriesLecture Notes in Computer Science, 2013
- How to Update Documents Verifiably in Searchable Symmetric EncryptionLecture Notes in Computer Science, 2013
- Functional encryptionCommunications of the ACM, 2012
- On the (im)possibility of obfuscating programsJournal of the ACM, 2012
- Near-optimal hashing algorithms for approximate nearest neighbor in high dimensionsCommunications of the ACM, 2008
- Signal Processing in the Encrypted DomainEURASIP Journal on Information Security, 2007
- Software protection and simulation on oblivious RAMsJournal of the ACM, 1996
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970