Cryptography Reference
In-Depth Information
(iii) Induction step: Let ψ
k
= GenDisable(ψ,hB
i
,B
i
1
,B
i
2
,···B
i
k−1
i,σ)
be the the revocation instruction containing the subset S
j
k
as given in the
induction assumption. The pirate box B
i
k
= CSBox
j
k
is capable of decrypt-
ing ciphertexts distributed according to Encrypt(ek,·,ψ
k
) with probability
greater than the threshold σ. The revocation algorithm of Figure
4.2
against
the pirate box B
i
k
with respect to ψ
k
will output S
j
k
as the subset con-
taining the traitor. The algorithm will then partition S
j
k
into two equally-
sized subsets where one of it is S
j
k+1
. The decoder B
i
k
will no more be able
to decrypt the encryption due to the partition in Revocation(ψ
k
,B
i
k
,σ).
Hence, the final outcome partition that disables all boxes will satisfy fol-
lowing: S
j
k+1
∈ GenDisable(ψ,hB
i
,B
i
1
,B
i
2
,···B
i
k
i,σ) as the statement of
induction step.
Using the claim we now conclude that
S
j
s
∈GenDisable(ψ,hB
i
,B
i
1
,B
i
2
,···B
i
s−1
i,σ)
Given that S
j
= S
j
s
we have that the box B
v+1
will be able to decrypt such
revocation instructions.
Claim 2: We next claim that revoking all the other boxes in the sequence
of {B
1
,···B
v
}\{B
i
,B
i
1
,B
i
2
,···B
i
s−1
} will not hurt the capability of B
v+1
to
decrypt. This would be the case as long as revoking those boxes will not result
in splitting the subset S
j
. The proof of claim follows easily by the fact that
revoking any of those boxes does not affect S
j
since each one corresponds to
a subset key disjoint from S
j
.
We conclude, as a consequence of the above,
S
j
s
= S
j
∈GenDisable(ψ,hB
1
,B
2
,···B
v
i,σ) = ψ
0
Recall that B
i
s
= B
v+1
= CSBox
j
, we finally obtain
Prob[B
v+1
(Encrypt(ek,m,ψ
0
)) = m] ≥ σ
(2) Suppose that j is an encoding of root(S) that is a root of one of the
trees in the forest {Steiner(T,S) | S ∈ ψ}, i.e. it holds that S ∈ ψ. Because
all the Steiner trees are disjoint, with a similar argument as claim 2 before,
S ∈ GenDisable(ψ,hB
1
,B
2
,···B
v
i,σ) since S was never split while tracing
all previous boxes. From the definition of B
v+1
, we can conclude
Prob[B
v+1
(Encrypt(ek,m,ψ
0
)) = m] ≥ σ
where ψ
0
= GenDisable(ψ,hB
1
,B
2
,···B
v
i,σ).
We next study the classes of leaking incidents and the number of boxes
they produce. For the polynomial time adversary P described in Figure
5.3
,
PE
R,GenDisable
P,Leaking
(t) is the number of nodes in the forest of the Steiner trees of
for different leaking incidents.
