Paper 2019/1314

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

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


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Searchable encryptionkeyword dictionary treesubset coverattribute-based multi-keyword searchencrypted index.
Contact author(s)
zhidanli @ bupt edu cn
2019-11-17: received
Short URL
Creative Commons Attribution


      author = {Zhidan Li and Wenmin Li and Fei Gao and Wei Yin and Hua Zhang and Qiaoyan Wen and Kaitai Liang},
      title = {Towards Privacy-Preserving and Efficient Attribute-Based Multi-Keyword Search},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1314},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.