EVMK-SSE: Efficient and Verifiable Multi-Keyword SSE from client-independent relaxed OPRF for outsourced database in cloud

Symmetric searchable encryption (SSE) is a foundational technology that enables privacy-preserving queries of encrypted data stored on untrusted cloud servers. However, advanced schemes that pursue strong privacy guarantees often face significant challenges when leveraging cryptographic primitives like private set intersection (PSI). These schemes rely on computationally expensive operations, which create performance bottlenecks in practical multi-keyword queries. Furthermore, their security models typically do not consider attacks where a malicious cloud server returns forged results. To address these challenges of efficiency and security, this paper proposes EVMK-SSE, an efficient and verifiable multi-keyword SSE scheme. Its core mechanism is to modify the Diffie-Hellman oblivious pseudorandom function (DH-OPRF) used in prior works into a lightweight, oblivious transfer-based client-independent relaxed OPRF. This substitution removes expensive exponentiation operations from the critical path and instead uses only symmetric-key primitives, yielding a 5-6$$\times $$ speedup in the core computational phases compared with the DH-OPRF. Furthermore, to defend against a malicious server, we integrate a lightweight verification mechanism. By embedding a verification tag within the file key and employing an authenticated encryption with associated data scheme, EVMK-SSE empowers the data user to detect any tampering of the results. Our implementation and comprehensive performance evaluation demonstrate the practical advantages of the scheme. For a database containing $$2^{24}$$ entries, the setup time is over five times faster than the related scheme. Token generation time for $$2^{16}$$ keywords is reduced by almost six times, confirming the scheme’s efficiency and scalability.