Criptosistema Benalo

El criptosistema Benalo es una modificación del criptosistema Goldwasser-Micali . Su principal diferencia es que el criptosistema le permite encriptar un bloque de datos a la vez, mientras que en el esquema de Goldwasser y Micali, cada bit de datos se encripta por separado [1] .

Diseñado por Josh Benalo en 1988. Ha sido utilizado en sistemas de votación electrónica [2] .

El sistema es parcialmente homomórfico . Como ocurre con muchos criptosistemas de clave pública, este sistema opera en el grupo , donde  es el producto de dos números primos .

Descripción del algoritmo

Generación de claves

  1. Se eligen un bloque de tamaño y dos números primos grandes y diferentes , satisfaciendo las siguientes condiciones:
    1. y  son coprimos;
    2. y  son coprimos.
  2. Calcula , ;
  3. se elige para que . Nota: si es compuesto, las condiciones anteriores no son suficientes para garantizar el descifrado correcto [3] , es decir, para garantizar que . Para evitar esto, se propone realizar la siguiente comprobación: let . Luego se elige de tal manera que para cada .
  4. Dejar ;

Entonces la clave pública es , y la clave secreta  es .

Cifrado

Cifrado de mensajes :

  1. Se elige arbitrario ;
  2. entonces _

Descifrado

Primero, tenga en cuenta que para cualquier y , se cumple lo siguiente:

Así, para calcular , conociendo , se realiza la operación del logaritmo discreto de con respecto a la base . Si el número es pequeño, es posible encontrarlo mediante una búsqueda exhaustiva, es decir, comprobando la igualdad para todos . Para valores grandes de , el hallazgo se puede realizar mediante el algoritmo de Gelfond-Shanks (algoritmo de pasos grandes y pequeños) , obteniendo la complejidad temporal del descifrado .

Descifrado de texto cifrado :

  1. calculado ;
  2. Se selecciona , es decir, tal que

Propiedades del criptosistema

Homomorfismo

El criptosistema Benalo es homomórfico con respecto a la operación de suma:

, ¿dónde está la función de cifrado del mensaje?

Resistencia

La fuerza del criptosistema Benalo se basa en el problema intratable de los residuos de alto grado. Conociendo el tamaño del bloque , el módulo y el texto cifrado , donde se desconoce la factorización del número , es computacionalmente difícil determinar el texto sin formato .

Literatura

  1. A. I. Trubey "Cifrado homomórfico: seguridad informática en la nube y otras aplicaciones (revisión)"
  2. Benaloh, Josh (1994) "Cifrado probabilístico denso"

Notas

  1. Benaloh, Josh (1994) "Cifrado probabilístico denso"
  2. Cifrado homomórfico: seguridad informática en la nube y otras aplicaciones (revisión) (A.I.Trubey)
  3. Fousse, Laurent; Lafourcade, Pascual; Alnuaimi, Mohamed (2011). "Revisión del cifrado probabilístico denso de Benaloh"