We revisit decentralized multi-authority attribute-based encryption (MA-ABE) through the lens of fully adaptive security – the most realistic setting in which an adversary can decide on-the-fly which users and which attribute authorities to corrupt. Previous constructions either tolerated only static authority corruption or relied on highly complex “dual system with dual-subsystems” proof technique that inflated ciphertexts and keys.
Our first contribution is a streamlined security analysis showing – perhaps surprisingly – that the classic Lewko–Waters MA-ABE scheme [EUROCRYPT 2011] already achieves full adaptive security, provided its design is carefully reinterpreted and, more crucially, its security proof is re-orchestrated to conclude with an information-theoretic hybrid in place of the original target- group-based computational step. By dispensing with dual subsystems and target-group-based assumptions, we achieve a significantly simpler and tighter security proof along with a more lightweight implementation. Our construction reduces ciphertext size by 33 percent, shrinks user secret keys by 66 percent, and requires 50 percent fewer pairing operations during decryption – all while continuing to support arbitrary collusions of users and authorities. These improvements mark a notable advance over the state-of-the-art fully adaptive decentralized MA-ABE scheme of Datta et al. [EUROCRYPT 2023]. We instantiate the scheme in both composite-order bilinear groups under standard subgroup-decision assumptions and in asymmetric prime-order bilinear groups under the Matrix-Diffie–Hellman assumption. We further show how the Kowalczyk–Wee attribute-reuse technique [EUROCRYPT 2019] seamlessly lifts our construction from “one-use” boolean span programs (BSP) to “multi-use” policies computable in NC1, resulting in a similarly optimized construction over the state-of-the-art by Chen et al. [ASIACRYPT 2023].
Going beyond the Boolean world, we present the first MA-ABE construction for arithmetic span program (ASP) access policies, capturing a richer class of Boolean, arithmetic, and combinatorial computations. This advancement also enables improved concrete efficiency by allowing attributes to be handled directly as field elements, thereby eliminating the overhead of converting arithmetic computations into Boolean representations. The construction – again presented in composite and prime orders – retains decentralization and adaptive user-key security, and highlights inherent barriers to handling corrupted authorities in the arithmetic setting.