Public Key Encryption with Keyword Search (PEKS) is a desirable technique to provide searchable functionality over encrypted data in public key settings, which allows a user to delegate a third party server to perform the search operation on encrypted data by means of keyword search trapdoor without learning about the data. However, the existing PEKS schemes cannot be directly applied to practice due to keyword guessing attack or the absence of a mechanism to limit the lifetime of a trapdoor. By addressing these issues at the same time, this paper presents a Public Key Encryption Scheme with Temporary and Fuzzy Keyword Search (PETFKS) by using a fuzzy function and an encryption tree. The proposed PETFKS scheme is proven adaptively secure concerning keyword confidentiality and backward and forward secrecy in the random oracle model under the Bilinear Di e-Hellman assumption. Moreover, it is also proven selectively secure with regard to the resistance of keyword guessing attack. Furthermore, the security and e ciency analyses of the proposed scheme are provided by comparing to the related works. The analyses indicate that the proposed scheme makes a threefold contribution to the practical application of public key encryption with keyword search, namely o ering secure search operation, limiting the lifetime of a trapdoor and enabling secure time-dependent data retrieval.