Problema Marelui Maestru

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 mai 2021; verificarea necesită 1 editare .

Problema marelui maestru al șahului este una dintre modalitățile prin care se abuzează dovada zero-cunoștințe . Este, de asemenea, una dintre problemele teoriei jocurilor . [1] Rezultatul acestei probleme este o înșelăciune efectuată de mafie . Problema este că un atacator poate dovedi deținerea secretului fără a-l deține efectiv sau, cu alte cuvinte, poate imita persoana care deține de fapt secretul.

Problemă

Un exemplu al acestei probleme este povestea unei fete care a demonstrat [1] jocul simultan împotriva a doi mari maeștri. Metodologia ei a fost următoarea:

Alice joacă împotriva a doi mari maeștri care se află în camere diferite și nu sunt conștienți de prezența celuilalt.
Alice notează mișcările unui mare maestru și le dublează într-un joc cu altul, apoi notează mișcările celui de-al doilea și le repetă cu prima și așa mai departe.

Acest lucru continuă în acest fel până când ea pierde un joc, câștigând al doilea sau până când ambele jocuri se termină la egalitate. Folosirea acestei înșelăciuni vă permite să înșelați orice jucător de șah și să câștigați datorită altora decât propriile cunoștințe.

Această tehnică de înșelăciune poate fi utilizată împotriva dovezilor de identitate fără cunoștințe . [2]

Soluție posibilă

O posibilă soluție la această problemă a fost propusă de Thomas Beth ( 1949 - 2005 ) și Ivo Desmedt . Pentru a elimina posibilitatea de a înșela, ei au propus următorul algoritm . [3]

Marii maeștri vor să fie siguri că acest tip de înșelăciune nu se va întâmpla și adversarii vor juca folosind doar cunoștințele lor, fără ajutorul nimănui altcuiva. Pentru a face acest lucru, toți jucătorii de șah vor urma următorul protocol:

Înainte de începerea jocului, jucătorii de șah sunt de acord cu o anumită valoare a timpului , exprimată în secunde. Ei sunt de acord și asupra cine joacă alb și cine joacă negru. Pentru comoditate, notăm începătorul F (din cuvântul primul (primul)) și al doilea S (din cuvântul al doilea (al doilea)). Fiecare jucător are propriul cronometru. $t$
F începe jocul și setează ora pe cronometru . $z:=0$
S pornește cronometrul și se gândește și face o mișcare exact la timp . După mutare, el trebuie să seteze instantaneu ora pe cronometru . $t$ $y:=t$
F numără timpul pe cronometru . Dacă , atunci F oprește jocul și se consideră înșelat. Protocolul se încheie. În caz contrar, în cazul unei mișcări câștigătoare din S , F admite înfrângerea și protocolul se încheie. Dacă mutarea nu este una câștigătoare, atunci F se gândește și face o mișcare exact la timp . În acest moment, F va avea timp pe cronometru $e$ $ez\neq t$ $t$ $z:=e+t.$
S numără timpul pe cronometru . Dacă , atunci S se oprește din joc pentru că se consideră înșelat și protocolul se încheie. În caz contrar, în cazul unei mișcări câștigătoare de la F , S admite înfrângerea și protocolul se încheie. Dacă mutarea nu este una câștigătoare, atunci S se gândește și face o mișcare exact la timp . Până în acest moment, S va avea timp la ceas $f$ $fy\neq t$ $t$ $y:=f+t.$
Treci la punctul 4.

Teorema

Formulare [4]

Dacă fetița G are nevoie de cel puțin timp pentru a face tranziția între „jocul 1” și „jocul 2” și atât F cât și S urmează protocolul, iar numărul de mișcări în joc este mai mare de două ( ), atunci înșelăciunea fetei va fi detectat de F sau S. $l>0$ $m$ $m\geq 3$

Text original (engleză)[ arataascunde] Dacă micul G are nevoie de cel puțin Q timp pentru a comunica mișcările dintre „jocul 1” și „jocul 2” și F și S urmează protocolul, iar numărul de mișcări din joc este mai mare de 2 (deci ), atunci frauda fetiței este detectată de F sau S.

l>0

m

m\geq 3

Dovada [4]
Luăm denumirile F și S din soluția propusă. Fetița va fi notată cu litera G - de la cuvântul fată (fată).

Dacă fata G este prezentă, „jocul 1” este jucat între F și G, iar „jocul 2” este jucat între G și S. Fata copiază mișcările așa cum este descris mai devreme. Să presupunem că la punctul 1 al protocolului nostru, în „lotul 1”, F și G sunt de acord cu un timp , iar în „lotul 2” G și S sunt de acord cu un timp ( și nu sunt neapărat egali). F face prima mișcare la momentul 0 în „jocul 1” și setează ora pe cronometru Pentru a copia și transfera această mișcare în „jocul 2”, G are nevoie de timp Ea își face mișcarea la timp și în același timp S își resetează cronometrul . Apoi S își face mișcarea la timp și pornește ceasul Pentru a transfera această mișcare în „jocul 1”, G are nevoie de timp . Ea își face mișcarea în „jocul 1” la ora F verifică ceasul și se asigură că Acum și F, în caz că , nu va detecta frauda. Dacă se găsește F, atunci se demonstrează teorema. Să ne prefacem că: $t_{1}$ $t_{2}$ $t_{1}$ $t_{2}$
$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}$ $z=0.$
$t_{1}=l_{1}+t_{2}+l_{2}$

