You are looking at a specific version 20201110:125231 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Industrial SecurityOblivious RAMSearchable Symmetric Encryption
Contact author(s)
wzq @ csust edu cn
History
2022-06-27: withdrawn
2020-11-10: received
See all versions
Short URL
https://ia.cr/2020/1387
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.