Broadcast Authenticated Encryption with Keyword Search

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.