Mental poker

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 oktober 2018; kontroller kräver 5 redigeringar .

Mental poker  är ett system med kryptografiska problem relaterade till rättvisa spel på distans (via telefon eller Internet) [1] [2] . Termen kommer från namnet på kortspelet  poker . Ett liknande problem är relaterat till problemet med att kasta ett mynt på avstånd [3] .

Historik

Sedan mitten av 1900-talet började många transaktioner, monetära transaktioner utföras på distans, det fanns ett behov av att skapa ett kryptografiskt protokoll som kunde lösa sådana problem. Ett sådant protokoll var tänkt att ge inte bara användarvänlighet, utan också tillförlitlighet. En sådan uppgift kan formuleras i en spelform utan att några tekniska detaljer utelämnas - så att termen "mental poker" dök upp [1] .

För första gången försökte Niels Bohr , hans son och vänner spela poker utan kort 1933, men försöket misslyckades [4] . Problemet togs senare upp av Robert Floyd . Hans forskning fick skaparna av RSA-krypteringsprotokollet , Adi Shamir , Ron Rivest och Len Adleman , att publicera en vetenskaplig rapport där protokoll föreslogs för att lösa problemet med mental poker [5] .

Problemformulering

Shamir, Rivest och Adleman formulerade problemet på följande sätt: "Kan två spelare som är oärliga mot varandra spela rättvis poker utan att använda kort, men till exempel via telefon?" [6] [7]

I poker låter det så här: "Hur kan vi se till att ingen spelare kikar på andra spelares kort medan vi blandar leken?". I ett riktigt kortspel är denna fråga lätt att besvara, eftersom spelarna sitter mitt emot varandra och tittar på varandra (vi överväger fallet när möjligheten till vanligt fusk är uteslutet). Men om spelarna inte sitter bredvid varandra, utan i separata rum, och kan överföra hela kortleken till varandra (till exempel med hjälp av post ), blir uppgiften mycket svår. För elektroniska kortspel, som online poker , där processen att spela är dold för användaren, är det helt omöjligt att lösa problemet om metoden som används tillåter en spelare att lura en annan. För att förhindra sådana problem finns det så kallade tankenivåer i poker [8] , tack vare vilka det är möjligt att spela med motståndare på samma nivå.

Spelet måste uppfylla vissa krav [3] :

  1. Spelaren känner inte till ens delvis information om sin motståndares kort.
  2. Alla möjliga utfall är lika sannolika för båda spelarna.
  3. I slutet av spelet kan spelaren se till att spelet var rättvist och att det inte förekom något fusk.

Kortblandning med kommutativ kryptering

En möjlig algoritm för att blanda kort är att använda ett kommutativt krypteringsschema. Det kommutativa schemat innebär att om vissa data krypteras mer än en gång, spelar ordningen i vilken den dekrypteras ingen roll.

Exempel : Alice krypterar klartexten och skapar en förvrängd chiffertext som hon skickar till Bob . Bob krypterar chiffertexten igen med samma schema som Alice, men med en annan nyckel . Om krypteringsschemat är kommutativt spelar det ingen roll vem som dekrypterar först när ett meddelande dekrypteras.

Krypteringsfunktionen, som i RSA , måste vara enkelriktad  x , du kan enkelt beräkna f(x) , men i motsatt riktning måste du känna till "hemligheten" för att beräkna. Protokollets kryptografiska styrka är baserad på komplexiteten i att vända sådana funktioner. Detta utesluter dock inte möjligheten till partiell beräkning av x från f(x) [9] .

Algoritm

Algoritmen för att blanda kort med kommutativ kryptering är som följer [3] :

  1. Alice och Bob kommer överens om att använda en viss "lek" med kort. I praktiken betyder detta att de går med på att använda en uppsättning siffror eller annan data så att varje element i uppsättningen är en karta.
  2. Alice krypterar varje kort i kortleken med nyckel A.
  3. Alice blandar korten.
  4. Alice skickar det krypterade och blandade däcket till Bob. Han vet inte vilka kort som är vilka.
  5. Bob väljer att kryptera nyckel B och använder den för att kryptera varje kort från den redan krypterade och blandade kortleken.
  6. Bob blandar däcket.
  7. Bob passerar det dubbelkrypterade och blandade däcket tillbaka till Alice.
  8. Alice dekrypterar varje kort med sin nyckel A. Men Bobs kryptering finns fortfarande kvar, vilket betyder att hon inte vet vilka kort som är vilka.
  9. Alice väljer krypteringsnyckeln för varje kort (A1, A2, etc.) och krypterar dem individuellt.
  10. Alice skickar däcket till Bob.
  11. Bob dekrypterar varje kort med sin nyckel B. Alices privata kryptering finns fortfarande kvar, vilket betyder att han inte vet vilka kort som är vilka.
  12. Bob väljer en nyckel för att kryptera varje kort (B1, B2, etc.) och krypterar dem individuellt.
  13. Bob skickar däcket tillbaka till Alice.
  14. Alice visar kortleken för alla spelare (i detta fall är spelarna Alice och Bob).

Däcket är nu blandat.

Under spelet kommer Alice och Bob att ta kort från kortleken för vilken ordningen i den blandade kortleken är känd. När en av spelarna vill se sina kort kommer han att begära motsvarande nycklar från en annan spelare. Den spelaren (efter att ha verifierat att spelaren faktiskt har rätt att titta på korten) skickar de individuella nycklarna för dessa kort till en annan spelare. Det är också nödvändigt att kontrollera att spelaren inte har försökt begära en nyckel till kort som inte tillhör honom.

Exempel

Alice och Bob delar ut tre kort . Följande algoritm används:

