The actual content is encrypted, but one can still build an index that points to individual email IDs and score the search results properly. Only when returning the top N results that one needs to decrypt those N emails with the right keys. The index would be kept in the server. Of course, the devil is in the details and things like email threading, order by by date or group by senders will make or break the user experience.