Paper 2020/1387

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

Zhiqiang Wu, Kenli Li, 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.