Gravatar is a service that serves avatars for users based on
md5(email_address). The hash is embedded on websites, so it's public.
One of the problems with this solution is that it's easy to track users across websites, since the same e-mail will have the same hash.
I'm wondering if there's a cryptographic solution to that problem? Requirements:
A. It must not be practical to correlate users across websites by the avatar URL alone (hash/identifier for the same e-mail must be different on different sites)
B. The server, given a hash/identifier, can decode it and look user up in a large database in a better-than-linear time.
C. No clock synchronization, no challenge-response protocol (it must be possible to generate identifiers offline). Ideally it shouldn't require pre-shared keys for every website.
The only solution that comes to my mind is something like
salt + hash(email_address + salt), which would meet requirements A and C, but not B: salted hash would force the server to re-hash e-mails of all users to find the relevant one.