1) De väljer ett primtal , Alice väljer ett primtal med , och beräknar talet enligt den generaliserade euklidiska algoritmen , det vill säga: , därav .

2) På liknande sätt definierar Bob sitt nummerpar: och .

3) Därefter väljer Alice tre olika nummer i intervallet , till exempel , och sätter dem i linje med sina kort. Hon ger dem till Bob i det klara.

4) Sedan räknar Alice ut siffrorna: , blandar dem och skickar dem till Bob.

5) Låt Bob välja vilket nummer som helst, till exempel skicka det till Alice, och detta nummer är hennes kort (i det här fallet ).

6) Nu beräknar Bob: .

7) Han skickar siffrorna till Alice, hon väljer till exempel och räknar ut .

8) Alice skickar numret till Bob, han beräknar , så han får sitt kort , det vill säga kortet . Kortet förblir i dragningen, medan Alice och Bob inte vet om det [1] .

Nackdelar

Denna algoritm har nackdelar. När data är krypterad kan vissa egenskaper hos dessa data bevaras från klartext till chiffertext. Detta kan användas för att markera vissa kort. Således måste parterna komma överens om användning av en kortlek där det inte finns kort med egenskaper som bevaras under kryptering.

Dessutom måste krypteringsschemat som används vara säkert mot klartextattacker : Bob kan inte fastställa Alices ursprungliga nyckel [10] .

Toolkit för mentala kortspel

En beskrivning av komplexa protokoll för att utföra och verifiera ett stort antal operationer på kort och kortlekar ges i en artikel av Christian Schindelhauer. Detta arbete behandlar "allmänna ändamål" operationer (blanda, sätta in ett kort i en kortlek) som skapar protokoll som är tillämpliga på alla kortspel [11] .

Biblioteket libtmcg (C++) tillhandahåller en implementering av . Schindelhauer. Det användes för att implementera det tyska kortspelet Skat . Detta spel har 3 spelare och en kortlek med 32 kort, så det finns betydligt färre beräkningar än poker, som har fem till åtta spelare och använder en hel kortlek med 52 kort [12] .

No-shuffle pokerprotokollet

Hittills kan den mentala pokeralgoritmen baserad på standard Alice-Bob-protokollet inte ge hög prestanda i onlinespel. Kravet på att varje spelare krypterar varje kort individuellt medför betydande begränsningar. Golles artikel beskriver ett mentalt pokerprotokoll som uppnår störst effektivitet genom att utnyttja egenskaperna hos pokerspelet och undvika "kryptera-och-shuffla"-modellen [13] . Istället för att blanda kort genererar spelare (krypterade) slumpmässiga nummer som används för att välja nästa kort. Varje nytt kort måste jämföras med resten som redan har delats ut för att upptäcka dubbletter [14] . Således är denna metod mest effektiv i spel som "poker", där antalet kort som delas ut till spelarna är mycket litet jämfört med storleken på hela kortleken [13] .

Kartgenereringsalgoritmen kräver att man organiserar ett kryptosystem med två nyckelegenskaper. Kryptering E måste vara additivt homomorf , det vill säga sådan att: E(c1 )E(c2 ) = E ( c1 + c2 ) . För det andra måste kollisioner upptäckas utan att klartexten avslöjas. Med andra ord, givet E(c 1 ) och E(c 2 ) , kan vi bestämma om c 1 och c 2 är lika . Ett exempel på ett system med sådana egenskaper är ElGamal-krypteringsschemat [15] .

Algoritmen fungerar enligt följande [13] :

  1. Spelare skapar en tom lista L som fångar de kort de använder.
  2. För att dra ett kort beräknar varje spelare ett slumptal r i i {0, ..., 51}, beräknar E(r i ) och lägger upp ett åtagandeschema E(r i ) .
  3. Då visar spelarna sitt värde E(r i ) och du kan se till att varje spelare är ärlig mot de andra.
  4. Spelarna beräknar värdet , som bildar ett nytt krypterat kort E(r*):
  5. Spelare kontrollerar om E(r*) är i L . Om inte, delas E(r*) ut av respektive spelare och läggs till L . När korten avslöjas kan de dechiffreras gemensamt.

Således behöver spelarna bara bestämma vilken kortkrypteringsmetod som används i spelet, samt vissa gränser för kollisioner, som är så små som antalet kort som krävs.

Se även

Anteckningar

  1. ↑ 1 2 3 Ryabko, Fionov, 2004 , sid. 61-65.
  2. ↑ Goldwasser, Micali, 1982 , sid. 374.
  3. ↑ 1 2 3 Goldwasser, Micali, 1982 , sid. 375.
  4. ↑ Fortune, Merritt, 1984 , sid. 455.
  5. ↑ Matematiska rekreationer, 1998 , sid. 41.
  6. ↑ Matematisk blomsterträdgård, 1983 , sid. 58.
  7. ↑ Matematiska rekreationer, 1998 , sid. 37.
  8. ↑ Sergey Larionov. Tankenivåer inom poker - typer, regler för att använda för ett vinnande spel  (ryska)  ? . Poker.ru (5 oktober 2022). Tillträdesdatum: 5 oktober 2022.
  9. ↑ Goldwasser, Micali, 1982 , sid. 365-366.
  10. ↑ Goldwasser, Micali, 1982 , sid. 376-377.
  11. ↑ En verktygslåda för mentala kortspel, 1998 .
  12. ↑ Effektivt elektroniskt spelande: En utökad implementering av verktygslådan för mentala kortspel, 2005 , s. 7.
  13. ↑ 1 2 3 Golle, 2005 , sid. 1-3.
  14. ↑ Golle, 2005 , sid. 6.
  15. ↑ Golle, 2005 , sid. fyra.

Litteratur