Mielenosoitus nolla tietoa

Mielenosoitukseen salaus tietoinen nolla tai nolla-tieto protokolla on interaktiivinen menetelmä käyttää henkilö todistaa toiselle henkilölle, että väite pitää paikkansa, paljastamatta mitään muuta kuin todenperäisyyttä viipymättä.

Abstrakti kuva

On tarina tunnettu esittelemään joitakin ajatuksia takana nollatietotodistuksen. On tapana kutsua kaksi puolta nollatietotodistuksen Peggy ja Victor.

Tässä tarina, Peggy selville salaisuuden sanaa käytetään avaamaan maaginen ovi luolassa. Luola on muodoltaan ympyrä, jossa sisäänkäynti toisella puolella ja maaginen ovi, joka estää toisella puolella. Victor sanoo hän aikoo maksaa salaisuus, mutta ei ennen kuin se on varma, että hän tietää häntä todella. Peggy kertoo se kertoo salaisuuden, mutta ei ennen kuin saa rahat. Sitten suunnitella järjestelmä, jossa Peggy voi yrittää tietää sanan ilmoittamatta sitä Victor.

Ensinnäkin, Victor odottaa ulos luolasta, kun Peggy tulee. Merkitsemme polku vasemmalle ja oikealle sisäänkäynnin A ja B Peggy satunnaisesti valitsee yhden kahdesta polusta. Niin, Victor saapuu luola ja huutaa nimi polku, Peggy käyttää palata takaisin, välillä A ja B, on otettu satunnaisesti. Olettaen, että hän todella tuntee taikasana, se on helppo: avaa oven tarvittaessa ja palauttaa läpi halutun polun. On huomionarvoista, että Victor ei tiedä polku, joka Peggy syötetty.

Kuitenkin oletetaan, että Peggy ei tiedä sana. Sitten se voisi palata läpi polku nimeltään Victor jos hän oli valinnut nimen samaa polkua, että hän oli tullut. Koska Victor on valinnut tai B osalta, se olisi 50% todennäköisyydellä oikein arvaamaan. Jos kaksi toistoa tämä temppu monta kertaa, sanovat kaksikymmentä kertaa peräjälkeen, mahdollisuus Peggy oikein ennakoida kaikki pyynnöt Victor tulisi tilastollisesti hyvin pieni.

Siksi, jos Peggy näyttää niin "luotettava" exit puhelun Victor, tämä voidaan päätellä, että todennäköisesti todella tietää salaisuus sana.

Määritelmä

Nollatietotodistuksen on täytettävä kolme ominaisuudet:

  • Täydellisyys: jos lausunto on totta, mielenosoittaja vakuuttaa rehellinen tosiasia rehellinen vahvistamia.
  • Oikeudenmukaisuus: jos lausunto on väärä, ei mielenosoittaja petkuttaja voi vakuuttaa rehellinen todentaja että se on totta, tai paremmat mahdollisuudet vakuuttavia voidaan tehdä pieni mieleisekseen.
  • Zero tietoa: jos väite pitää paikkansa, ei todentajan huijari tiedä mitään, mutta tämä tieto. Tämä seikka on virallistettiin osoittamalla, että kukin todentajan huijari voi olla simulaattori, jos hänelle annetaan vain todistaa väitteen, voi saada transkriptio että "näyttää" vuorovaikutusta todentajan ja mielenosoittajan rehellinen roisto.

Kaksi ensimmäistä ovat ominaisuuksia yleisempi luokan vuorovaikutteisten järjestelmien esittely; kolmas on spesifinen mielenosoituksia nollaan tietoon. Erityisesti ensimmäinen ominaisuus vastaa täydellisyyttä kuin yleisesti ymmärretään logiikka, kun taas toinen ei ole suoraan liitettävissä oikeellisuutta; keskeisiä komponentti on tietenkin kolmas.

Tutkimus nollatietotodistuksen edistettiin autentikointi järjestelmiä, joissa toinen osapuoli haluaa todistaa henkilöllisyytensä toisen osan läpi joitakin salaisia ​​tietoja, mutta haluavat toinen osa ei tiedä mitään tästä salassa. Tätä kutsutaan "nollatietotodistuksen tiedon."

