I just heard an interesting talk by Birgit Pfitzmann of the University of Hildesheim on "asymmetric and anonymous fingerprinting". I thought I'd write up a little summary of the techniques she presented, what they are good for. More detail (including papers) is available on the web at http://www.semper.org/sirene/ see below for specific references Quick summary: background for what fingerprints are and what they're good for traditional fingerprints are symmetric - buyer and merchant both have the fingerprinted data scheme for asymmetric fingerprinting so only buyer has the fingerprint but merchant can still trace fingerprint scheme for anonymous asymmetric fingerprinting so buyer remains anonymous Fingerprinting is something like watermarking. The basic idea is giving merchants of data some way to protect themselves if unauthorized copies of the data are made. Watermarking is useful for proving that a document came from some provider. Fingerprinting goes further in that the merchant gives different buyers subtly different copies of the data - if a copy shows up, the merchant can look at the fingerprint imbedded in the data and figure out who leaked the copy. Traditional fingerprinting has a few hard problems. First, the fingerprint marks need to be embedded in the data without causing any significant change to the data itself. But this goal is in tension with the goal of having the fingerprint survive through potentially lossy transforms. Ie, if I want to fingerprint an audio stream I could modify some of the least significant bits. But then if that audio stream were compressed through some lossy filter the fingerprint might be removed. Furthermore, you want to make it difficult for multiple buyers to collude to remove your fingerprint. Ie: if two buyers compare their purchased data they can identify the parts that are different and conclude that these parts are part of the fingerprint. A good fingerprint coding will make this sort of collusion difficult, although there's a tradeoff between the size of the fingerprint and the number of colluders you can protect against. In a typical fingerprint protocol the merchant calculates the fingerprint, applies it to the data, and then gives the marked copy to the buyer. This is OK except that it means that if an illicit copy of the data shows up no one can prove whether it was the buyer who was responsible for the copy or if it was the merchant. At first glance this might seem silly (what incentive does the merchant have to make illegal copies?) but you can imagine several scenarios where this is a problem. For instance, the buyer wants to be sure it's impossible for the merchant to frame him or her. Also if the merchant's data storage is insecure then someone could steal the merchant's copy and the buyer would be falsely accused. So traditional fingerprints are something like symmetric authentication schemes: both the merchant and the buyer have the secret. The asymmetric fingerprint scheme presented provides a way for the merchant to guarantee that the buyer gets a fingerprinted copy of the data but *the merchant never has a copy of the data with the fingerprint*. Ie: the fingerprinted version is a secret that only the buyer has. This is analagous to asymmetric authentication: people can check that the fingerprint belongs to a buyer but they can't generate it. If a copy with the fingerprint is released then the world knows which buyer is to blame. The details of how this is accomplished were presented but I confess I didn't follow them very closely. Each buyer has a public/secret key pair: the fingerprint is keyed to the buyer's secret key. With a bit commitment algorithm it's possible to arrange it so that the merchant can generate a fingerprint based on the buyer's secret key without actually seeing the key or the fingerprint itself. The merchant can check if a copy of his data came from a buyer by checking the fingerprint with the buyer's public key. I'm sure the paper has the details of the actual algorithm. The system sketched above is not anonymous - the merchant knows the identity of the buyer. The next goal is to make it possible for a buyer to get a fingerprinted copy of data from the merchant without revealing his or her identity. Full anonymity is currently not possible. I didn't follow this very well, but my understanding is there's some scheme where the buyer registers a pseudonym with a third party who then works with the merchant to perform the transaction. The third party doesn't need to be trusted. Consult the web site for details. Overall, this work seems like a nice improvement on fingerprinting schemes. The asymmetry seems like a big win to me. The two directly relevant papers are linked from http://www.semper.org/sirene/lit/abstr96.html Birgit Pfitzmann, Matthias Schunter: Asymmetric Fingerprinting; Eurocrypt 96, LNCS 1070, Springer-Verlag, Berlin 1996, 84-95. Birgit Pfitzmann, Michael Waidner: Anonymous Fingerprinting; IBM Research Report RZ 2881 (#90829) 11/18/96, IBM Research Division, Zürich, Nov. 1996.