Cryptography Reference
In-Depth Information
The above can be executed whenever A produces a key δ; it follows im-
mediately that if A produces such key with probability σ then we can recover
successfully the corresponding identities of the traitors.
3.6 Bibliographic Notes
Traitor tracing, as a piracy detection mechanism, was proposed by Chor, Fiat
and Naor [
28
] as a possible solution to the threats that broadcast encryption
[
42
] faced in terms of key leakage. In this chapter we provided a formalization
of the notion of tracing as a two player game between the tracer and the ad-
versary. The goal of the tracer is to perform identification of one of the traitor
users while the goal of the adversary is to prevent this from happening while
still maintaining a level of required functionality. We also put emphasis in the
complexity of this process that is expressed as a function of the required level
of functionality that is required by the adversary as well as other parameters.
Of independent interest is the fact that this formalization of tracing is the
flip side of a class of privacy related interactions considered in [
38
]; there the
adversary is in the tracer side and wishes to violate the privacy of the users.
Given that the intended application of traitor tracing schemes is to handle
encryption of large messages, we envisioned the security of the constructions
in this chapter as key encapsulation mechanisms similar to the broadcast
encryption chapter, i.e. cryptographically strong keys are transmitted using
the multiuser encryption scheme and the actual message is encrypted by the
transmitted key. Such hybrid type of encryption provides an asymptotically
constant rate for long messages (given that the transmission overhead of the
underlying scheme is negligible compared to the length of the message), where
rate is measured as the ratio of ciphertext length to plaintext length. Achieving
constant transmission rate overall in the basic encryption setting was studied
by Kiayias and Yung [
70
] and others [
27
,
39
].
Putting aside the traceability, multiuser encryption schemes fall into two
categories: first we consider the combinatorial constructions, for which the
key assignment is made through some combinatorial distribution from a pool
of cryptographic keys. This follows the seminal work of Chor Fiat Naor [
28
]
and subsequent works [
29
,
110
,
111
,
100
,
113
,
114
,
89
,
9
,
13
] including the
Boneh-Naor [
21
] and Kiayias-Yung [
67
] schemes should all be considered in
this class of multiuser encryption.
The second category of multiuser encryption schemes, are structured simi-
lar to broadcast encryption, and assumes that the key space is endowed with
some structure so that either (i) it enables the preparation of tracing cipher-
texts that makes the corresponding tracing game winnable as e.g., in [
22
] or
(ii) any possible pirate key created from traitor keys carries enough informa-
tion to trace back to one of its traitor keys as in [
16
,
78
].
The Kurosawa-Desmedt scheme[
78
] is based on a public key technique,
in particular on a variant of ElGamal encryption. Stinson and Wei in [
114
]
