Persistencia semántica

Un criptosistema semánticamente seguro en criptografía es un criptosistema que no permite ninguna fuga de información significativa sobre el texto sin formato original del texto cifrado . Tomemos cualquier algoritmo probabilístico de clase PP , cuya entrada en el primer caso es el texto cifrado de algún mensaje aleatorio y la longitud de este mensaje, y en el segundo caso solo la longitud del mensaje. Si la diferencia entre las probabilidades de obtener alguna información confiable sobre el mensaje original en el primer y segundo caso es insignificante, entonces el criptosistema que produjo este cifrado se considera semánticamente seguro. [1] En términos de complejidad computacional , este concepto es análogo al cifrado de Shannon absolutamente seguro . Un cifrado perfectamente seguro implica que no se puede obtener ninguna información sobre el mensaje original, mientras que la seguridad semántica significa que ninguna información sobre el mensaje original que se encuentra en el texto cifrado se puede utilizar para descifrar ningún fragmento del mensaje. [2] [3] :378–381

Historia

El concepto de fuerza semántica fue introducido en la criptografía por Goldwasser y Micali en 1982. [1] Sin embargo, la definición que propusieron originalmente no proporcionó una estimación de la fuerza de los criptosistemas reales. Más tarde, Goldwasser y Micali demostraron que la seguridad semántica es equivalente a la indistinguibilidad del texto cifrado para los ataques de texto sin formato coincidente . [4] Esta definición de fuerza semántica es más común, ya que ayuda a evaluar la fuerza de los criptosistemas utilizados.

Criptografía simétrica

En el caso de los criptosistemas simétricos , el adversario no debería poder obtener ninguna información sobre el texto sin formato del texto cifrado. Esto significa que el adversario, al tener dos textos sin formato y dos textos cifrados correspondientes, no puede determinar exactamente qué texto cifrado corresponde a qué texto sin formato.

Criptografía de clave pública

Se dice que un criptosistema de clave pública es semánticamente seguro si un adversario, en posesión del texto cifrado y la clave pública, no puede obtener ninguna información significativa sobre el texto sin formato original. La seguridad semántica solo considera casos de criptoataques pasivos, por ejemplo, cuando un criptoanalista solo puede observar los textos cifrados transmitidos y generar sus propios textos cifrados utilizando la clave pública. A diferencia de otras nociones de seguridad, la seguridad semántica no considera los ataques de texto cifrado elegidos , donde el criptoanalista puede descifrar algunos textos cifrados elegidos, y muchos esquemas de cifrado semánticamente fuertes resultan ser débiles contra este tipo de ataques. Por lo tanto, la fuerza semántica no puede considerarse una condición suficiente para la fuerza de un esquema de cifrado de propósito general.

La indistinguibilidad del texto cifrado para los ataques basados ​​en el texto simple elegido generalmente se determina mediante el siguiente experimento: [5]

  1. Se genera un par de claves aleatorias .
  2. A un adversario, con límite de tiempo polinomial, se le da una clave pública que puede usar para generar cualquier número de textos cifrados (dentro de los límites de tiempo polinomial).
  3. El adversario genera dos mensajes de la misma longitud y los envía al remitente junto con la clave pública.
  4. El remitente selecciona uno de los mensajes al azar, lo cifra con la clave pública recibida y envía el texto cifrado resultante al adversario.

El criptosistema bajo consideración tiene la propiedad de indistinguibilidad del texto cifrado (y, por lo tanto, es semánticamente resistente a los ataques de texto sin formato elegido) si el adversario no puede determinar cuál de los dos mensajes fue elegido por el remitente con una probabilidad significativamente mayor que (probabilidad de adivinar al azar) .

Dado que el adversario tiene la clave pública, un esquema semánticamente seguro, por definición, debe ser probabilístico, es decir, tener un componente aleatorio. De lo contrario, el adversario puede, utilizando la clave pública , simplemente calcular los textos cifrados de los mensajes y compararlos con el texto cifrado devuelto y determinar con éxito la elección del remitente.

Ejemplos de algoritmos semánticamente seguros son el criptosistema Goldwasser-Micali , el esquema ElGamal y el criptosistema Peye . Estos esquemas se consideran demostrablemente seguros , ya que en cada caso la prueba de la seguridad semántica se puede reducir a un problema matemático intratable. Los algoritmos semánticamente frágiles como RSA se pueden hacer semánticamente seguros utilizando esquemas de relleno (por ejemplo, OAEP ).

Notas

  1. ↑ 1 2 S. Goldwasser y S. Micali , Cifrado probabilístico y cómo jugar al póquer mental manteniendo en secreto toda la información parcial Archivado el 31 de marzo de 2020 en Wayback Machine , Simposio anual de ACM sobre teoría de la computación, 1982.
  2. ↑ Shannon, Claude. Teoría de la comunicación de los sistemas secretos  //  Revista técnica del sistema Bell : diario. - 1949. - vol. 28 , núm. 4 . - Pág. 656-715 . -doi : 10.1002 / j.1538-7305.1949.tb00928.x .
  3. ↑ Goldreich, Oded. Fundamentos de criptografía: Volumen 2, Aplicaciones básicas. vol. 2. Prensa de la Universidad de Cambridge, 2004.
  4. ↑ S. Goldwasser y S. Micali , Cifrado probabilístico . Revista de Ciencias de la Computación y Sistemas, 28:270-299, 1984.
  5. ↑ Katz, Jonathan; Lindell, Yehuda. Introducción a la Criptografía Moderna : Principios y Protocolos  . — Chapman and Hall/CRC, 2007. Archivado el 8 de marzo de 2017 en Wayback Machine .