In an attribute-based signature (ABS), users sign messages with any predicate of their attributes issued from an attribute authority. Under this notion, a signature attests not to the identity of the individual who signed a message, but a claim regarding the attributes the underlying signer possesses. In ABS, users cannot forge signatures with attributes they do not possess even through colluding. On the other hand, a legitimate signer remains anonymous without the fear of revocation and is indistinguishable among all the users whose attributes satisfying the predicate specified in the signature. ABS is useful in many important applications such as anonymous authentication and attribute-based messaging systems.
In this paper, we propose two efficient ABS constructions supporting flexible threshold predicate by exploring a new technique for signature signing. Compared with existed schemes, the new constructions provide better efficiency in terms of both the computational cost and signature size. The first new construction is provably secure in the random oracle model, while the second construction does not rely on the random oracle assumption. To further reduce the trust on attribute authority, we also show an ABS construction with multiple attribute authorities. It is worth noting that the security of all the proposed constructions is not relying on generic group. As an illustrative application, we construct an efficient non-transferable access control system from ABS.