Cryptography Reference
In-Depth Information
1
Fingerprinting Codes
In the context of digital content distribution, an important problem is tracking
the origin of an observed signal to one out of many possible sources. We are
particularly interested in settings where no other help is available for achieving
this tracking operation except the mere access to the signal itself. We take a
quite liberal interpretation of the notion of a signal : it may correspond to
data transmission or even to a content related functionality. For instance, it
might correspond to the decryption function of a decoder owned by a user
where the population of users is defined by the keys they have access to. In
another setting, it might be the retransmission of a certain content stream
where the copies licensed to each user have the capacity to uniquely identify
them.
An immediate application of such tracking capability is a leakage deter-
rence mechanism : by linking an incident of exposure of content back to the
event of licensing the content, it is possible that willful content leaking can
be deterred.
The problem of tracking can be addressed through “fingerprinting” : a
one-to-one mapping from the set of users to a set of objects of equivalent
functionality. Ideally there will be as many objects as the number of users
and each object, even if slightly manipulated, it will still be capable of dis-
tinguishing its owner from others. Unfortunately it is the case that it can be
quite expensive or even infeasible to generate a high number of variations of a
certain functionality. Consider, for instance, in the context of encryption, as-
signing each user an independently generated key; this trivial solution would
make it easy to distinguish a certain user but in order to maintain identical
functionality among users a linear blowup in the complexity of encryption
would be incurred.
A solution approach for solving the fingerprinting problem that is consis-
tent with digital content distribution is the expansion of the object set to the
set of sequences of objects of certain lengths. In this way, if at least two vari-
ations are feasible at the object level, say 0 and 1, then it is possible to assign
to each user one sequence out of exponentially many that corresponds to a
