Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-180 | 4th November 2015 01:46

#### Barriers to Black-Box Constructions of Traitor Tracing Systems

TR15-180
Authors: Bo Tang, Jiapeng Zhang
Publication: 12th November 2015 13:02
Reducibility between different cryptographic primitives is a fundamental problem in modern cryptography. As one of the primitives, traitor tracing systems help content distributors recover the identities of users that collaborated in the pirate construction by tracing pirate decryption boxes. We present the first negative result on designing efficient traitor tracing systems via black-box constructions from symmetric cryptographic primitives, e.g. one-way functions. More specifically, we show that there is no secure traitor tracing scheme in the random oracle model, such that $\ell_k\cdot\ell_c^2\ge\widetilde{\Omega}(n)$, where $\ell_k$ is the length of user key, $\ell_c$ is the length of ciphertext and $n$ is the number of users, under the assumption that the scheme does not access the oracle to generate user keys. To our best knowledge, almost all the practical (non-artificial) cryptographic schemes (not limited to traitor tracing systems) via black-box constructions satisfy this assumption. Thus, our negative results indicate that most of the standard black-box reductions in cryptography cannot help construct a more efficient traitor tracing system.