[13158] in cryptography@c2.net mail archive
Re: eWeek: Cryptography Guru Paul Kocher Speaks Out
daemon@ATHENA.MIT.EDU (Peter Wayner)
Fri May 2 09:10:25 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Thu, 1 May 2003 22:59:21 -0400
To: <cryptography@metzdowd.com>
From: Peter Wayner <pcw2@flyzone.com>
Cc: nobody@dizum.com, rivest@mit.edu, tls@rek.tjls.com,
iang@systemics.com, decoy@iki.fi, sidney@sidney.com
At 7:14 PM -0400 5/1/03, Ronald L. Rivest wrote:
>There is a _very_ relevant paper to this
>discussion by Boneh and Shaw:
> http://crypto.stanford.edu/~dabo/abstracts/finger.html
Here's what I took away from the paper:
The crucial point seems to be that you can't do much better than
finding $n$ hiding spots in a document/file (call them "bits") to
make $n$ different marks signifying ownership. So if you sell copy
$i$ to person $i$ you flip $i$.
You can do some clever coding, but it's all just a minimum of one bit
per person/mark.
Let's say four people get together to steal a document by "averaging"
their documents. Since you can't have half a bit, they flip a coin
for the four bits, "i,j,k$ and $l$ that are different in the four
documents. Two of these will be returned to the "unmarked" position
and two will be left accusing two of the people. There should be no
easy way for the thieves to know who's left on the hook.
It's possible to flip several bits for each person increasing the
odds. If you flip, say, 16 bits for each person/mark, then the gang
of four will find 64 different bits in their files. They flip some
coins and each person is still stuck with an average of about 8 bits
accusing them. This is certainly better, but it takes more work to
hide 16 bits/person.
How do you hide the bits? Any stego will do. Some error correction
can make it even more interesting.
My feeling is that this is a pretty solid result because it didn't
seem like one could do much better. A few tweaks of the problem,
though, may yield something different. It's still not a well-defined
space.
Of course, I'm willing to be corrected/pestered/pilloried/praised
etc. by those on the list who came away with other conclusions.
-Peter
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
