Paper 2023/591

Post-Quantum Public-key Authenticated Searchable Encryption with Forward Security: General Construction, and Applications

Abstract

Public-key encryption with keyword search (PEKS) was first proposed by Boneh et al. (EUROCRYPT 2004), achieving the ability to search for ciphertext files. Nevertheless, it is vulnerable to inside keyword guessing attacks (IKGA). Public-key authenticated encryption with keyword search (PAEKS), introduced by Huang et al. (Inf. Sci. 2017), on the other hand, is secure against IKGA. Nonetheless, it is susceptible to quantum computing attacks. Liu et al. and Cheng et al. addressed this problem by reducing to the lattice hardness (AsiaCCS 2022, ESORICS 2022). Furthermore, several scholars pointed out that the threat of secret key exposure delegates a severe and realistic concern, potentially leading to privacy disclosure (EUROCRYPT 2003, Compt. J. 2022). As a result, research focusing on mitigating key exposure and resisting quantum attacks for the PAEKS primitive is far-reaching. In this work, we present the first generic construction and instantiation of forward-secure PAEKS primitive based on lattice hardness without trusted authorities, mitigating the secret key exposure while ensuring quantum-safe properties. We extend the scheme of Liu et al. (AsiaCCS 2022), and formalize a novel post-quantum PAEKS construction, namely FS-PAEKS. To begin with, we introduce the binary tree structure to represent the time periods, along with a lattice basis extension algorithm, and SamplePre algorithm to obtain the post-quantum one-way secret key evolution, allowing users to update their secret keys periodically. Furthermore, our scheme is proven to be IND-CKA and IND-IKGA secure in a quantum setting. In addition, we also compare the security of our primitive in terms of computational complexity and communication overhead with other top-tier schemes. Ultimately, we demonstrate two potential applications of FS-PAEKS.