Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why should hard be secure enough? Information and non-invertibility

diogomonica.com

Post reply on HN
Print view View original

41–48 of 48 posts

Re: Why should hard be secure enough? Information and non-invertibility

#41

Post by klodolph »

inimino wrote: post #29
klodolph wrote: post #19

Earlier quoted context omitted.

Mathematician here. You can't have a uniform distribution on a set with infinite measure. Unbounded sets are fine as long as they have finite measure.

What is an unbounded set with finite measure?

Other answers failed to give examples of a set with positive finite measure, which is what you really need. What we want is a set that has no upper bound, but isn't really weird or tricky—if it's too tricky, then the uniform continuous distribution doesn't make any sense—and an easy way to do this is take a union of a countable set of intervals.

For example, consider a set that contains (0,1/2), (1,1+1/2), (2,2+1/4), ... etc, so interval i has measure 2^-i. It should be obvious that there is no largest element, and if you sum the measures of all the sets you will find that the measure is 1. A big chunk of "doing mathematics" is having a library of techniques on tap to come up with weird objects like this to attack assumptions.

Re: Why should hard be secure enough? Information and non-invertibility

#42

Post by klodolph »

danbruc wrote: post #33
klodolph wrote: post #25

The concepts are a bit sloppy here. "Zero information" is a bit of hand waving which relies on the idea of having a uniform distribution on a set with infinite measure, which is not mathematically sound nor is it useful as an approximation. All messages that you choose to transmit follow some probability distribution with each message having finite, nonzero probability. This is what the author gets wrong, on a very f…

I think the article mixes up two things, namely the hash function business and uninformative priors. Hash functions. In case of a good hash function the information about the actual distribution of the inputs is erased. That the hashes are uniformly distributed does not imply that the inputs are uniformly distributed which in turn renders any conclusion about the distribution of the inputs after applying a transforma…

That is not a very precise way of describing the uniformity of hash functions, and it's not actually true. For example, if my input has some element with 50% probability, then the hashed output is going to have some element with at least 50% probability.

But this is well-known, and because it's well-known, no sane cryptographic system cares that hash outputs leak information that way. For example, look at PBKDF2, HMAC, or various asymmetric key authentication schemes.

Re: Why should hard be secure enough? Information and non-invertibility

#43

Post by danbruc »

klodolph wrote: post #42
danbruc wrote: post #33

Earlier quoted context omitted.

I think the article mixes up two things, namely the hash function business and uninformative priors. Hash functions. In case of a good hash function the information about the actual distribution of the inputs is erased. That the hashes are uniformly distributed does not imply that the inputs are uniformly distributed which in turn renders any conclusion about the distribution of the inputs after applying a transforma…

That is not a very precise way of describing the uniformity of hash functions, and it's not actually true. For example, if my input has some element with 50% probability, then the hashed output is going to have some element with at least 50% probability. But this is well-known, and because it's well-known, no sane cryptographic system cares that hash outputs leak information that way. For example, look at PBKDF2, HMA…

You are right, I did not correctly word what I wanted to say. I was not thinking about repeated messages, I was only thinking about subsets of all possible messages. Say you are hashing HTML documents, then all your inputs will be in the subspace having <html as first characters but that information will be erased by the hash function.

Re: Why should hard be secure enough? Information and non-invertibility

#44

Post by kutkloon7 »

klodolph wrote: post #39
vog wrote: post #32

Earlier quoted context omitted.

As a somewhat extreme case, the rationals (Q) are unbounded but their measure is 0, hence finite.

Sorry, by "finite" I also mean non-zero. You can't have a uniform distribution on a measure zero set.

You can certainly have a uniform distribution on the set {1, 2}, which has measure zero...

It seems to me that you can define a uniform distribution for finite sets of measure zero and for sets with finite measure.

Re: Why should hard be secure enough? Information and non-invertibility

#45

Post by kutkloon7 »

kutkloon7 wrote: post #8
obastani wrote: post #7

Earlier quoted context omitted.

Nitpicking, but you can have a uniform distribution on the unit interval, which is infinite :). What you cannot have is a uniform distribution on an unbounded set. Edit: As pointed out, the correct assumption is not unboundedness, but having infinite measure (since then no normalization constant exists). I thought they were equivalent, but a simple counterexample is [0,1] \cup Z.

Well, I was criticising the article in a condescending way, on very similar grounds, so you make a fair point ;)

In my defense, I was using the context of hash functions, in which the input set of the hash is discrete. You certainly can't hash any real number.

Re: Why should hard be secure enough? Information and non-invertibility

#46

Post by klodolph »

kutkloon7 wrote: post #44
klodolph wrote: post #39

Earlier quoted context omitted.

Sorry, by "finite" I also mean non-zero. You can't have a uniform distribution on a measure zero set.

You can certainly have a uniform distribution on the set {1, 2}, which has measure zero... It seems to me that you can define a uniform distribution for finite sets of measure zero and for sets with finite measure.

Okay, again, I was being imprecise. All continuous uniform distributions have support with nonzero finite measure. The discrete uniform distribution is often thought of as a different distribution than the continuous uniform distribution.

This just goes to show how much math relies on people knowing which definitions you happen to be using at the moment you say something.

The point is that not all sets with nonzero finite measure are bounded, therefore you can have a uniform distribution whose support is equal to such a set.

Re: Why should hard be secure enough? Information and non-invertibility

#47

Post by inimino »

klodolph wrote: post #41
inimino wrote: post #29

Earlier quoted context omitted.

What is an unbounded set with finite measure?

Other answers failed to give examples of a set with positive finite measure, which is what you really need. What we want is a set that has no upper bound, but isn't really weird or tricky—if it's too tricky, then the uniform continuous distribution doesn't make any sense—and an easy way to do this is take a union of a countable set of intervals. For example, consider a set that contains (0,1/2), (1,1+1/2), (2,2+1/4),…

Thanks. That seems obvious now that you point it out. Just like Zeno's paradoxes, which are also about stretching a finite measure over a countable infinity.

Re: Why should hard be secure enough? Information and non-invertibility

#48

Post by kutkloon7 »

klodolph wrote: post #46
kutkloon7 wrote: post #44

Earlier quoted context omitted.

You can certainly have a uniform distribution on the set {1, 2}, which has measure zero... It seems to me that you can define a uniform distribution for finite sets of measure zero and for sets with finite measure.

Okay, again, I was being imprecise. All continuous uniform distributions have support with nonzero finite measure. The discrete uniform distribution is often thought of as a different distribution than the continuous uniform distribution. This just goes to show how much math relies on people knowing which definitions you happen to be using at the moment you say something. The point is that not all sets with nonzero f…

I agree. I am of course nitpicking, but it is exactly the same mistake I made in the first post (but I was assuming a discrete distribution instead of a continuous distribution).
Post reply on HN