Fingerprinting with minimum distance decoding

This paper adopts an information-theoretic framework for the design of collusion-resistant coding/decoding schemes for digital fingerprinting. More specifically, the minimum distance decision rule is used to identify 1 out of $t$ pirates. Achievable rates, under this detection rule, are characterized in two scenarios. First, we consider the averaging attack where a random coding argument is used to show that the rate 1/2 is achievable with $t=2$ pirates. Our study is then extended to the general case of arbitrary $t$ highlighting the underlying complexity-performance tradeoff. Overall, these results establish the significant performance gains offered by minimum distance decoding compared to other approaches based on orthogonal codes and correlation detectors which can support only a subexponential number of users (i.e., a zero rate). In the second scenario, we characterize the achievable rates, with minimum distance decoding, under any collusion attack that satisfies the marking assumption. For $t=2$ pirates, we show that the rate $1-H(0.25)\approx 0.188$ is achievable using an ensemble of random linear codes. For $t\geq 3$, the existence of a nonresolvable collusion attack, with minimum distance decoding, for any nonzero rate is established. Inspired by our theoretical analysis, we then construct coding/decoding schemes for fingerprinting based on the celebrated belief-propagation framework. Using an explicit repeat-accumulate code, we obtain a vanishingly small probability of misidentification at rate 1/3 under averaging attack with $t=2$. For collusion attacks, which satisfy the marking assumption, we use a more sophisticated accumulate repeat accumulate code to obtain a vanishingly small misidentification probability at rate 1/9 with $t=2$. These results represent a marked improvement over the best available designs in the literature. © 2009 IEEE.