Problema del gran maestro

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 20 de mayo de 2021; la verificación requiere 1 edición .

El problema del gran maestro de ajedrez es una de las formas en que se abusa de la prueba de conocimiento cero . Es también uno de los problemas de la teoría de juegos . [1] El resultado de este problema es un engaño llevado a cabo por la mafia . El problema es que un atacante puede demostrar la propiedad del secreto sin poseerlo realmente o, en otras palabras, puede imitar a la persona que realmente posee el secreto.

Problema

Un ejemplo de este problema es la historia de una niña que demostró [1] juego simultáneo contra dos grandes maestros. Su metodología fue la siguiente:

Alice está jugando contra dos grandes maestros que están en habitaciones diferentes y no se dan cuenta de la presencia del otro.
Alice anota los movimientos de un gran maestro y los duplica en un juego con otro, luego anota los movimientos del segundo y repite con el primero, y así sucesivamente.

Esto continúa de esta manera hasta que pierde un juego, ganando el segundo, o hasta que ambos juegos terminan en empate. Usar este engaño te permite engañar a cualquier ajedrecista y ganar gracias a algo diferente a tu propio conocimiento.

Esta técnica de engaño se puede utilizar contra la prueba de identidad de conocimiento cero . [2]

Posible solución

Una posible solución a este problema fue propuesta por Thomas Beth ( 1949 - 2005 ) e Ivo Desmedt . Para eliminar la posibilidad de hacer trampa, propusieron el siguiente algoritmo . [3]

Los grandes maestros quieren estar seguros de que este tipo de trampa no ocurrirá y los oponentes jugarán utilizando solo su conocimiento, sin la ayuda de nadie más. Para ello, todos los ajedrecistas seguirán el siguiente protocolo:

Antes del inicio de la partida, los ajedrecistas acuerdan un valor específico de tiempo , expresado en segundos. También están de acuerdo en quién juega con blancas y quién juega con negras. Por conveniencia, denotamos el principiante F (de la palabra primero (primero)) y el segundo S (de la palabra segundo (segundo)). Cada jugador tiene su propio cronómetro. $t$
F comienza el juego y pone el tiempo en su cronómetro . ${\ estilo de visualización z: = 0}$
S pone en marcha el cronómetro y piensa y hace un movimiento exactamente a tiempo . Después del movimiento, debe establecer instantáneamente el tiempo en el cronómetro . $t$ ${\ estilo de visualización y: = t}$
F cuenta el tiempo en el cronómetro . Si , entonces F detiene el juego y se considera engañado. El protocolo termina. De lo contrario, en caso de una jugada ganadora de S , F admite la derrota y finaliza el protocolo. Si el movimiento no es ganador, entonces F lo piensa y hace un movimiento exactamente a tiempo . En este momento, F tendrá tiempo en el cronómetro $mi$ $ez\neq t$ $t$ ${\ estilo de visualización z: = e + t.}$
S cuenta el tiempo en el cronómetro . Si , entonces S deja de jugar porque se considera engañado y el protocolo finaliza. De lo contrario, en caso de una jugada ganadora de F , S admite la derrota y el protocolo finaliza. Si el movimiento no es ganador, entonces S lo piensa y hace un movimiento exactamente a tiempo . En este momento, S tendrá tiempo en el reloj $F$ $fy\neq t$ $t$ ${\ estilo de visualización y: = f + t.}$
Ir al punto 4.

Teorema

Formulación [4]

Si la niña G necesita al menos tiempo para hacer la transición entre el "juego 1" y el "juego 2" y tanto F como S siguen el protocolo y el número de movimientos en el juego es más de dos ( ), entonces la niña hará trampa. ser detectado por F o S. ${\ estilo de visualización l> 0}$ $metro$ $m\geq 3$

Texto original (inglés)[ mostrarocultar] Si la pequeña G necesita al menos Q tiempo para comunicar los movimientos entre el "juego 1" y el "juego 2" y F y S siguen el protocolo, y el número de movimientos en el juego es más de 2 (entonces ), entonces el El fraude de la niña es detectado por F o S.

