¿Cuál es actualmente el mejor algoritmo de cifrado de búsqueda (SE) que funciona en la práctica?

Estuve en esta charla a principios de este año y me impresionó el enfoque. El producto se llama EncryptedQuery que intenta resolver el problema (supongo que está relacionado) de Recuperación de información privada . PIR es probablemente un requisito más estricto que SE ya que con PIR, incluso el servidor de base de datos no puede saber qué buscó o qué registro se devolvió.

Mis notas sobre la charla:

• Motivación: casos en los que desea mantener en privado sus patrones de acceso a los datos.
• PIR está interrelacionado con los problemas de la Transferencia Obligatoria y la Computación Multipartita Segura.
• En 2016, la NSA tiene un código abierto de software PIR llamado PIRK
• En 2017 se retiró el proyecto PIRK. La empresa Envieta tomó el proyecto y le cambió el nombre a EncryptedQuery
• Utiliza el cifrado de Paillier, que es homomórfico en el sentido de que la adición en el espacio de texto simple se convierte en multiplicación en el espacio de texto cifrado.

Mi comprensión del algoritmo (probablemente incorrecto, aunque esto tenía sentido en ese momento) es que el solicitante encripta una cadena

encr_req = encr(0 0 0 0 0 1 0 0 0 0 ...}

donde, por ejemplo, la columna k th que contiene el 1 es el número de fila que desea recuperar. Una vez que esta cadena está encriptada, el servidor no sabe qué columna contiene el 1.

Luego el servidor itera sobre la base de datos haciendo

sum_i( encr_req[i] * encr(data[i]) )

Debido a que Paillier es homomórfico y todos menos uno de los valores de texto simple es 0, esto es equivalente a

0*data[0] + 0*data[1] + ... + 1*data[k] + 0*data[k+1] + ...

Entonces, cuando descifres, obtendrás el resultado.

decr( sum_i( encr_req[i] * encr(data[i]) ) ) = data[k]

Pros:

• El servidor puede manejar la recuperación de elementos de la base de datos por ID sin saber qué ID se solicitó.
• El ancho de banda de la respuesta es bajo: sum_i( encr_req[i] * encr(data[i]) ) es el ancho de un solo campo de base de datos.
• Se puede extender para solicitar varios elementos en la misma consulta.

Contras:

• Rendimiento: para cada solicitud, el servidor debe recorrer toda la base de datos, cifrando cada entrada con la clave pública del solicitante.
• Todas las filas de la base de datos deben tener el mismo ancho de bits (que desea mantener pequeño por razones de rendimiento en el paso de cifrado).
• El número de entradas en la base de datos y su orden deben ser fijos y conocidos por el solicitante.
• Para bases de datos grandes o menos estructuradas, use un cifrado de búsqueda más general (pero menos seguro).

TL; DR No estoy seguro de que esto responda realmente a la pregunta de HelloWorld sobre cuál es el mejor cifrado de búsqueda: /

Es escaso porque el cifrado de búsqueda rara vez es práctico.

En general, significa que estás usando un código muy débil o que descifras todo a medida que avanzas. El primer caso es malo porque puede usar los patrones en el cifrado para romperlo con una muestra lo suficientemente grande. El segundo método, más recomendable, es extremadamente lento porque tiene que descifrar todo el conjunto de datos para ejecutar una sola consulta. De cualquier manera, Searchable Encryption solo es realmente práctico con conjuntos de datos muy pequeños.

Un ejemplo de dónde lo usaría sería si desea buscar palabras clave en un solo registro de empleado. La identificación del empleado no estaría encriptada; por lo tanto, podría usar eso para solo consultar los registros de esa persona, luego podría pasar todo el conjunto de registros a su aplicación para descifrar. Luego busque los datos desencriptados y solo genere los campos que necesita a partir de eso.

Dicho esto, existe una gran cantidad de promesas con el cifrado clasificable siempre que se realicen búsquedas exactas. El cifrado clasificable establece el alcance de cada nueva cadena cifrada entre las que debe clasificar; Entonces, digamos que lo siguiente es cierto:

7iFA384S4BPmuXokR9rcMI37SKnClqnE = ant
E10ZJbnmvJHs3MOKkzDXw7sd037kLCUJ = cat
miHBVXxATe1Jg6G97ug86zv31BxrpRAa = dog
z0L9f8Py12euq9Nhy9Zk0e9L83F8MiBi = man

Si quisiera agregar "fox" a la lista, entonces mi algoritmo de encriptación regresará entre "miHBVXxATe1Jg6G97ug86zv31BxrpRAa" y "z0L9f8Py12euq9Nhy9Zk0e9L83F8MiBi" que resultó en algo como:

7iFA384S4BPmuXokR9rcMI37SKnClqnE = ant
E10ZJbnmvJHs3MOKkzDXw7sd037kLCUJ = cat
miHBVXxATe1Jg6G97ug86zv31BxrpRAa = dog
Pe2624gcRjP6YGWOnhiW2xnRomAjDYQK = fox // sorts alphabetically between dog and man
z0L9f8Py12euq9Nhy9Zk0e9L83F8MiBi = man

Esto funciona porque la primera parte de la cadena cifrada es solo ordenar la información, y la segunda parte es la información cifrada real

SortingId(Pe2624gcRjP6YG), EncyptedData(WOnhiW2xnRomAjDYQK)

Una vez que haya ordenado el cifrado, esto significa dos cosas, una es que puede ordenar los datos cifrados tan fácilmente como los datos no cifrados, lo cual es bastante sorprendente en sí mismo, pero en segundo lugar, significa que puede usar un método similar para combinar la clasificación de forma selectiva descifrar Personalmente, no sé qué bases de datos realmente admiten / no soportan esto todavía, pero en la lista anterior, si busco "hombre" y descifro "perro", sé que los dos elementos principales no son hombre, así que No tienes que descifrarlos para buscarlos. Esto significa que cuanto mayor sea su conjunto de datos, menor será el porcentaje de su conjunto de datos que necesita descifrar para encontrar cosas.