Cryptography Reference
In-Depth Information
success probability at least σ, which is a parameter of the underlying trace
and revoke scheme.
The first pirate box is tested against the 'initial' broadcast pattern ψ
whereas any subsequent box is tested against Disable(ψ,hB 1 ,...,B i−1 i,σ)
which is the resulting pattern that corresponds to the conjunctive tracing of
all previous pirate boxes. Here, we refer to the Disable algorithm of section 4.1
and an example can be considered as the generic algorithm given in Figure 4.1 .
The iteration stops when the master pirate box MasterBox is incapable of
producing a pirate decoder with decryption success exceeding the threshold
σ. Each iteration of the master box corresponds to a “generation” of pirate
boxes. The number of successfully decoding pirate generations that the master
box can spawn is the output of the game-based definition given in Figure 5.1 .
In the figure, the Disable algorithm is a procedure that disables the sequence
of pirate decoders; it utilizes the tracer that is given from the fact that the
revocation game winnable for any ψ.
We say that a trace and revoke scheme is immune to pirate evolution if
the number of generations that an evolving pirate can produce equals the
number of traitor keys that have been corrupted (i.e., the number of traitors).
The number of traitors is a natural lower bound to the generations that an
evolving pirate can produce: trivially, an evolving pirate can set each version
it releases to be equal to the decoder of one of the traitors. Nevertheless, the
number of generations that a pirate may produce can be substantially larger
depending on the combinatorial properties of the underlying trace and revoke
system. We call the maximum number of decoders an evolving pirate can
produce, the pirate evolution bound evo of the trace and revoke scheme. Note
that this bound will be a function of the number of traitors t as well as of
other parameters in the system (such as the number of users).
When evo is larger than t, we say that a trace and revoke scheme is suscep-
tible to pirate evolution. The amount of susceptibility varies with the differ-
ence between the number of generations and t; the pirate evolution bound evo
is the highest number of generations any evolving pirate can produce. When
evo is much larger than t, this means that an initial leaking incident can be
“magnified” and be of a scale much larger than what originally expected.
Formally, we have the following:
Definition 5.1. Consider the game of figure 5.1 given a probabilistic time ad-
versary P and two probabilistic algorithms Leaking,Disable and parameters
n ∈ N,R ⊆ [n], t, r = |R|,σ.
Let PE R,Disable
P,Leaking (t) be the output of the game. We say that the trace and re-
voke scheme TR based on a broadcast encryption scheme (KeyGen,Encrypt,
Decrypt) is immune to pirate evolution with respect to key-leaking incident
Leaking if, for any probabilistic polynomial time adversary P, any R and any
t ∈ [n−r], there exists Disable 0 algorithm that satisfies PE R,Disable 0
P,Leaking (t) = t.
We define the pirate evolution bound evo[ TR ,Disable] of a trace and revoke
scheme TR as the supremum of all PE R,Disable
P,Leaking (t), for any leaking incident
Search WWH ::




Custom Search