Reducing the CRS Size in Registered ABE Systems

Attribute-based encryption (ABE) is a generalization of public-key encryption that enables fine-grained access control to encrypted data. In (ciphertext-policy) ABE, a central trusted authority issues decryption keys for attributes 𝑥 to users. In turn, ciphertexts are associated with a decryption policy P. Decryption succeeds and recovers the encrypted message whenever P (𝑥) = 1. Recently, Hohenberger, Lu, Waters, and Wu (Eurocrypt 2023) introduced the notion of registered ABE, which is an ABE scheme without a trusted central authority. Instead, users generate their own public/secret keys (just like in public-key encryption) and then register their keys (and attributes) with a key curator. The key curator is a transparent and untrusted entity.

Currently, the best pairing-based registered ABE schemes support monotone Boolean formulas and an a priori bounded number of users 𝐿. A major limitation of existing schemes is that they require a (structured) common reference string (CRS) of size 𝐿 2 • |U| where |U| is the size of the attribute universe. In other words, the size of the CRS scales quadratically with the number of users and multiplicatively with the size of the attribute universe. The large CRS makes these schemes expensive in practice and limited to a small number of users and a small universe of attributes.

In this work, we give two ways to reduce the CRS size in pairing-based registered ABE schemes. First, we introduce a combinatoric technique based on progression-free sets that enables registered ABE for the same class of policies but with a CRS whose size is sub-quadratic in the number of users. Asymptotically, we obtain a scheme where the CRS size is nearly linear in the number of users 𝐿 (i.e., 𝐿 1+𝑜 (1) ). If we take a more concrete-efficiency-oriented focus, we can instantiate our framework to obtain a construction with a CRS of size 𝐿 log 2 3 ≈ 𝐿 1.6 . For instance, in a scheme for 100,000 users, our approach reduces the CRS by a factor of over 115× compared to previous approaches (and without incurring any overhead in encryption/decryption time). Our second approach for reducing the CRS size is to rely on a partitioning-based argument when arguing security of the registered ABE scheme. Previous approaches took a dual-system approach. Using a partitioning-based argument yields a registered ABE scheme where the size of the CRS is independent of the size of the attribute universe. The cost is the resulting scheme satisfies a weaker notion of static security. Our techniques for reducing the CRS size can be combined, and taken together, we obtain a pairing-based registered ABE scheme that supports monotone Boolean formulas with a CRS size of 𝐿 1+𝑜 (1) . Notably, this is the first pairing-based registered ABE scheme that does not require imposing a bound on the size of the attribute universe during setup time.

As an additional application, we also show how to apply our techniques based on progression-free sets to the batch argument (BARG) for NP scheme of Waters and Wu (Crypto 2022) to obtain a scheme with a nearly-linear CRS without needing to rely on non-black-box bootstrapping techniques.

A partitioning-based proof strategy. To achieve a shorter CRS (whose size is independent of the size of the attribute universe), we take a different approach for arguing security. In particular, we consider a weaker "static" security model where the adversary must declare the set of corrupted slots 𝑖 ∈ [𝐿] at the very beginning of the game. In this model, the reduction algorithm "knows" in advance which slots it needs to be able to generate the secret key for and which ones it does not. This enables us to use a "partitioning" strategy to argue security, where the indices of the corrupted slots are programmed into the CRS itself. The programming ensures that the adversary is able to generate secret keys for all of the corrupted slots (but not for the non-corrupted slots). While this is a weaker security notion that adaptive security, it still captures a meaningful security property, and moreover, the work of [FWW23] show how generically compile a registered ABE scheme that does not allow corruption queries into a scheme that supports adaptive corruptions in the random oracle model. The advantage of using a partitioning-based argument is we no longer require a different sets of attribute exponents for each slot, and in fact, all of the attribute can share the same set of attribute-slot components. This means the size of the CRS becomes independent of the size of the attribute universe. This has the added benefit that the size of the attribute universe no longer needs to be fixed at setup time. Note however that the size of the public key still grows with the number of attributes since we still need to associate a group element with each attribute which encodes which slots in the scheme are associated with the attribute.

Our partitioning-based approach can be applied with or without progression-free sets. For