Stormester problem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 20. maj 2021; verifikation kræver 1 redigering .

Skak - stormesterproblemet er en af måderne , hvorpå nul-viden bevis misbruges . Det er også et af spilteoriens problemer . [1] Resultatet af dette problem er et bedrag udført af mafiaen . Problemet er, at en angriber kan bevise ejerskab af hemmeligheden uden faktisk at eje den, eller med andre ord kan efterligne den person, der faktisk ejer hemmeligheden.

Problem

Et eksempel på dette problem er historien om en pige, der demonstrerede [1] samtidig spil mod to stormestre. Hendes metode var som følger:

Alice spiller mod to stormestre, der er i forskellige rum og ikke er klar over hinandens tilstedeværelse.
Alice skriver ned en stormesters træk og duplikerer dem i et spil med en anden, skriver derefter træk fra den anden ned og gentager med den første, og så videre.

Dette fortsætter på denne måde, indtil hun taber det ene parti, vinder det andet, eller indtil begge partier ender uafgjort. Ved at bruge dette bedrag kan du bedrage enhver skakspiller og vinde takket være noget andet end din egen viden.

Denne vildledningsteknik kan bruges mod nul-viden bevis for identitet . [2]

Mulig løsning

En mulig løsning på dette problem blev foreslået af Thomas Beth ( 1949 - 2005 ) og Ivo Desmedt . For at eliminere muligheden for snyd foreslog de følgende algoritme . [3]

Stormestre vil være sikre på, at denne form for snyd ikke vil ske, og modstandere vil spille kun ved at bruge deres viden, uden nogen andens hjælp. For at gøre dette vil alle skakspillere følge følgende protokol:

Før spillets start bliver skakspillere enige om en bestemt værdi af tid , udtrykt i sekunder. De er også enige om, hvem der spiller hvid og hvem der spiller sort. For nemheds skyld betegner vi begynderen F (fra ordet først (første)), og den anden S (fra ordet anden (anden)). Hver spiller har sit eget stopur. $t$
F starter spillet og indstiller tiden på sit stopur . $z:=0$
S starter stopuret og tænker og foretager et træk præcis i tide . Efter flytningen skal han øjeblikkeligt indstille tiden på stopuret . $t$ $y:=t$
F tæller tiden på stopuret . Hvis , så stopper F spillet og betragter sig selv som snydt. Protokollen slutter. Ellers, i tilfælde af et vindende træk fra S , indrømmer F nederlag, og protokollen slutter. Hvis træk ikke er en vindende, så tænker F sig om og foretager et træk præcis i tide . På dette tidspunkt vil F have tid på stopuret $e$ $ez\neq t$ $t$ $z:=e+t.$
S tæller tiden på stopuret . Hvis , så stopper S med at spille, fordi han anser sig selv for bedraget, og protokollen slutter. Ellers, i tilfælde af et vindende træk fra F , indrømmer S nederlag, og protokollen slutter. Hvis træk ikke er et vindende, så tænker S sig om og foretager et træk præcis i tide . På dette tidspunkt vil S have tid på uret $f$ $fy\neq t$ $t$ $y:=f+t.$
Gå til punkt 4.

Sætning

Formulering [4]

Hvis lille pige G mindst har brug for tid til at lave overgangen mellem "spil 1" og "spil 2", og både F og S følger protokollen, og antallet af træk i spillet er mere end to ( ), så vil pigens snyd blive opdaget af F eller S. $l>0$ $m$ $m\geq 3$

Originaltekst (engelsk)[ Visskjule] Hvis den lille gjord G har brug for mindst Q-tid til at kommunikere trækkene mellem "spil 1" og "spil 2", og F og S følger protokollen, og antallet af træk i spillet er mere end 2 (så ), så lille piges bedrageri opdages af F eller S.

l>0

m

m\geq 3

Bevis [4]
Vi tager betegnelserne F og S fra den foreslåede løsning. Den lille pige vil blive betegnet med bogstavet G - fra ordet pige (pige).

Hvis pige G er til stede, spilles "spil 1" mellem F og G, og "spil 2" spilles mellem G og S. Pigen kopierer trækkene som beskrevet tidligere. Lad os antage, at i punkt 1 i vores protokol, i "batch 1", er F og G enige om et tidspunkt , og i "batch 2" er G og S enige om et tidspunkt ( og er ikke nødvendigvis ens). F laver det første træk til tiden 0 i "spil 1" og indstiller tiden på stopuret For at kopiere og overføre dette træk til "spil 2" har G brug for tid. Hun laver sit træk til tiden og nulstiller samtidig sit stopur . Så får S hende til at bevæge sig til tiden og indstiller uret . For at overføre dette træk til "spil 1", har G brug for tid . , vil ikke opdage svindel. Hvis F findes, så er sætningen bevist. Lad os lade som om: $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 laver et træk til tiden For at overføre dette træk til "spil 2", har G brug for tid. Hun laver et træk på tidspunktet S ser på uret og får det, og det vil sige, S tjekker det I tilfælde af at han ikke bemærker snyden , han skal ligestilling er opfyldt: $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)$

