Problem with anonymously merging information from distributed sources Some Background:

There is an entity with an identifier and some information. The identifier of this entity is a string with a known scheme/pattern(Which means the total number of such possible entities is say 10-100 million).

Information about the entities is stored in two geographically distributed systems.
A third system is responsible for aggregating information about these entities. 

And here is where the security comes into play - The third system should not know the actual identifiers of the entities and should not be able to derive the actual identifiers.

Existing proposed solution:

Both of the sites storing information about the entities decide upon a one way hashing algorithm to use, say 'PBKDF-2' and also securely communicate a long random salt that they will use while hashing. Both the sites do the one way hashing and send the hash as identifier to the third entity. The third entity can still merge the entities based on the hash but does not know the actual identifier.

Problem with the solution:

Since the set of all possible entity identifiers can be recreated(about 10-100 million), someone can execute a dictionary attack fairly easily. The salt makes it a bit more difficult but that's just some more additional overhead and does not provide a lot of comfort.

Alternatives proposed:


Use multiple hashing cycles with different salts
Use multiple hashing cycles with different salts and ciphers(scrypt, bcrypt and PBKDF-2)
Use mappings of identifiers to random strings (but that adds the overhead of always communicating the mappings between the two systems)


Please let me know if any of the three approaches listed above is acceptable. If there is some other more known/acceptable solution to scenarios like above(which I imagine must be plenty out there), I would gladly appreciate and accept them.
If you have a secret key (256-bits) shared between the two systems that see the entity identifiers, you can use HMAC-SHA256 to map entity identifiers to a random string.  Under the assumption that HMAC-SHA256 security is good (which is widely believed to be a reasonable one), this is just as secure as having generated a truly random mapping, but requires only communicating 256-bits instead of the full mapping.  If there are multiple rounds of this process of aggregation, you could use a different secret key or a different (public) nonce if it is not necessary for the aggregating system to know which entities are the same between rounds.

However, it sounds like the information associated with each entity will not be encrypted (since it needs to be processed in some fashion by the third system), and you therefore have to very carefully consider whether it may be possible to de-anonymize the entities based on their associated information.  There have been many cases of researchers de-anonymizing (http://en.wikipedia.org/wiki/De-anonymization) supposedly annoymized datasets.