Пробовал решить схожую задачу:
— данные хранятся на сервере, шифруются на клиенте, сервер даже об алгоритме шифрования не знает, хотя вообще алгоритм симметричный, ключ один и закрытый как следствие
— необходимо было реализовать автодополнение на AJAX (строки относительно короткие, ФИО в общем)
Выкрутился пока так:
— при сохранении поля клиент шифрует данные и помешает в основную таблицу
— дополнительно для каждой подстроки (первая буква, две первых буквы, три первых буквы, ..., всё ФИО) формируется хэш (с солью) и помещается в другую таблицу, связанную с основной (много хэшей для каждой записи в основной)
— при вводе новой записи пользователем клиент отправляет хэш введенных букв на сервер, тот выдаёт зашифрованные записи для которых этот хэш есть (например, все записи, которые начинаются с 'А')
— клиент расшифровывает записи, уникализирует (дубли есть даже на относительно небольшой базе, в теории полных тёзок очень много) и показывает пользователю часть из них (на начальных буквах все показать если и реально, но смысла нет)
Глобальный недостататок:
— большая нагрузка на клиента, когда надо расшифровывать порядка пары сотен записей (при базе в 3000 человек) после ввода первой буквы — на JavaScript это, мягко говоря, не быстро, генерация порядка 20-40 хэшей при сохранении на этом фоне мелочь, как и несколько лишних килобайт на запись в хэше. Что будет когда возвращаться будут тысячи записей для расшифровки — страшно подумать, надо думать над тем, как ограничивать и уникализировать записи на сервере и как из JS браузера вызывать нативные библиотеки шифрования типа mhash и mcrypt