SHS: Secure Hybrid Search by Combining Dynamic and Static Indexes in PEKS

Peng Xu; Hai Jin

Paper 2011/190

SHS: Secure Hybrid Search by Combining Dynamic and Static Indexes in PEKS

Peng Xu and Hai Jin

Abstract

With a significant advance in ciphertext searchability, Public-key encryption with keyword search (PEKS) is the first keyword searchable encryption scheme based on the probabilistic encryption, such that it is more secure than almost all previous schemes. However, there is an open problem in PEKS that its search complexity is linear with the sum of ciphertexts, such that it is inefficient for a mass of ciphertexts. Fortunately, we find an elegant method that by adaptively taking the keyword trapdoor of each query as an index, the search complexity of the queried keywords can be decreased in a huge degree. We call this method dynamic index (DI) technique. Furthermore, for keywords having not been queried before, we employ deterministic encryption to establish indexes to decrease their first search complexity. We call this method static index (SI) technique. Consequently, we propose a secure hybrid search (SHS) system by combing DI and SI techniques in PEKS to decrease the search complexity of PEKS. At last, we demonstrate its semantic security and convergent search complexity, which is considerably lower than that of PEKS.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: public-key encryption with keyword search dynamic index technique static index technique secure hybrid search
Contact author(s): xupeng @ mail hust edu cn
History: 2011-04-16: received
Short URL: https://ia.cr/2011/190
License: CC BY

BibTeX

@misc{cryptoeprint:2011/190,
      author = {Peng Xu and Hai Jin},
      title = {{SHS}: Secure Hybrid Search by Combining Dynamic and Static Indexes in {PEKS}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/190},
      year = {2011},
      url = {https://eprint.iacr.org/2011/190}
}