Dining Cryptographer Problem

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

Dining kryptografens problem handlar om sätt att säkert utvärdera en boolesk ELLER- funktion på många sätt . David Chaum identifierade detta problem först 1988 och använde ett illustrativt exempel för att visa att det är möjligt att skicka anonyma meddelanden utan begränsningar för avsändaren och ospårbarhet av mottagarens adress [1] [2] . Anonyma kommunikationsnätverk som kan lösa detta problem kallas ofta för DC-nätverk .

Trots ordet "matställe" har problemet med matkryptograferna ingenting att göra med matfilosofernas problem .

Beskrivning

Tre kryptografer samlades vid middagsbordet. Servitören informerar dem om att deras mat redan är betald av någon. Det kan vara en av kryptograferna eller National Security Agency (NSA). Kryptograferna respekterar en väns rätt att göra en betalning anonymt, men vill ta reda på om National Security Agency betalat. Så de bestämmer sig för att implementera ett tvåstegsprotokoll.

I det första steget bestämde varannan kryptograf en delad hemlighet på en bit genom att gå med på att kasta ett mynt. De gömde sig bakom menyn på ett sådant sätt att bara de två kastande kryptograferna kan se resultatet av kastningen. Låt oss anta att efter att ha kastat ett mynt har kryptograferna A och B en gemensam hemlighet - kryptograferna A och C- , B och C- .

I det andra steget tillkännager varje kryptograf offentligt en bit, som beräknas enligt följande:

Anta att ingen av kryptograferna betalade, då kommer kryptograf A att meddela , B kommer att meddela , C - . Å andra sidan, om kryptograf A gjorde en betalning kommer han att meddela .

I slutet av det andra steget avslöjas sanningen. En av kryptograferna utför XOR-operationen av alla deklarerade bitar. Om resultatet är , betyder det att ingen av kryptograferna betalade (så vi kan dra slutsatsen att betalningen gjordes av NSA). Annars, om en av kryptograferna betalade, förblir hans identitet okänd för alla andra kollegor.

För detta problem myntade David Chaum termen "Dinner Cryptographer Problem", samt ett namn för nätverk som kan lösa detta problem [2] [3] .

Begränsningar

David Chaums ursprungliga arbete postulerar flera begränsningar som kan påverka den praktiska användningen av DC-nätverksprotokollet.

Kollisioner Om två kryptografer betalade för lunch, kommer deras meddelanden att överlappa varandra, och resultatet av XOR-operationen för paret i fråga blir 0. Denna situation kallas en kollision, i vilket fall endast en betalande deltagare får använda detta protokoll för att överföra sitt meddelande inom den aktuella omgången [4] [2] . Kränkningar Alla illvilliga kryptografer som inte vill att gruppen ska kommunicera framgångsrikt kan blockera protokollet så att det slutliga resultatet av XOR-operationen är värdelöst. Det är möjligt att begå en grymhet genom att skicka godtyckliga bitar istället för det korrekta resultatet av XOR-operationen. Detta problem uppstår eftersom det ursprungliga protokollet utformades utan en mekanism för att kontrollera om deltagarna följer protokollet rättvist [5] [2] [6] . Komplexitet Protokollet kräver parvis delade hemligheter mellan deltagare, vilket är svårt när det finns ett stort antal deltagare [7] [8] .

Generaliseringar

DC-nätverk är generaliserade för att tillhandahålla sändningar större än en bit för fler än tre deltagare, och för godtyckliga bokstäver i alfabetet andra än binära 0 och 1.

Skicka långa meddelanden

För att en anonym avsändare ska kunna sända mer än en bit information i en omgång av exekvering av DC-nätverksprotokollet, kan en grupp kryptografer helt enkelt upprepa protokollet så många gånger som behövs för att skapa önskat antal bitar ( baserat på kanalens bandbredd). I DC-nätverk har par av deltagare möjlighet att i förväg komma överens om en gemensam nyckel, med till exempel en nyckel som erhålls med hjälp av Diffie-Hellman-protokollet . Varje deltagare ställer sedan in denna delade nyckel lokalt i en pseudo-slumptalsgenerator för att producera så många vanliga "myntvändningar" som möjligt, vilket gör att den anonyma avsändaren kan överföra några bitar av information [9] [2] .

Fler medlemmar

Protokollet kan tillämpas på en grupp som består av deltagare, som var och en delar en hemlig nyckel med resten av deltagarna. I varje omgång av protokollet, om en deltagare vill skicka ett meddelande som inte kan spåras till hela gruppen, inverterar han sina offentligt tillkännagivna bitar. Deltagarna kan representeras som en komplett graf , där hörnen är deltagarna och kanterna är deras delade hemliga nycklar [2] [4] .

Diagram för delad åtkomst

