Attribute-based signature (ABS) is a new cryptographic primitive, in which a signer can sign a message with his attributes, and the verifier can only known whether the signer owns attributes satisfying his policy. Moreover, the signature cannot be forged by any user not having attributes satisfying the policy. ABS has many applications, such as anonymous authentication, and attribute-based messaging systems. But these applications may require a user to obtain attributes from different authorities, which calls for a multi-authority ABS scheme. In addition, multiple authorities can distribute the trust to all authorities, instead of concerning on a single attribute authority. In this paper, we propose a multi-authority ABS scheme, supporting complex policies, expressing AND, OR, and threshold conditions. We use a central authority to assure the usability of attribute keys a user getting from different attribute authorities. To prevent collusion attacks, we adopt a unique global identity (GID) for a user to bind his attribute keys and identity together. And a secret key from the central authority help the verification be independent of the user's identity. So our scheme can fit the requirements of real applications, and also distribute the trust to all authorities in the system.