In an Attribute-Based Signature (ABS), users sign messages with any predicate of their attributes issued from an attribute authority. Under this notion, a verifier verifies the signature that attests to a claim regarding the attributes the signer possesses rather than the identity of the individual who signed the message. ABS provides flexible access control policy and has many applications such as anonymous authentication. While in the real-world environment, more than one central authority and attribute authority usually co-operate to manage and issue different attributes for individuals. Unfortunately, to the best of our knowledge, no existing attribute-based signature scheme can be deployed in such setting. In this paper, we propose a Multi-Central-Authority Attribute-Based Signature (MCA-ABS) scheme corresponding to the setting with multiple Central Authorities (CAs) and Attribute Authorities (AAs). To produce a secret key of an attribute, the signer is required to obtain both id-related keys from all CAs and attributed-related key from the corresponding AA. In this way, the trust of a single CA is distributed to multiple CAs. Thus, the system remains secure, as long as there is one CA has not been compromised. We prove that the proposed MCA-ABS scheme is selectively unforgeable in the standard model and achieves perfect privacy. Compared with other existing ABS schemes, our scheme has shorter signature length and higher efficiency.