Traitor Tracing - Encryption for Digital Content - page 126

that a decryption key from the key-space K should be available to the tracer
because of the unlikelihood of performing decryption without a key.
We first define the set of key material K ek ⊆ K that is useful in decrypting
the transmission of any vector of message M = hm 1 ,...,m s i∈M s in an s-ary
multiuser encryption scheme (KeyDist,Transmit,Receive) as follows:
K ek = {k ∈ K |∀M = hm 1 ,...,m s i∈M s
Prob[Receive(Transmit(ek,M),k) ∈{m 1 ,...,m s }] = 1} (3.2)
where (tk,ek,sk 1 ,...,sk n ) is distributed according to KeyDist(1 n ). Note
that the above can be relaxed by requiring only probabilistic correctness.
We define the tracing game in the non-black box model by specializing the
predicate R as follows.
Definition 3.15. We say that a multiuser encryption scheme (KeyDist,
Transmit,Receive) is a non-black box traitor tracing scheme for t-coalitions
with success probability α against σ-pirates if there exists a tracer T such that
the tracing game hKeyDist,Q NB ,R NB i is winnable by T with probability α for
σ-threshold and t-coalitions where R NB (tk,ek,sk 1 ,...,sk n ,q,a) = 1 holds if
and only if a ∈ K ek and Q NB = {open}.
According to the above formulation, an adversary is allowed to respond
with the same exact key material for each query. Hence, without loss of gen-
erality, we will consider only the case that the number of rounds r hA,T i equals
to 1. The design of a multiuser encryption scheme with capability of non-black
box traitor tracing should be feasible so that the tracer T is able to output a
traitor identity having access to only one response from the adversary A.
3.4.2 Black-Box Tracing Game.
In many settings the non-black box approach is inapplicable. Reverse engi-
neering can be expensive and can be possibly deterred through obfuscation
techniques. Thus, it is important to consider the case whether the tracing
procedure can be black-box. This allows tracing to work successfully using
merely black-box access to the pirate decoder. Black-box traitor tracing re-
duces tracing costs significantly as there is no need to “reverse-engineer” the
pirate decoder and may in some cases even allow tracing to be performed
remotely without the physical availability of the pirate decoder.
The major challenge in the black-box traitor setting is to extract infor-
mation regarding the original keys utilised in the construction of the pirate
decoder. The tracer will communicate with the pirate decoder using a set of
specially crafted queries. These queries will not be necessarily normal trans-
missions as the tracing center is allowed to communicate with the decoder in
an arbitrary way. The response of the decoder may be equal to the decrypted
plaintext, or be simply of binary form, essentially “yes”, in case of returning