Mielenosoitukset eivät ole nollatietotodistuksen vedoksia matemaattisessa mielessä, koska siellä on aina pieni mahdollisuus, että mielenosoittaja petkuttaja voi vakuuttaa todentaja väärän lausunnon. Toisin sanoen, nämä tyypit algoritmit ovat todennäköisyyksiin ja ole deterministinen. On kuitenkin olemassa, joilla voidaan vähentää tämä todennäköisyys pieniin arvoihin maun.

Virallista määritelmää nollatietotodistuksen täytyy käyttää joitakin mallin laskenta, prinssi on Turingin kone. Olkoon P, S ja V Turingin koneiden. Interaktiivinen mielenosoitus, jossa kieli L on tietoinen nolla, jos jokaiselle probabilistisen polynomiaikainen todentaja olemassa PPT simulaattori S siten, että

Mielenosoittaja on modelizzato P olevan rajaton laskentatehoa. Intuitiivisesti määritelmän mukaan järjestelmä interaktiivinen todiste on nollatietotodistuksen jos kunkin todentajan olemassa tehokas simulaattori S, joka pystyy lisääntymään välistä keskustelua P ja kunakin panos. Ylimääräisten merkkijono z roolissa määritelmässä "aiempaa tietoa". Määritelmä merkitsee sitä, että se voi käyttää merkkijonoa etukäteen tiedossa selvittää tietoa keskustelun P koska se vaatii, että jos S annetaan tämän etukäteen tietoa voi sitten toistaa välistä keskustelua P ja kuten ennen.

Määritelmä on, että nolla tiedon täydellinen. Laskennallinen nolla tieto saadaan vaatimalla, että näkemykset tilintarkastaja ja simulaattori ovat vain laskennallisesti erottamattomat, koska ylimääräiset merkkijono.

Joko niin, salasana on tyypillisesti liian lyhyt tai liian vähän satunnainen voidaan käyttää monissa järjestelmiin nollatietotodistuksen. Esittelyn nollaan tietoa salasanat on erityinen todisteita nollaan ominaisen osaamisen salasanan pituus rajallinen.

Yksi käyttötavoista kiehtovimmista mielenosoituksia nollaan tietoa kryptografisen protokollan on vahvistaa käyttäytymistä rehellinen ja silti säilyttää yksityisyyden. Karkeasti, ajatus on pakottaa käyttäjän kokeilla, käyttäen nollatietotodistuksen, oikeellisuuden sen käyttäytymistä suhteessa pöytäkirjan. Koska oikeudenmukaisuus, me tiedämme, että käyttäjä on käyttäytyä todella rehellinen taitava tarjoamaan pätevä todiste. Ja koska nolla tieto, me tiedämme, että käyttäjä ei vaaranna yksityisyyttä salaisuuksia prosessissa, joka tarjoaa todisteet. Tämä sovellus mielenosoitukset nolla tietoa käytettiin ensimmäisen kerran julkaisemisen järkyttävä Goldreich, Micali, ja Wigderson laskentakeskukset turvallinen moniosaisia.

Konkreettinen esimerkki

Voimme laajentaa näitä käsitteitä hakemuksen salauksen realistisempi. Tässä skenaariossa Peggy tietää Hamiltonin kehä on suuri kuvaaja "G". Victor tietää "G", mutta ei sykli Peggy yrittää tietää syklin paljastamatta sitä. Hamiltonin sykli kuvaaja on vain yksi tapa toteuttaa nollatietotodistuksen; Itse asiassa, joka NP-täydellinen ongelma voidaan käyttää tähän tarkoitukseen, sekä joitakin muu vaikea ongelma, kuten factoringia. Kuitenkin, Peggy ei yksinkertaisesti paljastaa Hamiltonin tai muut tiedot Victor; Hän haluaa pitää salassa sykli.