{\ estilo de visualización l> 0}

metro

m\geq 3

Prueba [4]
Tomamos las designaciones F y S de la solución propuesta. La niña se denotará con la letra G, de la palabra niña (niña).

Si la niña G está presente, el "juego 1" se juega entre F y G, y el "juego 2" se juega entre G y S. La niña copia los movimientos como se describió anteriormente. Supongamos que en el punto 1 de nuestro protocolo, en el "lote 1", F y G están de acuerdo en un tiempo , y en el "lote 2" G y S están de acuerdo en un tiempo ( y no necesariamente son iguales). F hace el primer movimiento en el tiempo 0 en el “juego 1” y pone el tiempo en el cronómetro Para copiar y transferir este movimiento al “juego 2”, G necesita tiempo Hace su movimiento en el tiempo y al mismo tiempo S pone a cero su cronómetro . Entonces S hace su movimiento en el tiempo y se pone en el reloj Para transferir este movimiento al "juego 1", G necesita tiempo Hace su movimiento en el "juego 1" en el tiempo F comprueba el reloj y se asegura de que Ahora y F, por si acaso , no detectará el fraude. Si se encuentra F, entonces se prueba el teorema. Supongamos que: $t_{1}$ $t_{2}$ $t_{1}$ $t_{2}$
${\ estilo de visualización z: = 0.}$ $l_{1}\geq l>0.$ $l_{1}$ $t_{2}+l_{1}$ $y:=t_{2}.$ $l_{2}\geq l>0.$ $l_{1}+t_{2}+l_{2}.$ $ez\neq t_{1}.$ $e=l_{1}+t_{2}+l_{2}$ ${\ estilo de visualización z = 0.}$
$t_{1}=l_{1}+t_{2}+l_{2}$

$t_{1}=l_{1}+t_{2}+l_{2}\cuádruple (1)$

F hace un movimiento en el tiempo Para transferir este movimiento al "juego 2", G necesita tiempo Ella hace un movimiento en el tiempo S mira el reloj y obtiene eso y Es decir, S comprueba que En caso de que no se dé cuenta de la trampa , debe cumplirse la igualdad: $t_{1}+l_{1}+t_{2}+l_{2}.$ $l_{3}\geq l>0.$ $l_{1}+t_{2}+l_{2}+t_{1}+l_{3}.$ $f=t_{2}+l_{2}+t_{1}+l_{3}$ $y:=t_{2}.$ $fy=l_{2}+t_{1}+l_{3}.$ $fy\neq t_{2}.$

$t_{2}=l_{2}+t_{1}+l_{3}\cuádruple (2)$

Sin embargo, combinando y obtenemos que: $(una)$ $(2)$

$l_{1}+2l_{2}+l_{3}=0$

Pero como es imposible. Por lo tanto, S detectará el engaño. El teorema ha sido probado. $l_{1},l_{2},l_{3}>0$

Notas

Destacamos que según este teorema, F o S detecta el engaño. Esto significa que uno de ellos puede permanecer en la oscuridad sobre el fraude en curso . [5]
Esta solución matemática utiliza una precisión perfecta, lo que es imposible desde el punto de vista de la física. Dada la imprecisión de la velocidad de cómputo de la computadora, esta solución se vuelve poco práctica para muchas aplicaciones. [6]

Aplicación de la solución

El salto de canal probabilístico

El problema del gran maestro y el problema del engaño de la mafia están en el corazón del trabajo de Ammar Alkassar , Christian Stuble y Ahmad-Reza Sadeghi . Introdujeron un canal de reconstrucción probabilística. Se basa en la suposición de que un atacante no puede transmitir de manera eficiente todas las comunicaciones en paralelo. La idea principal es utilizar un sistema de salto de canal, gracias al cual un atacante no puede espiar la comunicación entre las partes involucradas. Este enfoque también utiliza una clave semánticamente segura compartida entre la primera (verificación) y la segunda (prueba). Esto permite el uso en redes inalámbricas ad hoc[ aclarar ] [7] .

