Paper 2025/650

ADC-BE: Optimizing Worst-Case Bandwidth in Broadcast Encryption with Boolean Functions

Abstract

Abstract. Recently, Dupin and Abelard [11] proposed a broadcast encryption scheme, outperforming the Complete Subtree-based and Subset Difference broadcast encryption in terms of encryption cost and bandwidth requirement. However, Dupin and Abelard acknowledge that the worst-case bound for bandwidth requirement of Complete Subtree approach can be reached in their scheme as well. In this paper, we answer the call to further reduce this bandwidth bottleneck. We first provide concrete analysis to show how this worst-case upper-bound is reached from particular Boolean functions. Our proof on [11]’s worst-case complexity demonstrates and shows that those Boolean functions, out of all 2^2^l possible Boolean functions of n variables, produces the worst-case upper-bound. Then we present two improved broadcast encryption schemes to significantly reduce this worst-case bandwidth consumption for further optimization of Dupin and Abelard’s technique. Our proposed ADC-BE suite, composed of two primitives, AD-BE and AC-BE, can significantly optimize this worst-case complexity from O(n/2) down to O(1) for a system of n users. This is efficient especially for large number of users in the system. Our schemes combines the algebraic normal form, disjunctive normal form, and conjunctive normal form to optimize a Boolean function to its minimized representation. Furthermore, our approaches support full range of Boolean functions without any restrictions, i.e., general access structures. This is more versatile than monotone access structure, where the group attribute policy is solely restrained to the Boolean clauses without bit-inversion nor negation. Last but not least, both AD-BE and AC-BE can be straightforwardly extended to post-quantum broadcast encryption schemes as the underlying hardness depends on one-way function, e.g., secure hash function.