This paper introduces a novel, generic construction for Registered Attribute-Based Encryption (Reg-ABE) using predicate encodings. This work significantly expands the capabilities of Reg-ABE by providing the first constructions for span programs and zero inner-product predicates in prime-order bilinear groups, and the first for arithmetic branching programs, all under standard assumptions.
TL;DR
This paper presents a generic, black-box construction for Registered Attribute-Based Encryption (Reg-ABE) using predicate encodings. It achieves new Reg-ABE schemes for span programs and zero inner-product predicates in prime-order groups, and arithmetic branching programs, improving upon prior work by relying on standard assumptions and avoiding generic group models.
What Problem Does This Paper Address?
Attribute-Based Encryption (ABE) allows fine-grained access control to encrypted data based on attributes. However, standard ABE suffers from a key escrow problem, where a central authority (the key escrow agent) can decrypt any ciphertext. Registered ABE (Reg-ABE) addresses this by allowing users to generate their own key pairs and register their attributes with a system, thus avoiding the need for a trusted key escrow agent.
Existing Reg-ABE schemes fall into two categories: those using non-black-box techniques (like garbled circuits or indistinguishable obfuscation) and those using black-box techniques based on concrete assumptions in bilinear groups or lattices. The latter, while more efficient, have often been limited to specific predicates and sometimes relied on weaker security models like the generic group model (GGM). This paper aims to provide a unified, black-box framework for constructing Reg-ABE schemes in prime-order bilinear groups that are secure under standard assumptions, covering a broader range of functionalities than previous work.
Methods
The core of this work is a generic construction of Reg-ABE from predicate encodings, building upon the dual-system ABE approach. The authors adapt the blueprint from Hohenberger et al. [HLWW23] but start from a prime-order dual-system ABE by Chen et al. [EUROCRYPT’15].
Key techniques include:
- Predicate Encoding: The paper leverages the concept of predicate encoding, where a predicate $P: X \times Y \to \{0,1\}$ is transformed into efficient algebraic structures ($C_x, K_y, a_y, d_{x,y}$) that allow for correctness and security proofs.
- Dual-System Approach: The security proof follows the dual-system method, conceptually treating helper keys as secret keys. This is a standard technique in ABE for achieving security proofs.
- Quasi-Adaptive Non-Interactive Zero-Knowledge Argument (QA-NIZK): To handle malicious public keys and ensure security, the construction employs QA-NIZK arguments for linear spaces, specifically adapting the scheme by Kiltz and Wee [KW15]. This allows for efficient and secure verification of registered public keys.
- Slotted Reg-ABE: The construction is first developed for a "slotted" version of Reg-ABE, where a fixed number of users can register their attributes. This slotted scheme is then transformed into a full-fledged Reg-ABE using the "power-of-two" approach from [HLWW23].
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Unified Framework for Reg-ABE: The paper demonstrates that predicate encodings provide a powerful and unified tool for constructing various Reg-ABE schemes, moving beyond single-predicate constructions.
- Prime-Order Advantage: By building on prime-order dual-system ABE, the authors achieve more efficient schemes and avoid potential issues associated with composite-order groups.
- Bridging GGM to Standard Assumptions: The work provides the first Reg-ABE for zero inner-product predicates under the standard k-Lin assumption, resolving a problem that previously required the generic group model.
- Handling Malicious Public Keys: The integration of QA-NIZK arguments is crucial for robustly handling malicious public keys during the registration process, a critical aspect for practical Reg-ABE systems.
Key Results
The paper presents the following novel Reg-ABE schemes:
- The first Reg-ABE scheme for span programs in prime-order groups. This improves upon prior work that required composite-order groups.
- The first Reg-ABE scheme for zero inner-product predicates from the k-Lin assumption. This avoids the need for the generic group model (GGM) used in prior work.
- The first Reg-ABE scheme for arithmetic branching programs (ABP), a functionality not previously achieved.
The security of these schemes is based on the k-Lin assumption in prime-order bilinear groups. The construction also supports variants such as dual-policy and composition of policies (disjunction, conjunction, negation).
Limitations and Future Work
The authors acknowledge that their Reg-ABE scheme inherits some restrictions from [HLWW23]:
- Bounded Number of Users: The size of the common reference string (crs) depends on the number of users, which is a limitation compared to schemes supporting an unbounded number of users (though such schemes often rely on non-black-box techniques).
- Explicit Public Key Verification: The scheme requires an explicit verification of public keys before registration, which is introduced to handle malicious public keys.
The paper suggests several avenues for future work:
- Exploring whether these restrictions are necessary for supporting expressive predicates.
- Adapting the notion of pair encoding for Reg-ABE constructions.
- Investigating optimizations for efficiency, potentially by leveraging the connection to ciphertext-policy ABE schemes.
- Achieving (weak) attribute-hiding under standard assumptions, as current constructions do not fully support it due to decryption requirements.
Summary updated