Cryptography Reference
In-Depth Information
We start the analysis of the traceability of these two schemes by a lemma
in the style of lemma
3.17
.
Lemma 3.20. Given a fingerprinting code
F
= (CodeGen
`
,Identify), con-
sider (tk,ek,sk
1
,...,sk
n
) ← KeyDist
F
(1
n
) such that tk = (W,ik) ←
CodeGen
`
(1
n
), ek = {k
i,j
}
(i,j)∈[q]×[`]
and sk
u
= hk
w
1
,1
,k
w
2
,2
,...,k
w
`
,`
i
where w
u
= hw
1
,w
2
,...,w
`
i∈W for u ∈ [n].
Assuming that k
i,j
∈ {k
w
j
,j
| u ∈ C}, any probabilistic polynomial time
adversary A, given {sk
u
}
u∈C
, distinguishes the following distributions
• Transmit
i,j−1
CFN[
F
]
(ek,m) from Transmit
i,
CFN[
F
]
(ek,m)
• Transmit
i,j−1
BN[
F
]
(ek,m) from Transmit
i,j
BN[
F
]
(ek,m)
with probability at most 2ε
p
where the underlying encryption scheme (
E
,
D
)
is ε
p
-insecure in the sense of Definition
2.5
.
Proof. The proof of the lemma is nearly identical to the proof of lemma
3.17
,
hence we skip it and leave it as an exercise for the reader.
The plan for the tracer design is as follows. The tracer will query the ad-
versary with the tracing ciphertexts of the above form. An adversary that
is su
ciently successful (we will make this requirement explicit later in the
statements of the theorems) in both of these schemes would be using a key
k
w
j
,j
for each j where w
j
∈{1,2,...,q}. The goal of the tracer is to deduce
the key k
w
j
,j
by using a walking argument over each column similar to the
procedure used in the linear length scheme of the previous subsection. Fi-
nally, we will be able to construct a pirate codeword w = hw
1
,...,w
`
i from
the keys deduced at each column. The Identify algorithm of the underlying
fingerprinting code will then be used to output a traitor as long as the traitor
coalition is bounded by t with su
ciently large success probability.
With the above brief summary of the tracer strategy, we will discuss the
traceability of both schemes separately as the constraint placed on the adver-
sary is different for the two schemes. On the one hand, the advantage of the
Boneh-Naor scheme is its short transmission length (which can even be con-
stant if the alphabet size q is taken to be constant). On the downside it will
support traceability against pirates with higher success rates. The Chor-Fiat-
Naor scheme, on the other hand, is successful in tracing pirates with smaller
σ probabilities at the price of requiring from the transmission length to be
a function of n; the exact relationship depends on the choice of the length
function ` of the underlying code.
We first discuss traceability of the Chor-Fiat-Naor scheme. We define p
i,j
to be the probability that the pirate decoder decrypts the special ciphertext
Transmit
i,
CFN[
F
]
(ek,m). Suppose, now, that the key k
i,j
is not available to the
adversary; in this case, it holds that the pirate decoder can distinguish between
the random variables Transmit
i−1,j
CFN[
F
]
(ek,m) and Transmit
i,
CFN[
F
]
(ek,m)
