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

**Abstract:**
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
l_{k} l_{c}^{2} ≥ *Ω*(n),
where l_{k} is the length of user key,
l_{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.

We prove our results by extending the connection between traitor
tracing systems and differentially private database sanitizers to the
setting with random oracle access. After that, we prove the lower bound
for traitor tracing schemes by constructing a differentially private
sanitizer that only queries the random oracle polynomially many times.
In order to reduce the query complexity of the sanitizer, we
prove a large deviation bound for decision forests, which
might be of independent interest.