Abstract: Traitor tracing schemes are used to fight piracy when distributing securely some data to multiple authorized receivers. By traitor tracing schemes, at least one authorized user will be found from those who collude and share their decryption keys to unauthorized users. Based on bilinear map a new public-key traitor tracing scheme is presented in this paper. The main contribution of this scheme is that it concurrently satisfies the following features: 1) Both the number of keys stored by a user and the length of broadcasted block data are independent of the number of users. 2) Full collusion resistance: no users can construct a different valid decryption key from themselves by coalition. 3) Full revoke: any selected users can be revoked without renewing the others’ decryption keys. 4) Full recoverability: any revoked users can be recovered without renewing their decryption keys. Most importantly, compared with the existing schemes that satisfy the above properties, the translation overhead and storage overhead in the new scheme are independent of the total number of users. Finally, in the scheme presented any sets of users can be treated as authorized users. The security of this scheme is based on the difficult problems of solving discrete logarithm problem and decision Diffie-Hellman problem (DDH).