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 sin formato del texto cifrado . Específicamente, cualquier algoritmo probabilístico de tiempo polinómico (PPTA) que recibe 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 en el mensaje con una probabilidad no despreciable más alta que todas las 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 información alguna sobre el texto plano, mientras que la seguridad semántica implica que la información revelada no puede extraerse de forma factible. [2] [3] : 378–381
Historia
La noción de seguridad semántica fue presentada por primera vez por Goldwasser y Micali en 1982. [1] Sin embargo, la definición que propusieron inicialmente no ofrecía un medio sencillo para probar la seguridad de los criptosistemas prácticos. Goldwasser / Micali posteriormente demostró que la seguridad semántica es equivalente a otra definición de seguridad llamada indistinguibilidad de texto cifrado bajo ataque de texto plano elegido. [4] Esta última definición es más común que la definición original de seguridad semántica porque facilita mejor probar la seguridad de los criptosistemas prácticos.
Criptografía de clave simétrica
En el caso de los criptosistemas de 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 puede plantearse como un adversario, dados dos textos en claro de igual longitud y sus dos textos cifrados respectivos, no puede determinar qué texto cifrado pertenece a qué texto simple.
Criptografía de clave pública
Para que un criptosistema de algoritmo de cifrado de clave asimétrica sea semánticamente seguro, debe ser inviable para un adversario limitado computacionalmente derivar información significativa sobre un mensaje (texto sin formato) cuando se le da solo su texto cifrado y la clave de cifrado pública correspondiente. La seguridad semántica considera solo el caso de un atacante "pasivo", es decir, uno que genera y observa textos cifrados utilizando la clave pública y los 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 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 asegurar un esquema de cifrado de propósito general.
La indistinguibilidad bajo el ataque de texto simple elegido ( IND-CPA ) se define comúnmente mediante el siguiente experimento: [5]
- Un par al azar se genera ejecutando .
- A un adversario de tiempo limitado polinomial probabilístico se le da la clave pública , que puede utilizar para generar cualquier número de textos cifrados (dentro de los límites de los polinomios).
- El adversario genera dos mensajes de igual longitud y y los transmite a un oráculo de desafío junto con la clave pública.
- El oráculo de desafío selecciona uno de los mensajes lanzando una moneda justa (seleccionando un bit al azar ), cifra el mensaje bajo la clave pública, y devuelve el texto cifrado desafiante resultante 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(la tasa de éxito de adivinar al azar). 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 , con un componente de aleatoriedad ; si este no fuera el caso, el adversario podría simplemente calcular el cifrado determinista de y y compare 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 resolución de algún problema matemático difícil (por ejemplo, Decisional Diffie-Hellman o el Problema de Residuosidad Cuadrática ). Otros algoritmos semánticamente inseguros, como RSA , pueden hacerse semánticamente seguros (bajo supuestos más fuertes) mediante el uso de esquemas de relleno de cifrado aleatorio como el relleno de cifrado asimétrico óptimo (OAEP).
Referencias
- ^ a b S. Goldwasser y S. Micali , Cifrado probabilístico y cómo jugar al póquer mental manteniendo en secreto toda la información parcial , Simposio anual de ACM sobre teoría de la computación, 1982.
- ^ Shannon, Claude (1949). "Teoría de la comunicación de los sistemas de secreto". Revista técnica de Bell System . 28 (4): 656–715. doi : 10.1002 / j.1538-7305.1949.tb00928.x . hdl : 10338.dmlcz / 119717 .
- ^ Goldreich, Oded. Fundamentos de la criptografía: Volumen 2, Aplicaciones básicas. Vol. 2. Cambridge University Press, 2004.
- ^ S. Goldwasser y S. Micali , cifrado probabilístico . Journal of Computer and System Sciences, 28: 270-299, 1984.
- ^ Katz, Jonathan; Lindell, Yehuda (2007). Introducción a la criptografía moderna: principios y protocolos . Chapman y Hall / CRC. ISBN 978-1584885511.