Een zero-knowledge proof moet drie eigenschappen hebben:
- Volledigheid: als de bewering echt waar is, dan zal de bewijzer de verificateur hiervan overtuigen.
- Juistheid: Als de bewering onjuist is, zal zelfs een oneerlijke beoordelaar de verificateur niet kunnen overtuigen, behalve door een verwaarloosbare waarschijnlijkheid.
- Geen kennis: als de bewering waar is, zal elke zelfs oneerlijke verificateur niets anders weten dan het feit dat de bewering waar is.
Algemene structuur van nulkennisbewijzen
Elke ronde of accreditatie van bewijsmateriaal bestaat uit drie fasen. Ze kunnen schematisch als volgt worden weergegeven:
In eerste instantie A selecteert uit een vooraf bepaalde set een element dat zijn geheim wordt ( privé sleutel). Op basis van dit element wordt het berekend en vervolgens gepubliceerd openbare sleutel. Het kennen van een geheim bepaalt veel vragen A zal altijd de juiste antwoorden kunnen geven. Dan A selecteert een willekeurig element uit de set en berekent het volgens bepaalde regels (afhankelijk van het specifieke algoritme). bewijs en stuurt het dan weg B. Daarna B kiest er één uit de hele reeks vragen en stelt A beantwoord het ( telefoongesprek). Afhankelijk van de vraag, A stuurt B-antwoord. Informatie ontvangen B genoeg om te controleren of A bezit het geheim. Rondes kunnen zo vaak als nodig worden herhaald totdat de kans groot is A"Gissende" antwoorden zullen niet laag genoeg zijn.
Deze techniek wordt ook wel “cut-and-choose” genoemd.
Voorbeeld
Laten we de verifiërende kant Petya noemen, en de bewijzende kant Dima (in Engelstalige literatuurparen Peggy (vanaf bewijzer) en Victor (van verificateur). Stel dat Dima een Hamiltoniaanse cyclus kent in een grote grafiek G. Petya kent de graaf G, maar hij kent de Hamiltoniaanse cyclus daarin niet. Dima wil aan Petya bewijzen dat hij de Hamiltoniaanse cyclus kent, zonder de cyclus zelf of enige informatie erover weg te geven (misschien wil Petya deze Hamiltoniaanse cyclus van Dima kopen, maar zorg er eerst voor dat Dima hem echt heeft).
Om dit te doen, voeren Petya en Dima gezamenlijk verschillende rondes van het protocol uit:
In elke ronde kiest Petya een nieuw willekeurig bit, dat onbekend is bij Dima, dus om Dima beide vragen te laten beantwoorden, is het noodzakelijk dat H was inderdaad isomorf G en Dima zou de Hamiltoniaanse cyclus moeten kennen H(en dus ook in G). Daarom kan Petya er na een voldoende aantal ronden zeker van zijn dat Dima echt een Hamiltoniaanse cyclus heeft G. Aan de andere kant onthult Dima geen enkele informatie over de Hamiltoniaanse cyclus G. Bovendien zal het voor Petya moeilijk zijn om aan iemand anders te bewijzen dat hij of Dima de Hamiltoniaanse cyclus kent G.
Laten we aannemen dat Dima geen Hamiltoniaanse cyclus heeft G en hij wil Petya bedriegen. Dan heeft Dima een niet-isomorf nodig G grafiek G", waarin hij de Hamiltoniaanse cyclus nog kent. In elke ronde kan hij ook doorgeven aan Petya H"- isomorf G", of H- isomorf G. Als Petya vraagt om isomorfisme te bewijzen en is geslaagd H, dan wordt het bedrog niet onthuld. Evenzo, als hij vraagt om een Hamiltoniaanse cyclus te laten zien en deze kreeg H". In dit geval is de kans groot dat Dima Petya daarna nog steeds zal bedriegen N rondes is gelijk aan 1/2 n, wat kleiner kan zijn dan elke vooraf bepaalde waarde, gegeven een voldoende aantal ronden.
Stel dat Petya de Hamiltoniaanse cyclus niet herkent, maar aan Vasya wil bewijzen dat Dima deze kent. Als Petya bijvoorbeeld alle rondes van het protocol heeft gefilmd, is het onwaarschijnlijk dat Vasya hem gelooft. Vasya kan ervan uitgaan dat Petya en Dima onder één hoedje spelen en Petya informeerde Dima elke ronde vooraf over zijn keuze voor een willekeurig bit, zodat Dima aan hem kon doorgeven H voor isomorfismecontroles en H" voor het controleren van de Hamiltoniaanse cyclus. Zonder de deelname van Dima kan men dus alleen bewijzen dat hij de Hamiltoniaanse cyclus kent door te bewijzen dat er in alle rondes van het protocol echt willekeurige bits zijn gekozen.
Misbruik
Er zijn verschillende manieren voorgesteld om nulkennisbewijs te misbruiken:
Zie ook
- Gillu-Kiskatra-protocol
Literatuur
- A. Menezes, P. van Oorschot, S. Vanstone. Handboek voor toegepaste cryptografie. - CRC Press, 1996. - 816 p. - ISBN 0-8493-8523-7
- Schneier B. Toegepaste cryptografie. Protocollen, algoritmen, bronteksten in C-taal = Toegepaste Cryptografie. Protocollen, algoritmen en broncode in C. - M.: Triumph, 2002. - 816 p. - 3000 exemplaren.
Wikimedia Stichting.
- 2010.
- Fonvizina, Natalya Dmitrievna
Tsjoezhumovo
Kijk wat “Zero Knowledge Proof” is in andere woordenboeken: zero-knowledge bewijs van vertrouwelijke informatie
- Ondoordringbaar bewijs van kennis; bewijs van het bezit van enige informatie, zonder deze informatie openbaar te maken. Onderwerpen: informatiebescherming EN zero Knowledge proof… iteratief nulkennisbewijs van gevoelige informatie
- — Onderwerpen informatiebeveiliging EN nulkennis iteratief proofZKIP … Handleiding voor technische vertalers iteratief nulkennisbewijs van gevoelige informatie
niet-iteratief nulkennisbewijs van gevoelige informatie- NDNR - [] Onderwerpen informatiebescherming Synoniemen NDNR EN niet iteratief nul kennis proofNIZK ...
Cryptografie- De Duitse Lorenz-cryptomachine werd tijdens de Tweede Wereldoorlog gebruikt om de meest geheime berichten te coderen Cryptografie (van andere Griekse ... Wikipedia
Lijst met algoritmen- Deze pagina is een informatielijst. Hoofdartikel: Algoritme Hieronder vindt u een lijst met algoritmen, gegroepeerd per categorie. Meer gedetailleerde informatie wordt gegeven in de lijst met datastructuren en ... Wikipedia Codeur- Duitse Lorenz-cryptomachine, gebruikt tijdens de Tweede Wereldoorlog om de meest geheime berichten te coderen Cryptografie (van het Griekse κρυπτός verborgen en γράφω schrijven), de wetenschap van
wiskundige methoden vertrouwelijkheid garanderen... ... Wikipedia Programmeerbare algoritmen- Een servicelijst met artikelen die is gemaakt om de werkzaamheden aan de ontwikkeling van het onderwerp te coördineren.
Deze waarschuwing niet geïnstalleerd... Wikipedia
SRP- Secure Remote Password Protocol (SRPP) is een wachtwoordverificatieprotocol dat bestand is tegen afluisteren en MITM-aanvallen en waarvoor geen derde vertrouwde partij nodig is. SRP bevat enkele elementen uit andere sleuteluitwisselings- en identificatieprotocollen... Wikipedia
Fiat-protocol- Het Fiat Shamir-protocol is een van de bekendste zero-knowledge-identificatieprotocollen (Zero Knowledge-protocol). Het protocol is voorgesteld door Amos Fiat en Adi Shamir. Let A... ... Wikipedia
Fiat-Shamir-protocol
Bij de definitie van een interactief bewijssysteem werd voorheen niet aangenomen dat V een tegenstander zou kunnen zijn (er werd alleen uitgegaan van de mogelijkheid van het bestaan van een oneerlijke deelnemer P). Maar V kan een tegenstander blijken te zijn die erachter wil komen wat nieuwe informatie van P. nuttige informatie over de verklaring van S. In dit geval wil P misschien niet dat dit gebeurt als gevolg van de werkzaamheden
Interactief bewijssysteemprotocol. Dus
28 Zapechnikov S.V. Cryptografische protocollen en hun voorgangers
Zo komen we op het idee van een zero-knowledge proof protocol. Kennis zonder kennis houdt in dat V, als gevolg van het interactieve bewijssysteemprotocol, zijn kennis over de bewering S niet zal vergroten, of, met andere woorden, er geen informatie uit zal kunnen halen over waarom S waar is.
Net als voorheen formuleert het protocol voorlopig een bepaalde verklaring S, bijvoorbeeld dat een object w de eigenschap L heeft: we L. Tijdens het protocol wisselen P en V berichten uit. Elk van hen kan willekeurige getallen genereren en deze gebruiken in hun berekeningen. Aan het einde van het protocol moet V zijn definitieve beslissing nemen over de vraag of S waar of onwaar is.
Het doel van P is altijd om V ervan te overtuigen dat S waar is, ongeacht of het feitelijk waar is of niet, dat wil zeggen dat P een actieve tegenstander kan zijn, en het is de taak van V om de argumenten van P te testen. Het doel van deelnemer V is om te beoordelen of S dat is waar of onwaar. Net als voorheen heeft V polynoom beperkte rekenmogelijkheden, namelijk dat de bedrijfstijd ervan wordt beperkt door een bepaalde polynoom
lengte van de bewering die moet worden bewezen: Laten we nu voorbeelden bekijken van bewijsprotocollen zonder enige kennis.
1. “Het probleem met de grot van Ali Baba.” Er is een grot, waarvan het plan wordt getoond in Fig. 1.2. De grot heeft een deur met een geheim tussen de punten C en D. Iedereen die de magische woorden kent, kan deze deur openen en van C naar D gaan of omgekeerd. Voor alle anderen leiden beide grotpassages naar een doodlopende weg.
Vertel R het geheim van de grot. Hij wil aan V bewijzen dat hij dit geheim kent, zonder de magische woorden prijs te geven. Hier is het protocol van hun communicatie:
V bevindt zich op punt A;
P gaat de grot binnen en komt bij punt C of punt D\
Nadat P in de grot is verdwenen, arriveert V op punt B, niet wetende welke kant P op is gegaan.
V belt R en vraagt hem om uit de linker- of rechtergang van de grot te komen, afhankelijk van de wensen van V;
R doet dit en opent indien nodig de deur, als hij natuurlijk de magische woorden kent;
P en V herhalen stappen (1) - (5) n keer.
Na n rondes van het protocol wordt de waarschijnlijkheid teruggebracht tot 1/2".
2. Bewijs van grafiekisomorfisme. P wil het V-isomorfisme van de grafieken Go en Gb bewijzen. Laat G, = (p(G0):G0 = G, waarbij φ de isomorfisme-transformatie is, m de kardinaliteit van de verzameling N van hoekpunten van de grafieken. Tabel 1.4 toont het protocol voor het bewijzen van deze verklaring.
Laten we de structuur van dit protocol uitleggen. Bij stap (1) maakt deelnemer P een willekeurige grafiek H, isomorf met G\. Bij stap (2) vraagt deelnemer V, die een willekeurig bit a = (0D) kiest, daarbij om dat te bewijzen
Н ~G0 of die Н « Gj. Bij stap (3) stuurt deelnemer P deelnemer V de transformatie \|/, die hij zo construeert dat voor a = 1, als gevolg van het toepassen van deze transformatie op de grafiek Gu, de grafiek F1 = TtG, = H wordt verkregen en voor a = 0 verkrijgen we, als gevolg van het toepassen van deze transformatie op de grafiek Ga, de grafiek F0 =
Zo Zapechnikov S.V. Cryptografische protocollen en hun toepassing
= 7i((p(G0))~7iG] = #, Bij stap (4) bepaalt deelnemer V, door een grafiekgelijkheidscontrole uit te voeren, of aan de voorwaarde is voldaan
N = Fa. Stappen (1) - (4) worden t keer herhaald. Als in alle rondes van dit protocol het testresultaat positief is, accepteert V het bewijs.
Tabel 1.4. Protocol voor het bewijzen van isomorfisme van grafieken PV 1% - willekeurige permutatie van hoekpunten, berekent H = nGl 2 f n, als (a -1),
V = 1 / h 1 l of if (a = 0) -> m maal 4 Berekent de grafiek \j/Ga en vergelijkt: H =\jfGa 5 Accepteert het bewijs dan en slechts dan als voor Vm
Dit protocol is echt een nul-kennisprotocol, omdat in het geval van isomorf G0 ~ Gx deelnemer V geen enkele informatie ontvangt behalve de isomorfismen van de grafieken G0 en G\ met enkele willekeurige hernummeringen, die hij onafhankelijk had kunnen ontvangen, het kiezen van een willekeurig bit a en het willekeurig hernummeren van de grafiek Ga.
3. Bewijs van kennis van de discrete logaritme x van het getal X. Voordat het protocol wordt gestart, worden open grootheden gespecificeerd: p,
Q- priemgetallen, zodat q\(p -1), element g e Z*, getal X. Do-]. Basis cryptografische protocollen 31
de persoon die P belt kent de geheime waarde x\xTabel 1.5. Protocol voor het bewijzen van kennis van de discrete logaritme P V I r&RZ
M = g (mod p) 2 A. Bewijs van kennis van de representatie van het getal y in de basis (nulkennisbewijs van kennis van de y-representatie). Voordat het protocol start, worden open grootheden gespecificeerd die bij alle deelnemers bekend zijn: priemgetallen p, q, elementen y, gvg2,..., gk Є Gq. Het spreekwoord P kent de geheime grootheden ara 2,...,ake ZQ: y =
= 8i" " 8r1""> waarvan hij de kennis aan V moet bewijzen, zonder deze grootheden zelf bekend te maken. Het protocol wordt weergegeven in tabel. 1.6.
Tabel 1.6. Vertegenwoordiging Kennis Proof Protocol
getallen in de basis P V 1 rl.r2,...,rk. ЄІ( Zq, 2 5. Bewijs van kennis van de representatie van een reeks getallen in de overeenkomstige bases (nulkennisbewijs van kennis van gelijkheid van representatie van alle y(j) in de respectieve bases). Voordat het protocol begint, open hoeveelheden zijn gespecificeerd, bekend
W ik >\
bekend bij alle deelnemers: priemgetallen p, q, elementen y, 82^є voor sommige (/). De bewijzer P kent de geheime waarden 0C[,a2,...,a,. є Zq, zodat voor V/ у^ =
= (і^) " 1 > kennis waarvan hij V moet bewijzen,
zonder deze waarden zelf bekend te maken. In tabel 1.7 toont een protocol dat dit probleem oplost.
Tabel 1.7. Protocol voor het bewijzen van kennis van een reeks getallen
in de overeenkomstige basen P V 1 rvr21...lrkeR voor U/ 2 (AiP«iT-(lt-
6. Bewijs van kennis van de multiplicatieve relatie tussen geëngageerde waarden. Een element X = gx van een cyclische subgroep van eenvoudige orde, waarin het discrete logaritmeprobleem als computationeel complex wordt beschouwd, wordt een vastgelegde waarde genoemd, die de geheime waarde x vertegenwoordigt. Laten
d is een onbekend element zodat h = gd. Voordat het protocol begint, worden open grootheden gespecificeerd: priemgetallen p, q, elementen A, B, C Є Gq. De bewijzer van P kent geheime hoeveelheden
a, a, b, b, c, c, zodat c = ab, A = gah"\ B = gbhb, C = gche. Hij moet de kennis ervan bewijzen V, zonder de waarden zelf bekend te maken. In tabel 1.8 , met - er is een protocol van dergelijk bewijsmateriaal bijgehouden.
Tabel 1.8. Protocol voor het bewijzen van kennis van de multiplicatieve relatie van afgezette hoeveelheden P V 1 М=і">/Ї, j Mt = gx-h*\ ¦ M2= Bx ¦ h"1 2 =CK-M2
openbaarmaking van kennis
Tabel 1.9. De structuur van bewijsprotocollen met nul P S: x є L - de bewering die wordt bewezen, h - dp, openbare parameters en hoeveelheden, s - geheime gegevens van de bewijzer over waarom S waar is, r - willekeurig getal V 1 rp - willekeurig, 2 rv - willekeurig getal,
c = LM Laten we de beschouwde voorbeelden generaliseren en een aantal definities formuleren. IN algemeen beeld Het interactieve proefprotocol met nulkenniskennis (Tabel 1.9) bestaat uit vier stappen:
Einde van tafel. 1.9 P S: xe L is de bewering die wordt bewezen, h zijn andere openbaar beschikbare parameters en grootheden, s zijn de geheime gegevens van de bewijzer over waarom S waar is, r is een willekeurig getal V 3 R = f3(C,x) 4
de bewijzer draagt het zogenaamde bewijs (getuige -W) over aan de verificateur - het resultaat van het berekenen van een eenrichtingsfunctie van de geheime waarde, waarvan hij de kennis bewijst;
de recensent stuurt hem een willekeurig verzoek;
de bewijzer beantwoordt deze vraag, en het antwoord hangt af van zowel de willekeurige vraag als de geheime waarde, maar het is computationeel onmogelijk om deze geheime waarde van hem te verkrijgen;
Na ontvangst van het antwoord controleert V de consistentie ervan met het “bewijs” dat in de eerste stap is verzonden.
Laten we eens kijken naar de basisprincipes van het construeren van bewijzen zonder openbaarmaking van kennis zonder kennis: wat de eigenschap van kennis zonder kennis inhoudt.
In de zero-knowledge proof-theorie worden kennis P en V behandeld als ‘zwarte dozen’ (Fig. 1.3).
Laat \tr ), \)Py ) de verzameling zijn van alle berichten die worden verzonden van P naar V (respectievelijk van V naar P), waarvan elk een willekeurige variabele is, en dus (x,h,rv,(mp ),( mv)) = = bekijkpy)