Otras Soluciones

Identificación de la jaula de Faraday propuesta por Samy Bengio [8 ] .
Sistema de medición de precisión propuesto por Ivo Desmedt y Thomas Beth [9] .
Protocolo de distancia limitada propuesto por Stefan Bands y David Chaum [10 ] .

Véase también

Notas

↑ 1 2 Conway, 1976 , págs. 75.
↑ Desmedt Y. G. , Goutier C. , Bengio S. Special Uses and Abuses of the Fiat-Shamir Passport Protocol (resumen extendido ) // Advances in Cryptology - CRYPTO '87 : A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, EE. UU., 16-20 de agosto de 1987, Proceedings / C. Pomerance - Berlín : Springer Berlin Heidelberg , 1987. - P. 21-39. - ( Lecture Notes in Computer Science ; Vol. 293) - ISBN 978-3-540-18796-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-48184-2_3
↑ Beth, Desmedt, 1991 , pág. 172.
↑ 1 2 Beth, Desmedt, 1991 , pág. 172-173.
↑ Beth, Desmedt, 1991 , pág. 173.
↑ Alkassar A. , Stüble C. , Sadeghi A. Identificación segura de objetos: o: resolver el problema del gran maestro de ajedrez // NSPW'03 : Actas del taller de 2003 sobre Nuevos paradigmas de seguridad / C. F. Hempelmann , V. Raskin — Nueva York, NY , EE.UU. : ACM , 2003. - P. 77-85. - ISBN 978-1-58113-880-1 - doi:10.1145/986655.986668
↑ Arbaugh W. A. , Farber D. J. , Smith J. M. Una arquitectura de arranque segura y confiable // SP'97 : Actas del Simposio IEEE de 1997 sobre seguridad y privacidad - Washington, DC, EE . UU .: IEEE Computer Society , 1997. - P 65- 71. - ISBN 978-0-8186-7828-8 - ISSN 1081-6011 ; 2375-1207 - doi:10.1109/SECPRI.1997.601317
↑ Bengio S. , Brassard G. , Desmedt Y. G. , Goutier C. , Quisquater J. Implementación segura de sistemas de identificación // Journal of Cryptology / I. Damgård - Springer Science+Business Media , Asociación Internacional para la Investigación Criptológica , 1991. vol. 4, edición. 3.- Pág. 175-183. — ISSN 0933-2790 ; 1432-1378 - doi:10.1007/BF00196726
↑ Beth, Desmedt, 1991 , pág. 174.
↑ Brands S. A. , Chaum D. Distance-Bounding Protocols : Extended abstract // Advances in Cryptology - EUROCRYPT '93 : Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, May 23–27, 1993 Proceedings / T Helleseth - 1 - Berlín : Springer Berlin Heidelberg , 1994. - P. 344-359. — 465 págs. — ISBN 978-3-540-57600-6 — doi:10.1007/3-540-48285-7_30

Literatura

Schneier, B. Capítulo 5. Parte 2. Identificación con pruebas de conocimiento cero. Problema del gran maestro // Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumf, 2002. - S. 133-134. — 816 pág. - 3000 copias. - ISBN 5-89392-055-4 .
Conway J. H. On Numbers and Games (inglés) - 111 Fifth Avenue, Nueva York, EE . UU .: 1976.
Beth T. , Desmedt Y. G. Fichas de identificación - o: Resolviendo el problema del gran maestro de ajedrez // Avances en criptología - CRYPTO '90 : 10.ª Conferencia anual internacional de criptología, Santa Bárbara, California, EE. UU., 11-15 de agosto de 1990, Actas / A. J. Menezes , S. A. Vanstone - Berlín , Heidelberg , Nueva York, NY , Londres [etc.] : Springer Berlin Heidelberg , 1991. - P. 169-176. - ( Lecture Notes in Computer Science ; Vol. 537) - ISBN 978-3-540-54508-8 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-38424-3_12