Generadores Pseudo-aleatorios | Funciones Pseudo-aleatorias | Alison
Loading
Apuntes
Study Reminders
Support
Text Version

Funciones pseudo-aleatorias

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) Fundación Infosys Fundación de Desarrollo Career ProfessorIndian Institute of Technology-BangaloreLecture-14Pseudo Random Functions PRFsHola a todos, bienvenidos a la conferencia 13. (Consulte Slide Time: 00 :31) El plan para esta conferencia es el siguiente. Introduciremos un bloque de construcción muy importante para la criptografía de clave simétrica, a saber, la función pseudo aleatoria. Y más adelante veremos que cómo la pseudo función aleatoria actúa como un bloque de construcción fundamental para el diseño de muchas hermosas primitivas de clave simétrica. También discutiremos las variantes de la función pseudo aleatoria, a saber, la permutación pseudo aleatoria y la fuerte permutación pseudo aleatoria. Veremos cómo construir generadores pseudo aleatorios a partir de la función pseudo-aleatoria. (Consulte el tiempo de la diapositiva: 01 :01) Así que, comencemos nuestra discusión sobre la función pseudo-aleatoria. En un nivel muy alto, una función pseudo aleatoria es un algoritmo determinista con dos entradas y una única salida donde y. Y asumiremos que el tamaño de clave es n y n es algún parámetro de seguridad. Así que es por eso que a menudo llamamos a la función F como una función por clave porque va a ser operada por una llave. En la práctica, el tamaño de n, l y L puede todo muy y más adelante veremos varias instanciaciones de la función pseudo aleatoria. De hecho n, l, L todos son diferentes, pero asintóticamente todo tiene que ser una función polinómica de su parámetro de seguridad. Ahora, cómo vamos a utilizar esta función pseudo-aleatorio. Por lo tanto, cada vez que estamos diseñando cualquier primitivo criptográfico, la forma en que utilizamos esta función pseudo aleatoria es la siguiente: al principio de las instanciaciones de la primitiva criptográfica, que utiliza esta función F, ya sea el emisor o el receptor va a generar una clave uniformemente aleatoria. Y de alguna manera se establecerá con la parte receptora también. Y no sería conocido por el atacante. Una vez que se haya arreglado la clave, no vamos a cambiar la clave a lo largo de esa sesión o a lo largo de esa instanciación. La clave seguirá siendo la misma. Ahora, una vez que arreglamos la clave, donde se va a arreglar k y no se le sabría al atacante. Esa es la forma en que vamos a utilizar una función pseudo aleatoria. Ahora, qué es exactamente la propiedad de seguridad que requerimos de la función pseudo aleatoria. Y informalmente requerimos lo siguiente: si la clave k es desconocida, y uniformemente elegida al azar del dominio del espacio clave, entonces básicamente requerimos que el comportamiento o la salida de la función clave de Fk debería casi asemejarse a la salida de cualquier función verdaderamente aleatoria a. Por lo tanto, recuerde, una función verdaderamente aleatoria es una función sin clave. Por lo tanto, lo que básicamente quiere es que la función por clave Fk, una vez que la clave ha sido elegida al azar, su comportamiento debería casi asemejarse al comportamiento de una pseudo función aleatoria. (Consulte el tiempo de la diapositiva: 03 :53) Por lo tanto, vamos un poco más profundo en lo que quiero decir exactamente por la declaración formal. Imagine que tiene una función verdaderamente aleatoria que es una función sin clave, no tiene ninguna clave, sólo toma una entrada de tamaño l bits y produce una salida de tamaño L bits. Por lo tanto, es fácil imaginar el comportamiento de una función verdaderamente aleatoria de la siguiente manera: lo que realmente funciona al azar básicamente toma es una entrada del tamaño x, y produce una salida de tamaño L bits. Y usted puede imaginar que básicamente, esta función verdaderamente aleatoria mantiene una tabla que consiste de 2lrows, donde básicamente las tiendas de primera fila. Las segundas tiendas y las últimas tiendas de fila. Por lo tanto, siempre que esta función realmente aleatoria recibe una entrada x, lo que básicamente hace es que internamente comprueba si ya hay una entrada para el valor de esta función realmente aleatoria en la entrada x. Si no está ahí, entonces llene esa fila, a saber, F (x) por. Para las futuras invocaciones de estas funciones verdaderamente aleatorias dijo que y para ser la salida de esta función verdaderamente aleatoria en la entrada x. Por otro lado, si el valor x que se ha pasado, usted ya tiene una entrada correspondiente a esa clave x en esta tabla entonces sólo pasa en el valor que se almacena en esa fila correspondiente como la salida y. Así que esa es la forma en que se puede imaginar el comportamiento de una función verdaderamente aleatoria. Lo importante aquí es que puesto que esta función es una función verdaderamente aleatoria, cada fila aquí es una cadena independiente de longitud L bits. Eso significa y son independientes entre sí, para cualquiera. Eso significa, si existe un algoritmo, que ha sido notyet visto el valor de la función verdaderamente aleatoria en alguna entrada x, no puede predecir cuál es exactamente el valor de la función va a ser para esa entrada x, excepto para adivinar la salida, y la adivinación tendrá éxito con probabilidad 1/2L. Aparte de eso, no hay manera de predecir el resultado de la función verdaderamente aleatoria en alguna entrada x. Y esto se mantiene incluso si ese algoritmo que en realidad está tratando de predecir el resultado de esta función verdaderamente aleatoria en la entrada x ya ha visto la salida de esta función verdaderamente aleatoria en varios valores x anteriores, que podrían estar relacionados con estos nuevos valores x. Pero esto se debe a que cada fila en la tabla de esta función verdaderamente aleatoria es independiente entre sí. La propiedad de seguridad que requerimos de una función pseudoaleatoria es que una vez que arreglamos la clave seleccionando la clave uniformemente al azar, entonces esa función por clave también debería tener las propiedades similares excepto con una probabilidad insignificante. (Consulte el tiempo de la diapositiva: 07 :02) Por lo tanto, lo que significa exactamente eso es que en su lado izquierdo tiene una función por clave Fk, donde se conoce públicamente la descripción de la función F. Subrayo que la descripción de la función es públicamente conocida y lo que no se conoce es básicamente el valor de la clave. En el lado derecho, usted tiene una función verdaderamente aleatoria que consiste básicamente de 2Lrows cada entrada que consiste de una cadena uniformemente aleatoria de longitud L bits. Y cuando digo que mi función F es una función pseudo al azar, lo que básicamente quiero decir es que no existe ninguna prueba estadística de tiempo polinomio o algoritmo estadístico que puede distinguir significativamente aparte una salida del algoritmo Fk de la salida de esta función verdaderamente aleatoria. Eso significa, si nuestro distinguidor o la prueba estadística es básicamente dado las salidas de la función Fk o la salida de la función al azar en varias entradas del adversario ’ s o la elección del distinguido. Desde el punto de vista del distinguido, esos resultados podrían ser tan propensos a venir de la función Fk como es probable que provenga de esta función verdaderamente aleatoria. Ahora, antes de ir más allá, esta condición es similar a la forma en que hemos definido la noción de generador pseudo-aleatorio. Por lo tanto, recuerde en el generador pseudo-aleatorio que la seguridad se define por decir que no existe ninguna prueba estadística, que cuando se le da una muestra no puede distinguir aparte si esa muestra se genera mediante la ejecución de un generador de pseudo-aleatorio, o por la ejecución de un generador realmente aleatorio. En ese experimento, ese diferenciador se dio sólo una muestra porque nuestro generador pseudo-aleatorio es una única función de entrada. Para cada invocación del pseudo generador aleatorio, la muestra va a ser diferente porque la clave para el generador pseudo aleatorio va a ser diferente. Pero en el contexto de la función pseudoaleatoria, la forma en que vamos a utilizar una función pseudo-aleatoria en la aplicación real del mundo es que la clave se fijará una vez para todos al principio de la sesión. Y luego las x entradas van a ser variadas. Y cada invocación de la función será con la misma llave. (Consultar Tiempo de Slide: 09:14) Así que lo que ahora vamos a hacer es que en nuestra definición formal, básicamente al adversario se le van a dar muchas muestras, y tiene que distinguir aparte si esas muestras se generan al ejecutar una función por clave Fk o por ejecutar una función verdaderamente aleatoria. Así que veamos cuáles son exactamente los detalles formales. Así que se le da la descripción de una función públicamente conocida, y el experimento que llamamos indistinguishability experimento contra un PRF con respecto a un algoritmo de distinción en contra de la función F y l es el parámetro de seguridad. Las reglas de los juegos son los siguientes: el diferenciador está permitido para pedir la salida de la función en muchas x entradas de su elección, y puede preguntar sus consultas de forma adaptable que significa que primero puede pedir la salida de la función en la entrada x1. A continuación, en función de la respuesta, puede decidir qué debe ser x2. Y luego en función de la respuesta, puede decidir qué debe ser x3, y así sucesivamente. No ponemos absolutamente ninguna restricción en qué tipo de consultas se puede distinguir. Ahora, una vez que el distinguidor envía sus consultas, el retador aquí tiene que llegar con la respuesta, a saber, la salida de las funciones en esos insumos. Y la forma en que el retador habría preparado esa respuesta es la siguiente: básicamente, el retador va a lanzar una moneda de forma uniforme al azar, que va a la salida 0 o 1 con probabilidad 1/2. Si el lanzamiento de moneda es 0, entonces todas estas respuestas y1, .., yq se generan básicamente ejecutando una función realmente aleatoria en esas x entradas. En un detalle más todas estas cuerdas y son básicamente independientes entre sí y cada una de ellas es básicamente una cadena de bits uniformemente aleatoria de longitud L bits. Por otro lado, si el lanzamiento de moneda del retador es 1, entonces esta y salidas son básicamente la salida de una función por clave Fk, donde la clave es elegida uniformemente al azar por el retador. Y ahora el reto para el distinguidor es averiguar cómo exactamente se generan estas respuestas y1, .., yq, si son generadas por el mecanismo 0 o si son generadas por el mecanismo 1. Eso es un desafío para nuestro distinguido. Por lo tanto, el diferenciador en este caso da salida b ’ que va a ser un poco que básicamente dice si se siente que una muestra y1, .., yq son generados por los mecanismos 0 o por el mecanismo 1. Y nuestra definición de seguridad es que la función F es una función pseudo aleatoria si por cada algoritmo de tiempo polinomio probabilístico D que participa en este experimento, existe una función insignificante como que la probabilidad de que el distinguidor identifique correctamente la etiqueta o la naturaleza de las muestras y1, .., yq es superior acotado por ½ + negl (n). Una vez más, la probabilidad se toma aquí sobre la elección aleatoria del retador y las consultas aleatorias del distinguidor. Otra formulación equivalente de la misma definición es que decimos que la función F es un PRFsi la ventaja distintiva de nuestro distinguidor es superior acotado por una función insignificante. Esto significa que no importa si b = 0 o si b = 1, lo que significa que no importa si las muestras y son generadas por una función realmente aleatoria o si son generadas por una función pseudo-aleatoria. En ambos casos, el diferenciador debe producir la misma salida, por ejemplo b ’ = 1 excepto con una probabilidad insignificante. Y de nuevo, podemos demostrar que si tenemos una pseudo función aleatoria que satisface la primera condición, entonces se aplica también se satisface la segunda condición y viceversa. Así que dependiendo de nuestra conveniencia, podemos usar cualquiera de estas dos definiciones. Así que esa es la definición de una pseudo funciona.Básicamente, la intuición en este experimento es que estamos dando a nuestro distinguido un acceso de oráculo a la función donde la función es una función verdaderamente aleatoria o una función por clave. Y el diferenciador tiene que distinguir aparte si está interactuando con un oráculo de función verdaderamente aleatorio o si está interactuando con un oráculo de función por clave. Esta definición de seguridad exige que, excepto con una probabilidad insignificante, no sea capaz de distinguir. Observe que aquí, estamos obligados a la parte superior de la probabilidad de éxito del adversario por ½ + negl (n). No podemos poner una definición diciendo que una probabilidad de éxito del distinguidor debe ser 0 porque siempre hay posibilidad de que el distinguido que puede adivinar que está interactuando con decir TRF o PRF y con la probabilidad la mitad de que realmente puede identificar correctamente o la probabilidad la mitad de su conjetura podría ser correcta.Así, nunca podemos poner una condición que la probabilidad de éxito del distinguido debe ser 0. La ventaja adicional insignificante es básicamente debido al mal necesario asociado con el hecho de que estamos en el mundo computacional. (Consultar Tiempo de Slide: 14 :25) Así que, ahora vamos a ver, si es fácil o si es lo fácil o lo difícil que es construir una función pseudo-aleatoria. Por lo tanto, imagine que diseñe una función F de la siguiente manera y por simplicidad, supongo que la longitud de la clave y la longitud de bloque y la longitud de salida son del mismo tamaño, es decir, decir n bitstrings y la forma en que se define la salida de la función. Esa es la forma en que se calcula la salida. Nuestro objetivo es probar o refutar si esta función es una función pseudo aleatoria. De hecho, queremos refutar esta construcción no es un PRF. Y para eso, básicamente queremos discutir si de hecho, las salidas de esta función F va a producir salidas pseudo aleatorias una vez que arreglamos la clave. Y si usted va un poco más profundo en el algoritmo, se puede ver claramente el siguiente hecho: si tenemos una función realmente aleatoria de correlación de caracteres n bits a n bit series entonces la salida de la función realmente aleatoria en 2 entradas diferentes x1 y x2 será completamente independiente entre sí. Por otro lado, para la función de que estamos considerando,, para cualquier y cualquiera. Eso significa que ahora tiene una prueba que siempre pasará o que siempre sostendrá para las muestras que son generadas por la función Fk. Y usted tiene una prueba, la misma prueba puede no ser siempre aplicable para las muestras generadas por una función verdaderamente aleatoria. Por lo tanto, esto básicamente nos da una intuición para diseñar un distinguidor que puede distinguir aparte el resultado de esta función F del resultado de una función verdaderamente aleatoria. Por lo tanto, aquí está la instancia del distinguidor: básicamente pide el valor de la función en la entrada x1, x2 que son diferentes. En respuesta, el retador responde con las salidas y1 y y2. La forma en que es y1 y y2 se habría generado según el juego de indistinguishabilidad de PRF es el siguiente: el retador básicamente habría lanzado una moneda si los lanzamientos de monedas es 0 entonces y1 y y2 son cadenas de n bits aleatorias. Mientras que, si el lanzamiento de moneda es 1 entonces y1 y y2 los resultados de la función por clave Fk para la clave uniformemente aleatoria conocida sólo para el retador. Y ahora el diferenciador puede actuar inteligentemente y básicamente distinguir si y1 y y2 son generados por una función verdaderamente aleatoria o una función pseudo-aleatoria simplemente realizando esta prueba. Se comprueba si x1 y x2 su XOR es el mismo que el XOR de y1 y y2. Si ese es el caso, entonces dice que, las muestras y1 y y2 son generadas por el mecanismo b = 1, es decir, presenta b ’ = 1. Mientras que si la prueba falla, y dice, las muestras y1 y y2 son generadas por el mecanismo 0, es decir, b ’ = 0. Ahora, analicemos cuál es la ventaja distintiva de este particular distinguidor. Así que primero analicemos cuál es la probabilidad de que nuestro distinguidor esté etiquetando correctamente las muestras y1 y y2 generadas por una función pseudoaleatoria de hecho siendo las muestras de una pseudo función aleatoria a saber las pr [D outputs b ’ = 1/b = 1]. Quiero decir que esta probabilidad es igual a 1. Porque si de hecho b = 1, es un caso, las muestras y1 y y2 son según las salidas de una función pseudo aleatoria. Y en ese caso, siempre pasará esta condición, la comprobación que el adversario o el distinguidor está realizando. Es por eso que la probabilidad 1, si b = 1, la estrategia de la distinguidora de hecho la salida b ’ = 1.Por otro lado, vamos a calcular la segunda probabilidad de que lo que es la probabilidad de que nuestro distinguido incorrectamente etiquetas muestras realmente aleatorias y1 y y2 siendo las muestras de una función pseudo aleatoria. Bueno, si b = 0, eso significa que nuestras muestras y1 y y2 son independientes entre sí. A continuación, la única manera en que el distinguido puede producir b ’ = 1 es que para la condición de y1 y y2esta condición uniformemente aleatoria o en otras palabras, la pr [D salida b ’ = 1/b = 0] = 1/2n.Así que nos da la ventaja distintiva del distinguido que hemos diseñado. Y si se toma la diferencia absoluta, es casi igual a 1 que hace con casi 100% de probabilidad. Si n se hace más grande, este 1 – 1/2ncasi se convierte en 1. Así que es por eso que con casi 100% de probabilidad un distinguidor puede distinguir aparte el resultado de la función clave F de la salida de una función verdaderamente aleatoria. Y es por eso que esta función F no es la pseudo función aleatoria. Así que eso significa diseñar una función pseudo-aleatoria es, de hecho, una tarea difícil. Veremos las construcciones candidatas más adelante. (Tiempo de Slide: 19 :56) Ahora vamos a definir algunas otras variantes de funciones pseudo-aleatorias con propiedades más fuertes y garantías de seguridad. Así que la primera variante se llama como la permutación pseudo aleatoria, que también se conoce como cifrado de bloques. Y aquí de nuevo tenemos una función por clave F. La única diferencia aquí es que la función por clave Fk debe ser ahora una bijection,. Esa es la única diferencia.Informalmente, la propiedad de seguridad que requerimos aquí es que requerimos que una vez que arreglamos la clave seleccionando una clave uniformemente aleatoria, y la clave no se conoce al atacante o a un distinguidor. Entonces, ningún distinguidor de tiempo polinomio puede distinguir aparte el comportamiento de salida o la naturaleza de esta función clave Fk de una correlación de bijection realmente aleatoria L bit strings to L bit strings, que de nuevo se puede modelar como un experimento de indistinguishabilidad. (Consulte Slide Time: 20 :53) Así que este es un experimento de indistinguishabilidad que llamamos como el experimento de indistinguishabilidad PRP y tenemos un bijection aquí, la bijección por clave. Queremos capturar la intuición de que ningún distinguidor debería ser capaz de distinguir el comportamiento de esta bijección por clave de una proyección verdaderamente aleatoria. Así que las reglas de los experimentos son las siguientes: consultas distinguisher para varias entradas de x de su elección y en respuesta el retador devuelve las respuestas. Las respuestas se preparan tirando de cualquiera de las siguientes reglas: se lanza una moneda y si la moneda es 0, entonces todas estas muestras y1, .., yq se generan básicamente ejecutando una permutación verdaderamente aleatoria. Mientras que si la moneda es 1 que todas estas muestras se generan mediante la ejecución de la función por clave F en una clave uniformemente aleatoria no conocida por el distinguido. El reto para el distinguidor es averiguar cuál es exactamente la forma en que se generan las muestras. Eso significa que tiene que salir un poco y nuestra definición de seguridad es que decimos que la bijección por clave F es un PRP, si la probabilidad de que cualquier distinguidor de tiempo polinómico pueda identificar correctamente la naturaleza de la muestra es superior limitada por ½ + negl (n). De manera equivalente diciendo que la ventaja distintiva de nuestro distinguidor debe estar limitada por una función insignificante. Por lo tanto, en esencia todo es lo mismo que para el caso de la función pseudo-aleatoria, la única diferencia es que ahora estamos básicamente en este caso de la función PRP es ahora una bijection. (Consultar Tiempo de Slide: 22 :34) Por lo tanto, es interesante ver la relación entre estas 2 primitivas función pseudo aleatoria y pseudo permutación aleatoria. Por lo tanto, en tu parte lateral izquierdo tienes una función pseudo aleatoria. La diferencia aquí es una función, que significa la longitud de entrada, la longitud de bloque y la longitud de salida podría ser diferente. Mientras que en el caso de la permutación pseudo aleatoria, es abijection. Eso significa, en el caso de las funciones pseudo-aleatorias, podría ser un muchos a un funcionariado mientras que en el caso de la permutación pseudo-aleatoria, es uno a una correlación. Dado que nuestro PRF puede no ser una bijección, es fácil ver que un PRF puede no ser un PRP. ¿Qué pasa al revés? Curiosamente, podemos demostrar que si el tamaño de salida L es mayor que igual a l, o en términos más genéricos, si el tamaño de salida es una función polinómica del parámetro de seguridad n entonces podemos ver una pseudo permutación aleatoria como una función pseudo aleatoria. Y la intuición para esta afirmación es la siguiente. Imaginamos que se nos da una permutación por clave. Por lo tanto, este Fk es una bijección por clave. Y ya que es un PRP seguro que significa que ningún distinguidor de tiempo polinómico puede distinguir aparte e interacción con esta función por clave Fk de una verdadera bijecación sin llave al azar, ese sentido tanto este Fk primitivo como FTRP son computacionalmente indistinguishable.Ahora, si comparamos una función verdaderamente aleatoria de correlación de cadenas de bits L a cadenas de bits L, cómo exactamente va a ser diferente de una permutación verdaderamente aleatoria, bien, la única diferencia entre una función verdaderamente aleatoria de una función verdaderamente aleatoria y una permutación verdaderamente aleatoria sin clave es que una función no necesita ser una bijección. Eso significa que hay posibilidades de colisiones que significa que podría ser una gran parte de una función donde varias x entradas podrían darle la misma y salida. Mientras que en el caso de la permutación verdaderamente aleatoria, no hay posibilidades de colisiones. Así que la única manera en que cualquier distinguidor puede distinguir entre la función verdaderamente aleatoria sin clave de esta bijección por clave Fk es la siguiente. Si sucede que nuestro distinguidor está interactuando con una función verdaderamente aleatoria sin clave y si es así sucede que algunas de sus consultas le da la misma salida y puede identificar claramente que está interactuando con una función verdaderamente aleatoria. Porque si está interactuando con este tipo de bijection Fk, las colisiones no van a suceder. Eso significa que podemos decir que condicionados en el caso de que nuestras consultas distinguisher nunca van a conducir a una colisión, entonces la interacción de nuestro distinguidor con Fk y FTRF es casi la misma que si el distinguidor está interactuando con Fk versus FTRP y ya que nuestra función Fk es una permutación por clave. Sabemos que esa interacción es computacionalmente indistinguible. Por lo tanto, la condición en el evento en nuestro distinguidor no es conseguir colisiones de sus consultas, la interacción de nuestro distinguido con la función verdaderamente aleatoria y la bijección por clave Fkare casi va a ser idéntica. Ahora la pregunta es ¿cuál es la probabilidad de que el distinguidor consiga una colisión haciendo preguntas al azar por medio de la función verdaderamente aleatoria?Si se está haciendo preguntas al azar q usando un resultado bien conocido, que llamamos como la paradoja del cumpleaños, que vamos a discutir más rigurosamente en el contexto de la función hash, podemos demostrar que las posibilidades de conseguir una colisión puede ser superior acotado por la probabilidad q2 /2L. Y es por eso que si su L es una función polinómica del parámetro de seguridad n, entonces claramente, esta es una cantidad insignificante. Eso significa que las posibilidades de que se produzcan colisiones son insignificantes. Y es por eso que podemos decir, o podemos tratar la bijección por clave Fk también como una función pseudo aleatoria. Así que esa es la relación entre las funciones pseudo-aleatorias y las permutaciones pseudo-aleatorias. (Consultar Tiempo de Slide: 27 :00) Ahora vamos a ver la variante final de las funciones pseudo-aleatorias que llamamos una fuerte pseudo-permutaciones aleatorias o SPRP, que es un tipo especial de permutación pseudo-aleatoria. Y básicamente aquí requerimos que la bijección por clave Fk debe ser indistinguible de una permutación verdaderamente aleatoria incluso si el distinguidor obtiene acceso oráculo a la inversa de la permutación. Lo que quiero decir con eso se demuestra en este experimento.Así, este experimento de indistinguishabilidad es llamado como Experimento. Y aquí el distinguidor ahora da acceso o respuesta para 2 tipos de consultas. Tiene acceso oráculo a los valores de las permutaciones, y también tiene acceso oráculo a la inversa de la permutación. Lo que quiero decir con esto es que puede pedir adaptativamente el valor de las permutaciones en varias x entradas de su elección y en respuesta, vuelve a obtener las correspondientes salidas y. Y también se permite pedir la inversa de la permutación de varios y valores de su choicey ver los valores x correspondientes. Y la forma en que el retador habría respondido es como sigue que habría lanzado una moneda uniforme al azar si el lanzamiento de moneda es 0, entonces todas estas consultas son respondidas por la evaluación de una permutación verdaderamente aleatoria. Eso significa que todos estos valores x son evaluados según esta permutación verdaderamente aleatoria. Y todas estas consultas inversas también son respondidas al consultar la inversa de esa correspondiente permutación verdaderamente aleatoria. Por otro lado, si la moneda lanza b = 1, entonces todos estos valores y todos estos valores inversos se calculan ejecutando la función por clave Fk e inversa de esa función por clave Fk. Y el desafío para el distinguidor como de costumbre es identificar si ha interactuado con oráculo que representa una permutación verdaderamente aleatoria o si está interactuado con un oráculo por clave. Nuestra definición de seguridad es que decimos que la función F es una fuerte permutación pseudo aleatoria si ningún polinomio tiempo de distinción puede identificar correctamente la naturaleza de su oráculo, excepto con probabilidad ½ + negl (n) o dicho en otras palabras, que la ventaja distintiva de nuestro distinguidor debe ser superior acotado por una cantidad insignificante. Resulta que, si tenemos una fuerte permutación pseudo aleatoria, entonces por definición, también es una pseudo permutación aleatoria. Y podemos dar construcciones donde la construcción será una pseudo permutación aleatoria. Esto significa que sólo será seguro cuando el adversario obtenga acceso a las consultas oracle para la salida de la función. Pero puede que no sea una fuerte permutación pseudoaleatoria que significa, tan pronto como proveemos el acceso del distinguido al oráculo inverso el adversario puede distinguir aparte. Eso significa que la fuerte permutación pseudo-aleatoria es más fuerte primitiva que la pseudo-permutación aleatoria. (Consulte Tiempo de Slide: 30 :01) Ahora, déjenme terminar esta conferencia dando un ejemplo de cómo construir un generador pseudo-aleatorio a partir de una función pseudo-aleatoria. Así que imagina que te dan un PRF seguro,. Ahora, usando esto puedo construir un generador pseudo aleatorio G, .Y básicamente, la forma en que opera este algoritmo G es la siguiente: toma la semilla k para el algoritmo G y crea la k para la función pseudo aleatoria F. Y la función pseudo aleatoria F ahora se evalúa en entradas conocidas públicamente 1 2 3 hasta t. Eso significa que las entradas de bloque que se utilizan dentro de este algoritmo G son públicamente conocidas que son 1 hasta t, es sólo la clave que no va a ser conocida por el distinguido. Y cada invocación de esta función F es con la misma clave, que es en realidad la entrada de nuestros generadores pseudo aleatorios. Y la salida del generador pseudo-aleatorio es básicamente la concatenación de las salidas individuales que se obtienen al ejecutar las instancias t de la función por clave Fk, esa es la forma en que nuestro pseudo generador aleatorio va a ser operado. Ahora queremos demostrar que si la función por clave Fk es un PRF seguro según nuestra noción de indistinguishabilidad, entonces el algoritmo G que hemos construido es también un PRG seguro. Según el juego de indistinguishabilidad PRG proporcionado, el número de veces que hemos invocado la función pseudo aleatoria Fk, a saber t, que es una función polinómica del parámetro de seguridad. Para probar eso, primero entendamos nuestra intuición. Básicamente consideramos otra versión del algoritmo G, a la que llamo como GTRG, donde cada instancia de la función por clave Fk se sustituye por una instancia de una función verdaderamente aleatoria que correlaciona cadenas de bits l a cadenas de bits L. Introdujimos el concepto de la función pseudo aleatoria; vimos la definición. E introdujimos varias variantes de funciones pseudo al azar como la permutación pseudo aleatoria, la fuerte permutación pseudoaleatoria, y hemos visto cómo construir un generador pseudo-aleatorio de forma segura y segura a partir de una función pseudo-aleatoria segura. ¡Gracias!

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