[Cryptography] Secret "rendezvous" based on telephone numbers

[Tobias Markus]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi,

Consider the following protocol:
Alice wants to send Bob a message. She wants to use asymmetric cryptography. Because Bob is not always online, she sends it to Charlie to have him relay the message to Bob later on. Alice only knows Bob's mobile number, but she does not want to reveal it to Charlie because Mallory often gets unauthorized access to Charlie's server (and it would be best if Charlie does not know the number in the first place because it's not his business). Mallory can do active attacks on all communication between Alice, Bob and Charlie (read, edit, replay, reorder, drop, etc.). Alice also has to retrieve Bob's public key from the server. (Let's leave key verification out of the game atm.)

Possible (Not Working) Solutions:
1) Hash: Does not work because of the small preimage space.
2) Hash + Salt: Alice can not easily tell Bob an unique salt.

Suggestions?

Some more background info:
Moxie Marlinspike (author of TextSecure and RedPhone) evaluated Bloom filters as a possible option to private contact discovery in the Open Whisper Systems Blog (see https://whispersystems.org/blog/contact-discovery/). He identified it as unsuitable to TextSecure because of the too large size of such Bloom filters for the TextSecure user base. 
Currently, TextSecure solves this by sending the entire address book to the server, doing the classical comparison and then having the server delete the address data again, therefore revealing contact metadata. (User X contacts User Y over TextSecure.)
Furthermore, TextSecure directly sends messages to the server using the PSTN as the identifier, which means that even if TextSecure used Bloom filters, this would reveal the metadata anyway (see https://github.com/WhisperSystems/TextSecure-Server/wiki/API-Protocol#submitting-a-message). So, the question is how to enable anonymous "rendezvous" over a potentially malicious server (in general, not only for TextSecure).
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iEYEARECAAYFAlOhllUACgkQAO6N0EYmC9ZhtgCdEulJeD2J8GEUqcH/30sblg49
tmoAniRbxicrBrX5aKhKV30SP4lCH0ud
=TLhx
-----END PGP SIGNATURE-----