Cryptology ePrint Archive: Report 2018/497

Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency

Xiangfu Song and Changyu Dong and Dandan Yuan and Qiuliang Xu and Minghao Zhao

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 a must-have property of all 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 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.

Category / Keywords: secret-key cryptography / searchable encryption, symmetric primitives, forward privacy, I/O efficiency

Original Publication (in the same form): IEEE Transactions on Dependable and Secure Computing

Date: received 22 May 2018, last revised 23 May 2018

Contact author: changyu dong at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180523:121348 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]