Encrypt user email but be able to find user by email
I ended up with the following solution:
For each email store two values: encrypted email and signature for the email.
For encryption I used AES in CBC mode with random IV.
For signing I used HMAC SHA256.
The keys used for encryption and for signing are different.

Later on I found the following link: docs.oracle.com. So looks like this is pretty standard approach.