Re: [Cfrg] Fwd: Hash-Based Key Derivation

On Tue, Oct 25, 2005 at 03:27:27PM -0700, David Wagner wrote:
> 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:

Your points 1/3/4 were implicit with my statement that it "doesn't exactly
ground the problem"; I'm well aware that creating a perfect compressor is
either nontrivial or impossible for any interesting input distribution. I
suppose a bit more formally, my speculation was that if one had an algorithm
that could create a perfect compressor for any input distribution, you could
create a secure KDF with it (assuming you could correctly characterize your
input distributions, itself a highly nontrivial problem).

[...]
> (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.

Nicely put! I had not considered this at all, and you make a good argument here
for why a perfect compressor wouldn't suffice in this context.

Jack

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