Secure hybrid-indexed search for high efficiency over keyword searchable ciphertexts

• We propose our high efficient Secure Hybrid Indexed Search (SHIS) scheme.
• We model semantic secure SHIS with universal transformations from PEKS and DE.
• We show the complexity of SHIS is much lower than PEKS and convergent.
• We universally extend SHIS by PKE schemes towards multiple-receiver applications.

With a significant advance in ciphertext searchability, public-key encryption with keyword search (PEKS) guarantees both security and convenience for outsourced keyword search over ciphertexts. In this paper, we establish static index (SI) and dynamic index (DI) for PEKS to make search efficient and secure in the state of the art. Suppose there are uu senders to generate nn searchable ciphertexts for ww keywords. The search complexity of PEKS always is O(n)O(n) for each query, even if the keyword has been searched for multiple times. It is obviously inefficient for massive searchable ciphertexts. Fortunately, SI and DI help PEKS lowering the burden respectively in two phases: if the queried keyword is the first time to be searched, apply SI to reduce the complexity from O(n)O(n) to O(u⋅w)O(u⋅w); otherwise, apply DI to reduce the complexity from O(n)O(n) to O(w)O(w). Because DI is invalid for the first time search on any keyword, SI and DI are simultaneously applied with PEKS to complete our work as the secure hybrid indexed search (SHIS) scheme. Since u≪w≪nu≪w≪n in practice, our SHIS scheme is significantly more efficient than PEKS as demonstrated by our analysis. In the end, we show the extension of SHIS to multi-receiver applications, which is absent for pure PEKS.