Traitor tracing with optimal transmission rate

Abstract. We present the first Traitor Tracing scheme with efficient black-box traitor tracing in which the ratio of the ciphertext and plaintext lengths (the transmission rate) is asymptotically 1, which is optimal. Previous constructions in this setting either obtained constant (but not optimal) transmission rate [KY02b], or did not support black-box tracing [CPP05]. As additional contributions, we point out and resolve an issue in the black-box traitor tracing mechanism in the scheme of [KY02b]; and we show that the scheme of [CPP05], which extends [KY02b] and inherits its tracing mechanism, in fact does not provide black-box tracing nor (local) public traceability. In particular, whereas fixing the scheme of [KY02b] requires just a simple, local change to the tracing algorithm, repairing the black-box functionality and the public traceability features of [CPP05] voids the claimed optimality of the transmission rate, and results in a new scheme with essentially the same parameters as in [KY02b]. Our construction is based on the Decisional Bilinear Diffie-Hellman (DBDH) assumption, and attains the same features of public traceability as (a repaired variant of) [CPP05], which is less efficient and requires non-standard assumptions for bilinear groups