Homomorphic encryption is about doing computation on encrypted data, but you don't need it just to search. All you need is some way to get the server to send you the encrypted blocks which contain the messages you want (and which you can decrypt); you don't need the server doing computation on the encrypted data itself.

A simple solution: divide the data into N blocks. Create an index that maps words to blocks (e.g. word "hello" is on blocks 36, 43, 84). Then encrypt the blocks and the index and upload them to the server. When you want to search, you just download the index, decrypt it, then use it to identify the blocks you need to download from the server.

The first paper I linked has some more advanced techniques of the same sort.