Paper 2026/1895

Large-Universe (Multi-Authority) ABE from LWE

Abstract

An attribute-based encryption (ABE) scheme is "large-universe" if its attribute universe is superpolynomial and is not enumerated during setup. In the multi-authority setting, we further require that each authority can independently manage a superpolynomial set of attributes and dynamically issue an arbitrary polynomial number of secret keys per user. Although large-universe (multi-authority) ABE from pairings is well studied, explicit lattice-based constructions have remained elusive. In the centralized setting, a standard workaround is to instantiate lattice-based ABE for general circuits and encode each attribute as a bit string; however, unless one adopts non-standard lattice assumptions, this approach typically yields prohibitively large ciphertexts. In the multi-authority setting, even though lattice-based ABE for general circuits is known, this bit-encoding approach applied to those schemes does not yield a genuine large-universe construction. We close this gap by presenting the first lattice-based large-universe (multi-authority) ABE schemes under the Learning With Errors (LWE) assumption, achieving ciphertext and key sizes that are comparable to those in the pairing-based setting. Concretely, we construct: • a large-universe key-policy ABE scheme with ciphertext size $O(t)$; • a large-universe ciphertext-policy ABE scheme with ciphertext size $O(|f|)$; and • a large-universe multi-authority ABE scheme, where $t$ is the number of attributes, $|f|$ is the policy size, and the $O(\cdot)$ notation suppresses $\tilde{O}(\lambda)$ factors. All schemes support policies in disjunctive normal form (DNF) and are proved secure in the random oracle model. We further develop more efficient variants of our key-policy and ciphertext-policy ABE schemes over ideal lattices under the Ring-LWE assumption, aiming for practical performance on the order of seconds to minutes. Experimental results from our implementations confirm practical runtimes and memory consumption, providing concrete evidence that large-universe lattice-based ABE is feasible for efficient real-world deployment.