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

A tightly secure BAEKS construction with adaptive full-hiding security under standard MDDH assumptions

Sayantan Mukherjee· 2026· DOI 10.48550/arXiv.2608.29191

The core problem

Broadcast Authenticated Encryption with Keyword Search (BAEKS) extends public-key encryption with keyword search (PEKS) to enable a sender to encrypt a keyword under multiple receivers' public keys, while allowing each receiver to generate a trapdoor for a keyword and test whether a ciphertext contains that keyword. Prior work on BAEKS has not considered the functionality requirement in its most realistic setting: multi-user with adaptive corruptions and multi-challenge (both ciphertext and trapdoor queries in an interleaved manner). This paper fills that gap by proposing a new security definition for BAEKS that captures these realistic adversarial capabilities. The authors also study the unforgeability of BAEKS, showing that their strong hiding requirement already implies a significant amount of unforgeability. The main contribution is a new BAEKS construction in bilinear pairing groups, proven adaptively tight full-hiding secure under (almost) standard MDDH assumptions. Restricting the construction to a single receiver yields an efficient and tightly secure PAEKS construction. The paper further provides experimental implementation and evaluation.

The main result is a BAEKS construction that achieves adaptive tight full-hiding security under (almost) standard MDDH assumptions in the standard model. The security is proven in the multi-user, multi-challenge setting with adaptive corruptions, which is stronger than previous models. The authors show that their strong hiding requirement implies a significant level of unforgeability, meaning that an adversary cannot forge a valid ciphertext for a keyword without the corresponding trapdoor. The scheme is also efficient: the experimental evaluation demonstrates practical performance. When restricted to a single receiver, the construction yields a PAEKS scheme that is both efficient and tightly secure, improving upon prior PAEKS constructions that either lacked tight security or relied on random oracles. The paper provides concrete security bounds and compares the efficiency with existing schemes, showing competitive performance.

Broadcast Authenticated Encryption with Keyword Search (BAEKS) extends public-key encryption with keyword search (PEKS) to enable a sender to encrypt a keyword under multiple receivers' public keys, while allowing each receiver to generate a trapdoor for a keyword and test whether a ciphertext contains that keyword. Prior work on BAEKS has not considered the functionality requirement in its most realistic setting: multi-user with adaptive corruptions and multi-challenge (both ciphertext and trapdoor queries in an interleaved manner). This paper fills that gap by proposing a new security definition for BAEKS that captures these realistic adversarial capabilities. The authors also study the unforgeability of BAEKS, showing that their strong hiding requirement already implies a significant amount of unforgeability. The main contribution is a new BAEKS construction in bilinear pairing groups, proven adaptively tight full-hiding secure under (almost) standard MDDH assumptions. Restricting the construction to a single receiver yields an efficient and tightly secure PAEKS construction. The paper further provides experimental implementation and evaluation.

The proposed BAEKS scheme is built in bilinear pairing groups. Let G_{1}, G_{2}, G_{T} be groups of prime order p with a bilinear map e : G_{1} \times G_{2} \to G_{T} . The construction leverages the Matrix Decisional Diffie-Hellman (MDDH) assumptions, which are standard in pairing-based cryptography. The security proof is conducted in the standard model (without random oracles) and achieves tight security, meaning the security loss is independent of the number of users and challenges. The scheme supports broadcast encryption of keywords to multiple receivers, and trapdoors can be generated by each receiver independently. The authors define a new security notion that combines multi-user adaptive corruptions and multi-challenge settings, where the adversary can interleave ciphertext and trapdoor queries. The proof uses a sequence of games to bound the adversary's advantage by the MDDH assumption. The construction is also adapted to the single-receiver case to obtain a PAEKS scheme with tight security. The paper includes an experimental evaluation to demonstrate efficiency.

The paper advances the state of the art in searchable encryption by addressing the realistic multi-user, multi-challenge setting for BAEKS. The new security definition captures adaptive corruptions and interleaved queries, which are crucial for practical deployments. The tight security proof ensures that the security degradation is minimal even with many users and challenges, making the scheme suitable for large-scale systems. The use of standard MDDH assumptions enhances the confidence in the security. The implied unforgeability is an additional desirable property. The adaptation to PAEKS provides a tightly secure alternative to existing schemes. However, the construction relies on bilinear pairings, which may be more computationally expensive than non-pairing-based schemes. The experimental results suggest that the overhead is acceptable. Future work could explore extensions to other settings, such as multi-keyword search or attribute-based access control. Overall, this work provides a solid foundation for secure and efficient broadcast searchable encryption.

CS practitioners and researchers

Opening member content…