eWeek: Cryptography Guru Paul Kocher Speaks Out

[Anonymous via the Cypherpunks Tonga Remailer]

Thanks to Ron Rivest for pointing to the paper on collusion-secure
fingerprinting by Boneh and Shaw from Crypto 95,
http://crypto.stanford.edu/~dabo/abstracts/finger.html.  It provides
an alternative to the "forensic watermarking" proposed by Cryptography
Research, with different characteristics.

The Boneh&Shaw paper uses the same idea as CR, embedding marks in the
content such that a colluding set of content viewers cannot successfully
identify and alter marks to hide their membership.  B&S have a slightly
weaker goal, which is to recover at least one member of the coalition,
while it appeared that the CR approach intended to discover the entire
coalition.  B&S also use a random component, so there is a certain error
probability that the recovered member is part of the coalition.

The formula for the required number of marks to be embedded using the
B&S scheme is c^4 * log(N/e) * log(1/e), where N is the number of users
in the system, c is the maximum number of users who are able to collude,
and e is the error probability.  CR assumed N = 1 billion.  The error
probability needs to be small, because when we find a pirated movie we
are going to invalidate someone's movie player such that it won't play
any more newly released movies, and we don't want to get the wrong guy.
I'll put e = 1/1000 but it might need to be even smaller.

If we use the same size collusion set as the CR example, c=4, we get about
49,000 marks being required, based on the above equation.  This compares
with only 1,620 marks in the CR approach.  CR used 1% of the frames, while
the B&S scheme will require more like 30% of the frames to be marked.

If we go up to 5 colluders, we need about 119,000 marks, or 74% of
the frames.  Beyond that to 6 colluders, we would have to start putting
more than one mark in each frame.

While this system does not explode quite as badly as the CR method,
it has the disadvantages of requiring more frames for smaller numbers of
colluders; of only identifying potentially one of the colluders, making it
easier for the remainder to continue their pirate operation by replacing
a small number of units; and of providing only a probabilistic result,
which in practice might require tighter error bounds than assumed above
and a correspondingly greater number of marks.

It's possible that the state of the art has improved since 1995 and
that newer techniques can reduce the number of marks needed.  But any
system which goes as the fourth power of the number of colluders is
going to have significant problems in real-world applications.

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