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
[ Cryptology ePrint archive ]