I know what you mean. I don't know what your requirements are, but if you know the users can search by the first two (and only two) characters of a last name or by some other constant substring, you may be able to store that somewhere else in the table. Or you could store the ASCII values of the first two characters of the string as an integer, index it and then include that field in your WHERE clause. If, however, your specs state that the name has to be completely encrypted, then you're out of luck.

I've seen performance problems when doing something like this when the table gets large and just wanted you to start thinking about it up front so you're not caught off guard later.