$t_{1}=l_{1}+t_{2}+l_{2}\quad (1)$

F face o mișcare la timp Pentru a transfera această mișcare în „jocul 2”, G are nevoie de timp Ea face o mișcare la ora S se uită la ceas și primește asta și Adică S verifică asta În cazul în care nu observă trucul , el trebuie să fie îndeplinită egalitatea: $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}\quad (2)$

Cu toate acestea, combinând și obținem că: $(unu)$ $(2)$

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

Dar din moment ce este imposibil. Prin urmare, S va detecta înșelăciunea. Teorema a fost demonstrată. $l_{1},l_{2},l_{3}>0$

Note

Subliniem că, conform acestei teoreme, F sau S detectează înșelăciunea. Aceasta înseamnă că unul dintre ei poate rămâne în întuneric cu privire la frauda în curs . [5]
Această soluție matematică folosește acuratețea perfectă, ceea ce este imposibil din punctul de vedere al fizicii. Având în vedere inexactitatea vitezei de calcul a computerului, această soluție devine nepractică pentru multe aplicații. [6]

Aplicarea soluției

Hoppingul probabilistic canalului

Problema marelui maestru și problema înșelăciunii mafiote se află în centrul lucrării lui Ammar Alkassar , Christian Stuble și Ahmad-Reza Sadeghi . Au introdus un canal probabilistic de reconstrucție. Se bazează pe presupunerea că un atacator nu poate transmite eficient toate comunicațiile în paralel. Ideea principală este de a folosi un sistem de salt de canale, datorită căruia un atacator nu poate asculta comunicarea dintre părțile implicate. Această abordare folosește, de asemenea, o cheie semantic sigură partajată între prima (de verificare) și a doua (demonstrare). Acest lucru permite utilizarea în rețele wireless ad-hoc[ clarifica ] [7] .

Alte soluții

Identificarea cuștii Faraday propusă de Samy Bengio [8 ] .
Sistem de măsurare de precizie propus de Ivo Desmedt și Thomas Beth [9] .
Protocolul limitat la distanță propus de Stefan Bands și David Chaum [10 ] .

Vezi și

Note

↑ 1 2 Conway, 1976 , pp. 75.
↑ Desmedt Y. G. , Goutier C. , Bengio S. Special Uses and Abuses of the Fiat-Shamir Passport Protocol (rezumat extins ) // Advances in Cryptology - CRYPTO '87 : A Conference on theory and Applications of Cryptographic Techniques, Santa Barbara, California, SUA, 16-20 august 1987, Proceedings / C. Pomerance - Berlin : Springer Berlin Heidelberg , 1987. - P. 21-39. - ( Note de curs în Informatică ; 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. 172.
↑ 1 2 Beth, Desmedt, 1991 , p. 172-173.
↑ Beth, Desmedt, 1991 , p. 173.
↑ Alkassar A. , Stüble C. , Sadeghi A. Secure object identification: or: solving the Chess Grandmaster Problem // NSPW'03 : Proceedings of the 2003 workshop on New security paradigms / C. F. Hempelmann , V. Raskin — New York, NY , SUA : 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. A secure and reliable bootstrap architecture // SP'97 : Proceedings of the 1997 IEEE Symposium on Security and Privacy - Washington, DC, SUA : 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. Secure implementation of identification systems // Journal of Cryptology / I. Damgård - Springer Science+Business Media , International Association for Cryptologic Research , 1991. Vol. 4, Iss. 3. - P. 175-183. — ISSN 0933-2790 ; 1432-1378 - doi:10.1007/BF00196726
↑ Beth, Desmedt, 1991 , p. 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 Berlin : Springer Berlin Heidelberg , 1994. - P. 344-359. — 465 p. — ISBN 978-3-540-57600-6 — doi:10.1007/3-540-48285-7_30

Literatură

Schneier, B. Capitolul 5. Partea 2. Identificarea cu dovezi cu cunoștințe zero. Problemă Grandmaster // Criptografia aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumf, 2002. - S. 133-134. — 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .
Conway J. H. On Numbers and Games (engleză) - 111 Fifth Avenue, New York, SUA : 1976.
Beth T. , Desmedt Y. G. Identification Tokens - sau: Solving The Chess Grandmaster Problem // Advances in Cryptology - CRYPTO '90 : 10th Annual International Cryptology Conference, Santa Barbara, California, SUA, 11-15 august 1990, Proceedings / A. J. Menezes , S. A. Vanstone - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer Berlin Heidelberg , 1991. - P. 169-176. - ( Note de curs în Informatică ; Vol. 537) - ISBN 978-3-540-54508-8 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-38424-3_12