Protokollet kan köras med hjälp av en ofullständig graf med publik nyckel, vilket kan förbättra prestandan och skalbarheten hos praktiska DC-nätverk. Vid användning av en ofullständig graf finns det dock en risk att deltagarna i samverkan kan dela upp delningsdiagrammet i separata anslutningskomponenter och uppnå anonymitetskränkning. Till exempel, för en grupp på fler än tre deltagare, är alternativet ringtopologi attraktivt , där varje kryptograf som sitter vid bordet delar en hemlig nyckel endast med kollegor som sitter direkt till vänster och till höger om honom. Denna topologi är attraktiv, eftersom varje kryptograf måste koordinera två myntkast i en omgång, snarare än kast, som är fallet med den ursprungliga fullständiga nyckelgrafen. Men om NSA-agenterna Adam och Charlie, som sitter omedelbart till vänster och höger om Commoner Bob, i hemlighet skulle samarbeta och avslöja sina hemliga nycklar för varandra, så skulle de med säkerhet kunna avgöra om Bob är avsändaren av det aktuella meddelandet. inom den aktuella omgången, oavsett det totala antalet deltagare. Denna effekt uppstår på grund av det faktum att de konspirerande deltagarna, Adam och Charlie, "delade upp" grafen för allmänhetens tillgång i två oberoende disparata komponenter, av vilka den ena endast består av Bob, den andra av alla andra ärliga deltagare [5] .

En annan topologi för det offentliga DC-nätverket som används i Dissent- systemet för skalning [10] kan beskrivas som en klient-server- topologi. Det här alternativet definierar två typer av deltagare som spelar olika roller: ett potentiellt stort antal användare som vill förbli anonyma och ett mycket mindre antal betrodda individer vars roll är att säkerställa anonymiteten för alla användare. I en sådan topologi delar var och en av användarna en hemlig nyckel med var och en av de betrodda parterna, men användarna delar inte hemliga nycklar med varandra direkt, precis som förvaltarna inte delar hemliga nycklar med varandra - resultatet är en interaktionsmatris . Om antalet betrodda personer är litet behöver varje användare bara känna till ett fåtal delade hemligheter, vilket förbättrar effektiviteten i användarinteraktion på samma sätt som gjordes i ringtopologin. Men så länge som minst en medlem av den betrodda personen är ärlig och inte ger ifrån sig sina hemligheter eller samarbetar med andra medlemmar, blir denna ärliga förvaltare ett nav som förbinder alla ärliga användare till en som interagerar med alla dess delar till komponenten, oavsett om andra användare eller betrodda personer har ingått i oärlig maskopi. Användare behöver inte veta eller gissa vilka förtrogna som är ärliga; deras säkerhet, enligt författarna till protokollet, beror endast på förekomsten av minst en ärlig, icke-samverkande proxy.

Alternativa alfabet och operatorer

Även om det enkla DC-nätverksprotokollet använder binärt som överföringsalfabet och XOR-operatören för att kombinera chiffertexter, använder kärnprotokollet båda alfabetet och använder XOR-liknande operatorer som är giltiga för användning i Werman-kryptering . Sådan flexibilitet uppstår naturligt, eftersom hemligheterna är fördelade mellan många par av deltagare, som faktiskt implementerar Verman-kryptering sinsemellan inom en omgång av DC-nätverket [11] .

Ett alternativt val av DC-nätverksalfabet är att använda en ändlig grupp som är lämplig för användning i kryptografi med publik nyckel. Det är till exempel acceptabelt att använda Schnorr-grupper eller elliptiska kurvor . Detta val av alfabet tillåter deltagarna att använda noll-kunskapsbevis för att verifiera chiffertexten som produceras av protokollet. I synnerhet kontrolleras om en av deltagarna bryter mot protokollet, och anonymiteten som tillhandahålls av DC-nätverket observeras under kontrollen. Denna teknik föreslogs först av Goll och Juels [12] och implementerades i Verdict , en implementering av Dissent [13] .

Undvikande och hantering av kollisioner

Chaums originalpapper föreslår följande metod för att hantera kollisioner. Användaren som för närvarande skickar ett meddelande på DC-nätverket tar emot den resulterande biten i varje omgång av dess överföring. Om den resulterande biten inte matchar den han vill sända i den aktuella omgången, drar användaren slutsatsen att en kollision har inträffat. Den väntar ett slumpmässigt antal omgångar och skickar om sitt meddelande. Chaum föreslår att man väljer specifika vidarekopplingsparametrar baserat på analys av trafiken i nätverket [4] .

Oliktänkande förhindrar oavsiktliga nätverkskollisioner genom att använda ett meddelandeöverföringsschema. Schemat skapas genom att slumpmässigt blanda deltagarna, där varje deltagare vet vilka av de föreslagna överföringsbitarna som tillhör hans kö, men inte vem som äger de återstående bitarna [14] .

