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 technology 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. Then, we further present the first quantum-resistant PAEKS instantiation based on lattices. The security proofs show that our instantiation not only satisfies the basic requirements but also achieves enhanced security models, namely the multi-ciphertext indistinguishability and multi-trapdoor privacy. Furthermore, the comparative results indicate that with only some additional expenditure, the proposed instantiation provides 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 authenticated encryption

Original Publication (in the same form): ASIACCS 2022

Date: received 29 Jul 2021, last revised 23 Nov 2021

Contact author: zyliu at cs nccu edu tw

Available format(s): PDF | BibTeX Citation

Version: 20211123:100238 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]