Cryptography Reference
In-Depth Information
Recall that the Identify TA algorithm accuses a codeword that will share
at least
`
w positions with the pirate codeword, indeed there exists a traitor
codeword who has a score at least w . We will now discuss the success prob-
ability of a forging algorithm in producing a pirate codeword that frames a
user, i.e. the maximum score, at least
`
w , belongs to an innocent user. The
probability is taken over all traitor coalitions and the framed user-index and
the code randomization. A critical component of the analysis below is that the
resulting code is not open, i.e., the adversary has no access to the code while
preparing the descendant codeword. We start with a preparatory lemma.
Lemma 1.17. Let σ be a mapping that, on input a set of strings T ⊆ 2 Q `
with |T| ≤ w, it outputs a string of the same length from desc(T ). Given a
vector f ∈ Q ` the following holds:
{i | f i = σ(T ) i }≥ `
Prob
≤ ε
w
for ` ≥ 4w log( ε ) and |Q| = q = 2w where the probability is taken over
random choices of σ and T ⊆ 2 Q ` with |T|≤ w.
Proof of Lemma 1.17 : Let X i , for i = 1,...,`, be the random variable such
that X i = 1 if the i-th symbol in the user codeword matches with the i-th
symbol of the pirate codeword that is the output of the adversarial strategy σ,
i.e. if f i = σ({c j } j∈C ) i . The mean value for any position would be q given that
the strategy is independent of the choice of f. Applying the Chernoff bound
(see Theorem 1.1 ) for δ > 0 we have :
q
l X
e δ
(δ + 1) δ+1
X i ≥ (1 + δ) · `
Prob[
q ] <
i=1
Setting δ = 1 and q = 2w we get:
Prob[ P l i=1 X i ≥ 2· 2w ] < 4 2w
Prob[ P l i=1 X i w ] ≤ e 2
4w
Prob[ P l i=1 X i w ] ≤ 2 −1 4w
16
Provided we choose ` ≥ 4w log ε the above probability is bounded by ε
and the theorem is proven.
Based on the lemma we can now put forth the following theorem on the
secret Chor-Fiat-Naor code:
Theorem 1.18. The q-ary secret fingerprinting (CodeGen ` CFN ,Identify TA )
is (ε,w)-identifier provided that ` ≥ 4w log( ε ) and q = 2w.
 
 
 
Search WWH ::




Custom Search