Nolla tietämyksen todiste

Zero-knowledge proof (informaatio) kryptografiassa ( eng .  Zero-knowledge proof ) on interaktiivinen salausprotokolla, jonka avulla yksi vuorovaikutuksessa olevista osapuolista ("Todentaja" - todentaminen) voi varmistaa minkä tahansa lausunnon (yleensä matemaattisen) oikeellisuuden ilman Tämän saaminen ei ole muita tietoja toiselta osapuolelta ("Todistaja" - todistaminen). Lisäksi viimeinen ehto on välttämätön , koska on yleensä triviaalia todistaa, että osapuolella on useimmissa tapauksissa tiettyjä tietojajos sillä on oikeus yksinkertaisesti paljastaa tiedot. Koko vaikeus on todistaa, että jollakin osapuolella on tietoa paljastamatta sen sisältöä. Pöytäkirjassa on otettava huomioon, että todistaja pystyy vakuuttamaan todentajan vain, jos väite on todella todistettu. Muuten tämä on mahdotonta tai erittäin epätodennäköistä laskennan monimutkaisuuden vuoksi .

Vuorovaikutteisella pöytäkirjalla tarkoitetaan osapuolten suoraa tietojenvaihtoa [1] [2] .

Näin ollen tarkasteltava protokolla vaatii vuorovaikutteisen syötteen todentajalta , yleensä tehtävän tai ongelman muodossa. Tämän pöytäkirjan laillisen todistajan (jolla on todiste ) tarkoitus on vakuuttaa todentaja , että hänellä on ratkaisu, luovuttamatta edes osaa "salaisesta" todisteesta ("nolla tietämys"). Todentajan tarkoituksena on varmistaa, että todistaja "ei valehtele" [2] [3] .

On myös kehitetty nollatietoprotokollia [4] [5] , jotka eivät vaadi vuorovaikutteista syöttöä ja joiden todistus perustuu tyypillisesti oletukseen ihanteellisesta kryptografisesta hajautusfunktiosta , eli oletetaan, että tulos on yksi . -way hash -funktiota ei voida ennustaa, jos sen syöttöä ei tunneta [6] .

Zero-knowledge proofia käytetään useissa lohkoketjuissa, lisäksi sillä tarkistetaan tiedon olemassaolo siirtämättä itse tietoa [7] [8] .

Määritelmä

Nollatietotodistus on vuorovaikutteinen todennäköisyyspohjainen protokolla , jonka avulla voit todistaa, että todistettava väite on totta, ja Todistaja tietää tämän todisteen, mutta ei samalla anna mitään tietoa itse tämän väitteen todistuksesta [9] . Tällä salausprotokollalla on oltava kolme ominaisuutta:

  1. Täydellisyys : Jos väite on todellakin totta, todistaja vakuuttaa todentajan tästä ennalta määrätyllä tarkkuudella.
  2. Oikeus : jos väite on väärä, mikään, edes "epärehellinen", Prover ei pysty vakuuttamaan todentajaa paitsi mitättömällä todennäköisyydellä .
  3. Nollatietoa : jos väite on totta, niin mikä tahansa, jopa "epärehellinen", todentaja ei tiedä muuta kuin sen tosiasian, että väite on totta [10] .

Nollatietotodistukset eivät ole todisteita termin matemaattisessa merkityksessä , koska on olemassa pieni mahdollisuus, että todistaja voidaan huijata vakuuttamaan todentaja väärästä väitteestä ( oikeusvirhe ). Toisin sanoen nollatiedon todisteet ovat todennäköisyystodistuksia, eivät deterministisiä . On kuitenkin olemassa menetelmiä, joilla oikea virhe voidaan pienentää merkityksettömiin arvoihin [11] [12] .

Erilaisia ​​nollatietoa

