En criptografía , un criptosistema semánticamente seguro es aquel en el que sólo se puede extraer del texto cifrado información insignificante sobre el texto sin formato . Específicamente, cualquier algoritmo probabilístico de tiempo polinomial (PPTA) al que se le proporciona 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 despreciable 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 la complejidad computacional análoga al concepto de secreto perfecto de Shannon . El secreto perfecto significa que el texto cifrado no revela ninguna información sobre el texto sin formato, mientras que la seguridad semántica implica que cualquier información revelada no se puede extraer de manera factible. [2] [3] : 378–381
La noción de seguridad semántica fue propuesta por primera vez por Goldwasser y Micali en 1982. [1] 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 sin formato elegido. [4] 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 de algoritmos de clave simétrica , un adversario no debe poder calcular ninguna información sobre un texto plano a partir de su texto cifrado. Esto puede plantearse como un adversario, dados dos textos claros de igual longitud y sus dos respectivos textos cifrados, no puede determinar qué texto cifrado pertenece a qué texto claro.
Para que un criptosistema con algoritmo de cifrado de clave asimétrica sea semánticamente seguro, debe ser inviable para un adversario computacionalmente limitado obtener información significativa sobre un mensaje (texto sin formato) cuando se le proporciona solo su texto cifrado y la clave de cifrado pública correspondiente. La seguridad semántica considera sólo el caso de un atacante "pasivo", es decir, uno que genera y observa textos cifrados utilizando la clave pública y textos sin formato 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), donde un atacante puede solicitar el descifrado de los textos cifrados elegidos, y muchos esquemas de cifrado semánticamente seguros son demostrablemente inseguros contra el ataque 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 el ataque de texto sin formato elegido ( IND-CPA ) se define comúnmente mediante el siguiente experimento: [5]
El criptosistema subyacente es IND-CPA (y por lo tanto semánticamente seguro bajo el ataque de texto plano 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 las adivinanzas aleatorias). Las variantes de esta definición definen la indistinguibilidad bajo el ataque de texto cifrado elegido y el 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 anterior, un esquema de cifrado semánticamente seguro debe ser, por definición , probabilístico y poseer un componente de aleatoriedad ; si este no fuera el caso, el adversario podría simplemente calcular el cifrado determinista 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 puede reducirse a la resolución de algún problema matemático difícil (por ejemplo, Diffie-Hellman decisional o el problema de residuosidad cuadrática ). Otros algoritmos semánticamente inseguros, como RSA , pueden volverse 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).
