Traitor Tracing - Encryption for Digital Content - page 125

from Q (and possibly with even higher probability when given queries
from outside of this set).
Now that we have defined the rules of engagement between the two players
of the tracing game we will specify when game is winnable by the tracer.
Definition 3.14. We say that the tracing game TG = hKeyDist,Q,Ri is
winnable by a tracer T with probability α for σ-threshold and t-coalitions if
for all A for which the pair hA,Ti is σ-admissible it holds that for all n ∈ N,
C ⊆ [n], |C|≤ t,
Prob[∅6= hA,Ti(tk,ek,sk 1 ,...,sk n ,C) ⊆ C] ≥ α
where (tk,ek,sk 1 ,...,sk n ) is distributed according to KeyDist(1 n ).
Provided that TG is winnable by a tracer T , we define the tracing overhead
trover[ TG ,T ] of the tracing game TG as the supremum of all r hA,T i ; note that
trover[ TG ,T ] is a function of t,σ and possibly of other parameters as well.
Note that in the notation trover[ TG ,T ] we may omit T and write simply
trover[ TG ] if it is clear from the context to which tracer T we refer to.
It is interesting to note that the tracing game can be thought of as a privacy
game if we flip the semantics of what side is adversarial. In this alternative
interpretation, the good side is sitting on the adversary side and attempts
to output some data that meet some “usefulness criterion” determined by R
and are based on the private information of the users. On the other hand, the
adversary is sitting on the tracer side and attempts to violate the privacy of
the users. We do not pursue this parallel further here.
3.4 Types of Tracing Games
In this section we will define two basic types of tracing games that will be the
focus of the chapter. Recall that a tracing game is a triple hKeyDist,Q,Ri
and is defined with respect to an s-ary multiuser encryption scheme ME =
(KeyDist,Transmit,Receive).
3.4.1 Non-Black Box Tracing Game.
In this setting, the adversary is considered to be a pirate decoder that is
capable of receiving the transmission through some key material that is made
out of traitor keys. The non-black box tracing game refers to the case where
the response of the adversary is defined to be the key material that makes
the decoder succesful. This response is not necessarily a real reaction of the
adversary but rather an abstract notion that in reality may include physical
tampering on behalf of the tracer. In many settings by “reverse-engineering”
a decoder, it might be possible to retrieve the key employed within. We note