[Cfrg] Fwd: Hash-Based Key Derivation

Jack Lloyd writes:
>On Tue, Oct 25, 2005 at 02:39:20PM -0700, David Wagner wrote:
>> there is NO known solution to this problem in the standard model.  If you
>> start with a secret value that is not known to be uniformly distributed,
>> but is only known to have high min-entropy, then the only (provably secure)
>> way I know of to get a good key out of it is to use a random oracle.
>
>I believe a perfect compressor might also do the trick here, would it not? Of
>course even if it does, that doesn't exactly ground the problem...

In theory, possibly, but there are many problems with this idea:

(1) You have to know the distribution on the secret input exactly before
you can apply perfect compression.  Different distributions will require
different compressors.  If you slightly mis-estimate the distribution,
all bets are off.  Now think about what happens if the secret input
includes any random values chosen by a human (e.g., a passphrase) to see
how hard this is.  In comparison, hashing of the secret input works even
when you don't know what the distribution is.

(2) Perfect compression assumes there is some information-theoretic
entropy in the secret input, which may not be true.  Suppose that the
secret input is a shared Diffie-Hellman g^{xy} key, where g^x and g^y
are public.  Then the perfect compression of g^{xy} is the empty string,
since it is (information-theoretically) already determined given g^x
and g^y.  Thus perfect information-theoretic compression might not
provide any useful key material at all.

(3) Perfect compression might be intractable.  Think about a shared
Diffie-Hellman key g^{xy} mod p where x,y are short exponents.  There is
a good compression, namely the value xy, but finding xy from g^{xy}
is intractably hard.

(4) No one knows how to build a perfect compressors for most
distributions, anyway, so the issue is pretty much moot.

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