Broadcast Authenticated Encryption with Keyword Search

Publication Name

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)


The emergence of public-key encryption with keyword search (PEKS) has provided an elegant approach to enable keyword search over encrypted content. Due to its high computational complexity proportional to the number of intended receivers, the trivial way of deploying PEKS for data sharing with multiple receivers is impractical, which motivates the development of a new PEKS framework for broadcast mode. However, existing works suffer from either the vulnerability to keyword guessing attacks (KGA) or high computation and communication complexity. In this work, a new primitive for keyword search in broadcast mode, named broadcast authenticated encryption with keyword search (BAEKS), is introduced, in which the sender not only encrypts the keyword but also authenticates it, eliminating the threats of KGA. Moreover, on top of keyword privacy, we formalize the notion of user anonymity (or key privacy) for BAEKS, which echoes the notion of key privacy for public-key encryption introduced by Bellare et al. (ASIACRYPT’01). We present a practical BAEKS construction that achieves all the desirable features, including keyword privacy of both searchable ciphertext and trapdoor, KGA-resistance, receiver anonymity of both searchable ciphertext and trapdoor, and universal keyword set scalability. Moreover, the trapdoor of our scheme achieves constant computation and communication cost, making it more suitable for broadcast mode where trapdoors are generated by multiple receivers in the search operations. The security of our scheme is proved under the standard DBDH assumption.

Open Access Status

This publication is not available as open access


13083 LNCS

First Page


Last Page


Funding Number


Funding Sponsor

National Natural Science Foundation of China



Link to publisher version (DOI)