Cryptography Reference
In-Depth Information
Theorem 5.7. Let n ∈ N be the number of receivers. For a given R ⊆ [n],
any leaking incident Leaking corrupting t users in a single subset S ∈
Revoke(Φ
CS
,R) = ψ enables an evolving pirate with respect to Leaking
so that PE
R,GenDisable
P,Leaking
(t) ≥ 2t−2 + log(|S|/t).
Proof of Theorem
5.7
: We will count the number of nodes in the Steiner
tree Steiner(T,S) as it is the number of decoders P can construct with re-
spect to any leaking incident Leaking corrupting t users in S. Denoting
the number of nodes with depth i by c
i
≥ 1 we have PE
R,GenDisable
(t) =
P,Leaking
P
log |S|
i=0
c
i
. It is clear that c
i
≥ dc
i+1
/2e and c
log |S|
= t. Then it holds that
c
i
≥dc
log |S|
/2
log |S|−i
e = dt/2
log |S|−i
e, hence:
log |S|
log |S|
X
X
dt/2
log |S|−i
e
c
i
≥
i=0
i=0
2
dlog te
it holds that dt/2
log |S|−i
e = 1 for all 0 ≤ i ≤ log|S|−
t
Since 1 ≥
dlog te.
log |S|
log |S|
log |S|−dlog(t)e−1
X
X
X
PE
R,GenDisable
P,Leaking
dt/2
log |S|−i
e+
(t) =
c
i
≥
1
i=0
i=log |S|−dlog(t)e
i=0
This yields the following:
(t) ≥ t·
P
dlog te
i=0
1/2
i
+
P
log |S|−dlog(t)e−1
i=0
PE
R,GenDisable
P,Leaking
1
≥ t· (2−1/2
dlog te
) + log(|S|/t) −1
≥ 2t−2 + log(|S|/t)
which completes the proof of the theorem.
Theorem 5.8. Let n ∈ N be the number of receivers. For a given R ⊆ [n],
there exists a leaking incident Leaking corrupting t users in a single subset
S ∈Revoke(Φ
CS
,R) = ψ so that PE
R,GenDisable
(t) ≥ t−1 + t log(|S|/t).
P,Leaking
Proof of Theorem
5.8
: It is su
cient to describe a leaking incident Leaking
that satisfies PE
R,GenDisable
P,Leaking
(t) ≥ 2t−1 +t log(|S|/t). Consider the nodes of
the Steiner tree Steiner(T,S) and denote the number of nodes with depth i by
c
i
. We choose the leaking incident as follows: (1) any node of depth ≤blog tc
is an ancestor of at least one traitor, (2) for any depth > blog tc there exist
t nodes at this depth that are ancestors of a traitor. These conditions are
equivalent to saying c
i
= 2
i
for all 0 ≤ i ≤blog tc, and c
i
= t otherwise. Such
log |S|
c
i
will give us the number of pirate decoder generations with respect to the given
leaking incident:
