Research Article

Efficient verifiable searchable encryption with search and access pattern privacy

¹ State Key Laboratory of Cryptology, Beijing, 100878, China
² TCA Laboratory, Institute of Software, Chinese Academy of Sciences, Beijing, 100190, China
³ National Engineering Research Center for Secured Wireless (NERCSW), School of Cyberspace Security, Xi’an University of Posts & Telecommunications, Xi’an, 710121, China

^* Corresponding author (email: waxinsec@163.com)

Received: 16 October 2024
Revised: 8 November 2024
Accepted: 17 December 2024

Abstract

Searchable encryption (SE) enables data users to securely search encrypted data stored in untrusted cloud servers. However, most SE schemes allow for leakages of access and search patterns to maximize efficiency and functionality. Recent attacks have shown that adversaries can recover query keywords with prior knowledge of the database by exploiting these leakages. Unfortunately, the existing schemes that protect access and search patterns result in frequent communications and high computational costs. Furthermore, complex calculation processes also raise challenges for verifying search results. To address these concerns, we first design an efficient conjunctive SE scheme with search and access pattern privacy using private set intersection. In the proposed scheme, we utilize random numbers to obfuscate the values of polynomials and randomly divide the results into two parts, which simplifies the search process, improves search efficiency, and eliminates the need for time-consuming ciphertext multiplication operations. We also extend this scheme to support search result verifiability. Specifically, by embedding a random number as the root of the return polynomial, we achieve verifiability of search results. Furthermore, we prove the security of both schemes employing the simulation-based method. Finally, we implement the schemes in a real database and thorough performance analyses demonstrate their efficiency.