Almost IPP-codes or provably secure digital fingerprinting codes

Codes with the Identifiable Parent Property (IPP codes) form a very useful tool in traitor tracing schemes since they guarantee (with probability 1) identification of at least one of the traitors. We consider a natural generalization of IPP codes, namely codes for which this property holds with probability close to 1. A probabilistic version of the IPP problem has been studied under the name of collusion-secure digital fingerprinting codes. We point out that, somewhat surprisingly, fingerprinting codes do no automatically have the “almost IPP property.” In practice, this means that for a given forged fingerprint, a good tracing algorithm identifies some user, say u, as a traitor, claiming that the probability of incorrect accusation is close to 0. Nevertheless this user can successfully dispute this claim because with high probability there exist coalitions that do not contain u and that can generate the same forged fingerprint. The described shortcoming of the accepted definition of fingerprinting capacity is manifest even in the simplest case of two traitors. We discuss this case and then analyze some known constructions of digital fingerprinting codes based on concatenated codes.