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

Dan Bernstein writes:
>David Wagner writes:
>> The simplest randomized construction is to let UH(.,.) be a 2-universal
>> hash, pick R randomly, publish R, and use UH(R,S) as your key, where
>> S is the secret input.  This is a KDF with no auxiliary inputs.
>
>For example, if you have a 1024-bit Diffie-Hellman result with 512 bits
>of apparent entropy, and you want to convert it into a 256-bit key, you
>can view it as a polynomial mod 2, multiply by x^256, and reduce the
>result modulo a standard irreducible degree-256 polynomial.

I'd like to see the proof.  Can you show me how the proof goes?
I'll admit to a little bit of skepticism about its provable security.

Here's what's got me puzzled.  The Leftover Hash Lemma requires that
the 2-universal hash be chosen randomly.  You have specified a scheme
where we use a single hash function that has been fixed in advance --
but then the Leftover Hash Lemma is not applicable.  If you're not using
the Leftover Hash Lemma, then what are you using to prove this fact?
What are you assuming about Diffie-Hellman?

If you change your fixed hash function to a random 2-universal hash
function, then I'll believe your claim, albeit with a caveat that you
didn't mention.  The caveat is that your 256-bit key actually has only
128 bits of security, in the sense that the distribution on keys has
variation distance at most 1/2^128 from the uniform distribution.  Thus,
you have started out with 512 bits of entropy, and you've ended up with
only 128 bits of provable security.  That seems a little bit wasteful,
if I understand correctly.

I'd like to better understand the performance overhead of using
2-universal extractors.  We need 512 bits of apparent entropy in the
Diffie-Hellman shared secret g^{xy}.  It looks to me like this means
that we cannot use short exponent Diffie-Hellman: each party's exponents
need to be at least 512 bits long.  This sounds unfortunate, due to its
significant performance costs.  Do I have this correct?  Or is there
some trick that lets you prove this secure even with short exponents?

I'd welcome feedback about whether if my reasoning above is accurate....

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