Cryptology ePrint Archive: Report 2020/1387

FB-Tree: Highly Efficient Tree-Based Index for Encrypted Boolean Queries in Smart Cities

Zhiqiang Wu and Kenli Li and Jin Wang and Naixue Xiong

Abstract: To expand capacity, many resource-constrained industrial devices encrypt and outsource their private data to public clouds, employing a searchable encryption (SE) scheme that provides efficient search service directly to encrypted data. Current tree-based SE schemes can do this and support sublinear encrypted Boolean queries. However, they all suffer from log n overhead in a search procedure. To resolve the challenge, in this paper, we propose a new tree structure called the four-branch tree (FB-tree). Our key design is to build a tree node with four branches, which helps a search reach the destination nodes with fast jumps. Based on the index tree, we setup two systems for different requirements. The first system for efficiency-first settings achieves nearly optimal search complexity and adaptive security. The second, constructed via an oblivious RAM for security-first environments, still achieves worst-case sublinear search complexity. FB-tree performance is extensively evaluated with several real datasets. The Experimental data demonstrate that the FB-tree-based systems outperform the state-of-the-art solutions in terms of efficiency and scalability when Boolean queries are issued.

Category / Keywords: cryptographic protocols / Industrial Security, Oblivious RAM, Searchable Symmetric Encryption

Date: received 6 Nov 2020

Contact author: wzq at csust edu cn

Available format(s): PDF | BibTeX Citation

Version: 20201110:125231 (All versions of this report)

Short URL: ia.cr/2020/1387