Probably the best you can do is compute a privacy-preserving message authentication code (such as HMAC) of each value, using a randomly generated secret key (with, preferably, 256 bits of entropy or more).
As long as you keep the secret key secret, HMAC will be effectively indistinguishable from a random mapping from the input strings to the output hash values. Thus, the only thing an attacker can really learn just by looking at your database is whether any two values are identical (which you scheme reveals by design, anyway).
Note, however, that the security of this scheme rests on two assumptions:
- that the secret key (and/or the database itself) stays secret, and
- that an attacker cannot use your application as an oracle, by feeding it guessed input values and seeing whether it finds a matching entry or not.
If these assumptions are not met, this system is no more secure than just plain old cryptographic hashing — which is to say, it's vulnerable to brute force attacks if your inputs are potentially guessable, but may remain secure if the inputs are e.g. sufficiently long random strings.
Implementing secure key management is far from a trivial challenge, and not really within the scope of this answer. However, one important aspect of it is isolating, as far as possible, the systems that have access to the key from any systems that an attacker might compromise.
For example, if possible, you could store the key inside a hardware security module that only provides an interface for taking in byte strings and returning their MAC. You should also consider setting up some kind of rate limiting within the security module (or whatever system you decide to implement the MAC computation with), so that even if other parts of your system are compromised, the module is of minimal utility as an oracle.
It's also be possible to make you scheme somewhat more resistant to brute force guessing attacks, even if the secret key is compromised, by replacing (or combining) the MAC with a deliberately slow key derivation function like those recommended for password hashing (PBKDF2, scrypt, Argon2, Catena, Balloon hashing, etc.).
However, such key stretching methods are fundamentally limited by the fact that they also slow down legitimate MAC computations. Thus, for example, if your legitimate system needs to be able to process, say, 100 inputs per second, then an attacker will also likely be able to test at least 100 guesses per second (and probably more, since they may have access to more efficient special purpose hashing hardware and algorithms).
Thus, while key stretching is definitely something you should do, if at all possible, it's not very effective by itself unless your inputs already are fairly hard to guess. Thus, to maximize security, you really should combine key stretching with a secret MAC key.
(There are various ways to do that, but e.g. simply first running then inputs through a slow password hashing function, and then through HMAC with a secret key, should be perfectly fine, and would allow you to offload the final HMAC calculation to a separate security module.)
Also note that, unlike the cipher-based solutions suggested by Yehuda Lindell, the MAC-based solution I suggested above is not guaranteed to generate distinct outputs for distinct inputs. However, as long as the length of the final MAC output is sufficient — say, 256 bits or more — the odds of an actual collision ever occurring are astronomically small.
Also, unlike AES-SIV or other deterministic cipher modes, a MAC cannot be decrypted to directly recover the original input, not even if the secret key used to compute it is known. In your case, I would consider that a feature.
