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

Abstract

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.