A New Trapdoor-indistinguishable Public Key Encryption with Keyword Search

Yuanjie Zhao, Xiaofeng Chen, Hua Ma, Qiang Tang, Hui ZhuJ. Wirel. Mob. Networks Ubiquitous Comput. Dependable Appl 2012 · OpenReview

Abstract

As sensitive data migrates to cloud environments, the need for privacy-preserving search mechanisms becomes paramount. Public Key Encryption with Keyword Search (PEKS) allows servers to search encrypted data without decryption, but traditional models suffer from secure channel dependencies and deterministic trapdoors vulnerable to statistical attacks. This paper proposes a new Secure Channel-Free (SCF) PEKS scheme that achieves trapdoor indistinguishability through randomization. Our approach eliminates the need for a secure communication line and reduces computational overhead for the receiver, offering a more practical solution for internet-scale deployment.

Introduction

The transition to cloud storage presents a fundamental paradox: users require data encryption for privacy, yet they also need efficient search capabilities. Public Key Encryption with Keyword Search (PEKS) was developed to address this. However, early implementations faced two critical limitations. First, the Secure Channel Requirement assumed a perfectly private channel for exchanging search "trapdoors," which is often impractical in real-world scenarios. Second, Trapdoor Determinism meant that a keyword always produced the same trapdoor, allowing attackers to perform frequency-analysis or keyword-guessing attacks.

The authors aim to resolve these issues by creating a system where search queries (trapdoors) for the same keyword appear different every time, achieving trapdoor indistinguishability.

Methodology

The proposed scheme is built upon Bilinear Pairings, utilizing mathematical groups ($G_1$ and $G_2$) and a mapping function. The innovation centers on a dynamic Trapdoor Generation Algorithm:

  • Randomization: Each search session incorporates a unique random element, ensuring that the resulting trapdoor is session-specific and unique even for repeated keywords.
  • Server-Side Verification: Despite the randomization, the server can leverage its private key and bilinear map properties to "cancel out" the noise and verify keyword matches against encrypted documents.
  • Security Proofs: The construction is formally proven to be secure against Chosen Plaintext Attacks (IND-CPA) for both ciphertexts and trapdoors.

Comparative Analysis and Results

The authors evaluate their scheme against existing state-of-the-art models, including standard PEKS, SCF-PEKS, and dual-PEKS (dPEKS).

Security Features

A primary advantage of this scheme is its comprehensive security profile. Unlike its predecessors, it simultaneously satisfies trapdoor indistinguishability and removes the secure channel requirement.

Table 2: Comparison of security features across different schemes

Performance and Efficiency

The scheme optimizes performance at the "edge"—specifically for the receiver, who often operates on resource-constrained devices like mobile phones.

  • Computational Cost: The receiver's cost is reduced to $2e$ (two modular exponentiations), outperforming the dPEKS model which requires $3e+m$.
  • Storage Trade-off: To achieve these security gains, the ciphertext size is slightly increased to $3G$, compared to $2G$ in older models.
Table 1: Comparison of storage and computational costs

Key Insights

  • Dynamic Trapdoors: By making search queries a "moving target," the scheme effectively neutralizes frequency-analysis attacks.
  • Public Channel Safety: Incorporating the server's public key into the encryption process facilitates practical deployment without pre-existing private lines.

Limitations and Future Work

While the mathematical foundation is robust, certain challenges remain. The increased ciphertext size may impact systems managing billions of keywords. Additionally, like most pairing-based cryptography, the scheme is theoretically vulnerable to future quantum computing attacks. Future research should focus on real-world implementation (e.g., on AWS or Azure) to provide concrete latency and energy consumption benchmarks.

Summary updated

BibTeX
@article{zhao2012new,
  author = {Yuanjie Zhao and Xiaofeng Chen and Hua Ma and Qiang Tang and Hui Zhu},
  title = {{A New Trapdoor-indistinguishable Public Key Encryption with Keyword Search}},
  journal = {J. Wirel. Mob. Networks Ubiquitous Comput. Dependable Appl.},
  year = {2012},
  url = {https://openreview.net/forum?id=aNQeTiIoAw},
}
Figure