Paper 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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- CryptanalysisGeneric constructionTrapdoor privacyPost-quantumKeyword searchPublic-key encryption
- Contact author(s)
- zyliu @ cs nccu edu tw
- History
- 2022-04-19: last of 5 revisions
- 2021-08-06: received
- See all versions
- Short URL
- https://ia.cr/2021/1008
- License
-
CC BY