Abstract: Recently, Wang et al. proposed a traitor tracing scheme based on bilinear map. They claimed that their scheme cloud achieve full collusion resistance, full revocation, full recoverability and black-box traceability, which is efficient in terms of the translation overhead and storage overhead in comparison with the previously proposed schemes. In this paper, we analyze their scheme and show that their scheme does not achieve full revocation. Then we modify their scheme and propose a new traitor tracing scheme based on bilinear map. In this scheme, we employ the polynomial function and the filter function as the basic means of constructing the traitor tracing procedures in order to minimize the storage, computational and communication costs. More importantly, when traitors are found, this scheme can safely revoke their private keys without updating the private keys of other receivers and deter the revoked users to recover the decryption key. Therefore, it can achieve full revocation, and thus overcomes the weakness in Wang et al.' scheme. The security of the proposed scheme is based on the difficult problems of solving bilinear discrete logarithm problem and decision Diffie-Hellman problem. The proof of security and analysis of performance show that the proposed scheme is secure and able to achieve full collusion resistance, full recoverability, black-box traceability and full revocation. Moreover, the scheme is better than Wang et al's scheme in terms of the storage, computation and communication costs.