The paper introduces a new Attribute-Based Encryption (ABE) scheme that allows private keys to be expressed using any access formula over attributes, including non-monotonic ones. This is a significant advancement over previous ABE schemes, which were limited to monotonic access structures. The authors provide a proof of security for their scheme based on the Decisional Bilinear Diffie-Hellman (BDH) assumption and demonstrate that the performance of their scheme compares favorably with existing, less expressive ABE schemes. The main technical challenge is to adapt secret-sharing schemes to support non-monotonic access structures. The authors achieve this by using a degree \(d\) polynomial created by the authority at setup, where each negative attribute node in the key is tied to this polynomial. The decryption algorithm can access the secret share corresponding to a negative attribute node if the attribute is not present among the ciphertext's attributes, allowing for the decryption of the ciphertext. The paper also discusses the efficiency of the scheme, showing how to remove the restriction that each ciphertext must have exactly \(d\) attributes. This is achieved by using multiple encryption systems, each designed to handle a different number of attributes, which minimizes the overhead for ciphertexts with fewer attributes. Finally, the authors prove the security of their scheme in the attribute-based selective-set model, reducing it to the hardness of the BDH assumption. They also show how their techniques can be applied to Ciphertext-Policy ABE (CP-ABE) schemes, and discuss future directions for creating even more expressive ABE systems.The paper introduces a new Attribute-Based Encryption (ABE) scheme that allows private keys to be expressed using any access formula over attributes, including non-monotonic ones. This is a significant advancement over previous ABE schemes, which were limited to monotonic access structures. The authors provide a proof of security for their scheme based on the Decisional Bilinear Diffie-Hellman (BDH) assumption and demonstrate that the performance of their scheme compares favorably with existing, less expressive ABE schemes. The main technical challenge is to adapt secret-sharing schemes to support non-monotonic access structures. The authors achieve this by using a degree \(d\) polynomial created by the authority at setup, where each negative attribute node in the key is tied to this polynomial. The decryption algorithm can access the secret share corresponding to a negative attribute node if the attribute is not present among the ciphertext's attributes, allowing for the decryption of the ciphertext. The paper also discusses the efficiency of the scheme, showing how to remove the restriction that each ciphertext must have exactly \(d\) attributes. This is achieved by using multiple encryption systems, each designed to handle a different number of attributes, which minimizes the overhead for ciphertexts with fewer attributes. Finally, the authors prove the security of their scheme in the attribute-based selective-set model, reducing it to the hardness of the BDH assumption. They also show how their techniques can be applied to Ciphertext-Policy ABE (CP-ABE) schemes, and discuss future directions for creating even more expressive ABE systems.