So, it looks to me like this is a homework problem, although it could be job assignment; I'll try to answer in a way that meets both. First, some general thoughts on databases and stored data encryption. FWIW, I used to work for a large database vendor and advised the developer who built their column and table encryption feature.
The challenge with encrypting stored data in a database is the diametrically opposed goals. With plain old stored data, you often want it indexed (for fast searches) be it for Primary Keys (data in column must be unique) or Foreign Keys (joins). With encrypted data, you don't care so much about the properties of the plain text data, however, you do care that crypt text doesn't accidentally reveal any information about the plaintext. Here, too, the crypt text can be unique, although the uniqueness property is actually working against you. More importantly, matches of crypt text (whether that crypt text is reversible encryption or irreversible hashes) is a non-requirement, that is, you don't want it to match ever.
See the diametrical opposition? Searchable vs. No Information Leakage. Searchable means there's an Index out there which means it's Sorted which means you have Information about the properties of the data. Sorting crypt text is useless, so you really want the Index to Sort on plaintext, but that then leaks Information! So, basically, what we are saying is, you're really quite up a creek with this one. In your example, you want the email address to be both unique (as in Primary Key, searchable in the database) and yet provide no information in the case of theft (encrypted in a secure manner).
All that said, we still want to solve the problem of stored data encryption, so what should we do?
There are two solutions: (1) native database encryption or (2) application level encryption.
In Native Database Encryption, the database itself runs the crypto, stores the data on disk as encrypted, maintains various keys in a wallet & IVs with the data, and provides access control for who can and cannot retrieve the data. It also encrypts indices when the data column is a Primary Key or the column has an Index on it. In some ways, this is nothing more than a glorified access control scheme. However, it meets the requirement that the data be stored (at rest) in an encrypted form. Of course, this means the crypto feature is built into the proprietary database or someone coded it into an Open Source database.
In Application Level Encryption, an app developer encrypts the data and then stores that in the database. I think Mike did an excellent job outlining some of the choices with this model. I'd reiterate that the biggest challenge here is how to handle encrypting data you also wish to be a Primary Key (unique to a column). Since the proper (i.e. secure) method of encrypting data is to generate a unique IV per plaintext, you'll have to scan and decrypt every crypt text email address before determining you have a unique email. That's not a very good situation from an operational perspective (very bad runtime behavior).
- Try to use an alternate unique identifier. Email addresses are bad for this, although they are seductive and everyone loves them. They're great for password reset, so leave them as part of the user profile, but instead assign the user a unique numeric ID. These are difficult to guess for an attacker. Often, the most public thing known about a person is their email. Using it as a username makes attacks on an account that much easier.
- If email address must be the unique user ID and if encrypted email address is a check the box requirement, use a database that provides native column/table encryption as you can legitimately check the I-encrypted-it box. Oracle (the company I used to work for) has a database that does this. There might be others.
- If email address must be the UID and you cannot specify a database that has native crypto (or this is a homework assignment), you'll have to resort to application level cryptography. I have a suggestion to solve the Primary Key problem.
Application Level Stored Data Encryption
Assumption: Some data which must be encrypted must also be unique in database column. Let's call that data "email address".
You're best bet is to properly encrypt the email address by adding a unique IV to each plaintext. This means you cannot make email address column an Index or a Primary Key. First, if you store the IV in a separate column from the crypt text, there's a very small chance that the crypt text will collide (be equal) even if the plaintext is not. It's very small, but I believe one should always code for correctness, so no Primary Key. Next, Index on crypt text is useless, anyway. If the IV is different per row, you cannot do any meaningful search or join on the column, so application level encrypted data columns should never be Indexed.
Depending upon the row count in your table (number of unique users/email addresses), doing anything with that data is going to be horrific. Every time you touch it, you'll have to decrypt on average 50% or possibly 100% of the data depending upon what you're doing. If the database has advanced features (like virtual tables, stored procedures that can build them and internal cryptographic APIs), you might be able to have the database do the heavy lifting for you. This, to be honest, is your best bet. Oracle has the DBMS_CRYPTO PL/SQL package (I wrote it), so, yes, again Oracle can help you solve this problem. No, I no longer work for the company, nor do I own any of its stock. Sorry, I don't mean this to be a sales pitch for Oracle.
Let's say you don't have access to these advanced database features, what to do next? All this comes down to the need to expose useful some information about the email address without allowing an attack on the user data. Here, your decision swings on how large your user population is.
If it's small, just encrypt everything with IVs and decrypt it all to match. The speed of operation won't be that expensive and the extra development work won't be worth it. If this is a homework assignment, that's your best bet.
If the user population is large enough that full table decrypt will be noticeable, then still encrypt everything with a unique IV, however, provide a second, indexed column in which you hash the email. Now, this hash is not your normal cryptographic hash. In fact, you don't want anything of the kind. You want a hash algorithm that has a fair amount of (but not too many) collisions. Collisions are your friend.
Here's a possible algorithm:
E = Email Address
Choose N s.t. 2^(N+3) <= NUM_USERS < 2^(N+4), N>=0)
H(E) = (Sum each ASCII value of E)%(2^N)
Assuming a uniform distribution of email addresses, H(E) will produce 12 or so collisions for a large dataset on average. If you store H(E) in a second column and index it, you can quickly locate candidate email addresses that may match the plaintext email address while ignoring most of the other email addresses. You'll need to redo all of the hashes every once in a while when the population of users jumps above a level. You should also redo them when it drops below a level. You should add hysteresis to this process so you don't flail around redoing the hash column if a user adds/deletes often.
There is Information Leakage with this design, you can guess email addresses and see if they match the Hash column. Other unencrypted data (like a State or Age field) might allow an attacker to triangulate on who the user really is. It's not perfect. However, if you've got 10^6 users, you're going to have to solve the problem some how which means leaking some information.
Also, this won't allow you to sort by email address (no alphabetic sort). It acts more like a true Hash Table from a Data Structures class.