Поиск по зашифрованной информации. Как реализовать?
Разбейте задачу на подзадачи.

Есть данные. Есть ключи шифрования этих данных. Ключи только у клиента. Вычленить фрагмент текста из зашифрованного блока невозможно по определению.

Вам нужно, чтобы пользователь мог с использованием индекса найти ссылку на нужное место в выбранной структуре хранения.
Так как индекс должен быть зашифрован, то доступ к нему может быть только у клиента. Т.е. задача обновления индекса падает на пользовательскую часть софта.

Ну вот Вам и ответ — индекс является отдельным зашифрованным документом пользователя. Каждый раз, как он вносит новые данные или меняет существующие он должен внести изменения в индекс.
Плюс — модуль для полного сканирования имеющихся документов для первого раза или для восстановления поврежденного индекса. Опять-же — работает только и исключительно на стороне клиента, ибо ключи только у него.
Ну пусть клиент вместе с шифрованными данными сам создает и передает незашифрованный массив из слов для построения индекса для этого документа. Все конфиденциальные данные отбрасываются (ну номера, пароли, легко регэкспом), остаются только обессмысленный набор простых слов, отсортированных по алфавиту.
Хэшировать каждое слово бессмысленно, ибо это не повышает безопасность: легко взять хэши у большого произвольного набора слов и сравнить с записями в существующем индексе.