Statistically Consistent Broadcast Authenticated Encryption with Keyword Search Adaptive Security from Standard Assumptions

Searchable Encryption (SE) allows users to perform a keyword search over encrypted documents. In Eurocrypt'04, Boneh et al. introduced Public-key Encryption with Keyword Search (PEKS). Broadcast Encryption with Keyword Search (BEKS) is a natural progression to allow some amount of access control. Unfortunately, PEKS and BEKS suffer from keyword-guessing attacks (KGA). In the case of KGA, an adversary guesses the keyword encoded in a trapdoor by creating a ciphertext on a sequence of keywords of its choice and testing them against the trapdoor. In ACISP'21, Liu et al. introduced a variant of BEKS called Broadcast Authenticated Encryption with Keyword Search (BAEKS), which tried to mitigate KGA in BEKS. This construction did not argue consistency and achieved weaker security in the random oracle model. In this work, we first introduce the notion of consistency for BAEKS and introduce security models much stronger than those of Liu et al. We propose a new statistically-consistent construction of BAEKS in the standard model that achieves security in the newly introduced models. Our proposal is proven adaptively secure under the well-studied bilateral Matrix Diffie-Hellman Assumption and still achieves asymptotic efficiency similar to that of Liu et al.