© 2017, Springer International Publishing AG. Public key encryption with keyword search (PEKS) is a promising cryptographic mechanism to enable secure search over encrypted data in cloud. The mechanism allows a semi-trusted cloud server to return related encrypted contents without knowing what the query is and what the corresponding contents are. It has been combined with attribute based encryption (ABE) to support more expressiveness in search. Most of the existing searchable ABE schemes, however, are restricted to heavy complexity. In particular, the size of ciphertext and pairing cost in the test phase are both linear in the size of the keyword set, say O(n), where n is the number of keyword. This limitation hinders the scalability of searchable ABE in practice. To address this long-lasting open problem, this paper proposes a new key-policy attribute-based search encryption (KP-ABSE) scheme. Our construction can be regarded as a novel combination of fast decryption, anonymous-like encryption, and KP-ABE technologies. As of independent interest, the scheme is built in asymmetric bilinear groups. The scheme is further proved secure under the asymmetric decisional DBDH, decisional q-BDHE a nd decisional linear assumptions in the standard model. Compared with existing KP-ABSE schemes, our new scheme achieves the following properties: (1) flexible access structure for search - any monotonic access structure, (2) constant ciphertext size, (3) constant pairing operations in the test phase.