prueba de conocimiento y su protocolo

8

En Zero-Knowledge Proof donde tomamos la analogía de Peggy (Prover) y Victor (Verifier):

  

En esta historia, Peggy descubrió la palabra secreta utilizada para abrir una puerta mágica en una cueva. La cueva tiene forma de círculo, con la entrada a un lado y la puerta mágica bloqueando el lado opuesto. Victor dice que le pagará por el secreto, pero no hasta que esté seguro de que ella realmente lo sabe. Peggy dice que le contará el secreto, pero no hasta que reciba el dinero. Ellos diseñan un esquema mediante el cual Peggy puede probar que conoce la palabra sin decírselo a Victor.

     

Primero, Victor espera fuera de la cueva cuando entra Peggy. Etiquetan los caminos izquierdo y derecho de la entrada A y B. Peggy toma al azar el camino A o el B. Luego, Victor entra en la cueva y grita el nombre del El camino que él quiere que ella use para regresar, ya sea A o B, elegido al azar. Siempre que ella sepa la palabra mágica, esto es fácil: abre la puerta, si es necesario, y regresa por el camino deseado. Tenga en cuenta que Victor no sabe qué camino ha tomado.

     

Sin embargo, supongamos que ella no sabía la palabra. Entonces, ella solo podría regresar por el camino nombrado si Victor le diera el nombre del mismo camino por el que había entrado. Dado que Victor elegiría A o B al azar, tendría un 50% de probabilidad de adivinar correctamente. Si tuvieran que repetir este truco muchas veces, por ejemplo, 20 veces seguidas, su posibilidad de anticipar con éxito todas las solicitudes de Victor se haría cada vez más pequeña.   Por lo tanto, si Peggy aparece de manera confiable a la salida de los nombres de Victor, él puede concluir que es muy probable que sepa la palabra secreta.

El siguiente método de verificación es suficientemente convincente para mí:

  1. Victor atraviesa los corredores A y B y se asegura de que no hay forma de ir al otro extremo (ya que Victor no tiene conocimiento de secretos, está convencido de que esto es cierto). p>

  2. Podría ir a la entrada del corredor A, pedirle a Peggy que pase por la entrada B y que venga desde el final de A. (Peggy lo hace y sale del final de A)

  3. Víctor también procederá por el otro lado donde se encuentra en la entrada de B y le pedirá a Peggy que venga al final de B después de pasar por A.

  4. Si Peggy puede hacer ambos 2 y 3, Victor está convencido de que Peggy conoce el secreto.

Siento que este método es incorrecto y me pregunto por qué. Entonces, ¿por qué se preferiría el método clásico a esto? ¿Cuáles son las debilidades de este método?

    
pregunta vaasu 02.07.2011 - 17:47
fuente

3 respuestas

8

La discusión en Wikipedia vinculada a Kerrek SB está cerca, pero tal vez no sea muy clara.

Digamos que Peggy logra convencer a Victor de que conoce el secreto. ¿Puede Victor convencerte de que Peggy conoce el secreto? En una prueba de conocimiento cero, la respuesta debería ser no. Víctor no solo gana el conocimiento "cero" sobre el secreto en sí, sino que tampoco posee un conocimiento transferible sobre quién conoce el secreto.

Como se mencionó en el enlace, considere el escenario en el que Victor graba la sesión para usted. En el primer protocolo, la cinta de video podría ser falsificada simplemente haciendo que Victor y Peggy estén de acuerdo en los desafíos "aleatorios" que Victor le dará a Peggy antes de tiempo. Como no tiene forma de saber si Victor le dijo a Peggy los desafíos o no, la cinta de video no tiene ningún valor y no lo convence de nada.

Sin embargo, en su protocolo modificado, una cinta de video sería convincente. Por lo tanto, se filtra más de conocimiento "cero". ¡Ahora tener la capacidad de transferir conocimiento no siempre es malo! En algunas aplicaciones, desea utilizar algo que es conocimiento cero en todos los aspectos, excepto que puede transferir conocimiento (se denominan pruebas de conocimiento cero no interactivas).

Los comentarios en Wikipedia luego tratan con un verificador que es deshonesto (es decir, si Victor puede probar que generó su desafío después de que Peggy ya está en uno de los caminos, tal vez lanzando la moneda en el video) y manteniendo el cero. -conocimiento con acceso blackbox rebobinable al verificador (que es donde la analogía se rompe un poco). Sin embargo, no es necesario considerar el caso deshonesto para distinguir entre los dos protocolos en la publicación original.

    
respondido por el PulpSpy 05.07.2011 - 20:59
fuente
7

El problema es que la analogía de la cueva no puede llevarse tan lejos. Hay una discusión sobre esa pregunta exacta , eche un vistazo. La parte de "conocimiento cero" requiere que la prueba no se pueda distinguir de una simulación por un verificador de trampa.

    
respondido por el Kerrek SB 02.07.2011 - 18:08
fuente
2

Tomando la analogía que es muy simple, no sabe qué camino tiene la puerta mágica y cuál es la contraseña. Ah, y solo se le permite tomar un camino hasta el final. Así que todavía no puede pasar.

Bueno, es una extensión de la analogía, la que escuché, hay dos puertas mágicas y Alice conoce el pase a las dos que tienen contraseñas diferentes, esto está más cerca del algoritmo real, y hace que la analogía sea mucho más sentido. Esto, por supuesto, me da una idea para un rompecabezas de laberinto de cristal donde, fundamentalmente, tienen que resolverlo con esta analogía.

    
respondido por el ewanm89 03.07.2011 - 12:56
fuente

Lea otras preguntas en las etiquetas