💻 computer science

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

This paper proposes a new tightly secure Broadcast Authenticated Encryption with Keyword Search (BAEKS) scheme in the standard model that addresses realistic multi-user and multi-challenge settings while ensuring strong hiding and unforgeability properties, alongside an efficient single-receiver variant and experimental evaluation.

Original authors: Sayantan Mukherjee

Published 2026-09-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sayantan Mukherjee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital age, sensitive information is often locked away in encrypted vaults, safe from prying eyes but also inaccessible to the very people who need to find specific details within them. Imagine a hospital where patient records are scrambled to protect privacy; a doctor needs to find a file about a specific allergy, but cannot simply search the scrambled text. To solve this, cryptographers developed a system called searchable encryption. This allows a user to generate a special key, known as a trapdoor, which acts like a unique fingerprint for a specific keyword. A server holding the encrypted files can use this fingerprint to check if a file contains that word without ever seeing the word itself or the file's contents. However, this system has a critical flaw: because the encryption keys are public, a malicious actor can guess common words, create their own test files, and compare them against the trapdoor to reverse-engineer the secret keyword. This is known as a keyword-guessing attack, and it threatens to expose the very secrets the system was designed to protect.

Researchers have tried to fix this by introducing authentication, ensuring that only a specific sender can create a searchable file and only a specific receiver can search it. This evolved into a more complex scenario called broadcast authenticated encryption with keyword search, where a single sender might want to share a secret with a group of authorized receivers, like a doctor sharing a diagnosis with a team of specialists. While previous attempts at this technology offered some protection, they fell short in realistic, high-stakes environments. They often failed to account for scenarios where an attacker could compromise multiple users or make thousands of simultaneous guesses, and their security proofs relied on mathematical shortcuts that left them vulnerable to clever attacks. The existing solutions were like a lock that worked perfectly in a test lab but might fail if someone tried to pick it while the door was being kicked down by a crowd.

A researcher at the Indian Institute of Technology, Jammu, has now proposed a new construction that addresses these weaknesses head-on. They designed a system that remains secure even when an attacker can corrupt multiple users and make a vast number of simultaneous queries in a chaotic, interleaved manner. Their work introduces a rigorous definition of security that ensures the keyword, the sender's identity, and the receiver's identity remain completely hidden, even under the most aggressive attacks. Unlike previous models that relied on idealized assumptions, this new scheme is proven secure in the standard model, meaning its safety holds up under real-world mathematical scrutiny without needing to rely on hypothetical "random oracle" shortcuts that often crumble under pressure.

The researcher built their solution using a specific type of mathematical structure known as bilinear pairing groups, which act as a complex, multi-layered filter for data. They demonstrated that their system is "tightly secure," a technical term meaning that the security guarantee does not degrade as the number of users or the number of attacks increases. In many older systems, the more users there are, the weaker the security becomes, but this new design maintains its strength regardless of scale. They also proved that their method prevents an attacker from forging a fake search key or a fake encrypted file, ensuring that only the genuine sender and receiver can participate in the search.

To verify that their theoretical design could actually work in practice, the researcher implemented the system on a standard virtual machine. They ran experiments with varying numbers of users and different sizes of receiver groups, simulating everything from a single doctor searching for a record to a large hospital network sharing data among a hundred specialists. The results showed that the system is efficient enough for real-world use. For a single search, the process takes less than a second, and even when searching across a group of one hundred people, the time required remains manageable. The computational cost scales linearly, meaning that as the group grows, the time it takes to search increases in a predictable and steady way, rather than exploding into unusable delays.

This work represents a significant step forward in securing encrypted data against sophisticated adversaries. By tightening the security definitions and providing a construction that holds up under adaptive attacks, the researcher has offered a robust tool for environments where privacy is paramount. Their findings suggest that it is possible to have a system where data is not only encrypted but also searchable and authenticated, without sacrificing security for the sake of convenience or scale. The paper concludes that while their current implementation is a proof of concept, it lays the groundwork for future systems that can withstand malicious actors who are actively trying to break the encryption, ensuring that sensitive information remains truly private even in a crowded digital landscape.

Technical Summary: Broadcast Authenticated Encryption with Keyword Search Tightly Secure in Multi-User, Multi-Challenge Settings

1. Problem Statement

Searchable Encryption (SE) allows users to search over encrypted data. While Public-key Encryption with Keyword Search (PEKS) enables this, it is vulnerable to Keyword Guessing Attacks (KGA), where an adversary generates ciphertexts to test against a trapdoor and deduce the keyword. To mitigate this, Public-Key Authenticated Encryption with Keyword Search (PAEKS) was introduced, requiring the sender's secret key for encryption. This was later generalized to Broadcast Authenticated Encryption with Keyword Search (BAEKS) to support a sender encrypting a keyword for a set of authorized receivers.

Despite existing works on BAEKS and PAEKS, several critical gaps remain:

