Improved anonymous broadcast encryptions: Tight security and shorter ciphertext

We investigate anonymous broadcast encryptions (ANOBE) in which a ciphertext hides not only the message but also the target recipients associated with it. Following Libert et al.’s generic construction [PKC, 2012], we propose two concrete ANOBE schemes with tight reduction and better space efficiency. The IND-CCA security and anonymity of our two ANOBE schemes can be tightly reduced to standard k-Linear assumption (and the existence of other primitives). For a broadcast system with n users, Libert et al.’s security analysis suffers from O(n³) loss while our security loss is constant.Our first ANOBE supports fast decryption and has a shorter ciphertext than the fast-decryption version of Libert et al.’s concrete ANOBE. Our second ANOBE is adapted from the first one. We sacrifice the fast decryption feature and achieve shorter ciphertexts than Libert et al.’s concrete ANOBE with the help of bilinear groups. Technically, we start from an instantiation of Libert et al.’s generic ANOBE [PKC, 2012], but we work out all our proofs from scratch instead of relying on their generic security result. This intuitively allows our optimizations in the concrete setting.