Seguridad semántica

En criptografía , un criptosistema semánticamente seguro es aquel en el que solo se puede extraer información insignificante sobre el texto plano a partir del texto cifrado . Específicamente, cualquier algoritmo probabilístico de tiempo polinomial (PPTA) que, dado el texto cifrado de un mensaje determinado, es seguro.${\displaystyle m}$(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 la de 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 plano, mientras que la seguridad semántica implica que cualquier información revelada no puede extraerse 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 ] [ 4 ]} Sin embargo, la definición que propusieron inicialmente no ofrecía un método directo para probar la seguridad de los criptosistemas prácticos. Posteriormente, Goldwasser y Micali demostraron que la seguridad semántica es equivalente a otra definición de seguridad denominada indistinguibilidad del texto cifrado bajo un ataque de texto plano elegido (utilizaron el término seguridad polinomial ). ^{[ 5 ]} Esta última definición es más común que la definición original de seguridad semántica porque facilita la demostración de la seguridad de los criptosistemas prácticos.

En el caso de los criptosistemas con algoritmo de clave simétrica , un adversario no debe poder calcular ninguna información sobre un texto plano a partir de su texto cifrado. Esto se puede plantear porque, dados dos textos planos de igual longitud y sus respectivos textos cifrados, un adversario no puede determinar a qué texto plano pertenece cada texto cifrado.

Para que un criptosistema con algoritmo de cifrado de clave asimétrica sea semánticamente seguro, debe resultar inviable para un adversario con recursos computacionales limitados obtener información significativa sobre un mensaje (texto plano) a partir de su texto cifrado y la clave pública correspondiente. La seguridad semántica solo considera el caso de un atacante "pasivo", es decir, aquel que genera y observa textos cifrados utilizando la clave pública y los textos planos de su elección. A diferencia de otras definiciones de seguridad, la seguridad semántica no contempla el ataque de texto cifrado elegido (CCA), en el que un atacante puede solicitar el descifrado de textos cifrados específicos, y muchos esquemas de cifrado semánticamente seguros son demostrablemente inseguros frente a este tipo de ataque. Por consiguiente, la seguridad semántica se considera ahora una condición insuficiente para garantizar la seguridad de un esquema de cifrado de propósito general.

La indistinguibilidad bajo un ataque de texto plano elegido ( IND-CPA ) se define comúnmente mediante el siguiente experimento: ^{[ 6 ]}

1. Un par aleatorio${\displaystyle (pk,sk)}$se genera al ejecutar${\displaystyle Gen(1^{n})}$.
2. A un adversario probabilístico con límite de tiempo polinomial se le proporciona la clave pública.${\displaystyle pk}$, que puede utilizar para generar cualquier número de textos cifrados (dentro de límites polinomiales).
3. El adversario genera dos mensajes de igual longitud.${\displaystyle m_{0}}$y${\displaystyle m_{1}}$y las transmite a un oráculo de desafío junto con la clave pública.
4. El oráculo del desafío selecciona uno de los mensajes lanzando una moneda justa (seleccionando un bit aleatorio).${\displaystyle b\in \{0,1\}}$), cifra el mensaje${\displaystyle m_{b}}$bajo la clave pública, y devuelve el texto cifrado desafiante resultante.${\displaystyle c}$al adversario.

El criptosistema subyacente es IND-CPA (y por lo tanto semánticamente seguro bajo un 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${\displaystyle 1/2}$(la tasa de éxito de adivinación aleatoria). Las variantes de esta definición definen la indistinguibilidad bajo un ataque de texto cifrado elegido y un ataque adaptativo de texto cifrado elegido ( IND-CCA , IND-CCA2 ).

Dado que el adversario posee la clave de cifrado pública en el juego anterior, un esquema de cifrado semánticamente seguro debe, por definición, ser probabilístico , poseer un componente de aleatoriedad ; si este no fuera el caso, el adversario podría simplemente calcular el cifrado determinista de${\displaystyle m_{0}}$y${\displaystyle m_{1}}$y compare estos cifrados con el texto cifrado devuelto.${\displaystyle c}$adivinar correctamente la elección del oráculo.

Entre los algoritmos de cifrado semánticamente seguros se incluyen Goldwasser-Micali , ElGamal y Paillier . Estos esquemas se consideran de seguridad demostrable , ya que su seguridad semántica se puede reducir a la resolución de algún problema matemático complejo (por ejemplo, el Diffie-Hellman decisional o el problema de la residuosidad cuadrática ). Otros algoritmos semánticamente inseguros, como RSA , pueden hacerse semánticamente seguros (bajo supuestos más estrictos) mediante el uso de esquemas de relleno de cifrado aleatorio, como el relleno de cifrado asimétrico óptimo (OAEP).