Anonymous Gravatar Problem 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.
Encrypt the hash using the public key of the avatar server with ECC. This has a space overhead of 32 bytes (43 Base64 characters). A modern CPU should be able to decrypt about 10000 messages per second per core. If a website uses a fixed key for all the avatars both sides can cache the shared key, so they don't have to pay the cost of the key exchange all the time.

While this solves the "everybody can do an offline search to guess the email matching a hash" problem gravatar suffers from, it doesn't solve all its privacy problems. In particular the avatar service can track users, and the picture data itself allows correlation across sites, even if the hash differs.