In this paper, we propose a novel technique called match-then-decrypt, in which a matching phase is additionally introduced before the decryption phase. This technique works by computing special components in ciphertexts, which are used to perform the test that if the attribute private key matches the hidden access policy in ciphertexts without decryption. For the sake of fast decryption, special attribute secret key components are generated which allow aggregation of pairings during decryption. We propose a basic anonymous ABE construction, and then obtain a security-enhanced extension based on strongly existentially unforgeable one-time signatures. In the proposed constructions, the computation cost of an attribute matching test is less than one decryption operation, which only needs small and constant number of pairings. Formal security analysis and performance comparisons indicate that the proposed solutions simultaneously ensure attribute privacy and improve decryption efficiency for outsourced data storage in mobile cloud computing.