How to Secure Searches in Encrypted Messages Without Slowing Down?

When you send an encrypted email, you usually have to decrypt it before you can search for a keyword. This is impractical, especially with huge archives. The PEKS model (Public Key Encryption with Keyword Search) solved this by allowing authorized users to search keywords directly in encrypted data without revealing the content. However, PEKS has a weakness: the keyword guessing attack (KGA). Because the trapdoor is deterministic, an attacker can guess the associated keyword. To counter this, PAEKS (Public Key Authenticated Encryption with Keyword Search) was introduced, adding source authentication and protecting both the message and the trapdoor. Many PAEKS schemes rely on bilinear pairing, which is computationally heavy. The paper proposes a new variant based on k‑resilient identity‑based encryption, removing the need for bilinear pairing. Formal security proofs show the scheme ensures privacy of both ciphertext and trapdoor. Benchmarks reveal that, especially in the Test phase, the new method is the fastest among competitors. Its practicality was confirmed on a real dataset: the Enron email collection, proving the solution works on large data volumes.

The new PAEKS scheme leverages k‑resilient Identity‑Based Encryption (IBE), a cryptographic construct whose security remains intact even if an adversary compromises up to k‑1 private keys. This approach eliminates bilinear pairings, operations based on elliptic curves that require costly multiplications in large-order groups. Trapdoor security is ensured via a reduction to the Decisional Diffie‑Hellman (DDH) problem in type‑2 groups, while ciphertext privacy relies on the IND‑CPA (Indistinguishability under Chosen‑Plaintext Attack) model. Computational complexity analysis shows that key‑gen, encrypt, and decrypt run in O(log p) time, with p a large prime, whereas the Test operation needs only a scalar multiplication and a hash comparison, drastically cutting execution time compared to pairing‑based methods (O(log² p)). Experiments on the Enron dataset measured throughput (emails/second) and search latency, revealing a 35 % improvement in the Test phase over traditional PAEKS. Moreover, the security proof in the ROM (Random Oracle Model) confirms that, without trapdoor access, an attacker cannot distinguish between different keywords, effectively mitigating KGA. This makes the scheme suitable for cloud‑based scenarios where scalability and fast search are critical.