Cryptography Reference
In-Depth Information
decoders produced by the evolving pirate. Next, we discuss how the pirate
evolution can be applied to the subset cover schemes and subsequently we
study pirate evolution for the complete-subtree and subset-difference exclu-
sive set systems as described in Section
2.5
. For the complete subtree method
we present a pirate evolution attack that given t traitor keys, it enables an
evolving pirate to produce up to t log(n/t) generations where n is the total
number of users in the system. For the subset difference method we present a
pirate evolution attack that given t traitor keys, it enables an evolving pirate
to produce up to t log n generations of pirate decoders.
5.1 Pirate Evolution: Definitions
In this section we introduce the concept of pirate evolution. We present a
game based definition that is played with the adversary which is the evolv-
ing pirate. Let t be the number of traitor keys in the hands of the pirate.
The traitor keys are made available to the pirate through a key-leaking in-
cident Leaking that somehow chooses a subset T of size t from the receiver
population {1,...,n}. The Leaking algorithm, on input the set of encodings
(L with all possible revocation instructions, recieves the corresponding subset
{sk
u
}
u∈T
of all users' private data where (L,{sk
1
,...,sk
n
}) ←KeyGen(1
n
).
We permit Leaking to be also based on the current set of revoked users R.
Specifically, if T = Leaking(L,t,R) then |T| = t, T ⊆ {u | u ∈ [n] \ R}.
This models the fact that the evolving pirate may be able to select the users
that it corrupts. Separating the evolving pirate from the leaking incident is
important though as it enables us to describe how a pirate can deal with leak-
ing incidents that are not necessarily the most favorable. Indeed, the forms of
pirate evolution that we will describe in the sequel will operate with any given
leaking incident and there will be leaking incidents that are more favorable
than others.
Once the leaking incident determines the private user data that will be
available to the evolving pirate (i.e., the traitor key material), the evolving
pirate P receives the keys and produces a “master” pirate box MasterBox.
The pirate is allowed to have oracle access to an oracle Encrypt(ek,m,ψ)
for each ψ ∈ L that returns ciphertexts distributed according to plaintext
distribution that is employed by the digital content distribution system.
Given the master pirate box, an iterative process is initiated: the master
pirate box spawns successively a sequence of pirate decoders B
1
,B
2
,... where
B
`
= MasterBox(1
t+log n
,`) for ` = 1,2,.... Note that we loosely think
that the master box is simply the compact representation of a vector of pirate
boxes; the time complexity allowed for its operation is polynomial in t+log n+
log `. We note that this may be generalized in other contexts but is su
cient
for describing a wide range of evolving pirate strategies. Each pirate box is
tested whether it decrypts correctly the plaintexts that are transmitted with
