A Searchable Encryption Scheme Based on Approximate Trapdoor Sampling

Public key encryption with keyword search (PEKS) over lattice plays an important role in ensuring the privacy, confidentiality, and flexibility of outsourced data while resisting quantum attacks. However, most existing lattice-based PEKS schemes are limited by the underlying preimage sampling algorithm, which suffers from high storage overhead or low efficiency issues. To address the above problems, an optimized public key encryption with keyword search scheme is first proposed. The scheme utilizes a new approximate trapdoor sampling algorithm to improve the computational efficiency. The algorithm outputs an approximate rather than an exact preimage. Then, a combination of non-spherical Gaussian sampling technique and an ideal extendable-output function is used to reduce key and trapdoor storage. Furthermore, an extended scheme with forward security and backward security is introduced to address the basic scheme’s update and search operation leakage. To avoid newly updated ciphertexts matching previous trapdoors, i.e., forward security, the key is periodically updated through a lattice-based delegation mechanism. To prevent subsequent searches from leaking information about deleted files, i.e., backward security, the addition and deletion of files is achieved by combining the bitmap index and lattice-based homomorphic encryption scheme. Theoretical analysis and experimental results exhibit that, compared with the efficient PEKS scheme, the proposed scheme reduces the public key storage overhead by 4.6% and the trapdoor storage overhead by 50.1%, and improves the efficiency of encryption, trapdoor generation, and search by 11.11%, 2.5%, and 26.15%, respectively.