FABS: Fast Attribute-Based Signatures

Attribute-based signatures (ABS) provide fine-grained control over who can generate digital signatures and have many realworld applications. This paper presents a pair of fast ABS schemes: one for Key-Policy ABS (KP-ABS) and another for Signature-Policy ABS (SP-ABS). Both schemes support expressive policies using Monotone Span Programs (MSP), and offer practical features such as large universe, arbitrary attributes, and adaptive security. Most notably, we provide the first implementation of MSP-based ABS schemes and demonstrate that our schemes achieve the best-known asymptotic and concrete performance in this domain. Asymptotically, key generation, signing and verification time scale linearly with the number of attributes; verification requires only two pairing operations. In concrete terms, for 100 attributes, our KP-ABS scheme performs key generation, signing, and verification in 0.16s, 0.10s, and 0.13s, respectively; our SP-ABS scheme achieves times of 0.082s, 0.26s, and 0.21s for the same operations. Our contributions We begin by comprehensively reviewing ABS research with the goal of identifying existing gaps and challenges in both KP-ABS and SP-ABS schemes. The outcomes of this review are presented in Section 2 and further detailed in Appendix D. Building on the insights gained from this analysis, our work primarily focuses on the design, security analysis, and implementation of efficient pairing-based ABS schemes that support flexible Monotone Span Program (MSP) policies. Our main contributions can be summarized as follows: • Synchronized syntax and security model. Similar to the ABE generalization [41], we introduce a general syntax and security model that can synchronize both KP-ABS and SP-ABS. The model captures the well-studied security properties, unforgeability and anonymity, and facilitates our design and security analysis. • Fast KP-ABS and SP-ABS schemes. We propose new pairing-based KP-ABS and SP-ABS schemes using MSP policies. Our schemes support the following highly desirable features: -Arbitrary attributes: No restrictions on the size or type of attributes and any arbitrary string can be used as an attribute. -Large universe 1 : Attributes are not required to be fixed at the setup stage and hence the attribute space is unbounded. Besides, the size of master public key remains constant. -Adaptive unforgeability: An adversary cannot forge a signature even if it is allowed to obtain signatures for its chosen attributes or messages at any time. -Type-III pairing: Two input groups to the pairing operation are distinct and there are no efficiently computable homomorphisms between them. It has been highly recommended due to their security and performance advantages [43] . -Fast algorithms: key generation, signing and verification time scale linearly with the number of attributes, while the number of pairing operations in verification remains constant (two), independent of the number of attributes. We provide a property-wise comparison between our schemes and the state-of-the-art pairing-based ABS schemes supporting MSP policies in Table 1 . As shown, our schemes are the only ones that support all the listed properties. • Security analysis. Following our security models, we prove that our ABS schemes satisfy adaptive unforgeability and anonymity under standard assumptions in the random oracle model. • Implementation and evaluation. We have implemented our KP-ABS and SP-ABS schemes and evaluated their performance. This is the first implementation in the MSP-based 1 The definition here was originally proposed for ABE [42] but it suits ABS as well.