Generadores pseudo-aleatorios | Creación de instancias seguras | Alison
Loading
Apuntes
Study Reminders
Support
Text Version

Instanciación segura de los PRG

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Foundations de CryptographyProf. Dr. Ashish Choudhury (Ex) Instituto de Desarrollo de la Carrera de Infosys Cátedra del Instituto Internacional de la Información Tecnología-BangaloreLecture-11Proviblemente Secure Instanciación de PRGHello todos, bienvenidos a la conferencia 10, el plan para esta conferencia es el siguiente. (Consulte Tiempo de Slide: 00:33) En esta conferencia, vamos a discutir acerca de la creación de una instancia teórica de los generadores pseudo aleatorios para los cuales introduciremos el concepto de una función de una manera. Y después de introducir el concepto de una función de una manera, veremos cómo diseñar PRG con una expansión de un poco y luego veremos cómo diseñar PRG con expansión arbitraria. (Consulte Tiempo de Slide: 00 :53) Por lo tanto, la pregunta que queremos responder es que existen los PRG. Por lo tanto, recordemos que en la última conferencia, habíamos visto que si usted tiene un generador pseudo-aleatorio, entonces usando que usted puede diseñar ciphers de la corriente, que le permiten cifrar los mensajes largos usando la tecla corta. Por lo tanto, la pregunta que no queremos responder es que tales PRG existen o no. Y para recordar, un PRG es un algoritmo determinista que toma una semilla o una entrada de tamaño l bits que denotamos por s. Y expande su salida y produce una salida que es significativamente mayor que la entrada y la seguridad de PRG significa que la salida de este algoritmo determinista G debe ser computacionalmente indistinguible de la salida de un generador realmente aleatorio del mismo tamaño, derecha. Por lo tanto, resulta que hay 2 maneras de diseñar los PRG. La primera manera es provablemente seguras construcciones de PRGs de una manera función. Y cuando digo provablemente seguro quiero decir que las construcciones que damos usando una función de camino para que demos una prueba de que de hecho la construcción es PRG en el sentido de que no existen polinomio tiempo de distinción que puede distinguir el resultado de la PRG resultante del correspondiente generador de número aleatorio verdadero. Desafortunadamente, no podemos usarlos en la práctica porque la cantidad de cálculo que están involucrados en la construcción resultante son de orden de varios grados. Por otro lado, hay instanciaciones prácticas de generadores pseudo aleatorios, pero desafortunadamente no son demostrablemente seguros en el sentido creemos que son heurísticamente seguros porque desde su construcción, no se han reportado debilidades para tales generadores pseudo aleatorios, pero la ventaja de la búsqueda de generadores pseudo aleatorios heurísticamente seguros son super fast.Así, por eso en la práctica preferimos usar tales una instanciación. Por lo tanto, el enfoque para esta conferencia serán las instanciaciones de construcción segura de generadores pseudo aleatorios de una función de una manera. En la siguiente imagen vamos a discutir acerca de las instanciaciones prácticas de pseudo generador aleatorio. (Consultar tiempo de la diapositiva: 03 :00) Así que déjenme introducir el concepto de una función u OWF en resumen, por lo que es una función desde el dominio de la cadena de bits hasta el codominio de la cadena de bits denotada por f. Y, informalmente, es una función que es fácil de calcular, pero difícil de invertir. Más concretamente, hay 2 requisitos de esta función. El primer requisito es que sea fácil de calcular. A saber, si se le da cualquier entrada x, calcular el valor de la función en esa entrada x debe ser el tiempo polinomial, polinomio en el tamaño de la entrada x. El segundo requisito, que es la propiedad interesante de esta función de una manera es la propiedad difícil de invertir a saber, el requisito es que si se le da una muestra aleatoria y, del codominio, entonces encontrar la preimagen o una de las preimágenes de este y en el tiempo polinómico debe ser difícil, excepto con una probabilidad insignificante. Y esta propiedad está modelada por un experimento. (Consulte el Tiempo de Slide: 03 :58) Así que en este experimento, se nos da la descripción de una función conocida públicamente f. Y el nombre del experimento es Invert, jugado con respecto a un algoritmo de tiempo polinómico cuyo objetivo es invertir la salida de una función en una muestra aleatoria con respecto a la función f, y n es el parámetro de seguridad aquí. Así que en este experimento, tenemos 2 entidades, a saber, el verificador y el adversario. Así que las reglas del experimento son las siguientes. El verificador aquí escoge un x aleatorio del dominio que es una cadena de bits arbitraria y calcula el valor de la función en esa entrada x, que se da como un desafío para el adversario. Así que el adversario no es consciente de la entrada x, sólo ve la salida de la función en la entrada x, es decir, y el objetivo o el desafío para el adversario es invertir a la muestra y a saber encontrar por lo menos una de las preimágenes de este valor dado y.Así que envía su respuesta, es decir, x ’ y decimos que la función f tiene una propiedad de wayness, iffor cualquier algoritmo de tiempo polinómico A participar en este experimento existe una función insignificante decir negl (n) de tal manera que la probabilidad es que la probabilidad de que el adversario es realmente capaz de producir x ’, que es en realidad una preimagen de la y es superior limitada por una función insignificante. Eso significa que requerimos que ningún algoritmo de tiempo polinómico debe ser capaz de invertir este yexcept aleatorio con una probabilidad insignificante. Por lo tanto, en esta definición el requisito es que la probabilidad de éxito de ese adversario para invertir el azar y debe ser superior limitada por una función insignificante no por 0, porque siempre existen una estrategia de adivinación por el adversario, es decir, el adversario puede simplemente adivinar una x ’ al azar.Y siempre existe una probabilidad no cero de que la adivinada x ’ de hecho resulta ser una de las preimágenes de la y dada, es por eso que en la definición, no necesitamos que no hagamos cumplir que la condición de que A debe ser capaz de invertir la muestra y debe ser superior limitada por 0, damos el apalancamiento y el límite superior la probabilidad de éxito del adversario por una probabilidad insignificante.También fíjate que no es requerido por el adversario para encontrar la x exacta, porque la función puede ser muchas a una función. Entonces, podría ser posible que la dada y que es lanzada como un desafío al adversario tenga varias preimágenes. El objetivo del adversario es encontrar una de esas preimágenes a la derecha. (Consulte el tiempo de la diapositiva: 06:25) Así que veamos un ejemplo para dejar claro nuestro entendimiento, considere la función f que es una función 2input y la función es del conjunto de números naturales al conjunto de números naturales. Por lo tanto, la función toma 2 entradas del conjunto de números naturales y la salida de la función es básicamente el producto de las 2 entradas. Ahora, la pregunta es esta función de una función de una manera que significa que si alguien le da el valor de x punto y, su x y y no son conocidos por usted. ¿Será capaz de invertir o encontrar una de las preimágenes a saber un par de x, y tal que cuyo producto es igual al producto dado en la cantidad polinómica de tiempo, y resulta que existen, de hecho, existe efectivamente un algoritmo simple para encontrar una de las preimágenes y el algoritmo es el siguiente. Así que se le da una muestra aleatoria z, que es básicamente la salida de la función en un par de entradas desconocidas x, y. Y su algoritmo de inversión es el siguiente. El algoritmo comprueba si z es par o no, si z es incluso entonces el algoritmo da salida al siguiente par de preimágenes, la primera preimagen x ’ es 2 y una segunda preimagen y ’ es z/2. Por lo tanto, eso es un par de entradas que realmente le daría la salida z, mientras que si la muestra z que se le da a usted es impar entonces usted sólo salida al azar x ’, y ’ en el conjunto de números naturales. Por lo tanto, resulta que la probabilidad de éxito de este algoritmo de inversión es en realidad 3 por 4. Debido a que la función es una función de 2 entradas, los valores posibles de x, y podrían ser (impares, impares), (impar, incluso), (incluso, impares) e (incluso, incluso). Y resulta que de esta 4 combinaciones, para 3 de las combinaciones, tu z siempre será parejo. Y si z es incluso y de hecho el algoritmo de inversión que se utiliza aquí, es decir, outputting 2 y z/2 como la posible preimagen es un algoritmo exitoso. El único caso problemático es cuando la muestra x, y es en realidad un par impar, impar en el que su z puede no ser z no será un número par, en cuyo caso es posible que usted esté superando una x ’ incorrecta, y ’. Por lo tanto, resulta que en tres cuartos de las instancias, el adversario o este algoritmo será capaz de invertir con éxito el valor dado z. Por lo tanto, esta función f no es una función de una sola manera porque la probabilidad de éxito de la inversión es 3/4, que es una cantidad significativa de probabilitting.Por otro lado, vamos a modificar ligeramente esta función. Por lo tanto, mi función f (x, y) sigue siendo el producto de x e y, pero en lugar de decir que x e y son números naturales aleatorios, poner la restricción aquí que x e y son números primos aleatorios de aproximadamente el mismo tamaño. Y resulta que esta función ahora es conjeturada para ser una función de una manera si x e y son grandes números primos dicen de orden 1024 bits. Así que el estrés aquí que es simplemente conjeturado que esta función f (x, y) donde x e y son números primos grandes arbitrarios es una función de una manera porque hasta ahora, no tenemos ningún algoritmo de tiempo polinomial para invertir esta función. No se prueba formalmente que de hecho esta función es una función de una sola manera. Y más adelante, cuando vamos a discutir acerca de la criptografía de la clave pública, y vamos a discutir la teoría de los números donde veremos varias funciones de tal candidato de una manera, que son conjeturas sobre varios duros llamados problemas teóricos del número. Así que por el momento, vamos a creer que esta función f (x, y) donde x e y son números grandes arbitrarios y la función es un producto de x y y es una función candidata de una manera. (Consulte el tiempo de la diapositiva: 10 :02) Así que ahora vamos a definir otro concepto relacionado que de una manera permutación u OWP. Y básicamente una forma de permutación de una manera es una función de una manera, que también pasa a ser una bijección. A saber, la correlación es ahora una correlación de uno a uno. Eso significa que cada y desde el codominio tendrá una preimagen única. Y el requisito o la parte difícil de invertir para una forma de permutación es que si se le da una y al azar de la codominio, el desafío para el adversario es encontrar una preimagen única x que realmente habría dado eso y en la cantidad polinómica de tiempo. Así que la diferencia aquí es para el caso de una función de una manera, el desafío aleatorio y podría tener varias preimágenes y su objetivo era encontrar una de esas preimágenes. En el caso de una forma de permutación, la muestra aleatoria y que se da a usted tendrá sólo una preimagen única. Y su objetivo es encontrar esa preimagen única y cantidad polinómica de tiempo. Observe que tanto en el caso de una función de una manera, así como de una manera permutación, ponemos la restricción que el algoritmo de inversión debe tomar la cantidad polinómica de tiempo. Porque si no ponemos ninguna restricción en la cantidad de tiempo, que se da al algoritmo de inversión, entonces siempre hay un algoritmo de fuerza bruta, el algoritmo puede tratar sobre todo posible candidato x del conjunto de candidato x y definitivamente va a golpear sobre una x que será dar el azar y que se lanza como el desafío, pero el tiempo de ejecución de este algoritmo de fuerza bruta será exponencialmente o será proporcional al tamaño del dominio. Y el tamaño del dominio es exponencialmente grande que el tiempo de ejecución de los algoritmos de inversión es también exponencial. Por lo tanto, es por eso que en el experimento, donde modemos la parte de inversión tanto para la función de una manera, así como una forma de permutación ponemos la restricción de que el tiempo de ejecución de ese adversario debe ser el tiempo polinómico. (Consultar Tiempo de Slide: 11 :52) Así que, ahora vamos a discutir otro concepto relacionado interesante, es decir, el predicado hardcore que será útil cuando diseñaremos nuestro candidato pseudo generador aleatorio de una función y la motivación para este predicado duro es el siguiente. Así que imagine que se le da una función f, que es una función de una manera o una permutación de una manera. Y si se le da el valor de la función en una entrada aleatoria x, entonces definitivamente calcular toda la x en la cantidad polinómica de tiempo es difícil. Porque eso es lo que es la propiedad de una función de una manera o una forma de permutación, pero eso no significa necesariamente que no se puede calcular nada sobre x en el tiempo polinómico, puede haber alguna información sobre x, que se puede calcular a partir del valor de f (x) en la cantidad polinómica de tiempo. Por lo tanto, básicamente el predicado hardcore modela lo que se puede calcular sobre x de una f (x) en la cantidad polinómica de tiempo y lo que no se puede calcular. Para dejar mi punto más claro, considere la función?: {0, 1} ∗ → {0, 1} ∗ y decir que esta función f es una función de una sola manera y utilizando esta función diseñamos otra función g, que es ahora una función 2input y la función g en el par de entrada x1, x2 se define como la salida que consiste en x1as it is, y la segunda parte de la salida de esta función g es en realidad el valor de la función f en la segunda parte de la entrada, es decir, x2,? (x1, x2) forma en que estoy definiendo mi función g. Y mi afirmación es que si el tamaño de x1 y x2 son aproximadamente iguales, a saber, alguna función polinómica en el parámetro de seguridad, entonces si la función f con la que empezamos es una función de una sola manera, entonces la función construida g, que se construye como esta también es una función de una sola manera. Por lo tanto, básicamente, la idea aquí es que si g no es una función de una sola manera, eso significa que si alguien le da el valor de g (x1, x2), y en realidad se puede encontrar fuera x1, x2 en la cantidad polinómica de tiempo. Entonces intuitivamente usando ese algoritmo, también se puede calcular el valor de x2 usando sólo dado f (x2), por lo que podemos establecer formalmente su hecho utilizando un argumento de reducción. Así que no voy a entrar en el argumento de la reducción. Pero básicamente la idea aquí es que si f es una función de una manera y la función g, que es una función de 2 entrada construida como esta es también una función de una manera siempre que x1 y x2 son aproximadamente el mismo size.Ahora, si usted ve la función g, resulta que a pesar de que es una función de una manera, al ver la salida de esta función g en un par de entrada aleatoria, usted realmente termina de aprender la mitad de la entrada, a la derecha. Debido a que la primera mitad de la salida es en realidad la primera mitad de la entrada como es. En ese sentido, a pesar de que esta función g es una función de una manera, no es el caso de que si le doy el valor de esta función g en un par arbitrario de entrada, no se puede calcular de nuevo la entrada entera en la cantidad polinómica de tiempo. Hay algo que usted puede calcular, hay algo que no se puede calcular en la cantidad polinómica de tiempo. Así que esta noción de predicado hardcore precisamente modela, lo que es polinomio tiempo computable del valor de la función f (x) en la entrada aleatoria x, a la derecha. (Consulte el tiempo de la diapositiva: 15 :01) Así que veamos la definición formal de este predicado hardcore. Por lo tanto, imagine que se le da una función de un dominio de la cadena de bits al codominio de la cadena de bits y subrayo que la función puede no ser una función de una manera podría ser una función normal. Por lo tanto, se nos da una función f y que corresponde a la función f definimos otra función hc que es una función booleana que significa, toma una serie binaria arbitraria como una entrada y produce una salida booleana 0, 1.Y luego vemos que esta función hc asociada con una función f es un predicado hardcore si las siguientes 2 condiciones se mantienen. Por lo tanto, la primera condición es que si se le da texto de entrada al azar y calcular el valor de esta función, el predicado hardcore es decir, hc de f debe ser polinomio tiempo computable que significa que usted debe ser capaz de calcular el valor de hc de x en el polinomio tiempo polinomio en el tamaño de la entrada x. La segunda propiedad interesante que en realidad hace el predicado hardcore muy interesante es el siguiente que si se le da el valor de f (x) para un x elegido al azar, entonces no es posible calcular el valor de hc (x) con probabilidad significativamente mejor que la mitad en la cantidad polinómica de tiempo. Eso significa que el reto aquí es que si te doy f (x) y no te digo el valor de x, donde x es elegido al azar, entonces incluso después de aprender f (x), no deberíamos ser capaces de calcular el valor de la función hc de x en la cantidad polinómica de tiempo, excepto con probabilidad, insignificante mejor que la mitad. Si ese es el caso, entonces decimos que la función hc (x), hc es actualmente el predicado hardcore asociado con la función f. Así que este requisito de incapacidad para calcular el valor de hc (x) con probabilidad significativamente mejor que la mitad por un algoritmo de tiempo polinómico es modelado por un experimento que llamamos como experimento muy duro. Y ahora este experimento está diseñado con respecto a una función f que es públicamente conocida, que es una función candidata que podría ser una función candidata de una manera o una forma de permutación o podría ser sólo una función y asociado con la función f tenemos un candidato duro predicado, que es una función booleana y el experimento involucra 2 entidades. Así que la regla del experimento es la siguiente. El verificador aquí escoge un x aleatorio del dominio, calcula el valor de la función en esa entrada x. Y la correspondiente salida y se le da como un desafío al adversario. Y el objetivo del adversario o el desafío para el adversario es después de ver el valor de y tiene que calcular el valor de hc (x) sin conocer la x. Por lo tanto, decir hc (x) va a ser un poco que somete al adversario salidas un poco que podría ser 0 o 1.Y decimos que el adversario ha ganado el juego si en realidad b = hc (x). Así que, eso significa, decimos que la función hc asociada con la función f es un predicado hardcore, si para cualquier algoritmo de tiempo polinómico que participa en este experimento, la probabilidad de que las salidas del adversario b donde b es en realidad igual a hc de x es superior limitada por la mitad más una probabilidad insignificante o una función insignificante en el parámetro de seguridad. Si ese es el caso, entonces decimos que la función hc es un predicado hardcore asociado con la función f. Así que, fíjate que hay en la definición, hemos limitado la probabilidad de éxito del adversario a ser medio más insignificante, no requerimos que la probabilidad de éxito del adversario debe ser 0, porque siempre hay una estrategia de adivinación o un adversario de adivinación que puede adivinar un poco y siempre existe una probabilidad de 1/2 que el huésped es de hecho el valor de hc (x) correctamente.Aparte de eso también estamos dispuestos a dar a ese adversario una ventaja extra insignificante y superar con éxito el predicado hardcore, porque estamos en un mundo computacionalmente seguro. Así que esa es la definición de predicado hardcore. (Consulte el Tiempo de Slide: 18 :53) Así que ahora la pregunta es, si se nos da una función candidata de una manera o una forma de permuta existe un predicado muy duro asociado o no. Y resulta que curiosamente la respuesta es sí. Y eso es debido a un teorema y criptografía muy fundamental, que también se llama como el teorema de Goldreich-Levin. Y el teorema de Goldreich-Levin básicamente le muestra cómo construir un predicado muy duro asociado con cualquier función dada de una manera, o cualquier otra manera dada la permutación. Así que no vamos a entrar en la prueba del teorema de Goldreich-Levin, simplemente veremos más o menos la declaración del teorema y la intuición de la seguridad. Así que la declaración del teorema es la siguiente. Así que imagina que te dan una función de candidato de una manera decir f o un candidato de una manera permutación. Ahora usando esta función candidata f, construimos una función de 2 entradas g, y la construcción de gis de la siguiente manera. Por lo que pasa la entrada como x, r. Y la salida de g se define de la siguiente manera. Así que evaluamos la función f en la primera parte de la entrada de g. Esto constituye la primera parte de la salida de g, y la segunda parte de la entrada de g se copia como está en la salida de la g. Y aquí el tamaño de las 2 entradas de la g, es decir, x y r son del mismo orden. Así que esa es la forma en que definimos nuestra función g. Ahora podemos probar formalmente que si la función f con la que empezamos es una función de una manera o una forma de permutación entonces la función g que hemos construido como (f (x), r) es también una función de una manera o una forma de permutación respectivamente.Y la prueba es por un argumento de reducción. A saber, podemos mostrar que si usted tiene un algoritmo de tiempo polinómico para invertir la salida de la función g que ha construido en un par aleatorio de entrada x, r. Eso significa que si usted tiene un algoritmo que sin conocer el par aleatorio de entrada x, r, pero sólo ver el valor de g (x, r) puede devolverle x, r en cantidad polinómica de tiempo. Entonces usando el mismo algoritmo de inversión podemos construir otro algoritmo de tiempo polinomial, que cuando se le da el valor de f (x) en un x aleatorio sin saber el valor de x realmente puede devolverle el valor de x, lo cual es una contradicción con el hecho de que f es una función de una manera o una permutación de una manera. Así que es un argumento de reducción directa usando el cual podemos probar este teorema. Por lo tanto, ahora nos centraremos en la función g. Y lo que el teorema de Goldreich-Levin te muestra básicamente que si esta función g es una función de una sola manera, entonces podemos asociar una predicta de núcleo duro correspondiente con esta función g. A saber, el predicado hardcore es la función booleana, que básicamente toma la combinación lineal aleatoria de los bits de la entrada x, derecha. Así que lo que consideramos aquí es que su r se interpreta como una cadena de bits de longitud n, y su x también se considera como una cadena de bits de longitud n, estas son las 2 entradas para la función g, y el predicado hardcore asociado, que se asocia con la función g es denotado por la función gl. Y la función gl es básicamente la combinación lineal aleatoria de los bits de la x, donde los combinadores se definen por la representación de bits de la entrada r. Y lo que el teorema de Goldreich-Levin afirma básicamente que esta función gl (x, r) es el predicado de núcleo duro asociado con la función g. Eso significa, si alguien le da el valor de la función g (x, r), para un x y r al azar, entonces, excepto con la probabilidad mitad más insignificante ningún algoritmo de tiempo polinomio puede calcular el valor de gl (x, r). Y la intuición detrás de esto la prueba del teorema de Goldreich-Levin es que a pesar de que se le da f (x) ya que no se sabe el valor de x, básicamente el desafío para la computación de la gl de Goldreich, la salida de la función gl (x, r) es básicamente para calcular el XOR de los subconjuntos aleatorios del bit de x pero ya que el adversario no sabrá los bits exactos de la x, será difícil para el adversario para calcular que XOR de los subconjuntos aleatorios de los bits de x. Eso es básicamente la intuición de este teorema. Sin embargo, resulta que la prueba de este teorema es realmente desafiante e involved.Así, los estudiantes que están interesados en pasar por la prueba de este teorema de Goldreich-Levin pueden referirse al libro de Katz y Lindel, donde han dado la prueba detallada, pero para nuestra discusión, vamos a suponer que la función gl (x, r) es asociado duro predicado que se asocia con nuestro candidato una forma función g (x, r) derecha. (Consultar tiempo de la diapositiva: 23 :36) Así, suponiendo que ahora tenemos un predicado muy duro, y tenemos un candidato de una manera permutación nos deja ver cómo podemos construir PRG con el mínimo expansión, y lo que queremos decir con una expansión mínima es que vamos a suponer que se nos da un candidato de una forma permutaciones del conjunto de las cadenas de bit n al conjunto de las cadenas de bits n. Eso significa que la función f toma una entrada que es una cadena de longitud n y produce salida que es también una cadena de longitud n. Y es una permutación de una manera. Y asociado a la función f, tenemos un hard-corepredicate. Ahora dado esto vamos a construir un generador pseudo-aleatorio donde la construcción del generador pseudo-aleatorio es el siguiente. A saber, podemos demostrar que no existe un polinomio de tiempo distinguido para nuestra construcción, de lo contrario, se reduce a la seguridad de la función subyacente de una manera y el hard-corepredicate. Espero que hayan disfrutado de esta conferencia. Gracias.

Notification
You have received a new notification
Click here to view them all