Noll kunskapsbevis

Zero-knowledge proof (information) i kryptografi ( eng.  Zero-knowledge proof ) är ett interaktivt kryptografiskt protokoll som tillåter en av de interagerande parterna ("The verifier" - verifiering) att verifiera giltigheten av något påstående (vanligtvis matematiskt), utan att ha detta är ingen annan information från den andra parten ("Bevisaren" - bevisar). Dessutom är det sista villkoret nödvändigt , eftersom det vanligtvis är trivialt att bevisa att en part har viss information i de flesta fall , om den har rätt att helt enkelt lämna ut information. Hela svårigheten ligger i att bevisa att någon av parterna har information utan att avslöja dess innehåll. Protokollet måste ta hänsyn till att bevisaren kommer att kunna övertyga verifieraren endast om påståendet faktiskt bevisas. Annars kommer det att vara omöjligt att göra detta, eller extremt osannolikt på grund av beräkningskomplexitet .

Protokollinteraktivitet avser parternas direkta informationsutbyte [1] [2] .

Således kräver protokollet som övervägs interaktiv input från verifieraren , vanligtvis i form av en uppgift eller ett problem. Syftet med den juridiska bevisaren (att ha bevis ) i detta protokoll är att övertyga verifieraren om att han har en lösning, utan att ge bort ens en del av det "hemliga" beviset ("noll kunskap"). Syftet med verifieraren är att säkerställa att den bevisande parten "inte ljuger" [2] [3] .

Protokoll för nollkunskapssäkring [4] [5] har också utvecklats som inte kräver en interaktiv ingång, och beviset för vilka vanligtvis förlitar sig på antagandet om en idealisk kryptografisk hashfunktion , dvs. det antas att utdata från en etta -way hash -funktion kan inte förutsägas om dess ingång inte är känd [6] .

Zero-knowledge proof används i flera blockkedjor, dessutom används det för att kontrollera förekomsten av information utan att överföra själva informationen [7] [8] .

Definition

Zero-knowledge proof är ett interaktivt probabilistiskt protokoll som låter dig bevisa att påståendet som bevisas är sant, och Bevisaren känner till detta bevis, samtidigt som den inte tillhandahåller någon information om beviset för detta påstående i sig [9] . Detta kryptografiska protokoll måste ha tre egenskaper:

  1. Fullständighet : Om påståendet verkligen är sant, kommer Provern att övertyga Verifieraren om detta med någon förutbestämd noggrannhet.
  2. Korrekthet : om påståendet är falskt, kommer alla, till och med "oärliga", Prover inte att kunna övertyga verifieraren förutom med en försumbar sannolikhet .
  3. Noll kunskap : om påståendet är sant, så kommer alla, till och med "oärliga", Verifier att veta något annat än själva det faktum att påståendet är sant [10] .

Nollkunskapsbevis är inte bevis i termens matematiska mening , eftersom det finns en liten chans att bevisaren kan luras att övertyga verifieraren om ett falskt påstående ( korrekthetsfel ). Med andra ord, nollkunskapsbevis är probabilistiska bevis, inte deterministiska . Det finns dock metoder för att reducera korrekthetsfelet till försumbara värden [11] [12] .

Olika typer av nollkunskap

Att köra nollkunskapsbevisprotokollet ger ett Acceptera/Avvisa-resultat och genererar även en transkription av beviset. Olika varianter av nollkunskap kan definieras genom att formalisera själva konceptet och jämföra distributionen av information för olika modeller med protokollet på följande sätt [13] [14] :

Utvecklingshistorik

1986 beskrev Silvio Micali , Oded Goldreich Avi Wigderson användningen av nollkunskapsbevis för att skapa kryptografiska protokoll som skulle säkerställa "rättvist beteende" för parterna samtidigt som konfidentialitet bibehålls [19] .

Noll-kunskapsbeviset skapades och utvecklades av följande forskare: Shafi Goldwasser , Silvio Micali och Charles Reckoff , och publicerades av dem i tidningen "Knowledge and Complexity of an Interactive System with Proof" [20] 1989 . Detta arbete presenterade en hierarki av interaktiva bevissystem baserat på mängden bevisinformation som måste skickas från Prover till Verifier. De föreslog också det första beviset på ett specifikt angivet nollkunskapsbevis, en kvadratisk restmodulo m [ 21] . Därefter, som komplement till deras arbete, belönades de med det första Gödelpriset 1993 [ 22] .

