Cryptology ePrint Archive: Report 2019/1314

Towards Privacy-Preserving and Efficient Attribute-Based Multi-Keyword Search

Zhidan Li and Wenmin Li and Fei Gao and Wei Yin and Hua Zhang and Qiaoyan Wen and Kaitai Liang

Abstract: Searchable encryption can provide secure search over encrypted cloud-based data without infringing data confidentiality and data searcher privacy. In this work, we focus on a secure search service providing fine-grained and expressive search functionality, which can be seen as a general extension of searchable encryption and called attribute-based multi-keyword search (ABMKS). In most of the existing ABMKS schemes, the ciphertext size of keyword index (encrypted index) grows linearly with the number of the keyword associated with a file, so that the computation and communication complexity of keyword index is limited to O(m) , where m is the number of the keyword. To address this shortage, we propose the first ABMKS scheme through utilizing keyword dictionary tree and the subset cover, in such a way that the ciphertext size of keyword index is not dependent on the number of underlying keyword in a file. In our design, the complexity of computation and the complexity of the keyword index are at most O ( 2 log (n/2) ) for the worst case, but O(1) for the best case, where n is the number of keyword in a keyword dictionary. We also present the security and the performance analysis to demonstrate that our scheme is both secure and efficient in practice.

Category / Keywords: cryptographic protocols / Searchable encryption, keyword dictionary tree, subset cover, attribute-based multi-keyword search, encrypted index.

Date: received 13 Nov 2019

Contact author: zhidanli at bupt edu cn

Available format(s): PDF | BibTeX Citation

Version: 20191117:181320 (All versions of this report)

Short URL: ia.cr/2019/1314


[ Cryptology ePrint archive ]