International Association
for Cryptologic Research

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 $\mathsf{NC^{1}}$, 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.

In a Multi-Client Functional Encryption (MCFE) scheme, n clients each obtain a secret encryption key from a trusted authority. During each time step t, each client i can encrypt its data using its secret key. The authority can use its master secret key to compute a functional key given a function f, and the functional key can be applied to a collection of n clients’ ciphertexts encrypted to the same time step, resulting in the outcome of f on the clients’ data. In this paper, we focus on MCFE for inner-product computations. If an MCFE scheme hides not only the clients’ data, but also the function f, we say it is function hiding. Although MCFE for inner-product computation has been extensively studied, how to achieve function privacy is still poorly understood. The very recent work of Agrawal et al. showed how to construct a function-hiding MCFE scheme for inner-product assuming standard bilinear group assumptions; however, they assume the existence of a random oracle and prove only a relaxed, selective security notion. An intriguing open question is whether we can achieve function-hiding MCFE for inner-product without random oracles. In this work, we are the first to show a function-hiding MCFE scheme for inner products, relying on standard bilinear group assumptions. Further, we prove adaptive security without the use of a random oracle. Our scheme also achieves succinct ciphertexts, that is, each coordinate in the plaintext vector encrypts to only O(1) group elements. Our main technical contribution is a new upgrade from single-input functional encryption for inner-products to a multi-client one. Our upgrade preserves function privacy, that is, if the original single-input scheme is function-hiding, so is the resulting multi-client construction. Further, this new upgrade allows us to obtain a conceptually simple construction.

Anonymous routing is an important cryptographic primitive that allows users to communicate privately on the Internet, without revealing their message contents or their contacts. Until the very recent work of Shi and Wu (Eurocrypt’21), all classical anonymous routing schemes are interactive protocols, and their security rely on a threshold number of the routers being honest. The recent work of Shi and Wu suggested a new abstraction called Non-Interactive Anonymous Router (NIAR), and showed how to achieve anonymous routing non-interactively for the first time. In particular, a single untrusted router receives a token which allows it to obliviously apply a permutation to a set of encrypted messages from the senders. Shi and Wu’s construction suffers from two drawbacks: 1) the router takes time quadratic in the number of senders to obliviously route their messages; and 2) the scheme is proven secure only in the presence of static corruptions. In this work, we show how to construct a non-interactive anonymous router scheme with sub-quadratic router computation, and achieving security in the presence of adaptive corruptions. To get this result, we assume the existence of indistinguishability obfuscation and one-way functions. Our final result is obtained through a sequence of stepping stones. First, we show how to achieve the desired efficiency, but with security under static corruption and in a selective, single-challenge setting. Then, we go through a sequence of upgrades which eventually get us the final result. We devise various new techniques along the way which lead to some additional results. In particular, our techniques for reasoning about a network of obfuscated programs may be of independent interest.