Goldwasser -Micali-kryptosystemet , baserat på det övervägda interaktiva protokollet, som är ett kryptografiskt system med offentlig nyckel utvecklat av Shafi Goldwasser och Silvio Micali 1982 , är det första probabilistiska krypteringsschemat med offentliga nyckel som bevisligen är säkert under standardkryptografiska antaganden. . Det föreslagna systemet uppskattades mycket av juryn: Goldowasser och Micali blev pristagare av Turing Award för 2012 [23] , för skapandet av ett kryptosystem med probabilistisk kryptering, noterat i nomineringen som ett innovativt verk som hade en betydande inverkan på modern kryptografi . Dock är kryptosystemet ineffektivt, eftersom chiffertexten som genereras av det kan vara hundratals gånger längre än det krypterade meddelandet .

För att bevisa säkerhetsegenskaperna hos ett kryptosystem introducerade Goldwasser och Micali begreppet semantisk säkerhet [24] [25] .

2021 tilldelades Laszlo Lovas och Avi Wigderson Abelpriset för sitt arbete inom teoretisk datavetenskap , som gav ett stort bidrag till utvecklingen av beräkningskomplexitetsteori, grafteori, distribuerade beräkningsmetoder och konceptet med nollkunskapsbevis [ 26] .

Allmän struktur för nollkunskapsbevis

Varje omgång, eller bevisackreditering , består av tre steg. Schematiskt kan de avbildas enligt följande:

Först väljer A något element från en förutbestämd icke-tom uppsättning , som blir dess hemliga - privata nyckel . Baserat på detta element beräknas den publika nyckeln och publiceras sedan . Att känna till hemligheten avgör den uppsättning frågor som A alltid kan ge de rätta svaren på. Sedan väljer A ett slumpmässigt element från mängden, enligt vissa regler (beroende på den specifika algoritmen) beräknar beviset och skickar det sedan till B . Därefter väljer B en fråga från hela uppsättningen och ber A att svara på den (utmaning). Beroende på frågan skickar A ett svar till B [27] . Den mottagna informationen B räcker för att kontrollera om A verkligen äger hemligheten. Omgångarna kan upprepas hur många gånger som helst tills sannolikheten att A "gissar" svaren är tillräckligt låg. Detta tillvägagångssätt kallas också "klipp-och-välj", som först användes i kryptografi av Michael Rabin [28] [29] .

Exempel

Zero Knowledge Cave

Det här exemplet skrevs först i det välkända nollkunskapsprovet "How to explain the zero-knowledge proof protocol to your children" av Jean-Jacques Kiskater.[30] .