Nollatietojen todisteprotokollan suorittaminen tuottaa Hyväksy/Hylkää -tuloksen ja luo myös todistuksen transkription . Nollatiedon eri muunnelmia voidaan määritellä formalisoimalla itse käsite ja vertaamalla eri mallien tiedon jakautumista protokollaan seuraavilla tavoilla [13] [14] :

Kehityshistoria

Vuonna 1986 Silvio Micali , Oded Goldreich ja Wigderson kuvasivat nollatietotodisteiden käyttöä salausprotokollien luomiseksi , joiden pitäisi varmistaa osapuolten "reilu käyttäytyminen" säilyttäen samalla luottamuksellisuus [19] .

Nollatietotodistuksen suunnittelivat ja kehittivät seuraavat tiedemiehet: Shafi Goldwasser , Silvio Micali ja Charles Reckoff, ja he julkaisivat sen julkaisussa "Knowledge and Complexity of an Interactive System with Proof" [20] vuonna 1989 . Tässä työssä esitettiin vuorovaikutteisten todistusjärjestelmien hierarkia, joka perustuu todisteiden määrään, joka on välitettävä Proverista Verifierille. He ehdottivat myös ensimmäistä todistetta nimenomaisesti ilmoitetusta nollatietotodistuksesta, neliöllisen jäännöksen modulo m [21] . Myöhemmin työtään täydentäen he saivat ensimmäisen Gödel-palkinnon vuonna 1993 [22] .

Lisäksi Goldwasser-Micali-salausjärjestelmä , joka perustuu harkittuun interaktiiviseen protokollaan, joka on Shafi Goldwasserin ja Silvio Micalin vuonna 1982 kehittämä julkisen avaimen salausjärjestelmä , on ensimmäinen julkisen avaimen todennäköisyyspohjainen salausjärjestelmä , joka on todistetusti turvallinen tavanomaisilla salausoletuksilla. . Tuomaristo arvosti ehdotettua järjestelmää suuresti: Goldowasser ja Micali palkittiin Turing Award -palkinnolla vuodelle 2012 [23] , salausjärjestelmän luomisesta todennäköisyyspohjaisella salauksella, joka todettiin ehdokkuudessa innovatiiviseksi teokseksi, jolla oli merkittävä vaikutus nykyaikaiseen. kryptografia . Salausjärjestelmä on kuitenkin tehoton, koska sen luoma salateksti voi olla satoja kertoja pidempi kuin salattu viesti .

Todistaakseen kryptojärjestelmän turvallisuusominaisuudet Goldwasser ja Micali esittelivät semanttisen turvallisuuden käsitteen [24] [25] .

Vuonna 2021 Laszlo Lovas ja Avi Wigderson saivat Abel-palkinnon teoreettisen tietojenkäsittelytieteen työstään , joka vaikutti merkittävästi laskennallisen monimutkaisuusteorian, graafiteorian, hajautettujen laskentamenetelmien ja nollatietotodisteiden käsitteen kehittämiseen . 26] .

Nollatietotodisteiden yleinen rakenne

Jokainen kierros eli todistusakkreditointi koostuu kolmesta vaiheesta. Kaavamaisesti ne voidaan kuvata seuraavasti:

Ensin A valitsee jonkin elementin ennalta määritetystä ei-tyhjästä joukosta , josta tulee sen salainen yksityinen avain . Tämän elementin perusteella julkinen avain lasketaan ja julkaistaan . Salaisuuden tietäminen määrää kysymysjoukon, joihin A voi aina antaa oikeat vastaukset. Sitten A valitsee joukosta satunnaisen alkion, laskee tiettyjen sääntöjen mukaan (riippuen tietystä algoritmista) todisteen ja lähettää sen sitten B :lle . Tämän jälkeen B valitsee yhden kysymyksen koko sarjasta ja pyytää A :ta vastaamaan siihen (haaste). Kysymyksestä riippuen A lähettää B :lle vastauksen [27] . Vastaanotettu tieto B riittää tarkistamaan, omistaako A todella salaisuuden. Kierroksia voidaan toistaa niin monta kertaa kuin halutaan, kunnes todennäköisyys , että A "arvaa" vastaukset, on riittävän pieni. Tätä lähestymistapaa kutsutaan myös "leikkaa ja valitse", jota ensimmäisenä käytti kryptografiassa Michael Rabin [28] [29] .