Security Models: Existing schemes often lack security definitions for the multi-user, multi-challenge setting, which is more realistic for deployed systems. Specifically, they fail to account for adaptive corruptions (where an adversary obtains secret keys of users) and interleaved queries (where an adversary challenges ciphertexts and trapdoors simultaneously).
Tightness: Current security reductions suffer from non-trivial multiplicative security losses (e.g., proportional to the number of queries or users), meaning the security guarantee degrades significantly as the system scales.
Consistency: Previous proofs of computational consistency for BAEKS (specifically in works by Emura) have been identified as incomplete or lacking formal reduction arguments.
Anonymity: Many schemes do not simultaneously hide the keyword, the sender's identity, and the receiver's identities in both ciphertexts and trapdoors under strong adversarial models.

2. Methodology and Construction

The author proposes a new BAEKS scheme, denoted as baeks, constructed in bilinear pairing groups (Type-3). The methodology involves:

New Security Definitions: The paper introduces full-cpa security, a definition that allows an adversary to make interleaved challenge queries on ciphertexts, trapdoors, and secret keys (adaptive corruptions). It also defines unforgeability notions (ct-cma and trap-cma), which the author argues are implied by the full-cpa security.
Encoding Strategy: Unlike previous constructions that used Boneh-Boyen hash encodings (which break down in multi-challenge settings due to linear dependencies), the author adopts a structure inspired by tightly secure Identity-Based Encryption (IBE) and Hierarchical IBE (HIBE) using randomized Naor-Reingold PRF structures.
- Users are represented by matrices $U_j$ (sender) and $V_j$ (receiver).
- Keywords are encoded via matrices $K_{\iota, b}$ .
- A tuple $(S, \omega, R)$ is encoded as a sum of these components: $\sum U_{S,i} + \sum K_{\omega,i} + \sum V_{R,i}$ .
- Randomness is injected via a random function $RF(S||\omega||R)$ into the ciphertext and trapdoor encodings.
Proof Technique: The security proof utilizes a hybrid argument involving a series of games ( $G_0$ $G_{0}$ to $G_6$ $G_{6}$ ). A crucial component is a Core Lemma (Theorem 2) which establishes the indistinguishability of the system under specific oracle queries. The proof relies on the Lateral Matrix Diffie-Hellman (lat-MDDH) assumption.
- The proof handles adaptive corruptions by ensuring that even when secret keys of non-challenged users are revealed, the entropy of the challenged users' keys remains sufficient to inject randomness without detection.
- The author addresses the "non-triviality" condition by restricting the adversary from querying secret keys for users involved in challenge ciphertexts or trapdoors.

3. Key Contributions

Novel Security Definition: The paper defines full-cpa security for BAEKS, covering multi-user, multi-challenge, and adaptive corruption settings with interleaved queries. This is the first such definition for BAEKS (and PAEKS) that achieves tight security (security reduction loss is constant, independent of the number of queries).
Tightly Secure Construction: The author presents a new BAEKS construction that achieves adaptive full-cpa security under the standard lat-MDDH assumption in the standard model. Restricting this to a single receiver yields a tightly secure PAEKS.
Unforgeability: The paper demonstrates that the proposed full-cpa security notion inherently implies unforgeability for both ciphertexts and trapdoors.
Consistency Analysis: The author provides a rigorous analysis of the consistency proofs in prior works (specifically Emura's), identifying gaps and offering a statistically consistent construction for their own scheme.
Implementation: The scheme was implemented in Python using the Charm framework. Experiments were conducted on a virtual machine to evaluate performance across varying numbers of receivers ( $\ell$ ), security levels ( $k$ ), and keyword/user space sizes ( $\alpha, u$ ).

4. Results

Security: The scheme is proven secure in the standard model under the lat-MDDH assumption. The security reduction is tight, avoiding the multiplicative loss ( $\Theta(|Q_{Ct}| + |Q_{Tr}|)$ ) found in previous BAEKS and PAEKS schemes.
Performance:
- Setup and KeyGen: These are run once per system/user. Setup complexity scales linearly with the keyword space size $\alpha$ .
- SrchEnc and TrapGen: These are efficient. The cost of encryption and trapdoor generation is largely independent of the number of users $u$ , scaling linearly with the keyword length $\alpha$ and the number of receivers $\ell$ .
- Test: The cloud server performs $2\ell$ bilinear pairings to verify a match. For PAEKS ( $\ell=1$ ), this requires only 2 pairings.
- Experimental Data: The author reports that for $\ell=1$ (PAEKS), the scheme is comparable in efficiency to existing works while offering tighter security. For larger $\ell$ , the overhead is manageable, though the scheme is noted to be slightly less efficient in ciphertext/key size compared to the statistical consistency scheme by Mukherjee [42], but superior in security guarantees.

5. Significance and Claims

The paper claims to revamp existing BAEKS security models by addressing the most realistic threat scenarios: multi-user environments with adaptive corruptions and interleaved challenges. The primary significance lies in achieving tight security in these settings, which was previously an open problem for BAEKS and PAEKS.

The author emphasizes that their work provides the first formalism for BAEKS that simultaneously ensures:

Keyword hiding.
Sender and receiver anonymity.
Resistance to adaptive corruptions.
Tight security reductions.

The paper concludes modestly, noting that while the current construction is a proof-of-concept that is practical, future work could aim for constructions robust against malicious adversaries who generate their own key pairs, and potentially optimize the ciphertext size further. The work also highlights that the tight security of their BAEKS construction immediately translates to a tightly secure PAEKS, filling a gap in the literature for single-receiver authenticated searchable encryption.