Cryptography-Digest Digest #844, Volume #9 Wed, 7 Jul 99 21:13:03 EDT
Contents:
Re: MP3 Piracy Prevention is Impossible (Tenexus)
Re: trapdoor one way functions (Nicol So)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Tenexus)
Subject: Re: MP3 Piracy Prevention is Impossible
Date: Thu, 08 Jul 1999 00:37:13 GMT
On 30 Jun 1999 18:18:52 -0400, [EMAIL PROTECTED] wrote:
[clip]
>If the file is encrypted, one will have to rerecord it to make a digital
>copy (e.g. using LOOPBACK as the sound source, which takes the output from
>the player as input ... or physically take the line-out from one computer
>to the line-input of the other). This involves (one) conversion from
>digital to analog and back again. The "watermark"/"serial number" will
>have to be strong enough to be resistant to conversions to analog and even
>filtering (if one wants to use an equalizer to boost the bass, for
>example). It will have to be audible. And so embedded in the sound that it
>cannot be removed (with filtering, say to remove all the lowest order bits
>in a 16 bit sound file).
[clip]
What would happen /w digital watermarking schemes, if one were to
purchase mutliple copies of a work and combine them? I assume these
different works would contain different signatures, would they not?
Consequently, if I were to digitally average multiple copies of a
song, could I not eventually degrade these watermarks to a useless
state? Or, am I missing something?
Neil Padgett
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: trapdoor one way functions
Date: Wed, 07 Jul 1999 20:13:22 -0400
[EMAIL PROTECTED] wrote:
>
> Nicol So wrote:
> > [argument that non-existence of weak one-way function => P = NP,
> > deleted]
>
> Yes that's convincing. I find that there are several
> definitions of one-way functions in the literature.
> Some require that they have inverses. That's what I
> was assuming, since for a one-way trap-door function
> to immediately yield a public key cryptosystem it must
> have an inverse.
I was not going to follow up on the argument, if nobody paid attention.
Since at least one person did, I think I should point out that there was
a problem with the argument. Although the formalization used (as
expressed by Proposition 1) did capture the notion of "easy in the
forward direction, hard in the reverse direction", the definition is not
equivalent to the commonly used definition of weak one-way function.
The common definition of one-way function requires the (polynomial-time)
inverting algorithm to be wrong at least a "non-neglible" fraction of
the time. ("Negligibility" here is defined in terms of polynomials in
the security parameter). The notion used in Proposition 1 only requires
the function to be hard to invert in the worst case. The problem is, it
is easy to construct a function with only an exponentially small
fraction of hard-to-invert images (assuming one-way functions do
exist). So... the two definitions are non-equivalent if one-way
functions exist.
Of course, it could still be the case that the existence questions of
one-way functions in the two senses are equivalent, but I don't have a
proof.
Nicol
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