Voit näyttää tietää sykli, Peggy pelaa yhdessä Victor seuraavasti:

  • Alussa jokaisen käden, Peggy luo "H", kuvaaja isomorfinen "G". Koska se on triviaalia kääntää Hamiltonin sykli tietyn kuvaajan isomorfismi, jos Peggy tietää Hamiltonin sykli "G" tietää edes yksi "H".
  • Victor sitten satunnaisesti valita yksi seuraavista kaksi kysymystä Peggy. Se voi pyytää teitä osoittamaan isomorphism välillä "H" ja "G" tai vaatia voit näyttää Hamiltonin in "H".
  • Ensimmäisessä tapauksessa, Peggy toimittaa käännökset kärki mitä karttaa "G" ja "H". Victor voi varmasti vahvistaa, että nämä kaksi ovat isomorfiset.
  • Toisessa tapauksessa, Peggy kääntää hänen Hamiltonin sykli "G" myös asianomaiseen "H" ja paljastaa Victor. Hän tarkistaa sen pätevyyttä.

Jokaiselle käsi Peggy ei tiedä, mitä pyyntö tehdään kunnes hän antoi Victor kohta "H". Siksi vihdoin pystyä vastaamaan sekä "H" on isomorfinen "G" ja Peggy oltava Hamiltonin sykli "H". Koska vain mielenosoittaja tietoinen Hamiltonin syklin "G" voi olla aina pystyä vastaamaan molempiin pyyntöihin, Victor, on vakuuttunut siitä, että Peggy tuntee tiedot, tai Hamiltonin syklin "G".

Kuitenkin vastaus Peggy kuten näemme ei paljasta tällaisia ​​tietoja. Jokaiselle käsi Victor on tietoinen ainoastaan ​​isomorphism peräisin "H" ja "G" tai Hamiltonin in "H". Tiedot toimisi sekä single "H" selvittää syklin "G", mutta huomaa, että voit vain tehdä yksi kaksi kysymystä molemmista käsistä, ja että Peggy käyttää uutta "H" kunkin: tiedot säilyvät tuntematon juuri tämä edellytys, kun perustettiin ensimmäinen sääntö peli muuttumaton.

Koska luonteesta isomorphism välillä kuvaajat ja syklit Hamiltonin, Victor ei saada tietoa Hamiltonin syklin "G" alkaen saamiensa tietojen jokaisen käden Peggy.

Jos Peggy ei tiedä tietoja, voit yrittää arvata, mikä kysymys kysyy Victor ja tuottaa kuvaaja tai isomorfinen "G" tai Hamiltonin sykli yleinen kuvaajan, mutta hän ei tiedä tietoja itsessään voi tehdä molempia. Tämän indovinìo, hänen mahdollisuutensa huijata Victor oli 2, missä n on määrä käsiä. Käytännössä, se on mahdotonta voittaa esittelyn nolla tietämyksen määrän käsiä kohtuullinen varmuus.

Malli versiot

Eri versioita nollatietotodistuksen voidaan määritellä virallistamalla intuitiivinen käsitys siitä, mitä tarkoitetaan tuotoksen simulaattori "tuntuu" suorituksen todellinen pöytäkirja, joka on mainittu edellä:

  • Puhumme täydellinen nolla tiedon jos jakaumat liittyvät simulaattori ja esittelyn protokolla ovat täsmälleen samat; Se on kyse ensimmäisen esimerkin.
  • Puhutaanpa tilastollinen tieto nolla jakaumat eivät välttämättä ole yhtä suuri, mutta ne ovat tilastollisesti lähellä, mikä tarkoittaa, että niiden tilastollinen ero on mitätön.
  • Puhumme algoritmeihin tietämyksen nolla, jos ei ole tehokas algoritmi voidaan erottaa kaksi jakaumat.

Historia ja tulokset

