Forwarded: tagging info

[Brian D Williams <talon57@well.sf.ca.us>]

Forwarded from Extropians:



 First off, before I discuss schemes for tagging data, let me say
that I'm completely opposed to copyrights, patents, and all forms
of intellectual property law.  They're unhip and anti-extropian. 
I realize that a majority of Extropians will come out in favor of
copyright law, given that they're knowledge workers, but they're
misguided:  there are plenty of ways to turn information into cash
without making the free exchange of information illegal.  Use your
originality rather than a big stick.
(For more, see my article "Free the Bits", article #94-9-488)

<falls off of soapbox>

 That said, let me describe the ways I've worked out to be Big
Brother. I've done some work on methods of tagging data in such a
way that the tags can't be removed without destroying the
information.  This is what we really want if we're trying to trace
where our data goes.

 I'm interested in cryptographically strong methods of tagging
data, so putting tags in the noise bits of an image, or in the
whitespace of text, is not good enough.  Such tags can be easily
ripped out.

 The old mapmaker's trick -- inserting a small nonexistent street
into each map -- is more like what I'm getting at.  The idea is to
do a small amount of damage at a chosen site, in such a way that if
the thieves try to cover up the damage without detecting the target
site, they will have to destroy the information they set out to
steal. 

 Mainly I've thought about the case of tagging a piece of ASCII
text, with a different set of tags for each copy of the text,
enabling me to enforce a contract with a buyer of the information
not to redistribute it.  I'm going to choose to make small content
changes, like exchanging a word for its synonym, as my means of
inserting tags into the text which can't be smoothed away.

 The meat of what I'm interested in is when, say, 10 thieves get
together and compare their (distinctly tagged) copies of a newswire
article. Can they succeed in removing the tags and distributing a
clean copy? They do a "diff" of their copies and discover that the
100'th word is sometimes "but" and sometimes "however", and
similarly for 20 other words throughout the document.  The thieves
now have to decide which word to include in their output document
(say, by flipping a coin), in order to scramble any information the
tagger hoped to insert.

 So who wins?  Tagger or thieves?  The short answer is, my kind of
tagging is effective in most cases, but not against a large group
of sophisticated thieves (more than about 20 or so of them).  This
is because the number of tag bits required, according to my
calculations, is exponential in the number of thieves.  

 To see some stuff I wrote last year as part of a discussion on the
sci.crypt newsgroup, and code for a simulator I wrote to test out
an interesting case, retrieve article #94-9-497...


-- Marc Ringuette (mnr@cs.cmu.edu).  Freely forward/archive this.



End of forwarded message


Brian D Williams
Extropian
Cypherpatriot

 "A country that wants to be unarmed and free, wants what never has
been and never will be."                       --- Thomas Jefferson