Men ved at kombinere og vi får det: $(en)$ $(2)$

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

Men da det er umuligt. Derfor vil S opdage bedrag. Sætningen er blevet bevist. $l_{1},l_{2},l_{3}>0$

Noter

Vi understreger, at ifølge denne sætning, opdager F eller S bedrag. Det betyder, at en af dem kan forblive i mørke om det igangværende bedrageri . [5]
Denne matematiske løsning bruger perfekt nøjagtighed, hvilket er umuligt ud fra et fysiksynspunkt. På grund af unøjagtigheden af computerens computerhastighed bliver denne løsning upraktisk til mange applikationer. [6]

Anvendelse af løsningen

The Probabilistic Channel Hopping

Stormesterproblemet og problemet med mafiabedrag er kernen i Ammar Alkassars , Christian Stubles og Ahmad-Reza Sadeghis arbejde . De introducerede en probabilistisk genopbygningskanal. Det er baseret på den antagelse, at en hacker ikke effektivt kan videresende al kommunikation parallelt. Hovedideen er at bruge et kanalhoppingssystem, takket være hvilket en angriber ikke kan aflytte kommunikationen mellem de involverede parter. Denne tilgang bruger også en semantisk sikker nøgle, der deles mellem den første (verificerende) og anden (bevisende) part. Dette tillader brug i trådløse ad hoc-netværk[ præciser ] [7] .

Andre løsninger

Faraday bur identifikation foreslået af Samy Bengio [8 ] .
Præcisionsmålesystem foreslået af Ivo Desmedt og Thomas Beth [9] .
Afstandsbegrænset protokol foreslået af Stefan Bands og David Chaum [10 ] .

Se også

Noter

↑ 1 2 Conway, 1976 , s. 75.
↑ Desmedt Y. G. , Goutier C. , Bengio S. Special Uses and Abuses of the Fiat-Shamir Passport Protocol (extended abstract ) // Advances in Cryptology - CRYPTO '87 : A Conference on the Theory and Applications of Cryptographic Techniques , Santa Barbara, Californien, USA, 16.-20. august 1987, Proceedings / C. Pomerance - Berlin : Springer Berlin Heidelberg , 1987. - S. 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 , s. 172.
↑ 1 2 Beth, Desmedt, 1991 , s. 172-173.
↑ Beth, Desmedt, 1991 , s. 173.
↑ Alkassar A. , Stüble C. , Sadeghi A. Sikker objektidentifikation: 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 , USA : ACM , 2003. - S. 77-85. - ISBN 978-1-58113-880-1 - doi:10.1145/986655.986668
↑ Arbaugh W. A. , Farber D. J. , Smith J. M. En sikker og pålidelig bootstrap-arkitektur // 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. Sikker implementering af identifikationssystemer // Journal of Cryptology / I. Damgård - Springer Science+Business Media , International Association for Cryptologic Research , 1991. Vol. 4, Iss. 3. - S. 175-183. — ISSN 0933-2790 ; 1432-1378 - doi:10.1007/BF00196726
↑ Beth, Desmedt, 1991 , s. 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, Norge, 23.-27. maj 1993 Proceedings / T Helleseth - 1 - 1 - 1 Berlin : Springer Berlin Heidelberg , 1994. - S. 344-359. — 465 s. — ISBN 978-3-540-57600-6 — doi:10.1007/3-540-48285-7_30

Litteratur

Schneier, B. Kapitel 5. Del 2. Identifikation med Zero-Knowledge Proofs. Stormesterproblem // Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protokoller, algoritmer og kildekode i C. - M. : Triumf, 2002. - S. 133-134. — 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
Conway J. H. On Numbers and Games (engelsk) - 111 Fifth Avenue, New York, USA : 1976.
Beth T. , Desmedt Y. G. Identification Tokens - eller: Solving The Chess Grandmaster Problem // Advances in Cryptology - CRYPTO '90 : 10th Annual International Cryptology Conference, Santa Barbara, Californien, USA, 11.-15. august 1990, Proceedings / A. J. Menezes , S. A. Vanstone - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 1991. - S. 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