Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency
Preprint
Abstract
Recently, several practical attacks raised serious concerns over the security of searchable encryption. The attacks have brought emphasis on forward privacy, which is the key concept behind solutions to the adaptive leakage-exploiting attacks, and will very likely to become mandatory in the design of new searchable encryption schemes. For a long time, forward privacy implies inefficiency and thus most existing searchable encryption schemes do not support it. Very recently, Bost (CCS 2016) showed that forward privacy can be obtained without inducing a large communication overhead. However, Bost's scheme is constructed with a relatively inefficient public key cryptographic primitive, and has a poor I/O performance. Both of the deficiencies significantly hinder the practical efficiency of the scheme, and prevent it from scaling to large data settings. To address the problems, we first present FAST, which achieves forward privacy and the same communication efficiency as Bost's scheme, but uses only symmetric cryptographic primitives. We then present FASTIO, which retains all good properties of FAST, and further improves I/O efficiency. We implemented the two schemes and compared their performance with Bost's scheme. The experiment results show that both our schemes are highly efficient, and FASTIO achieves a much better scalability due to its optimized I/O.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Searchable Encryption with Optimal Locality: Achieving Sublogarithmic Read Efficiency2018
- IO-DSSE: Scaling Dynamic Searchable Encryption to Millions of Indexes By Improving Locality2017
- A Secure and Dynamic Multi-Keyword Ranked Search Scheme over Encrypted Cloud DataIEEE Transactions on Parallel and Distributed Systems, 2015
- Practical Dynamic Searchable Encryption with Small Leakage2014
- Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation2014
- Shared and searchable encrypted data for untrusted serversJournal of Computer Security, 2011
- Oblivious RAM with O((logN)3) Worst-Case Cost2011
- Structured Encryption and Controlled Disclosure2010
- Fully homomorphic encryption using ideal lattices2009
- Software protection and simulation on oblivious RAMsJournal of the ACM, 1996