Paper 2017/741

Dynamic Searchable Public-Key Ciphertexts with Fast Performance and Practical Security

Peng Xu, Xia Gao, Wei Wang, Willy Susilo, Qianhong Wu, and Hai Jin


Public-key encryption with keyword search (PEKS) allows a sender to generate keyword-searchable ciphertexts using a receiver’s public key and upload them to a server. Upon receiving a keyword-search trapdoor from the receiver, the server finds all matching ciphertexts. Due to the characteristics of public-key encryption, PEKS is inherently suitable for the application of numerous senders. Hence, PEKS is a well-known method to achieve secure keyword search over the encrypted email system. However, we find that without a keyword-search trapdoor, the traditional concept of PEKS still allows the server to have the obvious advantage to distinguish ciphertexts in practice. In other words, the traditional PEKS cannot guarantee the well-recognized semantic security in practice. To solve this problem, this paper defines a new concept called dynamic searchable public-key encryption (DSPE). It can hide the relationships between keyword-searchable ciphertexts and their corresponding encrypted files, and guarantee semantic security in both theory and practice. In addition, it allows the server to delete the intended ciphertexts according to the receiver’s requirement. Then, we construct a DSPE instance with provable semantic security in the random oracle model. In terms of performance, the proposed instance also has the advantage that it only requires sublinear complexity to determine all matching ciphertexts or to delete the intended ciphertexts. Finally, we experimentally demonstrate the practicability of the instance.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Public Key Encryption with Keyword Search
Contact author(s)
wsusilo @ uow edu au
2017-08-07: received
Short URL
Creative Commons Attribution


      author = {Peng Xu and Xia Gao and Wei Wang and Willy Susilo and Qianhong Wu and Hai Jin},
      title = {Dynamic Searchable Public-Key Ciphertexts with Fast Performance and Practical Security},
      howpublished = {Cryptology ePrint Archive, Paper 2017/741},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.