Ioannis Demertzis (University of Maryland), Javad Ghareh Chamani (Hong Kong University of Science and Technology & Sharif University of Technology), Dimitrios Papadopoulos (Hong Kong University of Science and Technology), Charalampos Papamanthou (University of Maryland)

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 an operation counter for each unique keyword, either stored locally at the client or accessed obliviously (e.g., with an oblivious map) at the server, 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.

View More Papers

SODA: A Generic Online Detection Framework for Smart Contracts

Ting Chen (University of Electronic Science and Technology of China), Rong Cao (University of Electronic Science and Technology of China), Ting Li (University of Electronic Science and Technology of China), Xiapu Luo (The Hong Kong Polytechnic University), Guofei Gu (Texas A&M University), Yufei Zhang (University of Electronic Science and Technology of China), Zhou Liao (University…

Read More

Mind the Portability: A Warriors Guide through Realistic Profiled...

Shivam Bhasin (Nanyang Technological University), Anupam Chattopadhyay (Nanyang Technological University), Annelie Heuser (Univ Rennes, Inria, CNRS, IRISA), Dirmanto Jap (Nanyang Technological University), Stjepan Picek (Delft University of Technology), Ritu Ranjan Shrivastwa (Secure-IC)

Read More

SymTCP: Eluding Stateful Deep Packet Inspection with Automated Discrepancy...

Zhongjie Wang (University of California, Riverside), Shitong Zhu (University of California, Riverside), Yue Cao (University of California, Riverside), Zhiyun Qian (University of California, Riverside), Chengyu Song (University of California, Riverside), Srikanth V. Krishnamurthy (University of California, Riverside), Kevin S. Chan (U.S. Army Research Lab), Tracy D. Braun (U.S. Army Research Lab)

Read More

You Are What You Do: Hunting Stealthy Malware via...

Qi Wang (University of Illinois Urbana-Champaign), Wajih Ul Hassan (University of Illinois Urbana-Champaign), Ding Li (NEC Laboratories America, Inc.), Kangkook Jee (University of Texas at Dallas), Xiao Yu (NEC Laboratories America, Inc.), Kexuan Zou (University Of Illinois Urbana-Champaign), Junghwan Rhee (NEC Laboratories America, Inc.), Zhengzhang Chen (NEC Laboratories America, Inc.), Wei Cheng (NEC Laboratories America,…

Read More