Hash function for a small, enumerable set of elements Suppose you have a set of elements, that is relatively small (e.g. 100M) and its elements can be easily enumerated. For example phone numbers, that have a maximum fixed length and they are composed of only digits.

I would like to find a way for parties involved in an open communication to reference to elements without mentioning them in cleartext, so that only who "knows" a given element can understand that a message is referring to it.

For example, if elements would be arbitrary large files, parties may identify them by MD5 or SHA1 and communicate mentioning the hashes. Only the party that has the same file may understand that a hash actually refers to that file. This is based on the difficulty to invert the hashing function and to the fact that the set arbitrarly large files is almost infinite.

This mechanism however doesn't seem to work well when the set of the elements is small and enumerable.

QUESTION: do you envision another pattern the parties can implement to openly communicate and reference to the shared elements, without revealing their value?
To the best of my understanding, you're trying to make phone->ID an irreversible transformation. For long inputs, hashing would suffice, but there are so few possible inputs (phones) that enumeration is feasible and even a slow PBKDF won't make mapping prohibitively difficult.

Strong security is impossible in this scenario. The best you can do is slow down the data gathering process. To do that, you have to be the only one able to perform the transformation; that requires keeping a secret. It's not a salt then, but a key. The transformation can be hash(phone+key) or just encryption of the phone with the key - if the key is leaked, the security is broken either way. 

Preferably, I'd suggest that you consider alternative approaches. If it's a way to find "friends", do you have to reveal the ID right away? For instance, when one enters a phone number, you only send a friend request to that number's corresponding ID if it exists, without confirming whether it does. Only upon request confirmation do you reveal the ID. Can be combined with a friends-of-friends system to limit random requests.

Don't count on this for much. But, combined with limits on accounts and friend requests, and some monitoring for suspicious activity, it could make mapping the users take more effort than it's worth. If and only if that mapping actually isn't worth much.