Esimerkkejä

Zero Knowledge Cave

Tämä esimerkki kirjoitettiin ensimmäisen kerran Jean-Jacques Kiskaterin tunnetussa nollatietotodistuspaperissa "Kuinka selittää nollatietotodistusprotokolla lapsillesi".[30] .

Tässä tapauksessa Peggy toimii todistajana ja Victor todentajana (englanninkielisessä kirjallisuudessa käytetään yleensä osapuolten nimiä Peggy ja Victor (vastaavasti sanoista "Prover" ja "Verifier"). Peggy tietää taikasanan ("avain") "), syöte, jonka avulla hän voi avata oven C:n ja D:n välillä. Victor haluaa tietää, tietääkö Peggy todella salasanan, kun taas Peggy ei halua antaa itse salasanaa. Luola on pyöreä, kuten kuvassa näkyy. Ongelman ratkaisemiseksi he etenevät seuraavalla tavalla: Victorin ollessa pisteessä A Peggy menee ovelle ja kun hän katoaa näkyvistä, Victor menee haarukkaan eli pisteeseen B ja huutaa sieltä: "Peggy tarvitsee poistua oikealta " tai "Peggy tarvitsee poistua vasemmalle " Saamme joka kerta todennäköisyydellä, että Peggy ei tiedä salasanaa, on 50%.Jos toistamme prosessin k kertaa, silloin todennäköisyys on . 20 toistolla tämä todennäköisyys on suuruusluokkaa 10 −6 , mikä riittää oikeudenmukaisuudelle . Nämä oletukset, että Peggy tietää avaimen [30] .

Jos Victor tallentaa kaiken, mitä tapahtuu kameralla, tuloksena oleva video ei ole todiste kenellekään muulle osapuolelle. Loppujen lopuksi he olisivat voineet sopia etukäteen, mistä Peggy tulee. Näin ollen hän pystyy löytämään tien ulos tietämättä itse avainta. On toinenkin tapa: Victor yksinkertaisesti katkaisee kaikki Peggyn epäonnistuneet yritykset. Nämä yllä olevat vaiheet osoittavat, että luolaesimerkki täyttää täydellisyyden , oikeellisuuden ja nollatiedon ominaisuudet [31] .

Hamiltonin sykli suurille kaavioille

Tämän esimerkin keksi Manuel Blum , ja se kuvattiin artikkelissaan vuonna 1986 [32] . Kutsutaan testaajaa Victoria ja todistajaa Peggyksi. Oletetaan, että Peggy tietää Hamiltonin syklin suuressa graafissa G . Victor tuntee graafin G , mutta hän ei tiedä Hamiltonin sykliä siinä. Peggy haluaa todistaa Victorille tuntevansa Hamiltonin syklin paljastamatta itse sykliä tai mitään tietoa siitä (ehkä Victor haluaa ostaa tietoa tästä Hamiltonin syklistä Peggyltä, mutta ennen sitä hän haluaa varmistaa, että Peggy todella tuntee hänet ).

Tätä varten Victor ja Peggy suorittavat yhdessä useita protokollan kierroksia :

Jokaisella kierroksella Victor valitsee uuden satunnaisen bitin , jota Peggy ei tiedä, joten jotta Peggy voisi vastata molempiin kysymyksiin, H :n on todellakin oltava isomorfinen G :n kanssa ja Peggyn on tiedettävä Hamiltonin sykli H :ssa (ja siten myös G :ssä ). Siksi riittävän kierrosten määrän jälkeen Victor voi olla varma, että Peggy todella tietää Hamiltonin syklin G :ssä . Toisaalta Peggy ei paljasta mitään tietoa Hamiltonin syklistä G :ssä . Lisäksi Victorin on vaikea todistaa muille, että hän tai Peggy tuntee Hamiltonin syklin G :ssä [32] .

Oletetaan, että Peggy ei tunne Hamiltonin sykliä G :ssä , mutta hän haluaa huijata Victoria. Sitten Peggy tarvitsee ei-isomorfisen G - graafin G′ , jossa hän vielä tuntee Hamiltonin syklin . Jokaisella kierroksella hän voi siirtyä Victorille joko H′  - isomorfinen G: lle tai H  - isomorfinen G :lle . Jos Victor pyytää todistamaan graafien isomorfismin, ja hänelle annettiin H , niin petos ei paljasteta. Vastaavasti, jos hän pyytää näyttämään Hamiltonin syklin, ja hänelle annettiin H′ . Tässä tapauksessa todennäköisyys, että Peggy silti pettää Victorin k kierroksen jälkeen, on yhtä suuri kuin , mikä voi olla pienempi kuin mikä tahansa ennalta määrätty arvo riittävällä määrällä kierroksia [32] .

Oletetaan, että Victor ei tunnista Hamiltonin sykliä, mutta haluaa todistaa Bobille, että Peggy tietää sen. Jos Victor esimerkiksi nauhoittaisi kaikki protokollan kierrokset, Bob tuskin uskoisi häntä. Bob voi olettaa, että Victor ja Peggy ovat sekaisin, ja jokaisella kierroksella Victor kertoo Peggylle valitsemansa satunnaisen bitin etukäteen, jotta Peggy voi ohittaa hänelle H :n isomorfismitesteissä ja H′ :n Hamiltonin syklin testeissä. Siten ilman Peggyn osallistumista on mahdollista todistaa, että hän tuntee Hamiltonin syklin vain todistamalla, että todella satunnaiset bitit valittiin protokollan kaikilla kierroksilla [33] .

Sovellus käytännössä

Oded Goldreich , Silvio Micali ja Avi Wigderson [ 19] todistivat lauseen, jonka mukaan mille tahansa NP-täydelliselle ongelmalle on olemassa nollatietotodistus, kun taas yksisuuntaisia ​​funktioita käyttämällä voidaan luoda oikeat kryptografiset protokollat . 34] . Toisin sanoen voit todistaa kenelle tahansa skeptikolle, että sinulla on todiste jostain matemaattisesta lauseesta paljastamatta itse todistetta. Tämä osoittaa myös, kuinka tätä protokollaa voidaan käyttää käytännön tarkoituksiin [13] .

