Signal has spoken [1] at length about the issues of private contact discovery, and the many [2] solutions they've employed to minimize the amount of information that gets leaked. There's this intractable problem of requiring a social graph for easy discovery and for trust, and Signal's found one of the better solutions (though I'm sure we'll discover better ones yet).
[1] https://signal.org/blog/private-contact-discovery/ [2] https://signal.org/blog/contact-discovery/