Editado : vea la nota importante al final, que se agregó después de que publiqué originalmente y luego volví a leer la pregunta.
Lo único que se me ocurre es construir una tabla indexada usando hashes. Sin embargo, esto indudablemente debilitará su seguridad, ya que estamos intercambiando un cifrado completo que (con suerte) no filtra ninguna información sobre el contenido de las tablas de hashes, que filtran información sobre el contenido de los datos de un usuario (sabiendo el número de términos indexados para una cuenta dada le da a un ataque un punto de apoyo para el análisis de frecuencia, entre otras cosas).
Nota: Estoy asumiendo lo siguiente: tienes un iv diferente para cada usuario.
Antes de cifrar una fila de la base de datos, puede leer las filas y convertirlas en una tabla que indexará esos elementos. A continuación, se procesarán las fichas con una sal generada desde el iv. Entonces, ahora, para un usuario determinado, "secretfoo" se guarda en el índice como c9a60f248c3a99e2b7004061d5c74e5f2240426f1f0f95eaf5843aa875e68542 .
Cuando realice una búsqueda, deberá recorrer todas las direcciones iv para generar todas las sales, luego realizar una búsqueda del token c9a60f248c3a99e2b7004061d5c74e5f2240426f1f0f95eaf5843aa875e68542 para encontrar el registro que contiene 'secretfoo'.
Esta sería una búsqueda más rápida, pero hay un intercambio de velocidad por seguridad aquí. Debido a que esencialmente se ha guardado un diccionario de hashes para una palabra dada, si la base de datos se eliminara, es posible (pero improbable) que la información indexada se pueda usar para reunir los datos originales. Como mínimo, se puede utilizar para ensamblar metadatos sobre los datos. Dicho esto, sería computacionalmente difícil.
Supongamos que tiene 100,000 usuarios con aproximadamente 100 filas por usuario para un tamaño de tabla total de 100,000,000 filas de datos.
Descifrar todos los 100,000,000 millones para realizar una búsqueda no indexada llevará montañas de tiempo.
Bajo el paradigma anterior, solo tienes que generar 100,000 hashes y buscar cada uno de esos una vez en el índice para encontrar los registros que deseas. Además, podemos hacer coincidir cadenas completas (el hash) y no tiene que realizar ninguna búsqueda de subcadenas.
Esto tiene la ventaja de computar 100,000 hashes y realizar 100,000 búsquedas en una tabla indexada BTREE que nos da buenos resultados.
Como señaló Mike Ounsworth, todavía tendrá que decidir qué es sensible y qué no lo es para poder realizar una búsqueda; sin embargo, tener todos los tokens de hash SHA256 es órdenes de magnitud mejor que texto sin formato.
EDITADO :
Después de hacer mi publicación, volví a leer tu pregunta y me di cuenta de que habías guardado el iv en la base de datos, lo que haría que el índice fuera vulnerable a la exfiltración.
La única forma de solucionarlo es almacenar el iv en una base de datos separada que no está expuesta a la web y que solo se puede acceder a través de una API. Esta es una configuración común en aplicaciones compatibles con PCI.
Al realizar una consulta, su aplicación orientada a la web tendría que solicitar al servidor seguro el iv desde el que generaría el hash y realizar la búsqueda.
Esta es una implementación más complicada, pero si el iv está en la base de datos que está orientada a la web y está exfiltrada, todo lo que tienen que hacer es recorrer los ivs para descifrar todo el índice.