Seuraava menetelmä, jossa nollatietotodistusta voidaan käyttää, on identiteetin määritys, jossa Peggyn yksityinen avain on ns. "identiteettiindikaattori", ja kyseisellä protokollalla voidaan todistaa henkilöllisyytensä. Eli voit todistaa henkilöllisyytesi käyttämättä erilaisia ​​fyysisiä laitteita ja tietoja (symboleja), kuten passeja, erilaisia ​​henkilökuvia (verkkokalvo, sormet, kasvot jne.), mutta olennaisesti eri tavalla [35] . Sillä on kuitenkin useita haittoja, joita voidaan käyttää suojauksen ohittamiseen. Yllä kuvattua menetelmää ehdottivat ensimmäisen kerran Amos Fiat , Adi Shamir ja Uriel Feige vuonna 1987 [36] .

Myös nollatietotodistuksia voidaan käyttää luottamuksellisissa laskentaprotokollissa , jolloin useat osallistujat voivat varmistaa, että toinen osapuoli noudattaa protokollaa rehellisesti [19] .

Nollatietotodisteita käytetään kryptovaluuttojen Zcash , Byzantium (Ethereumin haarukka ) , Zerocoin ja muiden lohkoketjuissa. Nolla-knowledge proof -protokollien toteutuksia on luotu, erityisesti QED-IT Software Development Kit. Hollantilainen pankki ING loi protokollasta oman versionsa, ZKRP ( Zero-Knowledge Range Proof ) ja sovelsi sitä todistamaan, että asiakkaalla on riittävä palkka paljastamatta sen todellista kokoa [7] [8] .

