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

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

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.

> 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: Nicolas Williams <[email-masked]>
Date: Mon, 27 Sep 2004 13:09:12 -0500

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

I was nitpicking one of Larry's comments; I was saying that we need not
worry, in the PRF+ construction, about collisions in the PRF, provided
that the PRF is strong because such collisions would have to be rare and
unpredictable and would not affect the strength of the PRF+.

Nico
--

---

From: Ken Raeburn <[email-masked]>
Date: Mon, 27 Sep 2004 14:17:14 -0400

> unpredictable and would not affect the strength of the PRF+.

I think Larry's point was that he wanted some assurance that the 
probability would be extremely low, and he didn't think he was getting 
it from the specification...

Ken

---

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

> it from the specification...

In that case what do we gain by recalling kcrypto and adding the magic
words "cryptographically strong?"

The real question is: is the kcrypto PRF construction cryptographically
strong?

And in the context of PKINIT we might want to ask if the kcrypto PRF
construction is sufficiently strong for PKINIT's purposes, if it turns
out that the kcrypto PRF construction is not cryptographically strong.

Nico
--