Cryptology ePrint Archive: Report 2021/1008

Public-key Authenticated Encryption with Keyword Search: Cryptanalysis, Enhanced Security, and Quantum-resistant Instantiation

Zi-Yuan Liu and Yi-Fan Tseng and Raylin Tso and Masahiro Mambo and Yu-Chi Chen

Abstract: With the rapid development of cloud computing, an increasing number of companies are adopting cloud storage to reduce overhead. However, to ensure the privacy of sensitive data, the uploaded data need to be encrypted before being outsourced to the cloud. The concept of public-key encryption with keyword search (PEKS) was introduced by Boneh \textit{et al.} to provide flexible usage of the encrypted data. Unfortunately, most of the PEKS schemes are not secure against inside keyword guessing attacks (IKGA), so the keyword information of the trapdoor may be leaked to the adversary. To solve this issue, Huang and Li presented public key authenticated encryption with keyword search (PAEKS) in which the trapdoor generated by the receiver is only valid for authenticated ciphertexts. With their seminal work, many PAEKS schemes have been introduced for the enhanced security of PAEKS. Some of them further consider the upcoming quantum attacks. However, our cryptanalysis indicated that in fact, these schemes could not withstand IKGA. To fight against the attacks from quantum adversaries and support the privacy-preserving search functionality, we first introduce a novel generic PAEKS construction in this work. We further present the first quantum-resistant PAEKS instantiation based on lattices. The security proofs showed that our instantiation not only satisfied the basic requirements but also achieved an enhanced security model, namely the multi-ciphertext and multi-trapdoor indistinguishability. Furthermore, the comparative results indicated that with only some additional expenditure, this instantiation could provide more secure properties, making it suitable for more diverse application environments.

Category / Keywords: public-key cryptography / Cryptanalysis, Generic construction, Trapdoor privacy, Post-quantum, Keyword search, Public-key encryption

Date: received 29 Jul 2021

Contact author: zyliu at cs nccu edu tw

Available format(s): PDF | BibTeX Citation

Version: 20210806:072031 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]