Herbivore uppmanar också deltagarna att komma överens om ett meddelandeschema för varje kommunikationsrunda. Varje deltagare väljer en slumpmässig lucka i schemat för överföring, och om denna lucka används av någon annan, så vägrar deltagaren i fråga att överföra. Om en deltagare väntar för länge på sin plats kommer han automatiskt att återansluta till gruppen efter en tidsperiod som bestäms av protokollet. Protokollet tillhandahåller kontroll av dataintegritet med hjälp av MD5-hashalgoritmen [15] .

Motverka protokollöverträdelser

Herbivore delar upp DC-nätverket i flera grupper, vilket gör att deltagarna kan gå bort från kränkningar. Deltagaren kan lämna sin nuvarande grupp och kontrollera andra tills han hittar en grupp som är fri från kränkningar [16] . Detta tillvägagångssätt kan leda till att en angripare med tillgång till många grupper i DC-nätverket kan manipulera beteendet hos en deltagare, vilket leder till att han deltar i en grupp där alla andra deltagare är i maskopi [17] .

Oliktänkande implementerar flera system för att motverka kränkningar. Det ursprungliga protokollet [18] använder slumpmässiga meddelandeöverföringsscheman och sprider överföringstabellen tillsammans med storleken på det aktuella meddelandet. Detta tillvägagångssätt låter dig kontrollera riktigheten av chiffertextsekvensen i DC-nätverket genom att beräkna hashfunktionen . Denna teknik leder dock till stora, enligt författarnas beräkningar, förseningar i överföringen av meddelanden. Senare föreslogs ett annat motåtgärdsschema som inte blandar sig för att bygga ett överföringsschema i frånvaro av störningar, men om störningar börjar i nätet återupptas blandningen och det blir möjligt att beräkna förövaren. De senaste versionerna av Dissent stöder full DC-nätverksverifiering till en betydande beräkningskostnad på grund av användningen av ett kryptosystem med publik nyckel . Samtidigt kan moderna versioner av Dissent köras i hybridläge , som använder traditionella XOR-baserade DC-nätverk i normalfallet, och använder verifierbara DC-nätverk endast vid överträdelser. Enligt författarna till protokollet gör detta tillvägagångssätt det möjligt att beräkna inkräktaren snabbare än vad som är möjligt genom att bygga ett överföringsschema baserat på blandning [19] .

Anteckningar

  1. ↑ The Dining Cryptographers Problem: Ovillkorlig avsändare och mottagarens ospårbarhet, 1988 , 1.4. bevis på säkerhet.
  2. ↑ 1 2 3 4 5 6 Tillämpad kryptografi. Protokoll, algoritmer, källtexter i C-språk. 2:a upplagan, 2002 , 6.3 Anonyma sändningsmeddelanden.
  3. ↑ Dining Cryptographers Problem: Ovillkorlig avsändare och mottagarens ospårbarhet, 1988 , Inledning.
  4. ↑ 1 2 3 The Dining Cryptographers Problem: Ovillkorlig avsändare och mottagare ospårbarhet, 1988 , 1. Generalizing the Approach.
  5. ↑ 1 2 The Dining Cryptographers Problem: Ovillkorlig avsändare och mottagarens ospårbarhet, 1988 , 1.3. Kollision av deltagare.
  6. ↑ Problem om riddare och knavar
  7. ↑ The Dining Cryptographers Problem: Ovillkorlig avsändare och mottagarens ospårbarhet, 1988 , 2.3. Exempel på nyckeldelningsdiagram.
  8. ↑ Ett 2-runda anonymt vetoprotokoll, 2009 , 3. Prestanda.
  9. ↑ Dining Cryptographers Revisited, 2004 , 2 Bakgrund.
  10. ↑ Oliktänkande i siffror: att göra stark anonymitetsskala, 2012 , 3.2 Antaganden om design och implementering.
  11. ↑ Proactively Accountable Anonymous Messaging in Verdict, 2013 , 2.3 Praktiska generaliseringar.
  12. ↑ Dining Cryptographers Revisited, 2004 , 4.1 Intuition och verktyg.
  13. ↑ Proactively Accountable Anonymous Messaging in Verdict, 2013 , 5.1 Verifierbart DC-net Primitive API.
  14. ↑ Avvikande mening: Ansvarsfulla anonyma gruppmeddelanden, 2010 , 5.5 End-to-end-tillförlitlighet.
  15. ↑ Växtätare: Ett skalbart och effektivt protokoll för anonym kommunikation, 2003 , 4.2 Round Protocol.
  16. ↑ Undvika köttätare: Fildelning med stark anonymitet, 2004 , 3 växtätare.
  17. ↑ Denial of service eller denial of security?, 2004 , 1. INLEDNING.
  18. ↑ Avvikande mening: Ansvarsfulla anonyma gruppmeddelanden, 2010 , 7. RELATERAT ARBETE.
  19. ↑ Proactively Accountable Anonymous Messaging in Verdict, 2013 , 4.4 Hybrid XOR/Verifiable DC-Nets.

Litteratur