We present a new notion called the attribute-based signa- ture with message recovery. Compared with the existing attribute-based signature schemes, an attribute-based signature with message recovery scheme does not require transmission of the original message to verify the validity of the signature, since the original message can be recovered from the signature. Therefore, this scheme shortens the total length of the original message and the appended attribute-based signature. The contributions of this paper are threefold. First, we introduce the notion of attribute-based signature with message recovery. Second, we present a concrete construction of an attribute-based signature with message re- covery scheme based on bilinear pairing. Finally, we extend our scheme to deal with large messages. The proposed schemes support exible thresh- old predicates and are proven to be existentially unforgeable against adaptively chosen message attacks in the random oracle model under the assumption that the Computational Die-Hellman problem is hard. We demonstrate that the proposed schemes are also equipped with the attribute privacy property.