Could we share a secret key using the Birthday problem?
You are right that if it costs Alice &amp; Bob effort $N$ to agree on a key in this way, then it costs Eve only effort $N^2$ to find it. So the protocol is not secure in the standard sense, and probably not very useful. (Maybe in some highly constrained situation with very short-lived keys?)

More generally, this purports to be a key agreement protocol whose only ingredient is a hash function / one-way function used in a black-box way. It is known that such a thing is impossible:


  R Impagliazzo, S Rudich, Limits on the Provable Consequences of One-Way Permutations, CRYPTO 1988.