Nagymester probléma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. május 20-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A sakknagymester-probléma az egyik módja annak, ahogyan visszaélnek a nulla tudásszintű bizonyítással . Ez a játékelmélet egyik problémája is . [1] A probléma eredménye a maffia által végrehajtott megtévesztés . A probléma az, hogy a támadó be tudja bizonyítani a titok tulajdonjogát anélkül, hogy ténylegesen birtokolná azt, vagy más szóval utánozni tudja azt a személyt, aki valójában birtokolja a titkot.

Probléma

Példa erre a problémára egy lány története, aki [1] szimultán játékot mutatott be két nagymester ellen. A módszertana a következő volt:

Alice két nagymester ellen játszik, akik különböző helyiségekben vannak, és nincsenek tudatában egymás jelenlétének.
Alice lejegyzi az egyik nagymester mozdulatait, és lemásolja őket egy játékban egy másikkal, majd leírja a második lépéseit, és megismétli az elsővel, és így tovább.

Ez addig folytatódik, amíg el nem veszít egy játszmát, megnyeri a másodikat, vagy amíg mindkét játszma döntetlenre végződik. Ezzel a megtévesztéssel bármely sakkozót megtéveszthet, és nem a saját tudásának köszönhetően nyerhet.

Ez a megtévesztési technika a tudás nélküli személyazonosság-igazolás ellen is használható . [2]

Lehetséges megoldás

