How to search a MySQL database with encrypted fields Suppose I need to encrypt certain table-fields of a MySQL database. Additionally, I need to search some of those fields I did encrypt.

How would one search those fields anyway?

Decrypting each record step by step is no option: Suppose I have multiple of thousands of records. It would take too much time and space to decrypt each record and check if each single record matches the search.

UPDATE 2012-09-07

Adding further details to the database schema would be OK, since I'm about to implement a new application. Furthermore, I need to extend applications currently running in production. But even for those application, adding further details would be OK.

UPDATE 2012-09-08

Encryption is the kernel of this question. 

Access restrictions, as proposed by some answers, already apply - but do not fit the formal requirement to encrypt data.

This formal requirement is not Payment Card Industry Data Security Standard [PCI].
Obviously they are not meant to be viewed, therefore searching on them would be problematic.

One trick I have used in the past is to hash the encrypted data before encrypting it, and storing the hash in an indexed column.  Of course, this only works if you are searching on the whole value; partial values will not have the same hash.

You could probably extend this by making a "full text" index of hashes, if you needed to, but it could get complicated really fast.

ADDENDUM

It's been suggested that I add a footnote to my answer per a fairly lengthy debate in chat about vulnerability to dictionary attacks, so I will discuss this potential security risk to the above approach.

Dictionary Attack:  A dictionary attack is when someone pre-hashes a list of known values, and compares the hashes to your hashed column in the database.  If they can find a match, it's likely that the known value is actually what is being hashed (It's not definite though, because hashes are not guaranteed to be unique).  This is usually mitigated by hashing the value with a random "salt" appended or prepended so the hash will not match the dictionary, but the above answer cannot use a salt because you lose the searchability.

This attack is dangerous when dealing with things like passwords: if you create a dictionary of popular password hashes, you can then quickly search the table for that hash value and identify a user that has such a password and effectively extract credentials to steal that user's identity.

It is less dangerous for items with a high degree of cardinality, like SSN's, credit card numbers, GUIDs, etc. (but there are different risks [read: legal]  associated with storing these, so I am not inclined to advise on storing them).

The reason for this is in order for a dictionary attack to work, you need to have pre-built a dictionary of possible values and their hashes.  You could, in theory, build a dictionary of all possible SSNs (a billion rows, assuming all formatting permutations are removed; multiple dozens of trillions of entries for credit cards)... but that's not usually the point of a dictionary attack, and basically becomes comparable to a brute-force attack where you are systematically investigating every value.  

You could also look for a specific SSN or credit card number, if you're trying to match a SSN to a person.  Again, usually not the point of a dictionary attack, but possible to do, so if this is a risk you need to avoid, my answer is not a good solution for you.

So there you have it.  As with all encrypted data, it's usually encrypted for a reason, so be aware of your data and what you are trying to protect it from.