Abstract
This paper presents a critical security analysis of two cryptographic schemes designed for searching encrypted cloud data: Identity-Based Encryption with Equality Test (IBEET) and Ciphertext-Policy Attribute-Based Encryption with Equality Test (CP-ABEET). Through formal cryptanalysis, the authors demonstrate that both schemes are fundamentally broken, failing to meet their claimed security guarantees of One-Wayness under Chosen Ciphertext Attack (OW-ID-CCA) and Indistinguishability under Chosen Plaintext Attack (IND-CPA), respectively.
Introduction
As organizations increasingly outsource data storage to the cloud, a significant challenge arises in balancing data privacy with search utility. While encryption protects data from unauthorized access, it typically prevents the cloud server from performing useful operations like searching. Public-Key Encryption with Equality Test (PKEET) was introduced to bridge this gap, allowing a cloud server to determine if two different ciphertexts contain the same underlying message (e.g., a specific keyword) without decrypting the data.
To enhance flexibility, researchers proposed more granular models:
- IBEET: Ties the equality test to a user's identity (e.g., an email address).
- CP-ABEET: Ties the test to specific attributes or policies (e.g., "Department=HR" AND "Role=Manager").
This paper investigates whether two prominent schemes—proposed by Ma and Wang et al.—actually provide the security they claim against curious cloud providers or external adversaries.
System Model for Encryption with Equality Test
The functionality of these schemes relies on a specific interaction between several entities: a Key Generation Center (KGC), data owners (users), and a cloud server. The KGC issues private keys, while users generate ciphertexts and "trapdoors." The trapdoor is a specific piece of information that allows the cloud server to perform the equality test without gaining the ability to decrypt the full message.
Cryptanalysis Methods
The authors employ formal security games to test the robustness of the schemes. In these games, an adversary is given specific powers—such as the ability to request certain keys or trapdoors—and must then attempt to break the encryption (either by recovering the plaintext or distinguishing between two possible plaintexts).
Vulnerabilities in IBEET
In Ma’s IBEET scheme, the authors identified a flaw in the "One-Wayness under Chosen Ciphertext Attack" (OW-ID-CCA) model. They discovered that the encryption of the message and the random elements used for the equality test were handled almost independently. This modularity allowed an adversary to use a legitimate trapdoor to tamper with a challenge ciphertext. By submitting a slightly modified but still valid ciphertext to a decryption oracle, the adversary could trick the system into revealing the original secret message.
Vulnerabilities in CP-ABEET
For the CP-ABEET scheme proposed by Wang et al., the authors targeted the "Indistinguishability under Chosen Plaintext Attack" (IND-CPA) model. They found that the bilinear pairing equations used for the equality test leaked significant information. Specifically, the information contained within the trapdoor was sufficient for an adversary to mathematically verify which of two messages was encrypted, effectively breaking the confidentiality of the scheme with 100% success.
Key Insights
- The Trapdoor Gap: Previous authors failed to account for the full power of an adversary who possesses a trapdoor. In these schemes, the trapdoor intended for testing equality inadvertently provided a side-channel for decryption or message verification.
- Independent Component Vulnerability: The lack of strong mathematical binding between the message encryption and the equality test components in the IBEET scheme allowed for successful tampering.
Proposed Fixes and Future Work
The authors suggest a conceptual fix for the IBEET scheme by binding the random elements ($r_2$ and $r_3$) used during encryption. By making these values identical, the ciphertext structure becomes more rigid, making it significantly harder to tamper with one part without invalidating the whole. This modification reduces the potential for attack to the "Hard" Bilinear Diffie-Hellman problem.
However, the paper notes that creating a secure CP-ABEET scheme in the "standard model"—a rigorous mathematical environment that does not rely on idealized random oracles—remains an open and significant challenge. The authors identify the development of such a scheme as a primary goal for future research in secure cloud data utility.
Summary updated