Universal fingerprinting: Capacity and random-coding exponents

Bounds on fingerprinting capacity have been derived in recent literature. In this paper we present an exact capacity formula and a universal fingerprinting scheme. Our problem setup unifies the signal-distortion and Boneh-Shaw formulations of fingerprinting. The proposed scheme has four useful properties: (1) the receiver does not need to know the coalition size and collusion channel; (2) a tunable parameter Delta trades off false-positive and false-negative error exponents; (3) the receiver provides a reliability metric for its decision; and (4) the decoder is capacity-achieving when the false-positive exponent Delta tends to zero. The new random coding scheme uses a "time-sharing" randomized sequence and produces conditionally constant-composition fingerprints. The decoder is a minimum penalized equivocation decoder, where the penalty term is proportional to coalition size.