In my database, I would like to encrypt every identifiable piece of information, including the username, such that people with access to the database cannot deduce the actual username (because it could potentially indicate the actual identity of the user).
And, also, users should have the ability to log in.
What would be the best strategy to achieve this?
Currently, I am hashing the username and password together (it's ok that it can never be decrypted). However, this introduces the ability to perform a rainbow table attack (or?).
My next idea would then be to discard a large chunk of the hash -- large enough so that any outcome of a rainbow table attack would become inconclusive. This would of course introduce a higher collision rate, which is undesirable.
Then again, a rainbow table attack would be able to produce a set of candidates, which would not be good.
Are there any other known strategies to this kind of problem?