Parámetro de seguridad

En criptografía , un parámetro de seguridad es una forma de medir cuán "difícil" es para un adversario romper un esquema criptográfico. Hay dos tipos principales de parámetros de seguridad: computacionales y estadísticos , a menudo denotados por y , respectivamente. En términos generales, el parámetro de seguridad computacional es una medida del tamaño de entrada del problema computacional en el que se basa el esquema criptográfico, que determina su complejidad computacional, mientras que el parámetro de seguridad estadístico es una medida de la probabilidad con la que un adversario puede romper el esquema (lo que sea que eso signifique para el protocolo). ${\displaystyle \kappa }$ ${\displaystyle \lambda }$

Los parámetros de seguridad generalmente se expresan en representación unaria , es decir, se expresan como una cadena de s , convencionalmente escrita como , de modo que la complejidad temporal del algoritmo criptográfico sea polinómica en el tamaño de la entrada. ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle 1}$ ${\displaystyle \kappa =1\cdots 1}$ ${\displaystyle 1^{\kappa }}$

Seguridad computacional

La seguridad de los primitivos criptográficos depende de la dificultad de algunos problemas complejos . Se establece el parámetro de seguridad computacional de manera que el cálculo se considere intratable . ${\displaystyle \kappa }$ ${\displaystyle O(2^{\kappa })}$

Ejemplos

• Si la seguridad de un esquema depende del secreto de una clave para una función pseudoaleatoria (PRF), entonces podemos especificar que la clave PRF debe ser muestreada del espacio de modo que una búsqueda de fuerza bruta requiera poder computacional. ${\displaystyle \{0,1\}^{\kappa }}$ ${\displaystyle O(2^{\kappa })}$
• En el criptosistema RSA , el parámetro de seguridad denota la longitud en bits del módulo n ; por lo tanto, el entero positivo n debe ser un número del conjunto {0, ..., 2 - 1}. ${\displaystyle \kappa }$ ^{${\displaystyle \kappa }$}

Seguridad estadística

La seguridad en criptografía a menudo se basa en el hecho de que la distancia estadística entre

• una distribución basada en un secreto, y
• una distribución simulada producida por una entidad que no conoce el secreto

es pequeña. Formalizamos esto usando el parámetro de seguridad estadística diciendo que las distribuciones son estadísticamente cercanas si la distancia estadística entre distribuciones puede expresarse como una función despreciable en el parámetro de seguridad. Se establece el parámetro de seguridad estadística de modo que se considere una probabilidad "suficientemente pequeña" de que el adversario gane. ${\displaystyle \sigma }$ ${\displaystyle O(2^{-\sigma })}$

Consideremos las siguientes dos amplias categorías de ataque de adversarios a un esquema criptográfico dado: ataques en los que el adversario intenta obtener información secreta, y ataques en los que el adversario intenta convencer a una parte honesta de que acepte una declaración falsa como verdadera (o viceversa). En el primer caso, por ejemplo un esquema de cifrado de clave pública , un adversario puede ser capaz de obtener una gran cantidad de información de la que puede intentar obtener información secreta, por ejemplo examinando la distribución de textos cifrados para un texto plano fijo cifrado bajo diferente aleatoriedad. En el segundo caso, puede ser que el adversario deba adivinar un desafío o un secreto y pueda hacerlo con cierta probabilidad fija; en esto podemos hablar de distribuciones considerando el algoritmo para muestrear el desafío en el protocolo. En ambos casos, podemos hablar de la posibilidad de que el adversario "gane" en un sentido amplio, y podemos parametrizar la seguridad estadística al requerir que las distribuciones sean estadísticamente cercanas en el primer caso o definiendo un espacio de desafío dependiente del parámetro de seguridad estadística en el segundo caso.

Ejemplos

• En los esquemas de cifrado , un aspecto de la seguridad es (a un alto nivel) que todo lo que se puede aprender sobre un texto simple dado un texto cifrado también se puede aprender de una cadena muestreada aleatoriamente (de la misma longitud que los textos cifrados) que es independiente del texto simple. Formalmente, uno necesitaría demostrar que una distribución uniforme sobre un conjunto de cadenas de longitud fija es estadísticamente cercana a una distribución uniforme sobre el espacio de todos los textos cifrados posibles.
• En los protocolos de conocimiento cero , podemos subdividir los parámetros de seguridad estadística en parámetros de seguridad estadística de conocimiento cero y de solidez . El primero parametriza lo que la transcripción filtra sobre el conocimiento secreto, y el segundo parametriza la probabilidad con la que un verificador deshonesto puede convencer a un verificador honesto de que conoce un secreto incluso si no lo sabe.
• En la componibilidad universal , la seguridad de un protocolo se basa en la indistinguibilidad estadística de las distribuciones de una ejecución en el mundo real y una ejecución en el mundo ideal. Curiosamente, para un entorno computacionalmente ilimitado no es suficiente que las distribuciones sean estadísticamente indistinguibles, ya que el entorno puede ejecutar el experimento suficientes veces para observar qué distribución se está produciendo (real o ideal); sin embargo, cualquier adversario independiente contra el protocolo solo ganará con una probabilidad insignificante en el parámetro de seguridad estadística, ya que solo participa en el protocolo una vez.

Véase también

• Tamaño de la clave
• Función despreciable