A flexible-revocation scheme for efficient public-key black-box traitor tracing
We propose a new type of revocation scheme for efficient public-key black-box traitor tracing. Our revocation scheme is flexible and efficient in the sense that (i) any number of subscribers can be revoked in each distribution under an assumption that the number of revoked subscribers who collude in one coalition is limited to a threshold and (ii) both each subscriber's storage and the transmission overhead are independent of n, while (i) the maximum number of revoked ones cannot be changed or (ii) they depend on n in previous schemes, where n is the total number of subscribers. The flexibility in revocation is significant since flexible revocation can be integrated with efficient black-box tracing and this integration can be achieved without a substantial increase in the transmission overhead over the previous schemes. In this paper, we present a concrete construction of an efficient public-key black-box traceable and revocable scheme by combining flexible revocation with a known black-box tracing algorithm which works under the same attack model as assumed in the previous schemes. Our scheme achieves that (i) the transmission overhead remains efficient, especially linear only in k in case of bulk revocation and (ii) the tracing algorithm runs in 0(log n) time, while the previous ones cannot satisfy both of these properties, where k is the maximum number of traitors in a coalition.
flexible revocation black-box tracing public-key traitor tracing