Dynamic Searchable Encryption with Small Client Storage

被引:52
作者
Demertzis, Ioannis [1 ]
Chamani, Javad Ghareh [2 ,3 ]
Papadopoulos, Dimitrios [2 ]
Papamanthou, Charalampos [1 ]
机构
[1] Univ Maryland, College Pk, MD 20742 USA
[2] Hong Kong Univ Sci & Technol, Hong Kong, Peoples R China
[3] Sharif Univ Technol, Tehran, Iran
来源
27TH ANNUAL NETWORK AND DISTRIBUTED SYSTEM SECURITY SYMPOSIUM (NDSS 2020) | 2020年
基金
美国国家科学基金会;
关键词
D O I
10.14722/ndss.2020.24423
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We study the problem of dynamic searchable encryption (DSE) with forward-and-backward privacy. Many DSE schemes have been proposed recently but the most efficient ones have one limitation: they require maintaining one operation counter for each unique keyword, either stored locally at the client or stored encrypted at the server and accessed obliviously (e.g., with an oblivious map) during every operation. We propose three new schemes that overcome the above limitation and achieve constant permanent client storage with improved performance, both asymptotically and experimentally, compared to prior state-of-the-art works. In particular, our first two schemes adopt a "static-to-dynamic" transformation which eliminates the need for oblivious accesses during searches. Due to this, they are the first practical schemes with minimal client storage and non-interactive search. Our third scheme is the first quasi-optimal forward-and-backward DSE scheme with only a logarithmic overhead for retrieving the query result (independently of previous deletions). While it does require an oblivious access during search in order to keep permanent client storage minimal, its practical performance is up to four orders of magnitude better than the best existing scheme with quasi-optimal search.
引用
收藏
页数:18
相关论文
共 51 条
[1]  
Amjad G., 2019, EUROSEC
[2]  
[Anonymous], 2014, NDSS
[3]  
[Anonymous], 2014, NDSS
[4]  
Asharov G, 2018, IACR
[5]   Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations [J].
Asharov, Gilad ;
Naor, Moni ;
Segev, Gil ;
Shahaf, Ido .
STOC'16: PROCEEDINGS OF THE 48TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2016, :1101-1114
[6]  
Boneh D., 2013, ASIACRYPT
[7]   Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives [J].
Bost, Raphael ;
Minaud, Brice ;
Ohrimenko, Olga .
CCS'17: PROCEEDINGS OF THE 2017 ACM SIGSAC CONFERENCE ON COMPUTER AND COMMUNICATIONS SECURITY, 2017, :1465-1482
[8]  
Bost Raphael, 2016, CCS
[9]  
Boyle E., 2014, PKC
[10]  
Cash D, 2013, LECT NOTES COMPUT SC, V8042, P353, DOI 10.1007/978-3-642-40041-4_20