Paper 2019/280

Multi-Authority Attribute-Based Encryption from LWE in the OT Model

Sam Kim

Abstract

In a (ciphertext policy) attribute-based encryption (ABE) scheme, a ciphertext is associated with a predicate $\phi$ and a secret key is associated with a string $x$ such that a key decrypts a ciphertext if and only of $\phi(x) = 1$. Moreover, the scheme should be collusion-resistant meaning that no colluding set of users can learn about the message if none of their secret keys can individually decrypt the ciphertext. Traditionally, in an ABE scheme, there exists a central authority that generates the keys for each users. In a multi-authority attribute-based encryption (MA-ABE) scheme, individual components of the secret keys are generated by different key-generating authorities. Although the notion of MA-ABE is a natural extension of the standard ABE, its realization has so far been limited. Indeed, all existing MA-ABE constructions rely solely on bilinear maps and can only support predicates that are computable by monotone boolean formulas. In this work, we construct the first collusion-resistant MA-ABE scheme that can support circuit predicates from the Learning with Errors (LWE) assumption. Our construction works in a new model that we call the OT model, which can be viewed as a direct relaxation of the traditional GID model that previous MA-ABE constructions consider. We believe that the new OT model is a compelling alternative to the traditional GID model as it captures the core requirements for an MA-ABE scheme. The techniques that are used to construct MA-ABE in this model can also be used as a stepping stone towards constructing MA-ABE in the stronger GID model in the future.