Yleisimmät protokollat ​​ovat zk-SNARKit, juuri tämän luokan protokollia käytetään ZCashissa, Zcoinissa ja Ethereum-lohkoketjun Metropolis-protokollassa [37] [8] .

Lyhenne zk-SNARK tarkoittaa   nolla-tietoa, tiivistä ei-interaktiivista tiedon argumenttia [37] [8] . zk-SNARK-algoritmi koostuu avaingeneraattorista, todistajasta ja todentajasta, tukee välttämättä nollatietoa, on lyhyitä (laskettu lyhyessä ajassa), on ei-interaktiivinen (todentaja saa vain yhden viestin todistajalta) [8] .

Väärinkäyttö

On ehdotettu useita tapoja käyttää väärin nollatietotodisteita, jotka hyödyntävät protokollan tiettyjä heikkouksia:

Suurmestarin ongelma

Tässä esimerkissä joku osapuoli voi todistaa salaisuuden hallussa pitäneensä sitä tosiasiallisesti omaamatta, tai toisin sanoen se voi jäljitellä henkilöä, joka todella omistaa salaisuuden [38] . Tällä hetkellä tapaa ratkaista ongelma on ehdottanut Thomas Beth ja Ivo Desmedt [39] .

Petos useilla identiteeteillä

Jos puolue voi luoda useita salaisuuksia, se voi myös luoda "useita identiteettejä" vastaavasti. Älä koskaan käytä yhtä niistä. Tämä mahdollisuus mahdollistaa kertaluonteisen anonymiteetin, joka mahdollistaa esimerkiksi vastuun kiertämisen: osapuoli tunnistaa itsensä käyttämättömäksi henkilöksi ja tekee rikoksen. Sen jälkeen tätä "identiteettiä" ei käytetä enää koskaan. On lähes mahdotonta jäljittää tai yhdistää rikoksentekijää kenenkään kanssa. Tällainen väärinkäyttö estetään, jos mahdollisuus toisen salaisuuden luomiseen suljetaan alusta alkaen pois [40] .

Mafian tekemä petos

Toinen esimerkki siitä, että toinen osapuoli teeskentelee olevansa toinen. Olkoon 4 osallistujaa: A , B , C , D . Lisäksi B ja C tekevät yhteistyötä keskenään ("kuuluvat samaan mafiaan"). A todistaa henkilöllisyytensä B :lle ja C haluaa esiintyä A :na D :n edessä . B omistaa mafian omistaman ravintolan, C  on myös mafian edustaja, D  on jalokivikauppias. A ja D eivät ole tietoisia tulevasta petoksesta. Heti kun A on valmis maksamaan illallisen ja tunnistamaan itsensä B :lle , B ilmoittaa C :lle huijauksen alkamisesta. Tämä on mahdollista, koska niiden välillä on radiokanava. Tällä hetkellä C valitsee timantin, jonka hän haluaa ostaa, ja D alkaa tunnistaa C :tä , joka esiintyy A :na. C välittää protokollakysymyksen B :lle, joka puolestaan ​​kysyy sen A :lta. Vastaus lähetetään käänteisessä järjestyksessä. Siten A ei maksa vain illallisesta, vaan myös kalliista timantista. Kuten edellä olevasta voidaan nähdä, tällaisille petoksille on asetettu tiettyjä vaatimuksia. Kun A alkaa todistaa henkilöllisyytensä B :lle ja C D :  lle , B :n ja C :n toimet on synkronoitava. Tämäkin väärinkäyttö on sallittua. Jos esimerkiksi jalokiviliikkeessä on Faradayn häkki , "mafiosi" ei voi vaihtaa viestejä [41] .

