Multi-authority Registered Attribute-Based Encryption

Registered attribute-based encryption (ABE) enables fine-grained access control to encrypted data without a trusted authority. In this model, users generate their own public keys and register their public key along with a set of attributes with a key curator. The key curator aggregates the public keys into a short master public key that functions as the public key for an ABE scheme.

A limitation of ABE (registered or centralized) is the assumption that a single entity manages all of the attributes in a system. In many settings, the attributes belong to different organizations, making it unrealistic to expect that a single entity manage all of them. In the centralized setting, this motivated the notion of multi-authority ABE, where multiple independent authorities control their individual set of attributes. Access policies are then defined over attributes across multiple authorities.

In this work, we introduce multi-authority registered ABE, where multiple (independent) key curators each manage their individual sets of attributes. Users can register their public keys with any key curator, and access policies can be defined over attributes from multiple key curators. Multi-authority registered ABE combines the trustless nature of registered ABE with the decentralized nature of multi-authority ABE.

We start by constructing a multi-authority registered ABE scheme from composite-order pairing groups. This scheme supports an a priori bounded number of users and access policies that can be represented by a linear secret sharing scheme (which includes monotone Boolean formulas). Our construction relies on a careful integration of ideas from pairing-based registered ABE and multi-authority ABE schemes. We also construct a multi-authority registered ABE scheme that supports an unbounded number of users and arbitrary monotone policies using indistinguishability obfuscation (and function-binding hash functions).

• KeyGen(gpp, gid) → (pk gid , sk gid ): The key-generation algorithm uses the global public parameters gpp and the user identifier gid to generate a public/secret key-pair.

• RegPK(gpp, aux, gid, pk gid ) → (mpk ′ , aux ′ ): The registration algorithm uses the global public parameters gpp, the current state of the key curator aux, the user identifier gid, and the associated public key pk gid , and outputs a new master public key mpk ′ and curator state aux ′ . We require this algorithm to be deterministic (so that it is possible to audit the key curator).

• UpdateKey(gpp, aux, gid) → hsk gid : The update algorithm takes the global public parameters gpp, the curator state aux, and the identifier gid for the user requesting an update, and outputs a helper decryption key hsk gid .

• Encrypt(gep, (𝑆 enc , 𝜑), (aid, mpk aid ) aid∈𝑆 enc , 𝑚) → ct: The encryption algorithm take the global encryption parameters gep, a set of authority identifiers 𝑆 enc , a policy function 𝜑 defined over those authorities, the master public keys mpk aid associated with the authorities aid ∈ 𝑆 enc , and a message 𝑚, and outputs a ciphertext ct.

• Decrypt(gpp, 𝑆, (aid, sk aid,gid , hsk aid,gid ) aid∈𝑆 , ct) → 𝑚: The decryption algorithm takes in the global public parameters gpp, a set of authority identifiers 𝑆, and the secret keys sk aid,gid and helper decryption keys hsk aid,gid , and a ciphertext ct, and outputs the message 𝑚.

The correctness requirement is that any user registered with a set of authorities that satisfy the access policy associated with a ciphertext can successfully recover the message. Security says that any set of users who individually do not satisfy the access policy cannot learn anything about the encrypted message.

Slotted multi-authority registered ABE. Much like in [HLWW23], our constructions of multi-authority registered ABE will proceed in two steps: (1) we first construct a "slotted" version of the primitive; and (2) we show how to generically upgrade the slotted primitive to the full primitive. The slotted multi-authority registered ABE scheme makes the following simplifying assumptions:

• The slotted scheme supports a fixed number of users 𝐿 (which is provided as an explicit parameter to the setup algorithm GlobalSetup).

• The scheme supports one-shot aggregation rather than incremental updates to the public key. Instead of the RegPK, UpdateKey algorithms, the slotted scheme has a single Aggregate algorithm that takes as input the global parameters gpp, and a set of 𝐿 public keys pk 1 , . . . , pk 𝐿 for user identifiers gid 1 , . . . , gid 𝐿 . The aggregate algorithm outputs a succinct master public key mpk and helper decryption keys hsk 𝑖 for each of the users. 𝑡 𝑗 𝑖,0 , 𝑈 𝑡 𝑗 𝑖,1 ) and compute the cross terms as Ŵ𝑖 = 𝑗≠𝑖 𝐻 ( ì 𝐾 𝑗,𝑖 , gid 𝑖 ) = 𝑗≠𝑖 𝐻 ( ì 𝑈 𝑗 , gid 𝑖 ) 𝑡 𝑖 .

More generally, for policies involving 𝑃 attributes, we would use a 𝑃-universal hash function. Putting everything together, our slotted multi-authority registered ABE scheme (for policies involving up to 2 attributes