A probléma lehetséges megoldását Thomas Beth ( 1949-2005 ) és Ivo Desmedt [ en javasolta . A csalás lehetőségének kiküszöbölésére a következő algoritmust javasolták . [3]

A nagymesterek biztosak akarnak lenni abban, hogy ez a fajta csalás nem fog megtörténni, és az ellenfelek csak tudásukat felhasználva, bárki más segítsége nélkül játszanak. Ehhez minden sakkozó a következő protokollt követi:

A játék megkezdése előtt a sakkozók megállapodnak az idő bizonyos értékében , másodpercben kifejezve. Abban is megegyeznek, hogy ki játszik fehéret és ki feketét. Az egyszerűség kedvéért jelöljük a kezdő F -et (az első (első) szóból, a második S -t (a második (második) szóból). Minden játékosnak saját stopperje van. $t$
F elindítja a játékot, és beállítja az időt a stopperóráján . $z:=0$
S elindítja a stopperórát, és pontosan időben gondolkodik és tesz egy mozdulatot . A lépés után azonnal be kell állítania az időt a stopperórán . $t$ $y:=t$
F számolja az időt a stopperórán . Ha , akkor F leállítja a játékot, és becsapottnak tekinti magát. A protokoll véget ér. Ellenkező esetben S -ből nyerő lépés esetén F elismeri a vereségét, és a protokoll véget ér. Ha a lépés nem nyerő, akkor F átgondolja, és pontosan időben hajt végre egy lépést. Ebben az időpontban F -nek van ideje a stopperórán $e$ $ez\neq t$ $t$ $z:=e+t.$
S számolja az időt a stopperórán . Ha , akkor S abbahagyja a játékot, mert becsapottnak tartja magát, és a protokoll véget ér. Ellenkező esetben F nyerő lépése esetén S elismeri a vereségét, és a protokoll véget ér. Ha a lépés nem nyerő, akkor S átgondolja, és pontosan időben megteszi a lépést. Ekkor már S -nek lesz ideje az órán $f$ $fy\neq t$ $t$ $y:=f+t.$
Tovább a 4. pontra.

Tétel

Formuláció [4]

Ha G kislánynak legalább időre van szüksége az „1. játék” és a „2. játszma” közötti átmenethez, és F és S is követi a protokollt, és a lépések száma a játékban kettőnél több ( ), akkor a lány csalása F vagy S észleli. $l>0$ $m$ $m\geq 3$

Eredeti szöveg (angol)[ showelrejt] Ha a kis övnek G legalább Q időre van szüksége az „1. játszma” és a „2. játszma” közötti lépések kommunikálásához, és F és S követi a protokollt, és a mozdulatok száma a játékban több mint 2 (tehát ), akkor a kislány csalását F vagy S észleli.

l>0

m

m\geq 3

Bizonyítás [4]
A javasolt megoldásból átvesszük az F és S jelöléseket. A kislányt a G betű fogja jelölni - a lány (lány) szóból.

Ha G lány jelen van, az "1. játékot" F és G, a "2. játékot" G és S között játsszák. A lány a korábban leírtak szerint másolja a mozdulatokat. Tegyük fel, hogy protokollunk 1. pontjában az "1. kötegben" F és G megállapodik az időpontban , míg a "2. kötegben" G és S megegyezik az időpontban ( és nem feltétlenül egyenlő). F megteszi az első lépést a 0 időpontban az „1. játékban”, és beállítja az időt a stopperórán. Ennek a lépésnek a „2. játékba” való másolásához és átviteléhez G-nek időre van szüksége. Időben mozog, és ezzel egyidejűleg S alaphelyzetbe állítja a stoppert . Ezután S időben mozog, és beállítja az órát Ahhoz, hogy ezt a lépést az "1. játékba" vigye át, G-nek időre van szüksége . Az "1. játékban" F időpontban mozog, és megbizonyosodik arról, hogy a Now és F, abban az esetben , nem észleli a csalást. Ha F található, akkor a tétel bizonyítva van. Tegyünk úgy, mintha: $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 időben mozog Ahhoz, hogy ezt a lépést a "2. játékba" vigye át, G-nek időre van szüksége. S időpontban tesz egy lépést, és ránéz az órára, és azt kapja, és vagyis S ellenőrzi, hogy abban az esetben, ha nem veszi észre a csalást , akkor az egyenlőségnek teljesülnie kell: $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)$

Azonban kombinálva azt kapjuk, hogy: $(egy)$ $(2)$

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

De mivel ez lehetetlen. Ezért S észleli a megtévesztést. A tétel bizonyítást nyert. $l_{1},l_{2},l_{3}>0$

Jegyzetek

Hangsúlyozzuk, hogy e tétel szerint F vagy S megtévesztést észlel. Ez azt jelenti, hogy egyikük titokban maradhat a folyamatban lévő csalással kapcsolatban . [5]
Ez a matematikai megoldás tökéletes pontosságot alkalmaz, ami fizika szempontjából lehetetlen. A számítógép számítási sebességének pontatlansága miatt ez a megoldás sok alkalmazás számára nem használható. [6]

A megoldás alkalmazása

The Probabilistic Channel Hopping

Ammar Alkassar , Christian Stuble és Ahmad-Reza Sadeghi munkájának középpontjában a nagymesteri probléma és a maffia megtévesztésének problémája áll . Bevezettek egy valószínűségi újjáépítési csatornát. Ez azon a feltételezésen alapul, hogy a támadó nem tudja hatékonyan párhuzamosan továbbítani az összes kommunikációt. A fő ötlet egy csatornaugrásos rendszer alkalmazása, amelynek köszönhetően a támadó nem tudja lehallgatni az érintett felek közötti kommunikációt. Ez a megközelítés egy szemantikailag biztonságos kulcsot is használ, amelyet az első (ellenőrző) és a második (bizonyító) fél oszt meg. Ez lehetővé teszi a vezeték nélküli ad hoc hálózatokban való használatát[ pontosítás ] [7] .

Egyéb megoldások

Faraday ketrec azonosítását Samy Bengio javasolta [8 ] .
Ivo Desmedt és Thomas Beth által javasolt precíziós mérési rendszer [9] .
Stefan Bands és David Chaum által javasolt távolságkorlátozott protokoll [10 ] .

Lásd még

Jegyzetek

↑ 1 2 Conway, 1976 , pp. 75.
↑ Desmedt Y. G. , Goutier C. , Bengio S. A Fiat-Shamir útlevélprotokoll speciális felhasználásai és visszaélései (kibővített absztrakt ) // Advances in Cryptology - CRYPTO '87 : Konferencia a kriptográfiai technikák elméletéről és alkalmazásairól Santa Barbara, , California, USA, 1987. augusztus 16-20., Proceedings / C. Pomerance - Berlin : Springer Berlin Heidelberg , 1987. - P. 21-39. - ( Számítástechnikai előadások jegyzetei ; 293. kötet) - 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. Biztonságos objektum azonosítás: vagy: a sakknagymesteri probléma megoldása // NSPW'03 : Proceedings of the 2003 workshop on New security paradigms / C. F. Hempelmann , V. Raskin – New York, NY , USA : 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. Egy biztonságos és megbízható rendszerindítási architektúra // SP'97 : Proceedings of the 1997 IEEE Symposium on Security and Privacy - Washington, DC, USA : 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. Az azonosítási rendszerek biztonságos megvalósítása // Journal of Cryptology / I. Damgård - Springer Science+Business Media , International Association for Cryptologic Research , 1991. évf. 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, Norvégia, 1993. május 23–27. /1 Proceedsth / 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

Irodalom

Schneier, B. 5. fejezet 2. rész. Azonosítás nulla tudású bizonyítással. Nagymester probléma // Alkalmazott titkosítás. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód: C. - M . : Triumf, 2002. - S. 133-134. — 816 p. - 3000 példányban. - ISBN 5-89392-055-4 .
Conway J. H. Számokról és játékokról (angolul) – 111 Fifth Avenue, New York, USA : 1976.
Beth T. , Desmedt Y. G. Azonosító jelzők - avagy: A sakk nagymesteri problémájának megoldása // Advances in Cryptology - CRYPTO '90 : 10th Annual International Cryptology Conference, Santa Barbara, California, USA, 1990. augusztus 11-15., Proceedings J. Menezes / A. , S. A. Vanstone - Berlin , Heidelberg , New York, NY , London [stb.] : Springer Berlin Heidelberg , 1991. - P. 169-176. - ( Számítástechnikai előadások jegyzetei ; 537. kötet) - ISBN 978-3-540-54508-8 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-38424-3_12