Cryptography Reference
In-Depth Information
Proof. Fixing an encoding ψ = {S
j
1
,...,S
j
s
}, we will argue that the related
revocation game is winnable by the tracer T
SC
with the parameters given in
the theorem for the revocation-suitable relation
SC
. (i) Based on an almost
similar argument of the proof of Theorem
3.19
, it is left as an exercise for
the reader to see that the given parameters su
ce to locate a subset S
j
w
, for
w ≤ s, containing a traitor.
The tracer then splits the subset S
j
w
; we denote the output by (S
j
l
,S
j
r
) =
spt(S
j
w
); the tracer then returns the broadcast pattern ψ
0
= {S
j
1
,...,S
j
w−1
,S
j
l
,
S
j
r
,S
j
w+1
,...,S
j
s
}. It is easy to observe that for any u ∈ [n] \(R∪C) it holds
that Decrypt(sk
u
,c) = m where c ← Encrypt(ek,m,ψ
0
) and ψ encodes the
set R to be revoked. It further holds that (C,ψ)
SC
(C,ψ
0
) which completes
the proof of the theorem.
4.3 Tracing and Revoking Pirate Rebroadcasts
In this section, we consider a stronger scenario for tracing and revoking :
when the tracing needs to be performed alfresco against history recording
adversaries. This is important in the setting of pirate rebroadcasting : in
such case, it is not feasible for the tracer to privately experiment with the
rogue decoder. The tracer collects feedback from the pirate rebroadcasts but
is incapable of experimenting with the pirate decoder in a way that hurts
correctness for legitimate receivers.
To deal with this problem we will introduce a special class of stateful q-
ary broadcast encryption schemes. Each such scheme is parameterized by a
fingerprinting code
F
= (CodeGen,Identify) and is denoted by
BE
F
,q
. The
state σ ∈ States of the scheme
BE
F
,q
is a pair hW,li where W is an instance
of the fingerprinting code that is sampled by the CodeGen
`
algorithm on
input q ∈ [n], and l is an integer that satisfies 0 < l ≤ `. We also allow W to
be empty in which case l = 0. We define the three algorithms associated with
the scheme as follows.
• KeyGen
F
. Given 1
n
it chooses an (n,r,t)-exclusive set system Φ =
{S
j
}
j∈J
. The algorithm then generates a collection of keys {k
j
}
j∈J
⊆ K.
For any u ∈ [n], define J
u
:= {j | u ∈ S
j
} and K
u
= {k
j
| j ∈J
u
}. It sets
ek = hΦ,{k
j
}
j∈J
i and sk
u
= (J
u
,K
u
) for any u ∈ [n].
The language L consists of the descriptions of those elements of 2
Φ
such
that P = {S
j
1
,...,S
j
s
}∈L if and only if s ≤ t and the set R = [n]\∪
i=1
S
j
i
satisfies |R|≤ r; in such case we say that P encodes R.
The initial state σ
0
is set to be h⊥,0i.
• Encrypt
F
. Given ψ ∈ L and a vector of input M = hm
1
,...,m
q
i, say
ψ = {S
j
1
,...,S
j
s
} where j
i
∈J for i ∈{1,...,s}. The set of keys {k
j
| j ∈
J and S
j
∈ ψ} is retrieved from {k
j
}
j∈J
.
