Parámetro de seguridad

En criptografía , un parámetro de seguridad es una forma de medir qué tan "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 indicados 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 , escrita convencionalmente como , de modo que la complejidad temporal del algoritmo criptográfico es 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 las primitivas criptográficas depende de la dureza de algunos problemas difíciles . 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 muestrearse del espacio, de modo que una búsqueda de fuerza bruta requiera potencia 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 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 depende del 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 desconoce el secreto

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

Considere las siguientes dos categorías amplias de ataques de adversarios a un esquema criptográfico determinado: ataques en los que el adversario intenta conocer 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 obtener una gran cantidad de información de la cual puede intentar obtener información secreta, por ejemplo, examinando la distribución de textos cifrados para un texto plano fijo cifrado bajo diferentes condiciones. aleatoriedad. En el segundo caso, puede ser que el adversario deba adivinar un desafío o un secreto y pueda hacerlo con alguna 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 exigiendo que las distribuciones sean estadísticamente cercanas en el primer caso o definiendo un espacio de desafío que dependa del parámetro de seguridad estadística. en el segundo caso.

Ejemplos

• En los esquemas de cifrado , un aspecto de la seguridad es (en un nivel alto) que cualquier cosa que pueda aprenderse sobre un texto plano dado un texto cifrado también puede aprenderse a partir de una cadena muestreada aleatoriamente (de la misma longitud que los textos cifrados) que es independiente del Texto sin formato. Formalmente, sería necesario 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 aún más los parámetros de seguridad estadísticos en parámetros de seguridad estadísticos de conocimiento cero y solidez . El primero parametriza lo que la transcripción filtra sobre el conocimiento secreto, y el segundo parametriza la posibilidad con la que un probador 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 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.

Ver también

• Tamaño de clave
• Función insignificante