So first warning first:
If data is secure, it cannot be searched against, only checked
Now regarding searching: There is no good way to search encrypted or hashed fields, it will ALWAYS eat up CPU. There is a reason for this: Your data is in a one way street. It gets retrieved into memory, checked against, the in memory version destroyed, and the entry minus the data you can't send gets sent. This is for security purposes as well as attack proofing purposes. So then it begs the question "How do I search against it?" Literally an entry at a time. Because each hash or encryption should be unique and never repeatable unless checked against with the initial value, you have to retrieve every encrypted object, go through them until you get a match, and then return the id or pkey of that entry. Is this long, drawn out, annoying, and secure? Yes. Can this be done faster or better? Not really.
NEVER STORE A RAINBOW TABLE! Those are easily cracked vulnerabilities(Don't believe me?)
NEVER STORE SALTS IN THE DATABASE! If the data as a whole gets stolen, this encryption is now worthless
If the data needs to be *truly secure**, hash it through a one way hashing algorithm(like bcrypt)
IF you MUST search against encrypted data, use a separate decryption program to decrypt the data, do the search, and send it back again in a compiled, standalone binary app. This way if the public facing server has an unwelcome visitor, they can't get that data at all, the key is still secure, and your data is safe.