Cryptography Reference
In-Depth Information
ber of traitors at the expense of increasing the transmission overhead, i.e.
proportional to the square root of the number of receivers.
We have identified three types of tracing methods in this chapter: (i) non-
black box traitor tracing, (ii) black-box traitor tracing and (iii) tracing pirate
rebroadcasts which requires tracing alfresco in the case of history-recording
(stateful tracing alfresco also satisfies this). The Boneh-Franklin [
16
] (see sec-
tion
3.2
) and Kurosawa-Desmedt [
78
] and other variants we have cited above
are examples of schemes that are tracable in the non-black box setting.
Regarding the black-box traitor tracing, the power of an adversary plays an
important role in the design of the scheme. We have discussed a categorization
According to this categorization we have proved the traceability of the linear
length multiuser encryption scheme, Chor-Fiat-Naor[
28
] and Boneh-Naor [
21
]
schemes for resettable and available decoders only. An abrupt decoder will be
able to deploy a self-defensive mechanism while querying special ciphertexts
over any column. This foils the tracing process as stops the reconstruction of
the pirate codeword. A solution can be designed similar to the case in pirate
rebroadcasting with variating the message through watermarking and tracing
alfresco as if the decoders are history-recording.
In general, tracing abrupt decoders, in the absence of watermarking, is
not an easy task and requires some care in designing schemes. The first non-
trivial proposal for tracing unambiguously abrupt decoders was presented by
Matsushita and Imai [
84
]. Their scheme aimed at producing a ciphertext of
length
√
n and identify one traitor explicitly (i.e., the “suspect list” contained
merely a single member, the guilty receiver). It is based on an extension of
ElGamal encryption that divides the receivers into groups. Each group is
assigned a polynomial and each receiver obtains as secret-key the evaluation
of the group's polynomial on a certain value. The key-point of the scheme
is that the polynomials can share a lot of coe
cients without compromising
security and thus it is possible to compact the ciphertexts in the scheme so
that the total communication complexity becomes sublinear. However, this
scheme was broken by [
80
] and by [
63
] (a partial repair of the scheme is given
in [
63
] that puts a limitation on the way the corruption of traitor occurs).
An important aspect of traitor tracing schemes is the number of rounds
(tracing overhead as we defined in this work) of interaction that are required
between the tracing authority (or simply the tracer) and a rogue device in or-
der for the tracer to establish the desired identities. The majority of schemes
share the same tracing strategy that can be summarized in the following fash-
ion : divide the users in N subsets of a certain size and perform a “walking
procedure” of N steps that utilizes partially corrupted ciphertexts and identi-
fies which one of the N subsets is overlapping with the corrupted users. Then
repeat the procedure with a different set of subsets. In the end combine all the
results to infer a corrupted user identity. In its most basic form, the subsets
can be singletons, i.e., the users themselves and it is only needed to perform
a single such walking procedure (cf. [
70
]).
