Cryptography Reference
In-Depth Information
Referring to this ubiquitous tracing strategy as “linear tracing”; it was
utilized in the majority of the works cited above and in this work as well.
Two other tracing strategies based on a similar walking argument were put
forth in [
88
] called “binary search tracing” and “noisy binary search tracing”
(the latter being an improvement inspired by [
40
]). The authors of this work
presented in [
66
] a new tracing strategy that has an improved tracing overhead.
It relies on an application of fingerprinting codes superimposed on the tracing
process.
The Kiayias-Yung scheme [
67
] gives a way to play the tracing game alfresco
and win. Hence it can be used as a black-box tracing scheme against reset-
table or history-recording pirate decoders.(cf. the analysis in Theorem
3.24
for resettable case). In a similar vein can also be used in the setting of pirate
rebroadcasting. Pirate rebroadcasting as an attack concept was introduced
by Fiat and Tassa [
43
] that also introduced combinatorial constructions for
solving the problem assuming broadcast encryption as an underlying building
block.
In general a solution for pirate rebroadcasting would require the employ-
ment of watermarking embeddings (see [
30
]). The availability of the embed-
dings would enable the content to become varied over the user population.
Here we abstracted away this need by introducing plaintext distributions with
limited crossover. In practice one way to achieve such limited crossover is
through watermarking. In this case the crossover probability models the ca-
pability of the adversary to manipulate the watermark and fool the reading
algorithm to return an incorrect value (cf. Definition
1.6
).
There are essentially two techniques known in the literature for obtaining
non-trivial solutions for dealing with pirate rebroadcasting: one is dynamic
traitor tracing [
43
] and the other is sequential traitor tracing [
58
,
60
,
99
,
102
].
The idea in both cases is similar: the center will induce a marking of content
and by observing the feedback from the pirate rebroadcast we will identify the
traitors. The two methods differ in the following way: in the former, after each
transmission the center obtains the feedback and tries to refine the suspect
list by reassigning the marks adaptively. The number of traitors is not known
beforehand and the system adjusts itself after each feedback. In the latter
setting, the assignment of marks to the variations is predetermined, and hence
the transmission mechanism is not adaptive to the feedback. Depending on
the parameters used, it may take a number of transmissions until the system
converges and identifies one traitor. A hybrid approach due to the authors of
this text is given in [
64
] that is capable of supporting revocation while tracing
unlimited number of traitors.
Fingerprinting codes play a crucial role in all of the above schemes [
58
,
60
,
64
,
99
,
102
] that were proposed for solving the pirate rebroadcasting problem.
As a short diversion within this bibliographic notes we would like to describe
the multiuser encryption scheme of [
99
] (cf. the extended version of this work
in [
102
]) as an example of another scheme based on fingerprinting codes. It is
a q-ary multiuser encryption scheme that is stateful; the Boneh-Naor scheme