Mahdolliset hyökkäykset

Valittu salakirjoitushyökkäys

Tämä hyökkäys on toteutettavissa käyttämällä ei-vuorovaikutteista vuorovaikutusmenetelmää nollatietoprotokollassa.

Tässä protokollassa on useita ongelmia. Ensinnäkin sinun on päätettävä, kuinka haluat olla vuorovaikutuksessa, säilyttäen samalla protokollan perusominaisuudet: täydellisyys, oikeellisuus ja "nollatieto". Sen lisäksi, että on melko helppoa todistaa toiselle osapuolelle nollatietämys, jos on mahdollista salakuunnella kanavaa, eli kohdata suurmestari-ongelma .

Joten itse hyökkäys on seuraava: hyökkääjä käyttää tietonsa monimutkaisuutta ja sisältää "hyökkäävän" salatekstin , joka sujauttaa sen joukkoon muita salatekstejä, joiden salaus on purettava. Tätä hyökkäystä kutsutaan "toistohyökkäykseksi" [42] .

Mahdollinen ratkaisu perustuu Moni Naor ja Moti Yung työhön , joka on seuraava: Prover ja Verifier salaavat viestit julkisella avaimella , tämä aiheuttaa yllä olevan hyökkäyksen epäonnistumisen [43] .

Hyökkäys moniprotokollallista nollatietojärjestelmää vastaan

Chida ja Yamamoto ehdottivat nollatietoprotokollan toteutusta, joka lisää merkittävästi nollatietotodisteiden nopeutta ja samalla todistaa useita väitteitä kerralla ja sen seurauksena koko järjestelmän suorituskykyä [44] . Keskeinen piirre on todistuksen iteraatioiden määrän rajoittaminen. Kuten K. Pengin [45] työstä käy ilmi , tämä algoritmi osoittautui täysin epävakaaksi seuraavalle hyökkäykselle. Useita hyvin valittuja iteraatioita käyttämällä hyökkääjä voi läpäistä varmennuksen ja rikkoa protokollan pääehtoja. Lisäksi osoitettiin, että tämä hyökkäys on aina mahdollista tällaisessa järjestelmässä.

Hyökkäys kvanttitietokoneella

Vuonna 2005 John Watrus esitti , että kaikki nollatietojärjestelmät eivät kestä kvanttitietokonehyökkäyksiä . On kuitenkin osoitettu, että on aina mahdollista rakentaa järjestelmä, joka kestää kvanttihyökkäyksiä, olettaen, että on olemassa kvanttijärjestelmiä, joissa on "velvoitteiden salaaminen" [46] .

Katso myös

Muistiinpanot

  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 , s. 1444.
  10. Menezes et ai., 1996 , s. 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 , 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 ja Rackoff saavat Gödel-palkinnon vuonna 1993 (linkki ei ole käytettävissä) . ACM Sigact (1993). Arkistoitu alkuperäisestä 8. joulukuuta 2015. 
  23. Goldwasser, Micali saavat ACM Turing -palkinnon edistymisestä kryptografiassa (linkki ei ole käytettävissä) . ACM. Haettu 13. maaliskuuta 2013. Arkistoitu alkuperäisestä 16. maaliskuuta 2013. 
  24. Goldwasser, Micali, 1982 .
  25. Mao, 2005 , s. 524-528.
  26. Abel-palkinto - 2021 • Andrey Raigorodsky • Tieteen uutisia aiheesta "Elementit" • Matematiikka, tiede ja yhteiskunta . Haettu 17. toukokuuta 2021. Arkistoitu alkuperäisestä 3. kesäkuuta 2021.
  27. Mao, 2005 , s. 678-682.
  28. MORabin. digitaaliset allekirjoitukset . — Suojatun tietojenkäsittelyn perusteet. - 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 Ketjumedia , 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 .

Kirjallisuus

kirjoja ja monografioita artikkeleita

Linkit