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

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

> -----Original Message-----
> From: Nicolas Williams [mailto:[email-masked]]
> Sent: Monday, September 27, 2004 9:57 AM
> To: Liqiang(Larry) Zhu
> Cc: Ken Raeburn; Paul Leach; [email-masked]
> Subject: Re: Concern: Does kcrypto imply that PRF is really a PRF

> If the PRF is strong then we don't care if PRF(key, 0x00|input-string)
> == PRF(key, 0x01|input-string) for some value of key and input-string.
[Paul Leach] If you change a single bit of the input, and each output
bits doesn't change with probability .5, that's practically the
definition of _not_ strong.

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 27 Sep 2004 12:22:20 -0500

> bits doesn't change with probability .5, that's practically the
                                       ^^
That still leaves a very small probability that for _some_
key/input-string the two PRFs in the PRF+ given above will have the same
output.

> definition of _not_ strong.

The key word was "some."  Just because you have some such collisions
does not mean that the PRF is not strong -- such collision have to be
extremely unlikely, but cannot be impossible.

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Mon, 27 Sep 2004 14:47:56 -0400

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

    >> -----Original Message----- From: Nicolas Williams
    >> [mailto:[email-masked]] Sent: Monday, September 27,
    >> 2004 9:57 AM To: Liqiang(Larry) Zhu Cc: Ken Raeburn; Paul
    >> Leach; [email-masked] Subject: Re: Concern: Does kcrypto
    >> imply that PRF is really a PRF

    >> If the PRF is strong then we don't care if PRF(key,
    >> 0x00|input-string) == PRF(key, 0x01|input-string) for some
    >> value of key and input-string.
    Paul> [Paul Leach] If you change a single bit of the input, and
    Paul> each output bits doesn't change with probability .5, that's
    Paul> practically the definition of _not_ strong.

Not really.  The definition of strong includes a lot more than that.
But if the output bits don't flip with approximately probability 0.5
you can show it is not strong fairly trivially.

--Sam