En criptografía , un criptosistema semánticamente seguro es aquel en el que solo se puede extraer de forma factible información insignificante sobre el texto simple del texto cifrado . En concreto, cualquier algoritmo probabilístico de tiempo polinomial (PPTA) al que se le da el texto cifrado de un determinado mensaje (tomado de cualquier distribución de mensajes) y la longitud del mensaje, no puede determinar ninguna información parcial sobre el mensaje con una probabilidad no despreciablemente mayor que todos los demás PPTA que solo tienen acceso a la longitud del mensaje (y no al texto cifrado). [1] Este concepto es el análogo de complejidad computacional del concepto de secreto perfecto de Shannon . El secreto perfecto significa que el texto cifrado no revela ninguna información sobre el texto simple, mientras que la seguridad semántica implica que no se puede extraer de forma factible ninguna información revelada. [2] [3] : 378–381
La noción de seguridad semántica fue propuesta por primera vez por Goldwasser y Micali en 1982. [1] [4] Sin embargo, la definición que propusieron inicialmente no ofrecía medios sencillos para demostrar la seguridad de los criptosistemas prácticos. Goldwasser/Micali demostraron posteriormente que la seguridad semántica es equivalente a otra definición de seguridad llamada indistinguibilidad del texto cifrado bajo un ataque de texto simple elegido. [5] Esta última definición es más común que la definición original de seguridad semántica porque facilita mejor la prueba de la seguridad de los criptosistemas prácticos.
En el caso de los criptosistemas con algoritmos de clave simétrica , un adversario no debe poder calcular ninguna información sobre un texto simple a partir de su texto cifrado. Esto puede plantearse como que un adversario, dados dos textos simples de igual longitud y sus dos respectivos textos cifrados, no puede determinar qué texto cifrado pertenece a qué texto simple.
Para que un criptosistema con algoritmo de cifrado de clave asimétrica sea seguro desde el punto de vista semántico, debe ser imposible para un adversario con limitaciones computacionales obtener información significativa sobre un mensaje (texto simple) cuando solo se le proporciona su texto cifrado y la clave de cifrado pública correspondiente. La seguridad semántica solo considera el caso de un atacante "pasivo", es decir, uno que genera y observa textos cifrados utilizando la clave pública y los textos simples de su elección. A diferencia de otras definiciones de seguridad, la seguridad semántica no considera el caso del ataque de texto cifrado elegido (CCA), en el que un atacante puede solicitar el descifrado de textos cifrados elegidos, y muchos esquemas de cifrado semánticamente seguros son demostrablemente inseguros contra ataques de texto cifrado elegido. En consecuencia, la seguridad semántica ahora se considera una condición insuficiente para proteger un esquema de cifrado de propósito general.
La indistinguibilidad bajo un ataque de texto simple elegido ( IND-CPA ) se define comúnmente mediante el siguiente experimento: [6]
El criptosistema subyacente es IND-CPA (y, por lo tanto, semánticamente seguro ante un ataque de texto simple elegido) si el adversario no puede determinar cuál de los dos mensajes fue elegido por el oráculo, con una probabilidad significativamente mayor que (la tasa de éxito de una suposición aleatoria). Las variantes de esta definición definen la indistinguibilidad ante un ataque de texto cifrado elegido y un ataque de texto cifrado elegido adaptativo ( IND-CCA , IND-CCA2 ).
Debido a que el adversario posee la clave de cifrado pública en el juego mencionado anteriormente, un esquema de cifrado semánticamente seguro debe ser por definición probabilístico , es decir, poseer un componente de aleatoriedad ; si este no fuera el caso, el adversario podría simplemente calcular el cifrado determinista de y y comparar estos cifrados con el texto cifrado devuelto para adivinar con éxito la elección del oráculo.
Los algoritmos de cifrado semánticamente seguros incluyen Goldwasser-Micali , ElGamal y Paillier . Estos esquemas se consideran demostrablemente seguros , ya que su seguridad semántica se puede reducir a la solución de algún problema matemático difícil (por ejemplo, Diffie-Hellman decisional o el problema de residuo cuadrático ). Otros algoritmos semánticamente inseguros, como RSA , se pueden hacer semánticamente seguros (bajo suposiciones más sólidas) mediante el uso de esquemas de relleno de cifrado aleatorio, como el relleno de cifrado asimétrico óptimo (OAEP).
