Subject: RE: Concern: Does kcrypto imply that PRF is really a PRF

From: "Paul Leach" <[email-masked]>
Date: Mon, 27 Sep 2004 11:34:20 -0700

> -----Original Message-----
> From: Nicolas Williams [mailto:[email-masked]]
> Sent: Monday, September 27, 2004 11:09 AM
> To: Paul Leach
> Cc: Liqiang(Larry) Zhu; Ken Raeburn; [email-masked]
> Subject: Re: Concern: Does kcrypto imply that PRF is really a PRF
> 
> On Mon, Sep 27, 2004 at 11:07:17AM -0700, Paul Leach wrote:
> > IANAC (I am not a cryptographer) but I believe that a single bit
change
> > in the input MUST result in different output for a strong PRF.
> >
> > My .5 example as worded does imply a small possibility of no change,
but
> > its intent was to say that some bits _would_ change.
> 
> A mapping function that can map any items from an infinite set onto
> items from a finite set must allow for collisions.  When we say that a
> PRF is cryptographically strong we cannot mean that there are no
> collisions.
[Paul Leach] I'm not disagreeing with that -- I'm making a different
claim: that with a _single_ bit change, there must NOT be a collision if
the PRF is strong. That's different than saying that there can't be a
collision with an N bit change -- obviously that must be possible, as
you state.

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 27 Sep 2004 13:43:45 -0500

> collision with an N bit change -- obviously that must be possible, as

This cannot be guaranteed, even for a cryptographically strong PRF since
there must be collisions.

What we can state is that for a given, randomly-chosen key and string
pair, the probability that the PRF(key, string) == PRF(key, string XOR
C) (where C is a constant) is very low, and we can even calculate what
this probability should be and we can test this through brute-force.

Cheers,

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Mon, 27 Sep 2004 15:09:35 -0400

>>>>> "Paul" == Paul Leach <[email-masked]> writes:

    Paul> [Paul Leach] I'm not disagreeing with that -- I'm making a
    Paul> different claim: that with a _single_ bit change, there must
    Paul> NOT be a collision if the PRF is strong. That's different
    Paul> than saying that there can't be a collision with an N bit
    Paul> change -- obviously that must be possible, as you state.

That's not actually quite true.  The requirement is simply that the
probability of there being no change needs to be small enough that you
get no advantage trying to distinguish between a PRF and a random
function.

--Sam