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

    +

Fundaciones de la criptografía Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bengaluru Lecture – 57 Zero Knowledge Protocols Part I (Consultar diapositiva: 00:30) Bienvenido a esta conferencia. Por lo tanto, en esta conferencia continuaremos nuestro debate sobre protocolos interactivos en los que deseábamos resolver un problema mayor en lugar del problema de la comunicación segura. Así que en esta conferencia introduciremos protocolos de conocimiento cero. Veremos primero parte de la motivación en los protocolos de cero conocimiento y una definición formal. Y veremos un protocolo de cero conocimientos para el problema del isomorfismo gráfico. (Consulte la hora de la diapositiva: 00:52)Ahora vamos a empezar por intentar comprender una motivación para las pruebas de cero conocimientos. Así que imagina que tenemos dos partidos Alice y Bob y decir que Alice había elegido dos números primos al azar p y q dicen cada uno de tamaño de 512 bits y ha calculado el producto de p y q para obtener el producto N y ella va y afirma a Bob que sé los principales factores de N. Ahora si de hecho ella quiere demostrar a Bob que ella sabe que los principales factores de N entonces una manera simple de demostrar que es para mostrar los valores de p y q. Porque si los valores de p y q se dan a Bob, el propio Bob puede multiplicar esos dos números y ver si sus partidos N o no. Pero eso es lo que nosotros llamamos como prueba en claro. Porque p y q son aquí testigo de Alice para la declaración de que ella sabe los principales factores de N. Una manera de demostrar su declaración es mostrar a los testigos en claro, pero lo que un protocolo de cero conocimiento va a hacer aquí es su ir a permitir a Alice convencer a Bob que de hecho ella sabe los principales factores de N sin mostrar realmente los testigos a saber p, q. Porque p y coma q podría llegar información secreta para Alice y en todo este proceso de prueba de cero conocimientos básicamente Alice termina de convencer a Bob que sabe p y q sin revelar realmente p y q. Ahora es posible que te estés preguntando dónde es útil esta p y q. Por lo tanto, si usted recuerda en el contexto del criptosistema de claves públicas RSA, el valor N no es más que una parte de la clave pública de Alice y p, q no son más que parte de una clave de descifrado. Así que si de hecho Alice quiere convencer a Bob que N es su clave pública y ella sabe la clave secreta correspondiente sin mostrar los componentes relacionados con la clave secreta a saber p y q; ella podemos conveniencia Alice mediante el uso de esta prueba de conocimiento cero. (Consulte la hora de la diapositiva: 02:45) Veamos otra motivación. Imagine Alice tiene dos gráficos aquí. Y pictorialmente estos dos gráficos se dibujan de una manera diferente. Los nombres de vértice son diferentes; los nombres de borde son diferentes. Pero resulta que la información sabia que las dos gráficas son isomorfas o estructuralmente las gráficas son isomorfas entre sí y lo que quiero decir por gráficos isomorfos aquí es que, si se tienen en cuenta estos dos gráficos entonces para estos dos gráficos existe una bijección desde el conjunto vértice del primer gráfico hasta el vértice del segundo gráfico. Y esa bijección tiene la propiedad de que si hay un borde entre los nodos u y v en el primer gráfico, entonces en el segundo gráfico existe un borde entre el conjunto de u correlacionados y el conjunto de v correlacionados. Y esta es una declaración if y only if. Eso significa de la misma manera que si usted tiene un borde entre el vértice u vértice mapeado y el v vértice mapeado en el segundo gráfico entonces existe un borde entre el u vértice y el v vértice en el primer gráfico. Así que en ese sentido estos dos gráficos son isomorfos a pesar de que pictorialmente se ven diferentes. Así que imagine que Alice tiene dos gráficos isomorfos, por lo que hace la descripción de los dos gráficos disponibles para Bob y ella hace la declaración que dice a Bob que estos dos gráficos son isomorfos. Así que esa es la declaración. De nuevo Bob no puede comprobar directamente si los dos gráficos son isomorfos o no y verificar la reclamación de Alice porque es poco práctico para verificar si dos gráficos son isomorfos o no en la ausencia de la bijección que está disponible o que correlaciona el conjunto de vértice del primer gráfico con el conjunto de vértices del segundo gráfico. Así que una manera para que Bob verifique la declaración de Alice es que puede preguntar a Alice que por favor dame tu testigo, a saber, la bijección Π. Si usted me da la bijección Π entonces puedo verificar si de hecho para cada borde en el gráfico, el primer gráfico los vértices correlacionados correspondientes también constituyen un borde en el segundo gráfico y así sucesivamente. Pero eso será una prueba en claro. Así que lo que una prueba de conocimiento cero o un protocolo de conocimiento cero permitirá a Alice hacer es; permitirá a Alice convencer a Bob que de hecho estos dos gráficos son isomorfos sin mostrar realmente el testigo, a saber, la bijección Π. (Consulte la hora de la diapositiva: 05:10) Así que significa que una prueba de conocimiento cero es una especie de protocolo interactivo entre dos entidades que un prover y un verificador que permite a un probador probar una sentencia para verificar sin mostrar realmente nada sobre el testigo subyacente. Así que ahora vamos a formalizar esta declaración. Así que imagine R es una relación binaria y la interpretación de esta relación es la siguiente. Así que si tengo un par (x, w) presente en esta relación R que debe ser interpretado como si x es una instancia de algún problema computacionalmente difícil. Cuando digo el problema computacionalmente difícil informalmente significa en la cantidad de tiempo de la poli no se sabe cómo resolver ese problema. Pero una vez más que es una declaración muy floja, pero que es una comprensión intuitiva del problema computacionalmente difícil aquí y una w aquí es una solución para esa instancia de problema x es decir usted puede considerar la w para ser un testigo para la instancia de problema x. Así que para entender esta relación R vamos a considerar la relación del isomorfismo gráfico aquí. Por lo tanto, un par (x, w) en la relación imoromórfica gráfica RGI se verá como este {(G1 = (V1, E1), (G2 = (V2, E2))} y la interpretación de los elementos presentes en esta relación de isomorfismo del gráfico debe ser la siguiente. Así que la primera parte aquí es la descripción de los dos gráficos, es decir, es una instancia de problema. Eso significa que alguien quiere probar o refutar estos dos gráficos son isomorfos. Y el testigo correspondiente no es más que el isomorfo o la bijección desde el vértice del primer gráfico hasta el vértice del segundo gráfico. Así, por ejemplo, si usted considera estos dos gráficos aquí, estos dos gráficos son de hecho isomorfos. Así que el primer gráfico es su gráfico G1 y el segundo gráfico aquí es su gráfico G2. Así que ese es el componente x de cualquier x, w que podría estar presente en esta relación de isomorfismo gráfico. Y un testigo correspondiente con respecto a este gráfico G1 G2 específico no es más que la bijección del conjunto vértice del gráfico G1 al conjunto de vértice del gráfico G2 y así sucesivamente. (Consulte la hora de la diapositiva: 07:18)Por otro lado, si considero que estos dos gráficos son mi G1 y G2, resulta que estos dos gráficos no son isomorfos entre sí y como resultado si este es mi candidato x entonces para este candidato x no tengo ningún candidato con tal que x, w pertenece a esta relación RGI, a la derecha. Eso significa que sólo aquellas x, w estarán presentes en r donde la instancia de x tiene un testigo correspondiente w. Si para una instancia x no existe ningún testigo w de tal manera que x, w satisface esa relación entonces decimos que, (x, w) no está presente en la relación R. (Consulte el tiempo de la diapositiva: 07:57) Así que ahora vamos a la definición formal de pruebas de conocimiento cero. Así que se nos da alguna relación públicamente conocida que tendrá elementos de la forma x, w donde x es una instancia de algún problema computacionalmente difícil y w es la solución o el testigo para esa instancia. A continuación, un sistema a prueba de cero conocimientos para la relación R consiste en dos algoritmos de tiempo de poli dos algoritmos aleatorios uno para el prover y uno para el verificador. La entrada para el prover será un par x, w y el objetivo del prover es demostrar que sabe una w tal que x, w pertenece a r mientras que la entrada para el algoritmo del verificador será la instancia del problema x. Y el objetivo del verificador es verificar si de hecho Alice conoce una w de tal manera que x, w pertenece a R o no. Por lo tanto, en el sistema de prueba de cero conocimientos, el probador enviará mensajes o interactuará con el verificador en el que los mensajes para el prover se computarán según el protocolo P y la aleatoriedad interna que utiliza el prover. Y al final del prover de protocolo no se produce nada mientras el algoritmo del verificador interactúe con el probador donde los mensajes del verificador se computarán según el algoritmo V y la aleatoriedad interna elegida por el verificador y el verificador va a aceptar o rechazar la salida. Aceptar significa que acepta el hecho de que Alice conoce algún testigo, rechazar significa que no cree en la declaración de Alice. Ahora, ¿cuáles son las propiedades que requerimos de un sistema a prueba de cero conocimientos, la primera propiedad es la propiedad de completitud que exige que si tanto el prover como el verificador son honestos y si efectivamente prover conoce una x, w de tal manera que x, w pertenece a R y tanto el prover como el verificador participa, realiza todas sus acciones según el protocolo P y V. Entonces con una probabilidad muy alta la salida del verificador debe ser aceptado. Esto significa que el verificador debe aceptar la declaración de prover. La segunda propiedad es la propiedad de Soundness que consideramos con respecto a un prover corrupto. Así que lo que requerimos aquí es que si mi prover es corrupto y no tiene una x, w tal que x, w pertenece a la relación R entonces independientemente de sin embargo ella participa en el protocolo la salida del verificador debe ser rechazada. Eso significa un prover malintencionado que no tiene x, w o que no tiene un testigo de tal manera que x, w pertenece a la relación R con muy menos probabilidad el prover debe ser capaz de convencer al verificador de que conoce el testigo w. Eso significa que con una probabilidad muy alta el verificador debería ser capaz de atrapar un prover malintencionado. Ese es el requisito de solidez. (Consulte el tiempo de la diapositiva: 10:50)Y la tercera propiedad es una propiedad de cero conocimientos que es con respecto a un verificador corrupto y un probador honesto. Por lo tanto, la propiedad de conocimiento cero exige que si el prover es honesto y el verificador es corrupto entonces, independientemente de la forma en que el algoritmo del verificador o el verificador participa en este protocolo, el verificador no aprende absolutamente nada sobre el testigo w que está disponible con el prover. Así que aquí no hay nada en la cita, sin comillas “ nada ”. No es formal. Lo que queremos decir exactamente por nada se aprende sobre el testigo. Si usted quiere poco más formal podemos decir que, decimos que el protocolo tiene la propiedad de cero conocimiento si la distribución de probabilidad de las transcripciones vista por el verificador es independiente del testigo real que está disponible con el prover. Una vez más, no estoy demostrando formalmente qué significa exactamente decir que la distribución de probabilidad de las transcripciones vista por el verificador es independiente de w. El formalismo real es poco sutil e involucrado. Así que no vayamos al detalle real, pero para su comprensión pueden imaginar que el verificador no debe aprender nada sobre el testigo si el verificador es corrupto al participar en este protocolo. (Consulte el tiempo de la diapositiva: 12:06)Así que ahora vamos a ver un sistema de prueba de conocimiento cero para un problema de isomorfismo gráfico. Por lo tanto, la entrada común que está disponible tanto para el prover como para el verificador es una instancia de un problema del isomorfismo gráfico, a saber, la descripción de dos gráficos. Y Alice quiere convencer a Bob o al verificador aquí el prover; el Alice es prover y el Bob es verificador. Así que Alice quiere demostrar a Bob que de hecho estos dos gráficos son isomorfos. Y afirma que conoce el isomorfismo entre estas dos gráficas, eso significa que afirma que tiene una entrada privada que mapea el vértice del primer gráfico al vértice del segundo gráfico con respecto al cual estos dos gráficos son isomorfos y el objetivo aquí es diseñar un protocolo que permite a Bob saber si efectivamente estos dos gráficos son isomorfos o no sin realmente aprender el isomorfismo. Y debe ser sonido en el sentido de que si el prover no conoce el isomorfismo o los gráficos no son isomorfos en el primer lugar entonces ella debe ser atrapado mientras que da la prueba con una probabilidad muy alta. (Consulte la hora de la diapositiva: 13:07)Así que vamos a ver cómo se diseña exactamente el protocolo de cero conocimientos aquí. Así que este rectángulo de rectángulo he resaltado la información pública para que la información pública disponible tanto para Alice y Bob son la descripción de los dos gráficos. Y la información privada disponible con Alice, el prover es el testigo Π o la correlación desde el vértice del primer gráfico hasta el vértice del segundo gráfico. Así que la primera ronda del protocolo de cero conocimientos es la siguiente. Así que lo que hace Alice es, crea una copia isomorfa al azar del segundo gráfico G2. Y eso es muy fácil de hacer, lo que tiene que hacer es que básicamente tiene que llegar con una permutación aleatoria decir σ mapear el conjunto vértice del segundo gráfico y los vértices correlacionados resultantes le va a dar otra gráfica H. Así que una vez computa una copia isomorfa aleatoria del segundo gráfico envía la descripción de la copia isomorfa aleatoria del segundo gráfico a Bob. Así que eso es una especie de compromiso. Así que hago hincapié en que σ se elige al azar y sólo se conoce a Alice aquí. Ahora lo que Bob hace es, Bob escoge una moneda al azar y con probablemente 1/2 la moneda al azar podría dar la salida 1 o con probabilidad 1/2 podría dar la salida 2. Y ahora lo que Bob ’ s reto es, Bob desafía a Alice para mostrar un isomorfismo entre el gráfico de la ith y el nuevo gráfico H que Alice ha cometido. Así que si i = 1 entonces básicamente Bob está desafiando a Alice para mostrar un isomorfismo entre el gráfico G1 y el nuevo gráfico H mientras que si yo = 2 entonces Bob está desafiando a Alice para mostrar un isomorfismo entre el gráfico G2 y el nuevo gráfico H. Estrés aquí que cuando Alice estaba cometiendo la gráfica H, ella no sabe bien de antemano si será desafiada a mostrar un isomorfismo entre G1 y H o entre G2 y H. Ella no lo sabe con antelación. Desde aquí el punto de vista con probabilidad 1/2 ella podría ser desafiada a mostrar un isomorfismo entre G1 y H y con probabilidad 1/2 ella podría ser desafiada a mostrar un isomorfismo entre G2 y H. Ahora una vez Bob lanza el desafío que Alice tiene que responder. Y la respuesta será diferente dependiendo de si i = 1 o si i = 2. Namely si el reto es i = 2 que significa que si Alice es desafiada a mostrar el isomorfismo entre G2 y H entonces ella simplemente puede suministrar la bijection σ que ha utilizado para calcular H a partir del gráfico G2. Así que esa será su respuesta. Así que estoy denotando la respuesta por ρ aquí. Así que ρ será; la respuesta ρ no será más que el σ de correlación si i = 2. Por otro lado, si Bob ha desafiado a Alice para mostrar un isomorfismo entre el gráfico G1 y H, entonces básicamente Alice puede responder componiendo la correlación Π que fue su testigo con el σ de correlación secreta que ha elegido para pasar del gráfico G2 a H. Porque si componemos Π y σ entonces utilizando Π de G1 llegamos a G2, Alice viene de G1 a G2 y, a continuación, vuelve a componer con el σ de correlación de G2 que puede ir al gráfico H. Así que eso significa que la forma de ir de G1 a H es componer la correlación Π con el σ de correlación.. Y si, de hecho, Alice conoce a Π debe poder componer Π y σ y puede responder con esta respuesta ρ. Ahora Bob tiene que verificar si Alice ha respondido correctamente o no. Así que lo que Bob comprueba es que sabe que Alice se supone que muestra un isomorfismo entre el gráfico de ith y H y la respuesta de Alice es la correlación ρ y Bob sólo tiene que verificar si realmente el gráfico Gi lleva a Bob al gráfico H según esta correlación ρ o no. Si es entonces Bob está convencido de que Alice ha pasado con éxito esta ronda de lo contrario Bob dice que Alice ha fallado en esta ronda. Y lo que Bob va a hacer es Bob va a repetir todo este proceso, es decir, Alice comprometiendo algo Bob desafiante y Alice de nuevo enviando la respuesta k número de veces y para cada una de estas rondas Alice tiene que escoger el compromiso aleatorio H que significa que va a ser recién elegido el gráfico H para cada ronda o cada iteración y de la misma manera Bob estará eligiendo al azar los retos i para cada ronda, independiente de cada ronda anterior. Eso significa que no será el caso de que en cada ronda Bob estará escogiendo i = 1 o i = 2. Y el verificador Bob va a la salida 1, es decir, dirá que de hecho Alice conoce la correlación secreta Π, si todas las rondas son exitosas desde el punto de vista de Bob, eso significa que en todas las rondas Alice ha enviado con éxito las respuestas ρ. Mientras que si alguna de las rondas Alice falla, entonces Bob produce el rechazo. Eso significa que Bob rechaza la afirmación de Alice. Ese es el protocolo de cero conocimientos aquí para el problema del isomorfismo del gráfico. (Consulte la hora de la diapositiva: 18:47) Ahora vamos a hacer el análisis, vamos a ver si este protocolo del isomorfismo del gráfico satisface los requisitos de corrección, solidez y conocimiento cero o integridad, solidez o conocimiento cero. Así que la propiedad de completitud o la propiedad de corrección aquí es sencilla, si de hecho Alice es honesta que significa que conoce la correlación secreta Π entre el gráfico G1 y G2 y si está siguiendo las instrucciones de protocolo honestamente y si el verificador también es honesto, entonces cada una de la ronda tendrá éxito. Porque no sabe si Bob challenges con i = 1 o con i = 2. Alice siempre será capaz de responder con éxito con la correlación correcta ρ y por lo tanto todas las rondas tendrán éxito. (Consulte el tiempo de la diapositiva: 19:30) Ahora vamos a analizar la propiedad de solidez aquí y recordar la propiedad de solidez que tenemos para considerar el caso cuando Alice es potencialmente corrupta. Y no sabe la cartografía entre G1 y G2 o en primer lugar puede que no haya ningún mapeo entre G1 y G2 mostrando que son isomorfos y por lo tanto, ya que está corrompida podría no seguir el protocolo, y recordar como por el protocolo se supone que envía una copia isomorfa de G2 en cada ronda, pero ella no lo hace también. Así que para la solidez tenemos que analizar que con cuánta probabilidad puede engañar con éxito a pesar de que no sigue el protocolo y no tiene el isomorfismo entre el gráfico G1 y G2 disponible con ella. Resulta que la única manera en que puede hacer trampa en una ronda es adivinar de antemano cuál será el desafío del Bob honesto. Porque si ella puede adivinar correctamente de antemano si i = 1 o si i = 2 entonces en el primer lugar ella misma puede crear una copia isomorfa de Gi. Por lo tanto, recuerde que según los pasos del protocolo que debía crear una copia isomorfa de G2 es decir, H debe ser una copia isomorfa de G2. Pero si Alicia es corrupta puede que no sea capaz de seguir el protocolo, ella puede tratar de adivinar de antemano que podría ser 1, podría ser 2 y con respecto a esa conjetura ella puede crear una isomorfa de esa gráfica Gi. Y si de hecho su conjetura es correcta, ella será capaz de enviar con éxito la respuesta ρ. Pero la probabilidad de que ella pueda adivinar correctamente si voy a ser 1 o si voy a ser 2 es 1/2. Eso significa que con sólo probabilidad 1/2 ella puede hacer trampa en una ronda y terminar exitosamente pasando esa ronda. Pero ya que estamos repitiendo este proceso k número de veces, correcto porque recordar a Bob no está convencido sólo por hacer este protocolo una vez; dependiendo de la confianza que quiera estar en la reclamación de Alice, puede repetir el protocolo k número de veces. Entonces, ¿cuál es la probabilidad de que en cada una de la iteración k una mala Alicia que no conoce el isomorfismo entre G1 y G2 termine exitosamente pasando todas las rondas de k. La probabilidad de que tenga éxito en la primera ronda es 1/2; la probabilidad de que tenga éxito en la segunda ronda es también 1/2. Y recuerde, la probabilidad de éxito; conseguir éxito en la segunda ronda es independiente de la probabilidad de tener éxito en la primera ronda. Porque en la segunda ronda también el reto de Bob será independiente de los retos que Bob ha escogido en la primera ronda. Así que es por eso que la probabilidad de que Alice tenga éxito en la segunda ronda es 1/2 y como que la probabilidad de que Alice es capaz de engañar a Bob en todas las rondas correctamente adivinando de antemano el desafío de Bob en todas las rondas es 1/2 * 1/2 * 1/2 * 1/2 … k tiempos que no es nada más que 1/2k. Así que si k es significativamente grande decir imagina k = 100 y si un Alice no conoce el isomorfismo entre G1 y G2 entonces definitivamente existe al menos una de las rondas con muy alta probabilidad donde Alice será capturado y por lo tanto Bob rechazará la declaración de Alice. El único caso que Alice tendrá éxito en todas las rondas es cuando ella es capaz, cuando ella tiene la suerte de adivinar el reto de Bob en todas las rondas de k por adelantado que puede suceder sólo con probabilidad 1/2k que es muy pequeño si k se vuelve significativamente grande. (Consulte la hora de la diapositiva: 23:11)Ahora vamos a tratar de entender la propiedad de cero conocimientos aquí donde; recuerde que para el conocimiento cero tenemos que considerar el caso en el que Alice es honesta y Bob es corrupto, el verificador está corrupto. Y el objetivo del verificador corrupto es analizar la transcripción del protocolo y aprender la permutación secreta Π que mapea el gráfico G1 al gráfico G2, es decir, el isomorfismo entre el gráfico G1 y G2. Resulta que en cada ronda el verificador corrupto no aprende nada acerca de la correlación Π, porque si el reto de Bob es i = 2 entonces la respuesta que Alice lanza es la correlación del gráfico G2 a H que no revela nada acerca de una correlación secreta Π. Por otro lado, si el verificador desafía a Alice con i = 1, en ese caso Alice responde con la composición de la correlación secreta Π con otra correlación seleccionada al azar σ. Y dado que σ se elige de forma aleatoria; en la iteración puede imaginar que σ actúe como algún tipo de máscara aquí, porque desde que σ se ha elegido al azar y Π es cualquier forma de elección aleatoria y disponible sólo con Alice; esta correlación compuesta global σ no revela nada sobre la correlación secreta Π porque el enmascaramiento aquí es el σ de correlación secreta elegido al azar por Alice. Y puesto que σ se elige de forma aleatoria en cada iteración independientemente de todas las iteraciones, incluso si un prover malicioso sigue desafiando a Alice con i = 1, no podrá obtener información sobre la correlación secreta Π, y esto se mantiene incluso si el verificador no está limitado de forma computacional. Así que en ese sentido un Bob malicioso no aprende nada sobre el testigo secreto Π disponible con Alice. Así que eso demuestra que este sistema de prueba de cero conocimientos que hemos diseñado para el problema del isomorfismo gráfico efectivamente satisface todos los requisitos de un sistema de prueba de conocimiento cero para un problema de isomorfismo gráfico. Así que eso me lleva al final de esta conferencia. Sólo para resumir en esta conferencia hemos introducido el problema del sistema de prueba de cero conocimientos, hemos establecido formalmente sus requisitos, a saber, la completitud, la solidez y el requisito de conocimiento cero y también hemos visto una instancia