Loading
Study Reminders
Support
Text Version

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 of Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bangalore Lecture – 58 Zero-knowledge Protocols Part II Hola a todos, bienvenidos a esta conferencia. Sólo una rápida recapitulación. En la última conferencia habíamos comenzado nuestra discusión sobre protocolos de conocimiento cero. Así que en esta conferencia continuaremos nuestra discusión sobre cero protocolos de conocimiento específicamente vamos a introducir protocolos de conocimiento cero para la clase NP-completa. (Consulte la hora de la diapositiva: 00:44) Para ello introduciremos el problema de 3 colores y veremos un sistema de prueba de conocimiento cero computacionalmente seguro para un problema de 3 colores. (Consulte la hora de la diapositiva: 00:51)Por lo tanto, recuerde que en la última conferencia hemos visto cómo podemos especificar exactamente una relación. Por ejemplo, si recuerda la relación para el problema del imisomorfismo gráfico, la relación consistirá en pares (x, w) donde x es una instancia de problema. Así que en este ejemplo si consideramos un problema de isomorfismo gráfico que la instancia de x es básicamente la descripción públicamente conocida de 2 gráficos y el componente testigo correspondiente a esta instancia x será la correlación de isomorfismo entre el conjunto de vértice del primer gráfico al conjunto de vértices del segundo gráfico. Y de hecho si tenemos una x o una instancia de problema donde los 2 gráficos son isomorfos entonces deberíamos tener un testigo correspondiente w. En la última conferencia, hemos visto cómo podemos llegar con un sistema de prueba de cero conocimientos que permite al prover mostrar si una instancia x tiene un testigo correspondiente w disponible con el probador y no sin revelar nada sobre el testigo w. Pero resulta que la relación gráfica-isomorfismo no es una relación completa de NP y la siguiente pregunta retadora es ¿podemos tener un sistema de pruebas de conocimiento cero para cualquier relación completa de NP? Por lo tanto, para las personas que podrían estar preguntándose qué es exactamente NP-problema completo o NP relación completa es. Un problema x se llama un problema de NP-completo, si se le da un testigo w, podemos verificar si efectivamente el testigo w es un testigo correcto para la instancia de problema x y en cantidad polinómica de tiempo. Específicamente realizando el cálculo no determinista para la cantidad de tiempo polinómica. Este es el primer requisito. La razón por la que llamamos a tales problemas como NP-completo, el aspecto completo aquí denota que si tenemos algún otro problema y que pertenece a la clase NP entonces esa instancia de problema y se puede reducir a una instancia del problema x en la cantidad polinómica de tiempo. En ese sentido, este problema x será llamado como una relación completa de NP. Eso significa que si usted tiene una solución para resolver problemas de instancia x, eso significa que si usted puede encontrar testigos para la instancia de problema x en la cantidad polinómica de tiempo, entonces simplemente usando la reducción de las instancias de problemas de y a la instancia del problema de x, usted también puede obtener soluciones para sus instancias de problemas y. Por lo tanto, es una definición aproximada de la relación completa de NP. Por lo tanto, ahora estamos interesados en ver si podemos llegar a un sistema de pruebas de conocimiento cero para cualquier relación que sea NP completa. Por lo tanto, resulta que el gráfico-isomorfismo no es una relación completa de NP. (Consulte el tiempo de la diapositiva: 03:35) Por lo tanto, lo que vamos a hacer ahora es que vamos a ver un sistema de prueba de cero conocimientos para otro problema de cálculo que llamamos como problema de 3 colores que es un problema conocido de NP completo. Entonces, veamos primero lo que queremos decir con un gráfico 3-colorable? Decimos que un gráfico dado con n vértices es 3-colorable si cada uno de sus vértices se puede asignar uno de los colores de colores conocidos públicamente c1, c2, c3 de tal manera que ningún par de vértices adyacentes tienen asignado el mismo color. Eso significa que tenemos que colorear los vértices de tal manera que cada par de los puntos finales de cada borde debe tener diferentes colores. Si usted considera este gráfico por ejemplo, entonces este es un gráfico 3-colorable. Por lo tanto, por ejemplo si mi {c1, c2, c3} son {rojo, azul, amarillo} entonces podemos colorear los vértices en este gráfico utilizando estos 3 colores por una de estas asignaciones asignando estos colores a los vértices respectivos. Y ahora usted puede ver que no 2 vértices adyacentes a saber no 2 vértices adyacentes tienen asignado el mismo color aquí. Por ejemplo, si considero estos 2 vértices, son adyacentes en el sentido de que son los puntos finales de un solo borde dicen el mismo borde y están teniendo diferentes colores. De la misma manera si considero que este borde los puntos finales están obteniendo diferentes colores y así sucesivamente. Por otro lado, si considero el gráfico en su lado derecho entonces no es 3-colorable. Eso significa que no es en absoluto posible para colorear todos los vértices de este gráfico con sólo 3 colores satisfaciendo la condición de que ningún par de vértices adyacentes tienen asignado el mismo color. El problema de 3 colores o la relación de 3 colores es una relación completa de NP bien conocida y la entrada (x, w) en la relación de 3 colores se verá así. Por lo tanto, la instancia de x será la descripción pública de un gráfico, a saber, el número de vértices y el conjunto de vértices, y el conjunto de borde de la gráfica será públicamente conocido. Si de hecho esta instancia de x es decir este gráfico es 3-colorable entonces el testigo correspondiente w será la correlación de o la asignación del color {c1, c2, c3} al conjunto de vértice que yo llamo a. Y el color del testigo debe satisfacer la restricción de que si el borde (u, v) pertenece al conjunto de bordes, entonces el color asignado al nodo u y el color asignado al nodo v debe ser diferente. Si de hecho es posible llegar con tal asignación de color para la instancia de problema dada x entonces (x, w) será considerado como una entrada válida o satisfaciendo la relación 3-coloring. Si no podemos encontrar un testigo w, entonces corresponde a un x dado entonces que x no estará presente en la relación de 3 colores. (Consulte la hora de la diapositiva: 06:29)Así que ahora vamos a ver como sabe el sistema de pruebas de conocimiento para el problema de 3 colores. Así que, imagina que un Alice es el prover y Bob es el verificador. La entrada común para Alice y Bob es la descripción de un gráfico. Digamos, la entrada privada para el prover, a saber, Alice aquí es un 3-colorear del gráfico públicamente conocido, a saber, una asignación que mapea el vértice establecido en el juego de color {c1, c2, c3} y lo que Alice quiere demostrar a Bob que de hecho la gráfica dada es 3-colorable y ella tiene una asignación disponible con ella. Por lo tanto, el objetivo aquí es llegar con un sistema de pruebas de cero conocimiento que debe convencer a Bob que de hecho Alice conoce la correspondencia correspondiente sin revelar nada sobre la cartografía real. Al mismo tiempo, el sistema de pruebas de cero conocimiento debe asegurarse de que si el prover no conoce el 3-coloreado del gráfico dado o si el gráfico no es 3-colorable en el primer lugar entonces con muy alta probabilidad mientras que dar la prueba, Alice debe ser atrapado por Bob. Recordemos, que esta es su propiedad de solidez, el segundo requisito. Y la primera propiedad, a saber, Bob no debe aprender nada sobre el 3-colorear es la propiedad de cero conocimiento. (Consulte la hora de la diapositiva: 07:56)Así que ahora vamos a ver cómo será exactamente el sistema a prueba de cero conocimientos para el problema de 3 colores. Alice tiene el coloreado privado disponible con ella. Por lo tanto, lo que hace es que se permuta al azar el color que tiene disponible con ella, a saber, ver que tiene el mapa secreto de perdón que tiene el colorido original de la gráfica. Por lo tanto, lo que hace es que crea una permutación aleatoria del conjunto de colores. Por ejemplo, ella puede decir crear una permutación que somos rojos se mapea a azul, azul se correlaciona con el rojo y el tercer color permanece como lo es por la permutación. Básicamente, ahora lo que está haciendo es que está creando un nuevo 3-coloración del gráfico que está disponible con Bob con respecto a los nuevos colores correlacionados. Así que dondequiera que en el gráfico original que los vértices eran de color con el color rojo esos vértices en el nuevo color se asignará color azul porque el color rojo se correlaciona con el color azul. De la misma manera en el color viejo que los vértices se asignaron el color azul esos vértices en el nuevo 3-coloración se le asignará un color rojo y así sucesivamente. Todo esto que Alicia está haciendo a su final. Ahora una vez que Alice calcula el nuevo 3-coloración de la gráfica lo que hace es que mantiene los nuevos colores asignados de los vértices respectivos en una caja cerrada. Y aquí se bloquean las cajas y las comillas. Más adelante veremos qué son exactamente las propiedades que requerimos de esta caja cerrada y cómo se crea una instancia utilizando la primitiva criptográfica. Así que, a un nivel muy alto lo que significa estas cajas cerradas es que parece que en este ejemplo tenemos 6 vértices. Así que lo que Alice está haciendo es lo que sea el nuevo color asignado al vértice que se mantiene dentro de esta caja cerrada donde el bloqueado está disponible con Alice. Su caja cerrada en el sentido de que sin tener acceso a la llave, Bob no puede abrir la primera caja y ver cuál es el nuevo color del primer vértice. De la misma manera el nuevo color del segundo vértice está en el segundo cerrojazo el nuevo color del tercer vértice está en esa tercera caja cerrada y así sucesivamente. Bob ahora mismo no puede ver los colores que están disponibles en las cajas cerradas. Así que desde el punto de vista de los Bob, si de hecho Alice conoce el 3-colorante original entonces desde el punto de vista de Bob, Bob se sentirá como si ahora está viendo un nuevo 3-coloración del mismo gráfico existente públicamente conocido con la excepción de que en realidad no sabe cuáles son estos colores exactos ahora porque todos esos nuevos colores están en la caja cerrada. Por lo tanto, esta primera ronda de mensajes es como un compromiso de Alice a Bob. Eso significa que está diciendo que “ okay! Ahora he calculado un nuevo 3-coloring. No te mostraré el nuevo 3-coloring. Esos nuevos 3 colores están realmente disponibles en estas cajas bloqueadas. ” Ese es el compromiso de mi lado según el sistema de prueba de conocimiento cero. Ahora que Bob recibe el compromiso de Alice, lo que Bob hace es crear un reto para Alice. El reto es básicamente un borde aleatorio (i, j) del gráfico. Recuerde que Alice no va a saber qué es exactamente el borde aleatorio que Bob va a desafiar cuando Alice está cometiendo los nuevos colores en las cajas cerradas. Así que una vez que Bob escoge el borde aleatorio, desafía a Alice que “ por favor abre los nuevos colores en la caja i y la caja j. Quiero comprobar si de hecho son colores diferentes o no. Porque si en todo usted sabe el 3-colorante original entonces según su mapa el nuevo color también debe ser un 3-colorear. ” Y por lo tanto, ya que i y j son nodos adyacentes el nuevo color del nodo i y un nuevo color del nodo j debe ser idealmente diferente así que es lo que Bob está desafiando a Alice para mostrar. Y para responder al reto de Bob lo que Alice revela es que revela son las claves para la caja i y la caja j. Ahora necesito otra propiedad de la caja cerrada aquí. Así que recuerda, una de las propiedades de la caja bloqueada que lo que se mantenga dentro de la caja cerrada Bob no puede ver su contenido hasta y a menos que obtenga acceso a las teclas de la caja. La segunda propiedad que requiero de esta caja cerrada es que una vez que Alice ha guardado algo dentro de la caja cerrada y si más tarde, se le pide que revele el contenido de cualquiera de las cajas que más tarde no puede cambiar el contenido que ella ya ha mantenido dentro de ese cuadro en particular. Así que en este caso Bob está desafiando a Alice para abrir la caja i y la caja j y Alice se ve obligado a dar las claves para la caja i y la caja j. Según las propiedades de la caja de seguridad lo que haya cometido dentro de la caja de la ith y la caja de jth que no está permitido cambiar. Ahora Bob verificará. De hecho Bob tomará las llaves para la caja y la caja del jth, abrirá esas cajas para que sean los nuevos colores con respecto al nuevo 3-colorear para el gráfico. Bob considerará que es una ronda exitosa si encuentra que los nuevos colores del nodo i y el nodo j son diferentes, lo que debería ser idealmente el caso. Si este no es el caso, entonces la ronda es infructuosa y Bob detiene el protocolo aquí mismo. Así es como funciona una ronda del sistema de pruebas de cero conocimientos. Ahora para aumentar la confianza en esta prueba lo que Bob puede hacer es Bob puede repetir este proceso k número de veces de forma independiente donde en cada ronda Alice puede utilizar un diferente 3-colorear con respecto a las viejas técnicas de 3 colores. Eso significa que cada ronda ella va a recoger un mapa independiente del 3-coloring existente a un nuevo 3-colorear y de forma independiente Bob estará recogiendo nuevos retos (i, j) en cada ronda. Eso significa que no será el caso de que (i, j) que es escogido como el borde del desafío por el Bob seguirá siendo el mismo en todas las rondas. Ellos serán escogidos independientemente, y Alice no sabrá nada acerca de los desafíos para la siguiente ronda por adelantado y si todas estas rondas de k son exitosas Bob considerará que de hecho Alice conoce el 3-colorante real o original para el gráfico existente. (Consulte la hora de la diapositiva: 14:18)Para que sea un sistema a prueba de cero conocimientos. Ahora tratemos de hacer el análisis para el sistema de pruebas de conocimiento cero si satisface el requisito de corrección, solidez y conocimiento cero. Corrección o completitud, por lo que recordar la propiedad de completitud significa que si Alice y Bob son honestos y si de hecho Alice tiene un testigo para el gráfico es decir tiene el 3-colorante original entonces con alta probabilidad la prueba debe pasar y Bob debe ser convencido. Es fácil ver que si de hecho Alice conoce el 3-colorante original entonces de hecho en todas las rondas ella será capaz de convencer con éxito a Bob. Ella no fallará y por lo tanto cada ronda será exitosa, y Bob aceptará la prueba. (Consulte la hora de la diapositiva: 15:03)Ahora vamos a considerar la propiedad de solidez. Por lo tanto, recuerde que para la propiedad de la solidez tenemos que considerar el caso cuando el prover es corrupto. Prover es corrupto en el sentido de que o bien el gráfico no es 3-colorable, o podría ser el caso de que el gráfico es 3-colorable, pero Alice no sabe qué es exactamente el 3-coloración del gráfico original. Por simplicidad y sin pérdida de generalidad asumen que el gráfico no es 3-colorable. Así que ahora vamos a analizar cuál es la probabilidad de que cualquier ronda es exitosa con respecto a un Alice potencialmente corrupto que no sabe o que para un gráfico donde el gráfico no es 3-colorable. Resulta que si Alice es corrupta y Bob es honesto entonces la única manera en que Alice todavía puede pasar con éxito la ronda es cuando ella puede adivinar en avanzado el borde (i, j) que va a ser elegido como el desafío por Bob. Porque si el gráfico no es 3-colorable entonces Alice no puede crear ningún nuevo 3-colorear para el gráfico porque el gráfico no es 3-colorable en el primer lugar. Entonces la única manera que Alice puede ganar es que ella puede adivinar. Ella puede fingir en su mente que este podría ser el borde (i, j) que Bob puede desafiarme a mostrar. Por lo tanto, lo que puede hacer es que puede asignar un color arbitrario a los puntos finales del gráfico. De hecho, puede asignar los mismos colores a todos los nodos del gráfico excepto los puntos finales i y j. Porque Alice puede adivinar que este podría ser el borde que Bob me puede pedir que abra. ¿Qué puede hacer Alice por ejemplo ella puede adivinar que yo podría ser un decir 1 y j podría ser igual a cualquier cosa decir semántica número 3? Así, por ejemplo, puede imaginar que podría ser desafiada a mostrar los nuevos colores para el gráfico para el borde (v1, v3) o para los puntos finales v1 y v3. Lo que puede hacer es que la primera caja cerrada pueda mantener el color azul y la tercera caja cerrada que puede mantener el color amarillo y luego en todas las otras cajas solo puede guardar los mismos colores. Y si de hecho ella tiene suerte, entonces podría darse el caso de que de hecho se le pida que abra la primera caja cerrada y la tercera caja cerrada. Entonces, ella mostrará con éxito a Bob que “ Hey! He asignado diferentes colores al número de nodo v1 y al número de nodo v3. Pero cuál es la probabilidad de éxito de Alice adivinando de antemano que lo que será el azar (i, j) que Bob va a desafiar a Alice a abrir. La probabilidad de que Alice es capaz de adivinar con éxito el desafío aleatorio (i, j) no es nada más que 1 sobre el tamaño del conjunto de bordes. Aproximadamente el tamaño de borde establecido en el peor de los casos puede ser n2. Eso significa que la probabilidad de éxito de que la ronda sea exitosa está limitada por 1 sobre el conjunto de bordes a saber 1/n2. Recuerde que hay k tales rondas. Eso significa que la única manera de Alice sin siquiera saber el 3-colorear de la gráfica puede pasar con éxito todas las rondas de k es cuando para cada una de las k-rondas ella puede adivinar correctamente en avanzado que desafío (i, j) que Bob estará preguntando en cada ronda. Y la probabilidad de éxito de adivinar que en una ronda es 1/E. La probabilidad de que pueda hacerlo en todas las rondas k no es más que 1/ |E|k. Al establecer k para que sea suficientemente grande, se puede asegurar que esta cantidad 1/ |E|k se vuelve muy pequeña. De ahí que de manera definitiva en una de las k rondas Alice se pillará. Si ella es atrapada en cualquiera de estas rondas, Bob suspenderá el sistema de prueba y la reclamación de Alice será rechazada. Así que eso prueba la propiedad de la solidez. (Consulte el tiempo de la diapositiva: 19:07) Ahora vamos a analizar una propiedad de cero conocimientos y recordar la propiedad de cero conocimiento que tenemos para considerar el caso cuando nuestra prover es la honesta y de hecho, ella tiene un testigo que quiere ocultar de un verificador malicioso. Así que en este caso el verificador es el tipo corrupto y el objetivo del verificador es tratar de aprender sobre el original 3-coloring. Resulta que incluso si el verificador es corrupto, no aprende absolutamente ninguna información sobre el 3-coloring.Esto es porque lo que está viendo en la primera ronda. Él está viendo el nuevo 3-colorante, pero no el nuevo 3-colorante exacto, sino más bien el verificador está viendo los nuevos colores asignados a los vértices en el gráfico todos los cuales se mantienen en las cajas cerradas. Es sólo un par de cajas bloqueadas que es abierto por Alice en respuesta al desafío lanzado por nuestro verificador. Así que incluso si el verificador ve el color del nodo i y el nodo j, son los nuevos 3-coloring. Se corresponden con el nuevo 3-coloración y se aprende sólo los colores para el nodo y el nodo jth, pero no todo el nuevo 3-coloring. Recuerda en cada una de las rondas, Alice está escogiendo un fresco elegido independientemente. De esa manera ella está permutando al azar el 3-colorante existente y creando un nuevo 3-coloring. Así que eso significa que el nuevo 3-coloración en la primera ronda será independiente del nuevo 3-coloración en la segunda ronda y así el nuevo 3-coloración en la ronda kth será independiente de todos los nuevos 3-colorings en la ronda anterior. Eso significa en cada una de las rondas, el verificador sólo va a aprender que de acuerdo voy a ver los nuevos colores del nodo i y el nodo j que sé que van a ser distintos. Y es por eso que no revela nada sobre el 3-colorante original que estaba disponible con Alice. Así que eso prueba la propiedad de cero conocimiento. (Consulte la hora de la diapositiva: 21:01) Ahora, volviendo a la pregunta de ¿cuáles son las propiedades que necesitamos de los recuadros bloqueados? Como dije necesitamos 2 propiedades. Necesitamos básicamente la propiedad oculta. Es decir, si el prover es honesto, si Alice es honesto y si ella ha mantenido algunos contenidos dentro de la caja, entonces hasta y a menos que las llaves para esas cajas se dan a Bob, él no puede abrir y ver los contenidos que se mantienen dentro de la caja. Así que eso es lo que quiero decir con la propiedad oculta aquí. La propiedad de enlace significa que si Alice es corrupta entonces no debería ser el caso de que ella puso algo dentro de la caja, pero cuando se supone que abre la caja, ella puede darle la vuelta o ella puede cambiarlo a cualquier nuevo contenido. Así que es una propiedad vinculante y ahora sabemos muy bien cómo crear una instancia de este recuadro bloqueado, tanto con estas dos propiedades. Básicamente, podemos usar un esquema de compromiso para que eso signifique lo que Alice tiene que hacer es en cada ronda, ella tiene que calcular un nuevo 3-coloración y un nuevo color para los vértices. Ella tiene que comprometerse usando cualquier esquema de compromiso. Cuando Bob desafía a abrir los nuevos colores del nodo ith y el nodo jth, Alice tiene que dar la información de apertura correspondiente al compromiso de ith y el compromiso del jth. Por lo tanto, esto demuestra que ahora tenemos un 3-coloring. Ahora tenemos un sistema de prueba de conocimiento cero para el problema de 3 colores y su bien conocido que el problema de 3 colores es un problema de NP-completo que significa ahora que tenemos un sistema de prueba de cero conocimiento para cualquier relación NP. (Consulte la hora de la diapositiva: 22:31)Ahora vamos a ver la potencia del sistema a prueba de cero conocimientos. Lo que podemos hacer ahora es que podemos ver un marco muy agradable a saber, un compilador que puede compilar cualquier protocolo de seguridad pasiva en un protocolo seguro activamente. Imagine, tiene una tarea de computación distribuida decir f, puede ser cualquier tarea computacional abstracta. Se podría decir, por ejemplo, una tarea que involucra a múltiples partes 2 partes, 3 partes o decir 4 partes o cualquier n número de partes donde cada parte tiene alguna entrada decir x1, x2, x3, x4. Estoy tomando el caso en el que tengo 4 partidos. El objetivo de las partes es básicamente calcular f (x1, x2, x3, x4) y de tal manera que incluso si hay algunos malos en el sistema, ellos no aprenden nada sobre las entradas de x de los buenos otros que lo que pueden aprender de su propia entrada y la salida de la función. Este es un problema muy abstracto. Este problema también se llama como problema de cálculo de varias partes. La forma en que cualquier protocolo de cómputo multipartidista funcionará de la siguiente manera: las partes tendrán sus propios insumos y elegirán a alguna aleatoriedad local decir r1, r2, r3, r4 respectivamente y luego interactuarán entre sí según las instrucciones de este protocolo f. Al final obtendrán la función de salida y donde y = f (x1, x2, x3, x4) y por el momento imaginan que este protocolo f es pasivamente seguro. Es pasivamente seguro en el sentido de que si incluso hay un adversario que puede controlar o que puede ver la entrada y la aleatoriedad local de alguna fracción de estos n partidos y los mensajes que hayan intercambiado durante el protocolo, al ver sus entradas la salida y los mensajes que han recibido y han enviado durante el protocolo, el malo no aprende nada adicional sobre los insumos de los buenos. Así que eso es lo que quiero decir al decir que este protocolo f es pasivamente seguro. Ahora imagine que quiero compilar este protocolo. Recopilando este protocolo en el sentido quiero conservar el protocolo f y quiero asegurar que el protocolo siga siendo seguro aunque haya un adversario activo o un adversario malicioso. Adversario activo, eso significa que quiero compilar este protocolo en un portal maliciosamente seguro perdón por el error tipográfico debe ser maliciosamente seguro protocolo. Así que lo que quiero decir por seguridad maliciosa aquí es que incluso si los malos que están bajo el control de su adversario tratan de desviarse de las instrucciones del protocolo, no deben aprender nada sobre los insumos del buen tipo. No quiero diseñar un nuevo protocolo o un protocolo nuevo. Sólo quiero mantener el protocolo f que está garantizado para ser seguro contra el adversario pasivo. Entonces, ¿cómo podemos compilar el protocolo pasivamente seguro en un protocolo maliciosamente seguro? Esa es una pregunta que queremos saber la respuesta. Ahora queremos utilizar un sistema de prueba de cero conocimientos aquí. Por lo tanto, resulta que una manera genérica de convertir el protocolo pasivamente seguro en un protocolo maliciosamente seguro es el siguiente: si cada parte demuestra a cada otra parte que efectivamente está siguiendo las instrucciones del protocolo correctamente, entonces en presencia de un adversario malicioso, el protocolo f estará logrando su tarea. Ahora la pregunta es a qué nos referimos diciendo que una parte que demuestre a otra parte que de hecho está siguiendo correctamente la instrucción del protocolo. Con esto quiero decir que cada parte tiene que demostrar a cada otra parte que los mensajes que están enviando son de hecho con respecto a su aleatoriedad y su entrada según las instrucciones dadas por el protocolo f. ¿Cómo pueden las otras partes verificar si cada parte está siguiendo o no su instrucción de protocolo? Bien puede comprobar los mensajes que está enviando una parte en particular y el testigo de si esa parte está enviando o realizando su acción correctamente o no serán las partes de entrada y la aleatoriedad local. Por ejemplo, en este caso, si Alice quiere verificar si este tercero está siguiendo correctamente o no su instrucción de protocolo? entonces una manera de verificar que es Alice comprueba los mensajes que esta tercera parte está enviando. Junto con eso si este tercero muestra su entrada x3 y su aleatoriedad r3 que ha utilizado como parte de este protocolo f a Alice entonces de hecho Alice puede realizar la acción de este tercero, porque la descripción del protocolo se conoce lo que no se sabía era x3 y r3. Pero ahora x3 y r3 también se le da a Alice, por lo que ella misma puede calcular los mensajes que esta tercera parte se supone que enviar según el protocolo f. Si estos mensajes coinciden con los mensajes que, de hecho, este tercero ha enviado o comunicado durante la ejecución real del protocolo, esto demuestra que, de hecho, este tercero sigue su paso según el protocolo f. Al igual que esto, cada una de las partes puede verificar la acción de cada otra parte de si están realizando sus acciones según el protocolo f, si esa parte que envía revela su entrada y aleatoriedad local. Pero resulta que la entrada y la aleatoriedad local de cada partido no se pueden dar a otros partidos porque eso es lo que asegura la seguridad del protocolo f. Si aprendo la entrada y la aleatoriedad de cada otra parte, entonces no hay manera de que pueda garantizar la seguridad del protocolo f. Por lo tanto, resulta que la declaración que cada parte quiere probar a todas las demás partes, a saber, que estoy siguiendo la instrucción del protocolo, no es más que una instancia de una declaración de NP. Las instancias de problema son el conjunto de mensajes que he enviado, y quiero demostrarle que corresponde a estos mensajes que tengo alguna aleatoriedad y alguna entrada de tal manera que estos mensajes son efectivamente computados consistentemente según esas entradas y la aleatoriedad según la instrucción de protocolo f. Por lo tanto, lo que cada partido ahora tiene que hacer básicamente para convencer a otra parte de que de hecho está siguiendo la instrucción del protocolo tiene que probar básicamente una declaración de NP. Y curiosamente ahora tenemos un sistema de prueba de cero conocimientos para el problema de 3 colores que es una declaración de NP completa. Puesto que es una declaración de NP completa que significa cualquier instancia de problema NP o cualquier declaración NP puede ser reducida a una instancia de este problema de 3 colores. Eso significa que ahora podemos usar el sistema de prueba de cero conocimientos para el problema de 3 colores. Cada parte puede transformar una instancia de la declaración NP, es decir, que está siguiendo correctamente la instrucción de protocolo en una instancia del problema de 3 colores y nos da prueba de conocimiento cero para la existencia de 3-colorear y convencer a las otras partes que de hecho está siguiendo las instrucciones del protocolo. Si la prueba se cumple, eso significa que da la garantía de que cada parte está siguiendo las instrucciones del protocolo correctamente. Si la prueba no pasa, simplemente podemos detener el protocolo allí mismo. Así que, en ese sentido el sistema de prueba de cero conocimientos, te da un paradigma muy poderoso de compilar un protocolo pasivamente seguro en un protocolo maliciosamente seguro. Así que eso me lleva al final de esta conferencia. Sólo para resumir en esta conferencia hemos visto un sistema de prueba de conocimiento cero para el problema de los 3 colores. Y 3-el problema de la coloración es un problema conocido de NP-completo y hemos visto que el uso de un sistema de prueba de cero conocimiento podemos compilar cualquier protocolo de seguridad pasiva para cualquier tarea de computación distribuida en un protocolo que será seguro incluso contra un adversario malicioso.