Efficient Multi-Authority ABE from Learning With Errors Over Rings

Multi-authority attribute-based encryption (MA-ABE) has received increasing attention due to the proliferation of decentralized applications and services. Since its inception, various constructions have been proposed with different security assumptions. However, in light of the threat from quantum attacks, one major challenge is to construct an MA-ABE with post-quantum cryptography techniques. Nonetheless, existing post-quantum solutions have so far been constrained by either efficiency or the need for interactions among authorities, which limits the application of MA-ABE in emerging decentralized applications. In this work, we propose a truly decentralized and more efficient MA-ABE by leveraging the Ring Learning with Error (RLWE) problem. We achieve this by first adapting the generalized compact knapsack problem for an efficient lattice trapdoor sampler. To support any DNF access policy, we develop a ring-based monotone linear secret sharing scheme derived from the Lewko-Waters transformation. The complexity analysis shows that compared to the state of the art, our scheme improves by a factor of N<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>/logN on encryption and N/logN on decryption, where N is the lattice dimension. Experimental results demonstrate an encryption and decryption time of 28.60 and 15.71 seconds respectively when N =1024, thereby showing the feasibility of our construction in real-world applications.