Bem, você não pode pesquisar em texto descriptografado sem decodificá-lo primeiro, isso é verdade.

No entanto, isso não significa que não há maneiras de contornar isso. Por exemplo, você pode criar um índice invertido de seus dados e hash (sha1, md5, crc32, escolha um) as chaves usadas para pesquisar. Tudo o que você precisa fazer é fazer um hash dos termos de pesquisa que está usando, procurá-los no índice e recuperar qualquer registro que corresponda, que será apenas uma pequena parte da tabela em vez de toda a coisa.

Ao fazer o hash dos dados (use um salt!), você evita armazenar os dados de maneira insegura, enquanto ainda pode pesquisar os dados porque fez um índice para eles. Nenhuma descriptografia é necessária até que você tenha certeza de quais documentos correspondem.