Cryptography Reference
In-Depth Information
3
Traitor Tracing
A three word description for what traitor tracing aims to achieve is key leakage
deterrence. Arguably the single most important problem in the application of
cryptography is key management. Keys that are lost imply loss of data and
keys that are exposed imply loss of privacy. In the context of digital content
distribution the problem is heavily exacerbated by the fact that cryptographic
keys reside within a possibly adversarial environment.
In a setting where a transmission is aimed to many receivers and it is
desired to control the recipient list, encryption comes to mind as a possible
solution. Unfortunately standard encryption techniques lead to solutions that
are unrealistic to implement in practice. On the one hand, using the same key
throughout motivates key leakage while on the other hand using independent
keys throughout leads to heavy performance loss.
In this setting traitor tracing aims to deter key leakage while maintaining
performance loss to a minimum. In this chapter we will provide a formal treat-
ment of traitor tracing, we will introduce various constructions and measure
their performance characteristics.
3.1 Multiuser Encryption Schemes
Any traitor tracing scheme is based on an underlying encryption mechanism
called a multiuser encryption scheme (
ME
).
An s-ary multiuser encryption scheme
ME
is a triple (KeyDist,Transmit,
Receive) where s ∈ N. The parameter of the scheme is n, the number of
receivers and is associated with three sets K,M,C corresponding to the sets of
keys, plaintexts and ciphertexts respectively. In case s = 1, we will simply call
the scheme as a multiuser encryption scheme. We describe the I/O of these
procedures below:
• KeyDist. It is a probabilistic algorithm that on input 1
n
, it produces
(tk,ek,sk
1
,...,sk
n
). The decryption key sk
i
is to be assigned to the i-th
