Comment by godelski
You're reading the problem wrong. Yeah, even considering the birthday problem you're going to have a hard time finding a valid key.
But now we have a discovery problem. How do I find my current contacts? Do I need you rebuild my social graph from scratch? Good luck getting my friends with PhDs in computer science doing this, let alone my grandma.
Entropy is a double edged sword. IMO signal is doing a good job here. We can go drop phone numbers completely when enough people are using signal. But while the userbase is low it's probably worth the 3 spam messages I get a year. I get more than that in a week on my iPhone and more than that a month when I used Android. So I'll take the trade.
And I must stress, the phone number issue is about privacy, not security. At least with regards to signal
One can still use simpler contact information like a phone number, email or QR code to transfer a user id.
While I love what Signal has done, the compromises are significant. I use Secure Scuttlebutt, Cabal, Spritely Goblins, Tor, email and a variety of other P2P software on whatever device I like, but Signal requires a phone with Android or Apple, and requires that I lock my id to my phone number.