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

David McGrew writes:
>On Oct 25, 2005, at 5:25 PM, David Wagner wrote:
>> it does end up being wasteful of entropy: if I recall correctly,
>> you need 2x or 3x times as much entropy as you might naively think,
>> so in this sense it is much worse than the random oracle scheme.
>
>That's interesting; it could potentially harm the utility an  
>extractor-based KDF.  Can you point to something in the literature  
>which explains the inefficiency?

My favorite statement of the Leftover Hash Lemma is in Section 4 of
  http://www.cs.utexas.edu/users/diz/pubs/recycle.ps

Basically, the Leftover Hash Lemma says that if H is drawn at random from
a family of 2-universal hash functions with m-bit outputs, and if X is
drawn from a distribution with at least 3m bits of Renyi entropy, then
the random variable (H, H(X)) will be close to the uniform distribution:
in particular, the variation distance from uniform will be at most 1/2^m.
To put it even more roughly, if you want to derive a m-bit key with m bits
of security, then you need your source to come from a distribution with
3m bits of Renyi entropy.  (Note: The Renyi entropy is at least the min
entropy, so it suffices for X to have at least 3m bits of min entropy,
or in other words, that Pr[X=x] <= 2^{-3m} for all x.)

_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg