First off, this question is not about password hashing, my requirements are different. In particular I fully agree that salts are not useful for adding cryptographical complexity in password hashes, since the salt is almost always known to the attacker. In my situation, the salt is unknown.
I have a table with records, one column of which contains a username, covering two different dates. There may be multiple records with the same username. I want to share this table with someone else, however this person is not allowed to know which username goes with which record, however he should be able to link records for the same username on the same date.
My suggested solution to this is to generate a (CSPRNG) 1024-bit random salt for each date. I then hash the usernames, using the salt for their respective dates, and replace the username with this. I will send the tables, however not the salts.
My claim is that it is computationally infeasible (on current non-quatum-computing hardware) for the recipient of this data to:
- provided he has a username, find out which data belong to this username
- find out (just on the username column) which records belong to the same user, unless the records are on the same date
- even if he knows the true and hashed usernames of 99.9% of the records, to determine the usernames from the hashed values of the remaining 0.1%
To be complete: I do realise that there is always a chance that two different usernames map to the same hash, thereby losing the property that the recipient should be able to distinguish which records had the same usernames in the original table, however these chances are so astronomically small that I'm willing to accept them.
My question: Is my claim correct? Is there any documentation I can point to that supports this (without someone needing a PhD in mathematics --- I would like to be able to "prove" this to the legal department)? I guess I'm looking for the same kind of guarantees that (a)symmetrically encrypting the value with an key that is later deleted, gives, even though I feel that hashing with a 1024-bit salt is stronger than encryption with a 1024-bit key.
Note that it's (for organisational reasons) not feasible for me to just map every username to a random value, and store this value in memory so that if I see the same username/date again, I will use the same value.