I det här fallet agerar Peggy som Prover och Victor som Verifier (i engelsk litteratur används vanligtvis namnen på parterna Peggy och Victor (från "Prover" respektive "Verifier"). Peggy kan det magiska ordet ("nyckel") "), ingång som gör att hon kan öppna dörren mellan C och D. Victor vill veta om Peggy verkligen kan lösenordet, medan Peggy inte vill ge ut lösenordet själv. Grottan har en rund form, som visas i figur.För att lösa problemet går de tillväga på följande sätt: Medan Victor är vid punkt A, går Peggy till dörren, och efter att hon försvunnit från synhåll går Victor till vägskälet, det vill säga till punkt B, och ropar därifrån: "Peggy måste gå ut till höger " eller "Peggy måste gå ut till vänster " Vi får varje gång sannolikheten att Peggy inte känner till lösenordet är lika med 50%.Om vi ​​upprepar processen k gånger, då blir sannolikheten.Med 20 repetitioner kommer denna sannolikhet att vara av storleksordningen 10 −6 , vilket är tillräckligt för rättvisa . Dessa antaganden att Peggy känner till nyckeln [30] .

Om Victor spelar in allt som händer på kameran kommer den resulterande videon inte att vara bevis för någon annan part. De kunde trots allt ha kommit överens i förväg var Peggy skulle komma ifrån. Följaktligen kommer hon att kunna hitta en väg ut utan att känna till själva nyckeln. Det finns ett annat sätt: Victor klipper helt enkelt bort alla Peggys misslyckade försök. Dessa steg ovan bevisar att grottexemplet uppfyller egenskaperna för fullständighet , korrekthet och noll kunskap [31] .

Hamiltonsk cykel för stora grafer

Detta exempel uppfanns av Manuel Blum och beskrivs i hans papper 1986 [32] . Låt oss kalla testaren Victor och provaren Peggy. Låt oss säga att Peggy känner till en Hamiltonsk cykel i en stor graf G . Victor känner till grafen G , men han känner inte till Hamiltons cykel i den. Peggy vill bevisa för Victor att hon kan den Hamiltonska cykeln, utan att avslöja själva cykeln eller någon information om den (kanske Victor vill köpa information om denna Hamiltonska cykel från Peggy, men innan dess vill han försäkra sig om att Peggy verkligen känner honom ).

För att göra detta utför Victor och Peggy tillsammans flera omgångar av protokollet :

I varje omgång väljer Victor en ny slumpmässig bit som Peggy inte känner till, så för att Peggy ska kunna svara på båda frågorna måste H verkligen vara isomorf till G , och Peggy måste känna till Hamiltons cykel i H (och därmed även i G ). Därför kan Victor efter ett tillräckligt antal omgångar vara säker på att Peggy verkligen har kunskap om Hamiltons cykel i G . Å andra sidan avslöjar Peggy ingen information om Hamiltons cykel i G . Dessutom kommer det att vara svårt för Victor att bevisa för någon annan att han eller Peggy känner till Hamiltons cykel i G [32] .

Anta att Peggy inte känner till Hamiltons cykel i G , men hon vill lura Victor. Sedan behöver Peggy en icke-isomorf G - graf G′ , där hon fortfarande känner till Hamiltons cykel . I varje omgång kan hon passera till Victor antingen H′  — isomorf till G′ eller H  — isomorf till G . Om Victor ber om att bevisa grafernas isomorfism, och H gavs till honom , kommer bedrägeriet inte att avslöjas. På samma sätt, om han ber om att visa en Hamilton-cykel, och han fick H′ . I det här fallet är sannolikheten att Peggy fortfarande kommer att lura Victor efter k rundor lika med , vilket kan vara mindre än vilket förutbestämt värde som helst givet ett tillräckligt antal rundor [32] .

Låt oss anta att Victor inte känner igen Hamiltons cykel, utan vill bevisa för Bob att Peggy vet det. Om Victor till exempel filmade alla omgångarna i protokollet skulle Bob knappt tro honom. Bob kan anta att Victor och Peggy står i ledarled, och varje runda berättar Victor för Peggy om sitt val av slumpmässig bit i förväg så att Peggy kan ge honom H för isomorfismtest och H′ för Hamiltonska cykeltest. Således, utan deltagande av Peggy, är det möjligt att bevisa att hon känner till Hamiltons cykel endast genom att bevisa att verkligt slumpmässiga bitar valdes i alla omgångar av protokollet [33] .

Tillämpning i praktiken

Satsen som säger att för alla NP-kompletta problem finns det ett noll-kunskapsbevis, medan man använder envägsfunktioner kan man skapa korrekta kryptografiska protokoll , bevisades av Oded Goldreich , Silvio Micali och Avi Wigderson [19] [ 34] . Det vill säga, du kan bevisa för alla skeptiker att du har ett bevis på någon matematisk sats utan att avslöja själva beviset. Detta visar också hur detta protokoll kan användas för praktiska ändamål [13] .

Nästa metod där nollkunskapsbevis kan användas är identitetsbestämning, där Peggys privata nyckel är den så kallade "identitetsindikatorn", och med hjälp av protokollet i fråga kan man bevisa sin identitet. Det vill säga att du kan bevisa din identitet utan att använda olika fysiska enheter och data (symboler), såsom pass, olika bilder på en person (näthinna, fingrar, ansikte etc.), men på ett fundamentalt annorlunda sätt [35] . Det har dock ett antal nackdelar som kan användas för att kringgå skydd. Metoden som beskrivs ovan föreslogs först av Amos Fiat , Adi Shamir och Uriel Feige 1987 [ 36] .

Noll-kunskapsbevis kan också användas i konfidentiella datorprotokoll , vilket gör att flera deltagare kan verifiera att den andra parten följer protokollet ärligt [19] .

Nollkunskapsbevis används i blockkedjorna för kryptovalutorna Zcash , Byzantium (en gaffel av Ethereum ), Zerocoin och andra. Implementeringar av nollkunskapssäkra protokoll har skapats, i synnerhet QED-IT Software Development Kit. Den holländska banken ING skapade sin egen version av protokollet, ZKRP ( Zero-Knowledge Range Proof ), och tillämpade det för att bevisa att kunden har en tillräcklig lön utan att avslöja dess verkliga storlek [7] [8] .

De mest utbredda protokollen är zk-SNARKs, det är protokollen i denna klass som används i ZCash, Zcoin och i Metropolis-protokollet för Ethereum blockchain [37] [8] .

Förkortningen zk-SNARK står för   zero-knowledge succinct non-interactive argument of knowledge [37] [8] . zk-SNARK-algoritmen består av en nyckelgenerator, en provare och en verifierare, stöder nödvändigtvis noll kunskap, har korthet (beräknat på kort tid), är icke-interaktiv (verifieraren får bara ett meddelande från provaren) [8] .

Missbruk

Flera sätt att missbruka nollkunskapsbevis har föreslagits som utnyttjar vissa svagheter i protokollet:

Stormästarproblem

I det här exemplet kan någon part bevisa innehav av hemligheten utan att faktiskt ha den, eller, med andra ord, kan imitera personen som faktiskt äger hemligheten [38] . För närvarande har ett sätt att lösa problemet föreslagits av Thomas Beth och Ivo Desmedt [39] .

Bedrägeri med flera identiteter

Om en part kan skapa flera hemligheter, kommer den också att kunna skapa "flera identiteter" i enlighet med detta. Låt en av dem aldrig användas. Denna möjlighet ger anonymitet en gång, vilket gör att man till exempel kan undandra sig ansvar: parten identifierar sig som en aldrig använd person och begår ett brott. Därefter används aldrig denna "identitet" igen. Det är nästan omöjligt att spåra eller matcha gärningsmannen med någon. Sådant missbruk förhindras om möjligheten att skapa en andra hemlighet utesluts från början [40] .

Bedrägeri utfört av maffian

Ytterligare ett exempel på att ena sidan låtsas vara den andra. Låt det vara 4 deltagare: A , B , C , D . Dessutom samarbetar B och C med varandra ("tillhör samma maffia"). A bevisar sin identitet för B och C vill imitera A framför D. B äger en restaurang som ägs av maffian, C  är också representant för maffian, D  är juvelerare. A och D är omedvetna om det kommande bedrägeriet. I samma ögonblick som A är redo att betala för middagen och identifierar sig för B , meddelar B C om starten på bluffen. Detta är möjligt på grund av närvaron av en radiokanal mellan dem. Vid denna tidpunkt väljer C diamanten han vill köpa, och D börjar identifiera identiteten för C , som utger sig för att vara A. C skickar protokollfrågan till B , som i sin tur ställer den till A. Svaret sänds i omvänd ordning. Således kommer A att betala inte bara för middagen, utan också för den dyra diamanten. Som framgår av ovanstående finns det vissa krav för sådant bedrägeri. När A börjar bevisa sin identitet för B , och C  till D , måste B och C :s handlingar synkroniseras. Även detta övergrepp är tillåtet. Till exempel, om det finns en Faraday-bur i en juvelerares butik , kommer "mafiosi" inte att kunna utbyta meddelanden [41] .

Möjliga attacker

Vald chiffertextattack

Denna attack är genomförbar med en icke-interaktiv interaktionsmetod i ett noll-kunskapsprotokoll.

Det finns flera problem med detta protokoll. Först måste du bestämma hur du vill interagera, samtidigt som du behåller de grundläggande funktionerna i själva protokollet: fullständighet, korrekthet och "noll kunskap". Förutom att det är ganska lätt att bevisa noll kunskap för motparten, om det går att avlyssna kanalen, det vill säga att möta stormästarproblemet .

Så själva attacken är som följer: angriparen, med hjälp av komplexiteten i beviset för att ha kunskap, inkluderar den "attackerande" chiffertexten , och glider in den i en massa andra chiffertexter som måste dekrypteras. Denna attack kallas "playback"-attack [42] .

En möjlig lösning är baserad på arbetet av Moni Naor och Moti Yung , vilket är följande: Prover och Verifier krypterar meddelanden med en publik nyckel , detta gör att ovanstående attack misslyckas [43] .

En attack på ett noll-kunskapssystem med flera protokoll

Chida och Yamamoto föreslog en implementering av nollkunskapsprotokollet som avsevärt ökar hastigheten på nollkunskapsbevis samtidigt som de bevisar flera påståenden samtidigt och, som ett resultat, prestandan för hela systemet [44] . Nyckelfunktionen är begränsningen av antalet iterationer för ett bevis. Som framgår av K. Pengs arbete [45] visade sig denna algoritm vara helt instabil inför nästa attack. Genom att använda flera väl valda iterationer kan en angripare klara verifieringen och bryta mot huvudbestämmelserna i protokollet. Dessutom visades det att denna attack alltid är genomförbar på ett sådant system.

Attackera med en kvantdator

2005 visade John Watrus [ att inte alla nollkunskapssystem är resistenta mot kvantdatorattacker . Det har dock visat sig att det alltid är möjligt att bygga ett system som är resistent mot kvantattacker, förutsatt att det finns kvantsystem med "döljande av skyldigheter" [46] .

Se även

Anteckningar

  1. ↑ Goldreich, 2013 .
  2. ↑ 1 2 Schneier, 2002 , s. 87-92.
  3. ↑ Goldwasser, Micali, Rackoff, 1989 , s. 186-189.
  4. ↑ Santis, Micali, Persiano, 1988 .
  5. ↑ Blum, Feldman, Micali, 1988 .
  6. ↑ Schneier, 2002 , s. 90-91.
  7. ↑ 12 ForkLog , 2019 .
  8. ↑ 1 2 3 4 5 Gubanova, 2018 .
  9. ↑ Blum, 1988 , sid. 1444.
  10. ↑ Menezes et al, 1996 , sid. 406-408.
  11. ↑ Schneier, 2002 , s. 86-89.
  12. ↑ Goldwasser, Micali, Rackoff, 1989 , s. 188-189.
  13. ↑ 1 2 Schneier, 2002 , s. 91-92.
  14. ↑ Mao, 2005 , s. 683-696.
  15. ↑ Mao, 2005 , s. 684-688.
  16. ↑ Sahai, Vadhan, 2003 .
  17. ↑ Mao, 2005 , sid. 696.
  18. ↑ Mao, 2005 , s. 692-696.
  19. ↑ 1 2 3 Goldreich, Micali, Wigderson, 1986 .
  20. ↑ Goldwasser, Micali, Rackoff, 1989 .
  21. ↑ Goldwasser, Micali, Rackoff, 1989 , s. 198-205.
  22. ↑ Goldwasser, Micali och Rackoff får Gödelpriset 1993 (länk ej tillgänglig) . ACM Sigact (1993). Arkiverad från originalet den 8 december 2015. 
  23. ↑ Goldwasser, Micali får ACM Turing Award för framsteg inom kryptografi (länk ej tillgänglig) . ACM. Hämtad 13 mars 2013. Arkiverad från originalet 16 mars 2013. 
  24. ↑ Goldwasser, Micali, 1982 .
  25. ↑ Mao, 2005 , s. 524-528.
  26. ↑ Abelpriset - 2021 • Andrey Raigorodsky • Nyheter om vetenskap om "element" • Matematik, vetenskap och samhälle . Hämtad 17 maj 2021. Arkiverad från originalet 3 juni 2021.
  27. ↑ Mao, 2005 , s. 678-682.
  28. ↑ MORabin. digitala signaturer . — Grunderna för säker datoranvändning. - New York: Academic Press, 1978. - S. 155-168. — ISBN 0122103505 .
  29. ↑ Schneier, 2002 , s. 87-89.
  30. ↑ 12 Quisquater et al, 1990 .
  31. ↑ Schneier, 2002 , s. 87-88.
  32. ↑ 1 2 3 4 Blum, 1988 .
  33. ↑ Schneier, 2002 , s. 89-90.
  34. ↑ Goldreich, Micali, Wigderson, 1987 .
  35. ↑ Schneier, 2002 , sid. 92.
  36. ↑ Fiat, Shamir, 1987 .
  37. ↑ 12 Chain Media, 2017 .
  38. ↑ Schneier, 2002 , s. 92-93.
  39. ↑ Beth, Desmedt, 1991 .
  40. ↑ Schneier, 2002 , s. 93-94.
  41. ↑ Schneier, 2002 , sid. 93.
  42. ↑ Rackoff, Simon, 1992 .
  43. ↑ Naor, Yung, 1990 .
  44. ↑ Chida, Yamamoto, 2008 .
  45. ↑ Peng, 2012 .
  46. ↑ Watrous, 2006 .

Litteratur

böcker och monografier artiklar

Länkar