Paper 2021/1325

Decentralized Multi-Authority ABE for NC^1 from Computational-BDH

Abstract

Decentralized multi-authority attribute-based encryption (𝖬𝖠-𝖠𝖡𝖤) is a strengthening of standard ciphertext-policy attribute-based encryption so that there is no trusted central authority: any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. Essentially, any party can act as an authority for some attribute by creating a public key of its own and issuing private keys to different users that reflect their attributes. This paper presents the first 𝖬𝖠-𝖠𝖡𝖤 proven secure under the standard search variant of bilinear Diffie-Hellman (CBDH) and in the random oracle model. Our scheme supports all access policies captured by 𝖭𝖢1 circuits. All previous constructions were proven secure in the random oracle model and additionally were based on decision assumptions such as the DLIN assumption, non-standard 𝑞-type assumptions, or subspace decision assumptions over composite-order bilinear groups.

Note: Erratum: Subsequent to our publication, Wang [Wan26] showed plaintext-recovery attacks on both our DBDH construction and its CBDH variant through collusion between corrupt authorities and users in the stated static security model. One such attack uses a three-attribute conjunction policy with a single corrupt authority colluding with two users, neither of whom is authorized even when given the corrupt authority’s attribute. Our proof of security from Section 5.2 incorrectly applies Lemma 3.1, originally due to Rouselakis and Waters [FC'15], to conclude that replacing the LSSS matrix preserves the adversary’s entire view. The lemma does preserve the distribution of the secret shares, but the matrix transformation need not preserve the distribution of the ciphertext components containing the individual products 𝑀_{𝑖,𝑗}𝑥_𝑗 . Wang also shows how to modify our construction and recover our claimed results by replacing, for each index 𝑗, the products 𝑀_{𝑖,𝑗}𝑥_𝑗 across the rows with an independently sampled linear sharing of zero. Apart from this erratum and the annotation identifying the error in Section 5.2, we leave the rest of the paper as originally published.