From: nelson@media.mit.edu (Nelson Minar)
Date: Fri, 6 Dec 1996 15:36:02 -0800 (PST)
To: cypherpunks@toad.com
Subject: summary of talk by Birgit Pfitzmann on "Asymmetric and Anonymous Fingerprinting"
Message-ID: <199612062335.SAA09798@hattrick.media.mit.edu>
MIME-Version: 1.0
Content-Type: text/plain


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.