¿Qué implementaciones de cifrado homomorfo parcial existen y cómo las aprovecho?

9

Parece que solo El cifrado homomorfo parcial (PHE) es práctico para el uso moderno (2011). Sin embargo, tengo dificultades para localizar bibliotecas (FOSS o de otro tipo) que me permitan aprovechar esta tecnología.

El Gamal es un ejemplo de un algoritmo que hace PHE, pero la página wiki no explica claramente Qué operaciones matemáticas ciegas son compatibles y cómo implementarlas.

Posibles casos de uso

Un PHE es algo que se puede usar en forma abstracta para descargar operaciones matemáticas a un tercero sin que esa parte sepa cuál es el valor subyacente. p.ej. x + y = z se puede realizar y tendrá un resultado cifrado válido, pero los 3 valores nunca se conocen en formato no cifrado para el tercero. Esto es beneficioso para proteger los datos de análisis del mercado de valores, la PII o cualquier cosa que se considere de propiedad o confidencial.

Pregunta

Entonces, ¿qué algoritmos de cifrado existen y qué bibliotecas existen que me permiten operar con los datos cifrados? Muestras de operaciones en las que estoy interesado incluyen

  • Suma y resta
  • multiplicación o división
  • Las comparaciones (es X encriptada mayor que Y encriptada)
  • Una técnica que me permitirá comparar la versión ASCII binario / cifrada de la palabra "Ap" y hacer un Contains () o StartsWith () con la versión cifrada de "Apple"
pregunta random65537 17.05.2011 - 17:27
fuente

4 respuestas

10
El cifrado El Gamal permite la multiplicación. Esto ocurre dentro del grupo en el que corre El Gamal; por lo tanto, estás multiplicando números en un número primo dado, no en enteros "simples". Si puede multiplicar, puede dividir (la inversión en un grupo de tamaño q se realiza aumentando la potencia q-2 , por lo que es una cuestión de realizar algunas multiplicaciones) . El Gamal se implementa en libgcrypt (utilizado en GnuPG ) pero tendría que hacer las multiplicaciones usted mismo (El Gamal se usa en el formato OpenPGP, pero no por sus propiedades homomorfas).

El cifrado

Paillier permite la adición. De nuevo, la adición se produce en un grupo finito (aquí, números módulo n , un entero entero grande). No estoy al tanto de las implementaciones de este sistema en una biblioteca de criptografía genérica generalizada (mi no conocimiento no implica inexistencia, sin embargo) pero una simple búsqueda en Google encuentra algunas implementaciones basadas en Java (Java ofrece BigInteger , haciendo la implementación de tales sistemas fácil).

Un punto importante es que tales sistemas de encriptación son aleatorios: para un texto simple dado, hay muchos textos cifrados posibles. Por lo tanto, no puede saber si dos textos cifrados corresponden o no al mismo texto en claro. A fortiori , no permiten comparaciones (el orden dentro de un grupo finito no está bien definido de todos modos). Tenga en cuenta que un método de comparación no sería compatible con un cifrado asimétrico seguro: cualquiera podría cifrar los valores elegidos para adivinar los datos cifrados con una búsqueda dicotómica. En general, las palabras clave para eso son "minería de datos". Realizar minería de datos en datos encriptados es un campo ampliamente inexplorado, con una subcadena que concuerda como una especie de Santo Grial. En pocas palabras, no hay nada de inmediato aplicable allí.

    
respondido por el Thomas Pornin 17.05.2011 - 18:48
fuente
9

Un ejemplo de uso práctico de PHE (y de El Gamal en particular) es Helios Voting . Con él puede almacenar públicamente las boletas de votación encriptadas en la nube y también permitir que el público las agregue para confirmar los recuentos de votos de cada candidato y para verificar que su propio voto se haya incluido en el total, sin tener un recibo Eso podría probar cómo votaron a un tercero.

Es de código abierto. Puede obtener el código fuente (basado en Python, JavaScript, Django) aquí:

No sé qué tan fácil sería sacar trozos de Helios a una biblioteca reutilizable, pero es un lugar para buscar.

    
respondido por el nealmcb 17.05.2011 - 17:45
fuente
4

@Thomas lo clavó. Hay esquemas que admiten la suma y esquemas que admiten la multiplicación (pero no hay un esquema práctico que admita ambos). No hay ningún esquema que admita la comparación, ya que sería incompatible con la seguridad.

También hay esquemas que permiten verificar si el texto cifrado contiene una palabra clave en particular (por ejemplo, este documento ), aunque el modelo de amenaza y lo que se logra es un poco diferente. Estos esquemas están orientados a situaciones en las que usted mismo es el que cargó los datos, y recuerda las claves criptográficas, y se centran en conjuntos de datos de solo lectura (o de lectura mayoritaria). También revelan información que podría usarse para el análisis del tráfico (por ejemplo, el número de aciertos en la palabra clave y su ubicación en el archivo cifrado).

    
respondido por el D.W. 18.05.2011 - 02:45
fuente
1

Puede hacer comparaciones con un esquema preservación de la orden cuya seguridad es totalmente debatido aquí y aquí . También la sección II-A de que describe algunas debilidades de la OPE

    
respondido por el curious 22.03.2013 - 12:46
fuente

Lea otras preguntas en las etiquetas