All the state-of-the-arts works were unable to fully identify the requirements of a BED scheme. We first identify and propose a new security requirement that has not been considered before. After formally defining a BED scheme, we show simple pairing-based attacks on all previous constructions rendering all of them useless. We then give the first secure BED construction in the composite-order pairing groups. This construction achieves constant-size ciphertext and secret keys but achieves selectively secure message hiding only. We then give our second construction from Li and Gong’s (PKC’18) anonymous broadcast encryption. This construction achieves adaptively secure message hiding but has ciphertext size dependent on the size of the privileged set. Following that, we propose our third and final construction that achieves constant size ciphertext in the standard model and achieves adaptive message hiding security.