Cryptography Reference
In-Depth Information
subsets in the collection are are single element sets, it should be the case that
ψ
0
\ψ = ∅. Further, ψ 6= ψ
0
and thus ∃S
j
v
∈ ψ such that it is missing in ψ
0
;
this suggests that ψ
0
describes a set for revocation that contains (R∪{v}).
This means that after tracing B
1
the user with index v would be revoked.
Using the inductive argument we can state PE
R∪{v},GenDisable
P,Leaking
(t− 1) ≤ t−
1. Thus the number of pirate decoders succeeding B
1
will be bounded by
PE
R∪{v},GenDisable
P,Leaking
(t−1). The total number of pirate decoders produced by
P with respect to Leaking is thus at most t.
5.3 Pirate Evolution for the Complete Subtree Method
In this section, we demonstrate that the trace and revoke scheme based on
the complete subtree exclusive set system is susceptible to pirate evolution.
Specifically, we present an evolving pirate that can produce up to t log n/t
pirate boxes, given t traitor keys. Below we present some definitions that
will be used throughout this section. We first recall the specifications of the
Complete Subtree method from Section
2.5.1
.
An encoding j ∈J
CS
is a binary string of length at most log n. Each such
encoding corresponds to an index of a node in a full binary tree where the
indices are constructed in a top-down manner: the root of the binary tree is
encoded by (the empty string by ), an index of a left child is constructed by
appending '0' to its parent index, while an index of a right child is constructed
by appending '1' to its parent index. We denote the root of the subtree con-
taining the users in a subset S ∈ Φ
J
by root(S); occasionally we may say j
as opposed to root(S
j
) where j is a valid encoding in J
CS
. We generalize the
definition for the Steiner tree of Section
2.5.1
as follows: Steiner(T,S) is the
minimal subtree of the binary tree rooted at root(S) that connects all leaves
on which the users in T∩S are placed.
we picture the set of revoked users R (the black leaves) and the set of traitors
T = {T
1
,T
2
,T
3
,T
4
} (the squared leaves). The gray nodes correspond to the
subsets in the broadcast pattern that results by Steiner(R, [n]), or equivalently
Revoke(Φ
CS
,R) where the algorithm Revoke of the set system Φ
CS
outputs
a revocation instruction that encodes the set R.
We, next, propose an evolving pirate for the Complete Subtree. First we
consider the following type of pirate decoder:
Definition 5.4. Consider a pirate decoder that uses the key associated to S
j
for which root(S
j
) = j holds. The pirate decoder denoted by CSBox
j
, is con-
structed in such a way that satisfies CSBox
j
(Encrypt(ek,m,ψ)) = m if and
only if S
j
∈ ψ.
The description of the evolving pirate relies on a simple observation that
is the following lemma:
