Nul vidensbevis

Zero-knowledge proof (information) i kryptografi ( eng.  Zero-knowledge proof ) er en interaktiv kryptografisk protokol , der gør det muligt for en af ​​de interagerende parter ("The verifier" - verificerende) at verificere gyldigheden af ​​ethvert udsagn (normalt matematisk), uden at at have dette er ingen anden information fra den anden part ("Beviseren" - bevis). Desuden er den sidste betingelse nødvendig , da det normalt er trivielt at bevise, at en part har visse oplysninger i de fleste tilfælde , hvis den har ret til blot at videregive oplysninger. Hele vanskeligheden ligger i at bevise, at en af ​​parterne har oplysninger uden at afsløre deres indhold. Protokollen skal tage højde for, at beviseren kun vil være i stand til at overbevise verifikatoren , hvis påstanden faktisk er bevist. Ellers vil det være umuligt at gøre dette, eller ekstremt usandsynligt på grund af beregningsmæssig kompleksitet .

Protokolinteraktivitet henviser til parternes direkte udveksling af oplysninger [ 1] [2] .

Den pågældende protokol kræver således interaktivt input fra verifikatoren , normalt i form af en opgave eller et problem. Formålet med den juridiske bevis (med bevis ) i denne protokol er at overbevise verifikatoren om, at han har en løsning, uden at afgive en del af det "hemmelige" bevis ("nulviden"). Formålet med verifikatoren er at sikre, at den bevisende part "ikke lyver" [2] [3] .

Nulvidenssikre protokoller [4] [5] er også blevet udviklet , som ikke kræver et interaktivt input, og beviset heraf er typisk baseret på antagelsen om en ideel kryptografisk hash-funktion , dvs. det antages, at outputtet af en one -way hash -funktion kan ikke forudsiges, hvis dens input ikke er kendt [6] .

Zero-knowledge proof bruges i flere blockchains, derudover bruges det til at kontrollere eksistensen af ​​information uden at overføre selve informationen [7] [8] .

Definition

Zero-knowledge proof er en interaktiv probabilistisk protokol , der giver dig mulighed for at bevise, at den påstand, der bevises, er sand, og Beviseren kender dette bevis, samtidig med at den ikke giver nogen information om beviset for denne påstand i sig selv [9] . Denne kryptografiske protokol skal have tre egenskaber:

  1. Fuldstændighed : Hvis udsagnet faktisk er sandt, vil Beviseren overbevise Verifikator om dette med enhver forudbestemt nøjagtighed.
  2. Korrekthed : hvis udsagnet er falsk, så vil enhver, selv "uærlig", Prover ikke være i stand til at overbevise verifikatoren med undtagelse af en ubetydelig sandsynlighed .
  3. Nul viden : hvis udsagnet er sandt, så vil enhver, selv "uærlig", Verifier ikke vide andet end selve det faktum, at udsagnet er sandt [10] .

Nulvidensbeviser er ikke beviser i begrebets matematiske forstand , fordi der er en lille chance for, at beviseren kan narre til at overbevise verifikatoren om en falsk udsagn ( korrekthedsfejl ). Med andre ord er nulvidensbeviser probabilistiske beviser, ikke deterministiske beviser . Der er dog metoder til at reducere korrekthedsfejlen til ubetydelige værdier [11] [12] .

Forskellige typer af nul viden

Kørsel af nul-viden bevis- protokollen producerer et Accept/Afvis-resultat og genererer også en transskription af beviset. Forskellige varianter af nulviden kan defineres ved at formalisere selve konceptet og sammenligne distributionen af ​​information fra forskellige modeller med protokollen på følgende måder [13] [14] :

Udviklingshistorie

I 1986 beskrev Silvio Micali , Oded Goldreich Avi Wigderson brugen af ​​nulvidensbeviser til at skabe kryptografiske protokoller , der skulle sikre parternes "fair adfærd" og samtidig bevare fortroligheden [19] .

Nulvidensbeviset blev udtænkt og udviklet af følgende videnskabsmænd: Shafi Goldwasser , Silvio Micali og Charles Reckoff og offentliggjort af dem i papiret "Knowledge and Complexity of an Interactive System with Proof" [20] i 1989 . Dette arbejde præsenterede et hierarki af interaktive bevissystemer baseret på mængden af ​​bevisinformation, der skal videregives fra Prover til Verifier. De foreslog også det første bevis på et specifikt angivet nul-videns bevis, en kvadratisk rest modulo m [21] . Efterfølgende, som supplement til deres arbejde, blev de tildelt den første Gödel-pris i 1993 [22] .

Goldwasser- Micali -kryptosystemet , der er baseret på den betragtede interaktive protokol, som er et kryptografisk system med offentlig nøgle udviklet af Shafi Goldwasser og Silvio Micali i 1982 , er det første probabilistiske krypteringsskema med offentlig nøgle , der beviseligt er sikkert under standard kryptografiske antagelser . Det foreslåede system blev meget værdsat af juryen: Goldowasser og Micali blev vindere af Turing-prisen for 2012 [23] , for skabelsen af ​​et kryptosystem med probabilistisk kryptering, noteret i nomineringen som et innovativt værk, der havde en betydelig indflydelse på moderne kryptografi . Imidlertid er kryptosystemet ineffektivt, da chifferteksten , der genereres af det, kan være hundredvis af gange længere end den krypterede meddelelse .

For at bevise sikkerhedsegenskaberne for et kryptosystem introducerede Goldwasser og Micali konceptet semantisk sikkerhed [24] [25] .

I 2021 blev Laszlo Lovas og Avi Wigderson tildelt Abelprisen for deres arbejde inden for teoretisk datalogi , som ydede et stort bidrag til udviklingen af ​​beregningskompleksitetsteori, grafteori, distribuerede computermetoder og konceptet med nul-vidensbeviser [ 26] .

Generel struktur af nulvidensbeviser

Hver runde, eller bevisakkreditering , består af tre faser. Skematisk kan de afbildes som følger:

Først vælger A et element fra et forudbestemt ikke-tomt sæt , som bliver dets hemmelige- private nøgle . Baseret på dette element beregnes den offentlige nøgle og offentliggøres derefter . At kende hemmeligheden afgør det sæt af spørgsmål, som A altid kan give de rigtige svar på. Så vælger A et tilfældigt element fra sættet, ifølge visse regler (afhængigt af den specifikke algoritme) beregner beviset og sender det derefter til B . Herefter vælger B et spørgsmål fra hele sættet og beder A besvare det (udfordring). Afhængig af spørgsmålet sender A B et svar [27] . Den modtagne information B er nok til at kontrollere, om A virkelig ejer hemmeligheden. Runderne kan gentages så mange gange som ønsket, indtil sandsynligheden for at A "gætter" svarene er lav nok. Denne tilgang kaldes også "klip-og-vælg", først brugt i kryptografi af Michael Rabin [28] [29] .

Eksempler

Zero Knowledge Cave

Dette eksempel blev først skrevet i det velkendte nul-viden proof paper "How to explain the zero-knowledge proof protocol to your children" af Jean-Jacques Kiskater.[30] .

I dette tilfælde fungerer Peggy som Prover og Victor som Verifier (i engelsk litteratur bruges navnene på parterne Peggy og Victor (fra henholdsvis "Prover" og "Verifier"). Peggy kender det magiske ord ("nøgle" "), input, som giver hende mulighed for at åbne døren mellem C og D. Victor vil vide, om Peggy virkelig kender adgangskoden, mens Peggy ikke selv ønsker at give adgangskoden ud. Hulen har en rund form, som vist i figur.For at løse problemet går de frem på følgende måde: Mens Victor er ved punkt A, går Peggy hen til døren, og efter at hun er forsvundet af syne, går Victor til gaflen, det vil sige til punkt B, og råber derfra: "Peggy skal ud til højre " eller "Peggy skal ud til venstre " Vi får hver gang sandsynligheden for, at Peggy ikke kender kodeordet, er lig med 50%.Hvis vi gentager processen k gange, så vil sandsynligheden være.Med 20 gentagelser vil denne sandsynlighed være af størrelsesordenen 10 −6 , hvilket er tilstrækkeligt for retfærdighed . Disse antagelser om, at Peggy kender nøglen [30] .

Hvis Victor optager alt, hvad der sker på kameraet, vil den resulterende video ikke være bevis for nogen anden part. De kunne jo have aftalt på forhånd, hvor Peggy ville komme fra. Derfor vil hun være i stand til at finde en vej ud uden at kende selve nøglen. Der er en anden måde: Victor fjerner simpelthen alle Peggys mislykkede forsøg. Disse trin ovenfor beviser, at huleksemplet opfylder egenskaberne fuldstændighed , korrekthed og nul viden [31] .

Hamiltonsk cyklus for store grafer

Dette eksempel blev opfundet af Manuel Blum og beskrevet i hans papir i 1986 [32] . Lad os kalde testeren Victor og beviseren Peggy. Lad os sige, at Peggy kender en Hamilton-cyklus i en stor graf G . Victor kender grafen G , men han kender ikke Hamiltons cyklus i den. Peggy vil bevise over for Victor, at hun kender Hamilton-cyklussen uden at afsløre selve cyklen eller nogen information om den (måske vil Victor købe information om denne Hamilton-cyklus fra Peggy, men inden da vil han være sikker på, at Peggy virkelig kender ham ).

For at gøre dette udfører Victor og Peggy i fællesskab flere runder af protokollen :

I hver runde vælger Victor en ny tilfældig bit , som Peggy ikke kender, så for at Peggy kan svare på begge spørgsmål, skal H faktisk være isomorf til G , og Peggy skal kende Hamiltons cyklus i H (og dermed også i G ). Derfor kan Victor efter et tilstrækkeligt antal runder være sikker på, at Peggy virkelig har kendskab til Hamiltons cyklus i G . På den anden side afslører Peggy ikke nogen information om Hamiltons cyklus i G . Desuden vil det være svært for Victor at bevise over for nogen anden, at han eller Peggy kender Hamilton-cyklussen i G [32] .

Antag, at Peggy ikke kender Hamilton-cyklussen i G , men hun vil narre Victor. Så har Peggy brug for en ikke-isomorf G - graf G′ , hvor hun stadig kender Hamiltons cyklus . I hver runde kan hun sende til Victor enten H′  — isomorf til G′ eller H  — isomorf til G . Hvis Victor beder om at bevise isomorfien af ​​grafer, og H blev givet til ham , vil bedraget ikke blive afsløret. Tilsvarende, hvis han beder om at vise en Hamilton-cyklus, og han fik H′ . I dette tilfælde er sandsynligheden for, at Peggy stadig vil snyde Victor efter k runder, lig med , hvilket kan være mindre end enhver forudbestemt værdi givet et tilstrækkeligt antal runder [32] .

Lad os antage, at Victor ikke genkender Hamiltons cyklus, men vil bevise for Bob, at Peggy ved det. Hvis Victor for eksempel filmede alle runderne af protokollen, ville Bob næppe tro ham. Bob kan antage, at Victor og Peggy er i ledtog, og hver runde fortæller Victor Peggy om sit valg af tilfældig bit på forhånd, så Peggy kan bestå ham H til isomorfitest og H′ til Hamiltonske cyklustest. Uden Peggys deltagelse er det således muligt at bevise, at hun kun kender Hamilton-cyklussen ved at bevise, at der blev valgt virkelig tilfældige bits i alle runder af protokollen [33] .

Anvendelse i praksis

Sætningen om, at for ethvert NP-fuldstændigt problem er der et nul-viden bevis, mens man bruger envejsfunktioner , kan man skabe korrekte kryptografiske protokoller , blev bevist af Oded Goldreich , Silvio Micali og Avi Wigderson [19] [ 34] . Det vil sige, at du kan bevise for enhver skeptiker, at du har et bevis på en matematisk sætning uden at afsløre selve beviset. Dette viser også, hvordan denne protokol kan bruges til praktiske formål [13] .

Den næste metode, hvor nul-videns bevis kan bruges, er identitetsbestemmelse, hvor Peggys private nøgle er den såkaldte "identitetsindikator", og ved hjælp af den pågældende protokol kan man bevise sin identitet. Det vil sige, at du kan bevise din identitet uden at bruge forskellige fysiske enheder og data (symboler), såsom pas, forskellige billeder af en person (nethinde, fingre, ansigt osv.), men på en fundamentalt anderledes måde [35] . Det har dog en række ulemper, som kan bruges til at omgå beskyttelse. Metoden beskrevet ovenfor blev først foreslået af Amos Fiat , Adi Shamir og Uriel Feige i 1987 [36] .

Nulvidensbeviser kan også bruges i fortrolige computerprotokoller , som giver flere deltagere mulighed for at verificere, at den anden part følger protokollen ærligt [19] .

Nulvidensbeviser bruges i blockchains af kryptovalutaerne Zcash , Byzantium (en gaffel af Ethereum ), Zerocoin og andre. Implementeringer af nul-viden bevis protokoller er blevet oprettet, især QED-IT Software Development Kit. Den hollandske bank ING skabte sin egen version af protokollen, ZKRP ( Zero-Knowledge Range Proof ), og anvendte den for at bevise, at kunden har en tilstrækkelig løn uden at afsløre dens sande størrelse [7] [8] .

De mest udbredte protokoller er zk-SNARK'er, det er protokollerne i denne klasse, der bruges i ZCash, Zcoin og i Metropolis-protokollen for Ethereum blockchain [37] [8] .

Forkortelsen zk-SNARK står for   zero-knowledge succinct non-interactive argument of knowledge [37] [8] . zk-SNARK-algoritmen består af en nøglegenerator, en beviser og en verifikator, understøtter nødvendigvis nul viden, har korthed (beregnet på kort tid), er ikke-interaktiv (verifikatoren modtager kun én besked fra beviseren) [8] .

Misbrug

Der er blevet foreslået flere måder at misbruge nul-viden bevis på, som udnytter visse svagheder i protokollen:

Stormesterproblem

I dette eksempel kan en eller anden part bevise besiddelse af hemmeligheden uden faktisk at have den, eller med andre ord kan efterligne den person, der faktisk ejer hemmeligheden [38] . I øjeblikket er en måde at løse problemet på blevet foreslået af Thomas Beth og Ivo Desmedt [39] .

Bedrag med flere identiteter

Hvis en part kan skabe flere hemmeligheder, så vil den også være i stand til at skabe "flere identiteter" i overensstemmelse hermed. Lad en af ​​dem aldrig blive brugt. Denne mulighed giver engangsanonymitet, som for eksempel gør det muligt at unddrage sig ansvar: Parten identificerer sig selv som en aldrig brugt person og begår en forbrydelse. Herefter bliver denne "identitet" aldrig brugt igen. Det er næsten umuligt at opspore eller matche gerningsmanden med nogen. Et sådant misbrug forhindres, hvis muligheden for at skabe endnu en hemmelighed udelukkes fra begyndelsen [40] .

Bedrag udført af mafiaen

Endnu et eksempel på, at den ene side udgiver sig for at være den anden. Lad der være 4 deltagere: A , B , C , D . Desuden samarbejder B og C med hinanden ("tilhører den samme mafia"). A beviser sin identitet over for B , og C ønsker at efterligne A foran D. B ejer en restaurant ejet af mafiaen, C  er også repræsentant for mafiaen, D  er juveler. A og D er uvidende om den kommende svindel. I det øjeblik A er klar til at betale for middagen og identificerer sig over for B , giver B besked til C om starten på fidusen. Dette er muligt på grund af tilstedeværelsen af ​​en radiokanal mellem dem. På dette tidspunkt vælger C den diamant, han vil købe, og D begynder at identificere identiteten på C , som efterligner A. C sender protokolspørgsmålet til B , som igen stiller det til A. Svaret sendes i omvendt rækkefølge. A vil således ikke kun betale for middagen, men også for den dyre diamant. Som det fremgår af ovenstående, er der visse krav til sådan svig. Når A begynder at bevise sin identitet overfor B , og C  til D , skal B og Cs handlinger synkroniseres. Dette misbrug er også tilladt. For eksempel, hvis der er et Faraday-bur i en guldsmedsbutik , så vil "mafiosi" ikke være i stand til at udveksle beskeder [41] .

Mulige angreb

Valgt chiffertekstangreb

Dette angreb er muligt ved hjælp af en ikke-interaktiv interaktionsmetode i en nul-vidensprotokol.

Der er flere problemer med denne protokol. Først skal du beslutte, hvordan du vil interagere, mens du bevarer de grundlæggende funktioner i selve protokollen: fuldstændighed, korrekthed og "nul viden". Ud over at det er ret nemt at bevise nul viden over for den anden part, hvis det er muligt at aflytte kanalen, altså at møde stormesterproblemet .

Så selve angrebet er som følger: angriberen, ved at bruge kompleksiteten af ​​beviset for at have viden, inkluderer den "angribende" chiffertekst og glider den ind i en masse andre chiffertekster, der skal dekrypteres. Dette angreb kaldes "playback"-angreb [42] .

En mulig løsning er baseret på arbejdet fra Moni Naor og Moti Yung , som er som følger: Prover og Verifier krypterer meddelelser med en offentlig nøgle , dette får ovenstående angreb til at mislykkes [43] .

Et angreb på et multiprotokol-nulvidenssystem

Chida og Yamamoto foreslog en implementering af nul-viden-protokollen, der markant øger hastigheden af ​​nul-viden-beviser, mens de beviser flere udsagn på én gang og som et resultat af hele systemets ydeevne [44] . Nøglefunktionen er begrænsningen af ​​antallet af iterationer for et bevis. Som vist i K. Pengs arbejde [45] viste denne algoritme sig at være fuldstændig ustabil til det næste angreb. Ved at bruge flere velvalgte iterationer kan en angriber bestå verifikation og overtræde protokollens hovedbestemmelser. Desuden blev det vist, at dette angreb altid er muligt på et sådant system.

Angreb med en kvantecomputer

I 2005 viste John Watrus at ikke alle nul-viden-systemer er modstandsdygtige over for kvantecomputerangreb . Det har dog vist sig, at det altid er muligt at bygge et system, der er modstandsdygtigt over for kvanteangreb, forudsat at der findes kvantesystemer med "skjul på forpligtelser" [46] .

Se også

Noter

  1. ↑ Goldreich, 2013 .
  2. ↑ 1 2 Schneier, 2002 , pp. 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 , s. 1444.
  10. ↑ Menezes et al., 1996 , s. 406-408.
  11. ↑ Schneier, 2002 , s. 86-89.
  12. ↑ Goldwasser, Micali, Rackoff, 1989 , s. 188-189.
  13. ↑ 1 2 Schneier, 2002 , pp. 91-92.
  14. ↑ Mao, 2005 , s. 683-696.
  15. ↑ Mao, 2005 , s. 684-688.
  16. ↑ Sahai, Vadhan, 2003 .
  17. ↑ Mao, 2005 , s. 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 og Rackoff modtager Gödel-prisen i 1993 (link utilgængeligt) . ACM Sigact (1993). Arkiveret fra originalen den 8. december 2015. 
  23. ↑ Goldwasser, Micali modtager ACM Turing-prisen for fremskridt inden for kryptografi (link ikke tilgængeligt) . ACM. Hentet 13. marts 2013. Arkiveret fra originalen 16. marts 2013. 
  24. ↑ Goldwasser, Micali, 1982 .
  25. ↑ Mao, 2005 , s. 524-528.
  26. ↑ Abelprisen - 2021 • Andrey Raigorodsky • Nyheder om videnskab om "Elementer" • Matematik, videnskab og samfund . Hentet 17. maj 2021. Arkiveret fra originalen 3. juni 2021.
  27. ↑ Mao, 2005 , s. 678-682.
  28. ↑ MORabin. digitale signaturer . — Grundlaget for sikker databehandling. - 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 , s. 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 , s. 93.
  42. ↑ Rackoff, Simon, 1992 .
  43. ↑ Naor, Yung, 1990 .
  44. ↑ Chida, Yamamoto, 2008 .
  45. ↑ Peng, 2012 .
  46. ↑ Watrous, 2006 .

Litteratur

bøger og monografier artikler

Links