Ilmu Komputer & AI editorial
Large Universe Subset Predicate Encryption with IND-CCA Security (with Constant-size Ciphertext and Keys)
The core problem
Subset Predicate Encryption (SPE) was introduced by Katz et al. (CANS'17) as a generalization of broadcast encryption that emulates the *subset containment* predicate in the encrypted domain. In an SPE scheme, a ciphertext is associated with a set of attributes , and a secret key is associated with a set . Decryption succeeds if and only if . This primitive enables fine-grained access control and has applications in broadcast encryption, attribute-based encryption (ABE), and identity-based encryption (IBE).
Katz et al. proposed two selectively IND-CPA secure SPE constructions in the small universe setting, where the universe of attributes is bounded. They also demonstrated black-box transformations from SPE to well-known primitives like WIBE and ABE, establishing the richness of the SPE structure. However, small-universe schemes suffer from scalability issues as the system parameters grow with the universe size.
Chatterjee and Mukherjee (RSA'19) advanced the field by proposing two SPE constructions in the large-universe setting, where the universe can be exponentially large. Their first construction achieved constant-size ciphertexts and secret keys, but it
Innovation
The paper presents a novel SPE scheme that achieves several notable properties simultaneously:
- **Large Universe:** The attribute universe can be exponentially large, and the public parameters are of constant size, independent of the universe.
- **Constant-size Ciphertext and Keys:** Both ciphertexts and secret keys are of constant size, regardless of the number of attributes in the predicate or the data-attribute set.
- **IND-CCA Security:** The scheme is proven secure against adaptive chosen-ciphertext attacks in the standard selective security model, under standard subgroup decision problems.
- **Black-box Transformations:** The authors show how to transform the SPE scheme into the first CCA-secure WIBE, WKD-IBE, and other primitives with constant-size ciphertexts and secret keys.
A comparison with prior work is summarized in the table below:
| Scheme | Universe | Ciphertext Size | Key Size | Security |
|--------|----------|-----------------|----------|----------|
| Katz et al. (CANS'17) | Small | Constant | Constant | Selective IND-CPA |
| Chatterjee-Mukherjee (RSA'19) - Construction 1 | Large | Constant | Constant | Restricted Selective |
| Chatterjee-Mukherjee (RSA'19) -
Why it matters
The proposed scheme represents a significant advancement in the field of predicate encryption. By achieving CCA security in the large-universe setting with constant-size ciphertext and keys, it addresses a major open problem. The use of standard subgroup decision problems for security provides a solid foundation, as these assumptions are well-understood and have been extensively studied.
One limitation of the scheme is that it achieves selective security rather than adaptive security. In the selective model, the adversary must commit to the challenge attribute set before seeing the public parameters. While this is a common limitation in many predicate encryption schemes, achieving adaptive security with constant-size ciphertext and keys remains an open challenge. The authors note that their scheme can be extended to achieve adaptive security at the cost of larger ciphertexts, but this would sacrifice the constant-size property.
The black-box transformations to WIBE and WKD-IBE are particularly valuable because they enable the construction of efficient CCA-secure schemes for these primitives. WIBE and WKD-IBE have applications in secure messaging, group key management, and access control systems. The constant-size property is crucial for scalability in large-scale deployments.
From a practical perspective, the scheme's efficiency makes it suitable for resource-constrained devices. The constant number of pairing operations and group elements means that encryption and decryption are fast and require minimal bandwidth. This is important for IoT devices, mobile applications, and other scenarios where efficiency is paramount.
Future work could explore adaptive security with constant-size parameters, as well as extensions to other predicates such as inner-product or range queries. Additionally, implementing the scheme and benchmarking its performance against existing schemes would provide valuable insights into its practical viability.
In conclusion, this work makes a substantial contribution to the field of predicate encryption by providing the first large-universe CCA-secure SPE with constant-size ciphertext and keys, and by enabling efficient CCA-secure WIBE and WKD-IBE through black-box transformations.
Who should read this
Opening member content…