Paper 2022/1194

Multi-Authority ABE from Lattices without Random Oracles

Brent Waters, The University of Texas at Austin, NTT Research
Hoeteck Wee, NTT Research, École Normale Supérieure - PSL
David J. Wu, The University of Texas at Austin

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.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in TCC 2022
attribute-based encryption multi-authority lattices evasive LWE
Contact author(s)
bwaters @ cs utexas edu
wee @ di ens fr
dwu4 @ cs utexas edu
2022-09-12: approved
2022-09-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Brent Waters and Hoeteck Wee and David J. Wu},
      title = {Multi-Authority ABE from Lattices without Random Oracles},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1194},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.