International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Multi-Authority ABE from Lattices without Random Oracles

Brent Waters , UT Austin and NTT Research
Hoeteck Wee , NTT Research and ENS, Paris
David J. Wu , UT Austin
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2022
Abstract: Attribute-based encryption (ABE) extends public-key encryption to enable fine-grained control to encrypted data. However, this comes at the cost of needing a central trusted authority to issue decryption keys. A multi-authority ABE (MA-ABE) scheme decentralizes ABE and allows anyone to serve as an authority. Existing constructions of MA-ABE only achieve security in the random oracle model. In this work, we develop new techniques for constructing MA-ABE for the class of subset policies (which captures policies such as conjunctions and DNF formulas) whose security can be based in the plain model without random oracles. We achieve this by relying on the recently-proposed "evasive" learning with errors (LWE) assumption by Wee (EUROCRYPT 2022) and Tsabury (CRYPTO 2022). Along the way, we also provide a modular view of the MA-ABE scheme for DNF formulas by Datta et al. (EUROCRYPT 2021) in the random oracle model. We formalize this via a general version of a related-trapdoor LWE assumption by Brakerski and Vaikuntanathan (ITCS 2022), which can in turn be reduced to the plain LWE assumption. As a corollary, we also obtain an MA-ABE scheme for subset policies from plain LWE with a polynomial modulus-to-noise ratio in the random oracle model. This improves upon the Datta et al. construction which relied on LWE with a sub-exponential modulus-to-noise ratio. Moreover, we are optimistic that the generalized related-trapdoor LWE assumption will also be useful for analyzing the security of other lattice-based constructions.
  title={Multi-Authority ABE from Lattices without Random Oracles},
  author={Brent Waters and Hoeteck Wee and David J. Wu},