eWeek: Cryptography Guru Paul Kocher Speaks Out

Peter Wayner pcw2 at flyzone.com
Thu May 1 22:59:21 EDT 2003


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 at metzdowd.com



More information about the cryptography mailing list