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 denotados por y , respectivamente. A grandes rasgos, 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ística es una medida de la probabilidad con la que un adversario puede romper el esquema (lo que sea que eso signifique para el protocolo).
Los parámetros de seguridad generalmente se expresan en representación unaria , es decir, se expresa como una cadena de s, , escrito convencionalmente como - de modo que la complejidad temporal del algoritmo criptográfico sea polinomial en el tamaño de la entrada.
Seguridad computacional
La seguridad de las primitivas criptográficas se basa en la dureza de algunos problemas difíciles . Uno establece el parámetro de seguridad computacional tal que el cálculo se considera intratable .
Ejemplos de
- 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 tomarse una muestra del espaciode modo que una búsqueda de fuerza bruta requiere potencia de cálculo.
- En el criptosistema RSA , el parámetro de seguridaddenota la longitud en bits del módulo n ; por tanto, el entero positivo n debe ser un número del conjunto {0, ..., 2 - 1}.
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ño. 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 se puede expresar como una función insignificante en el parámetro de seguridad. Uno establece el parámetro de seguridad estadística tal que se considera una posibilidad "suficientemente pequeña" de que el adversario gane.
Considere las siguientes dos amplias categorías de ataques de adversarios en 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 obtener una gran cantidad de información de la que puede intentar aprender información secreta, por ejemplo, examinando la distribución de textos cifrados para un texto plano fijo cifrado bajo diferentes 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 requiriendo 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 de
- En los esquemas de cifrado , un aspecto de la seguridad es (en un nivel alto) que cualquier cosa que se pueda aprender sobre un texto plano dado un texto cifrado también se puede aprender a partir de una cadena muestreada aleatoriamente (de la misma longitud que los textos cifrados) que es independiente de la 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ística en parámetros de seguridad estadística 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 demostrador deshonesto puede convencer a un verificador honesto de que conoce un secreto aunque no lo sepa.
- 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.