Mielenosoituksia nolla tieto oli alunperin vuonna 1985 Shafi Goldwasserista, et al., In luonnos "tiedon monimutkaisuus vuorovaikutteisten proof-järjestelmät". Tästä huolimatta merkittävä julkaisu ei ole keksinyt järjestelmiä interaktiivinen esittely, se on ensimmäistä kertaa ehdotti hierarkia "IP" yhteydessä näiden ja suunniteltu käsite "kognitiivinen monimutkaisuus", mitta määrän tietoa esittelyn siirretään mielenosoittaja todentajalle. Kirjoittajat antoi myös ensimmäinen osoitus nolla tietoa todellinen ongelma, päättää nonresidui asteen malli "m". Lainaten:

Kyseinen ongelma on sekä liuos algoritmi NP on co-NP, on leikkauspiste kaksi luokkaa, ja sama koskee myös monia muita ongelmia, joita varten ne on myöhemmin saatetaan nollatietotodistuksen todisteita.

Oded Goldreich, et al., Led keskustelu seuraavalle tasolle osoittamalla, että olettaen olemassaolo salauksen valloittamaton, voit rakentaa nollatietotodistuksen NP-täydellinen ongelma värityksen kuvaajan kolme väriä. Koska jokainen ongelma NP voidaan tehokkaasti pienentää tätä ongelmaa, tämä tarkoittaa sitä, tämä oletus, kaikki ongelmat NP voi olla nolla tietoa todisteet. Motivaatio rekrytointi on että, kuten edellä olevassa esimerkissä, niiden protokollat ​​vaativat salausta. Tilanne yleisesti mainittu riittää olemassaolon salauksen voittamaton on olemassa yksisuuntainen toimintoja, mutta on mahdollista, että jokin fyysinen keinoja, pääsee itse.

Lisäksi ne ovat myös osoittaneet, että ongelma isomorfismi välillä kuvaajat täydennys on nollatietotodistuksen; tämä ongelma on co-NP tuolloin, mutta se ei ole tiedossa, jos joko NP tai muulla luokassa käytännössä. Yleisemmin Goldreich, Goldwasserista et al. He ovat myös osoittaneet, että vaikka oletettaisiin, kuten salaus teoreettinen, on nollatietotodistuksen todisteet "Kaikki" ongelmat IP = PSPACE, tai toisin sanoen, kaikki, jotka voidaan osoittaa interaktiivinen järjestelmä voi olla nollasta yhteen tietoa.

Mieluummin ei tehdä tarpeettomia oletuksia, monet tutkijat ovat keksineet tapoja poistaa tarvetta yksisuuntainen toimintoja. Muun muassa yksi oli kautta "useita interaktiivisia mielenosoituksen järjestelmät", joka on paljon mielenosoittajat riippumaton yhden sijaan, jolloin tilintarkastaja tutkia yksittäisten rajat prover yksilöllisesti välttää harhaan. Voidaan osoittaa, että ilman oletukset intractability, kaikki kielet NP mielenosoituksissa on nolla tietoa tällaisessa järjestelmässä.

On silmiinpistävää, että skenaario kuten että Internetissä, jossa useita protokollia voidaan suorittaa samanaikaisesti, rakentaa nollatietotodistuksen on kiinnostavampi. Linja tutkimusta, joka tutkii mielenosoitukset nolla tietoa kilpailijoiden aloitettiin työn Dwork, Naor ja Sahai. Erityisesti kehitys pitkin on ollut kehityksen pöytäkirjojen kutsutaan todistaja-erottamattomat. Omaisuus liittyy että nolla tietoa, mutta nämä pöytäkirjat eivät kärsi samoista ongelmista samanaikaisten suorittamisen.

Nollatietotodistuksen voi olla toista versiota myöskään vuorovaikutteinen. Blum, Feldman ja Micali osoitti, että satunnainen merkkijono jaettu mielenosoittajan ja todentaja on tarpeeksi saada kyseessä laskennallisen nolla tietoa, ilman vuorovaikutusta.

  0   0
Edellinen artikkeli Tekninen alue
Seuraava artikkeli Ida

Aiheeseen Liittyvät Artikkelit

Kommentit - 0

Ei kommentteja

Lisääkommentti

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Merkkiä jäljellä: 3000
captcha