KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]

[David Wagner <[e-mail]>]

Simon Blake-Wilson writes:
>min-entropy is an information-theoretic, as opposed to complexity
>theoritic, concept, isn't it?

(These are not stupid questions, by the way.)

True.  Actually, I believe that the 2-universal extractor also works
in the case where the input distribution is computationally indistinguishable
from a source with high min-entropy.

Warning: We're at the edge of my knowledge.  My understanding of the
subject of extractors is pretty sketchy.  I know there are others on
this list who know more; maybe they will chime in.

>I think it would be a great contribution to spell out a good definition.
>One comment though: I think a more palatable definition would be to take
>an unpredictable input and produce an indistinguishable output, in the
>face of an oracle that gives access to various other bits of the output.

Ok.  Let me give it a try:

Let D be a source distribution with min-entropy >= m.
Let S be a sampling algorithm: a randomized algorithm so that
the output of S() is computationally indistinguishable from D,
and so that S() is efficient.

Let H be a random oracle.
(Note: S is not permitted to invoke H, so S is independent of H.)

Let F be a KDF algorithm.  Namely, F is an algorithm that uses an
oracle (H) and accepts two inputs (K,X) and produces an output (Y).
Let R be a random function mapping X to Y.

Say that F is a (t,q,e)-secure KDF for S if for all adversaries A
running in time at most t and making at most q queries, Adv A <= e, where
  Adv A = |Pr[K <- S(); A^{F(K,.),H}=1] - Pr[A^{R(.),H}=1]|
where q counts the number of queries to A's first oracle.

Also we have the notion of a scheme F that is a (t,q,e)-secure KDF
for some class of distributions (e.g., for all distributions with
min-entropy >= m).

The chosen-input queries correspond to cases where the attacker
controls the auxiliary inputs X and somehow manages to learn the
session key (e.g., it leaks; it is cryptanalyzed; an endpoint is
hacked).

The above is probably pretty rough, and maybe there is a better
formalization; any thoughts?

_______________________________________________
Cfrg mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/cfrg