Information-theoretic analysis of spherical fingerprinting

Information-theoretic performance limits of digital fingerprinting systems subject to almost-sure squared-error distortion constraints on the fingerprint embedder and the colluders are derived in this paper. The rate of the fingerprinting code is R = 1/N log M where N is codelength and M is the number of users. No assumption is made on the host signal statistics, but the collusion channel is also subject to a location-invariant condition. The receiver knows neither the collusion channel nor even the number of colluders. Capacity is the supremum of achievable rates and is shown to be equal to 1/2K log(1 + D_f/KD_c) where K is the number of colluders, and D_f and D_c are the L²-distortion tolerance levels for the fingerprint embedder and the colluders, respectively. The worst collusion is shown to consist of uniform linear averaging of the coalition´s marked copies followed by addition of independent spherical noise. Positive error exponents are achieved at all rates below capacity using random spherical fingerprinting codes and a new universal decoding criterion based on empirical Gaussian mutual information. It is also shown that minimum-distance decoding fails for this problem, and that a simple single-user decoder is almost as good as the universal decoder for large K. Geometric interpretations for all the results are given.