Cryptography Reference
In-Depth Information
and Boneh and Franklin in [
16
] pointed out that the arguments behind the
traceability algorithm of [
78
] were problematic (in particular it was possible
for traitors to foil the the tracing algorithm). Boneh and Franklin presented
a different variant of ElGamal encryption and they provided the first prov-
ably robust traitor tracing procedure that could recover all traitors e
ciently.
This tracing procedure was suitable for the non black-box setting where it
is assumed that the tracer has access to the internals of the pirate decoder.
For the black-box setting (where the tracing is done based solely on input-
output interaction with the pirate device), they also introduced a technique
called “black-box confirmation” that can only deal with a logarithmic number
of traitors. Subsequently in [
68
] it was shown that such public key systems
cannot e
ciently support a black-box traitor tracing procedure for a super-
logarithmic number of traitors, thus showing that the black-box traitor trac-
ing procedure of confirmation presented in [
16
] was essentially tight for their
scheme for the black-box setting and could not be further improved. Later
Kurosawa and Yoshida [
79
] worked on black-box traitor tracing of the scheme
of [
78
]; they showed that the scheme also accepts black-box confirmation,
and thus any logarithmic number of traitors can be recovered as well in this
scheme (for black-box tracing). Extending these results, in [
118
] it was shown
that linear codes based schemes can support also revocation and in [
119
] a
relation between cover free families and ElGamal public-key traitor tracing
was explored.
An extended type of ElGamal encryption is introduced by Kiayias and
Yung in [
71
] that classifies the previous work in public key traitor tracing as
those of [
78
] and [
16
]. In this type of encryption which we term ExEG for
“extended ElGamal” the key of each user is a representation of an exponent.
Given that the key structure of the Kurosawa-Desmedt key space has the form
of a Generalized Reed-Solomon code that is e
ciently decodable, it is shown in
[
71
] that the traceability of [
78
] can be extended to superlogarithmic coalitions
by calibrating the ciphertext size appropriately in the non black-box setting
(beyond what is possible in the black-box case). The notion of a traitor tracing
scheme with unbounded enrollment is also introduced in [
71
] to suggest that
group of users can grow indefinitely and that the system administrator need
not know at the start of the system's operation a (polynomial) upper bound
on the number of users as it is the case with the schemes in this chapter.
The decodability of Boneh-Franklin scheme we have provided in the proof
of Lemma
3.26
is based on the Berlekamp-Welch algorithm (patented in [
11
]).
An improvement on the e
ciency of decoding is given in [
61
] by using the
Berlekamp-Massey algorithm instead. Using the list-decoding techniques of
Guruswami and Sudan [
51
] the size of the traitor coalition for which the
schemes based on extended ElGamal type encryption may resist can be in-
creased but at a high cost.
It should be noted that these schemes share a bound on the number of
the size of the traitor coalition. A notable construction is due to Boneh, Shai
and Waters [
22
] as the scheme is fully-collusion resistant against any num-
