eWeek: Cryptography Guru Paul Kocher Speaks Out

[Derek Atkins]

Peter Wayner <pcw2 at flyzone.com> writes:

> 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

But wait.  Based on your assumption, each user's data will differ from
an unmarked version by 1 bit and that one bit is different for each
person.  Sure, you can't have partial bits, but you CAN have bit
probabilities!  So you find that all but those four marked bits match
with probability 1, but each of these four marked bits matches a
distribution of .25/.75.  That means you now know with certainty 75%
what the proper bit setting is to make it an unmarked copy.

> 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.

Let's look at bit0 (which is the ID bit for user 0).  Let's assume the
bit is 0 for all users but user 1.  Even if you use pure averaging
across 4 users, you'll have three users with a 0 and one user with a
1, so on average the bit is .25 which rounds to 0.

So, I think you can do much better than "flip a coin" -- and the more
users you can get to collude, the better you can do in finding those
bits and removing them.

> 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.

Yes, if you add more bits per person, then you have a higher chance of
two colluders sharing a bit.  Let's assume you still have 4 colluders,
and 2 of them share a particular bit.  That means you have a 50/50
probability on that bit, so you don't have a good distribution.
However, the more colluders you add, the more likely you are to get a
good distrbution that tends towards the unmodified data.

-derek
-- 
       Derek Atkins
       Computer and Internet Security Consultant
       derek at ihtfp.com             www.ihtfp.com

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com