Kuvittele, että sinulla on hyödyllistä tietoa – ehkä salainen resepti tai salauksen avain. Voisitko todistaa ystävällesi, että sinulla oli tämä tieto paljastamatta siitä mitään? Tietojenkäsittelytieteilijät osoittivat yli 30 vuotta sitten, että pystyisit, jos käyttäisit niin sanottua nollatietotodistusta.
Jos haluat ymmärtää tämän idean helposti, oletetaan, että haluat näyttää ystävällesi, että osaat selviytyä sokkelon läpi paljastamatta mitään yksityiskohtia polusta. Voisit yksinkertaisesti kulkea sokkelon läpi tietyn ajan sisällä, samalla kun ystävääsi kiellettiin katsomasta. (Aikaraja on välttämätön, koska jos aikaa on riittävästi, kuka tahansa voi lopulta löytää tiensä ulos yrityksen ja erehdyksen kautta.) Ystäväsi tietäisi, että pystyt siihen, mutta he eivät tietäisi miten.
Nollatietotodistukset ovat hyödyllisiä salaustiedon parissa työskenteleville kryptografeille, mutta myös laskennallisen monimutkaisuuden tutkijoille, jotka käsittelevät eri ongelmien vaikeuden luokittelua. "Moni nykyaikainen kryptografia perustuu monimutkaisuusoletuksiin - olettamukseen, että tiettyjä ongelmia on vaikea ratkaista, joten näiden kahden maailman välillä on aina ollut joitain yhteyksiä", sanoi Claude Crépeau, tietojenkäsittelytieteilijä McGill Universityssä. "Mutta [nämä] todisteet ovat luoneet kokonaisen yhteyksien maailman."
Nollatietotodistukset kuuluvat luokkaan, joka tunnetaan nimellä interaktiiviset todisteet, joten jos haluat oppia, miten edellinen toimii, se auttaa ymmärtämään jälkimmäistä. Ensimmäinen on kuvattu Tietojenkäsittelytieteilijöiden vuoden 1985 artikkelissa Shafi Goldwasser, Silvio Micali ja Charles Rackoff, vuorovaikutteiset todisteet toimivat kuin kuulustelu: Viestien sarjan aikana toinen osapuoli (todistaja) yrittää vakuuttaa toisen (todentajan) siitä, että tietty väite on totta. Interaktiivisen todisteen on täytettävä kaksi ominaisuutta. Ensinnäkin tosi väite saa aina lopulta vakuuttuneeksi rehellisen todentajan. Toiseksi, jos annettu väite on väärä, mikään todistaja - edes sellainen, joka teeskentelee omistavansa tiettyä tietoa - ei voi vakuuttaa todentajaa, paitsi mitättömän pienellä todennäköisyydellä.
Interaktiiviset todistukset ovat luonteeltaan todennäköisyyspohjaisia. Todistaja pystyi vastaamaan yhteen tai kahteen kysymykseen oikein yksinkertaisesti tuurilla, joten tarvitaan riittävän suuri määrä haasteita, jotka kaikki todistajan on suoritettava oikein, jotta todentaja voi varmistua siitä, että todistaja todella tietää väitteen olevan totta.
Tämä ajatus vuorovaikutuksesta syntyi, kun Micali ja Goldwasser – silloiset jatko-opiskelijat Kalifornian yliopistossa Berkeleyssä – ymmärsivät pokerin verkossa pelaamisen logistiikan. Kuinka kaikki pelaajat voivat varmistaa, että kun joku heistä saa kortin virtuaalipakasta, tulos on satunnainen? Interaktiiviset todisteet voisivat näyttää tietä. Mutta kuinka pelaajat voivat varmistaa, että koko protokollaa – kaikkia sääntöjä – noudatettiin oikein paljastamatta jokaisen pelaajan kättä matkan varrella?
Tämän tavoitteen saavuttamiseksi Micali ja Goldwasser lisäsivät kolmannen ominaisuuden kahdelle, joka tarvitaan vuorovaikutteisessa todistuksessa: Todistuksen ei pitäisi paljastaa mitään itse tiedosta, vain väitteen totuudenmukaisuus. "On ajatus käydä läpi protokolla, jonka lopussa uskot, että [pokerinpelaajat] eivät tiedä mitään muuta kuin mitä heidän pitäisi tietää", Goldwasser sanoi.
Tarkastellaanpa klassista esimerkkiä. Alice haluaa todistaa Bobille tietyn kaavion G - ainutlaatuinen kokoelma kärkipisteitä (pisteitä), jotka on yhdistetty reunoilla (viivoilla) - sisältää "Hamiltonin syklin". Tämä tarkoittaa, että kaaviossa on polku, joka vierailee jokaisessa pisteessä täsmälleen kerran ja päättyy samaan pisteeseen, josta se alkoi. Alice voisi tehdä tämän yksinkertaisesti näyttämällä Bobille polun, joka tekee tämän, mutta tietysti silloin hänkin tietäisi polun.
Näin Alice voi vakuuttaa Bobin, että hän tietää sellaisen polun, näyttämättä sitä hänelle. Ensin hän piirtää uuden kaavion, H, ei siltä näytä G mutta on samankaltainen ratkaisevalla tavalla: Sillä on sama määrä pisteitä, jotka on kytketty samalla tavalla. (Jos G on todella Hamiltonin sykli, tämä samankaltaisuus tarkoittaa H tulee myös.) Sitten, kun olet peittänyt jokaisen reunan H maalarinteipillä, hän lukitsee H laatikossa ja antaa laatikon Bobille. Tämä estää häntä näkemästä sitä suoraan, mutta estää myös häntä muuttamasta sitä. Sitten Bob tekee valinnan: Joko hän voi pyytää Alicea näyttämään sen H on todella samanlainen G, tai hän voi pyytää häntä näyttämään hänelle Hamiltonin syklin H. Molempien pyyntöjen pitäisi olla Alicelle helppoja, olettaen että H on todella riittävän samanlainen G, ja että hän todella tietää polun.
Tietysti, vaikka Alice ei tiedä Hamiltonin kiertokulkua G, hän voi yrittää huijata Bobia joko piirtämällä kaavioita, jotka eivät ole samanlaisia G, tai lähettämällä kaavioita, joihin hän ei tiedä polkua. Mutta kun he ovat pelanneet useita kierroksia, mahdollisuus, että Alice pettää Bobia joka kerta, on häviävän pieni. Jos hän saa kaiken oikein, Bob on lopulta vakuuttunut siitä, että Alice tietää Hamiltonin syklin kaaviossa G, ilman että Bob olisi koskaan nähnyt sitä.
Tällaisia todisteita ensimmäisen kerran kuvailevan paperin jälkeen Micali ja kaksi matemaatikkoa – Oded Goldreich ja Avi Wigderson – löysivät odottamattoman seurauksen, jolla oli kauaskantoisia vaikutuksia. Se liittyy suurin piirtein saman vaikeusluokan ongelmaluokkaan, joka tunnetaan nimellä NP. Näitä ongelmia on vaikea ratkaista, mutta niiden ratkaisut on helppo tarkistaa. Kolme tutkijaa todettiin, että, jos todella turvallinen salaus on mahdollista, niin jokaisen NP:n ongelman ratkaisu voidaan todistaa myös nollatietotodistuksella. Tämä tutkimus auttoi tutkijoita kuvitella muunnelmia nollatietotodistuksista, jotka eivät edes vaadi turvallista salausta; nämä tunnetaan usean todistajan interaktiivisina todisteina.
Ja vuonna 1988 Micali ja muut osoittivat että jos todistaja ja todentaja jakavat lyhyen satunnaisten bittien jonon, vuorovaikutusta ei tarvita. Tämä teoriassa tarkoitti, että nollatietotodisteiden ei tarvitse olla vuorovaikutteisia, mikä merkitsisi sitä, että jatkuva kommunikointi kahden osapuolen välillä ei ole välttämätöntä. Tämä tekisi niistä paljon hyödyllisempiä tutkijoille, mutta vasta 21-luvun vaihteen jälkeen tällaiset todisteet lähtivät liikkeelle.
"2000-luvun lopulla aloimme nähdä tehokkaiden tekniikoiden kehitystä nollatietotodisteiden rakentamiseen", sanoi Matthew D. Green, kryptografi John Hopkinsin yliopistossa. "Pääsimme siihen pisteeseen, että tajusimme: "Odota hetki, saattaa olla olemassa tapa käyttää tätä käytännössä.""
Nyt todistaja voisi lähettää yhden viestin todentajalle ilman, että molempien tarvitsisi olla verkossa, ja tutkijat voisivat luoda erittäin lyhyen todisteen, joka voidaan nopeasti todentaa jopa erittäin monimutkaisissa ongelmissa. Tämä on johtanut useisiin käytännön käyttötarkoituksiin, kuten kykyyn tarkistaa lohkoketju nopeasti kryptovaluuttatapahtuman jälkeen ja samalla piilottaa tapahtuman yksityiskohdat. Ja vuonna 2016 ryhmä fyysikoita osoittivat kuinka nollatietotodisteet voivat auttaa ydinaseriisunnassa: Paljastamatta salaisuuksia ydinkärjensä suunnittelusta, maa voi nyt todistaa ydintarkastajille, onko taistelukärki aktiivinen vai ei-aktiivinen.
Viime aikoina kvanttilaskennan kehitys on pakottanut Crépeaun testaamaan aiempia tutkimuksia varmistaakseen, että nollatietoprotokollat ovat edelleen käyttökelpoisia. Vuonna 2021 hän auttoi osoittaa että usean kokeen vuorovaikutteiset todistukset säilyttävät salaisuutensa myös kvanttitietokoneiden ollessa mukana, mutta saman suojaustason saavuttaminen hidastaa protokollaa paljon. Löytö oli hyvä uutinen, hän sanoi, mutta uusia huolenaiheita syntyy tekniikan kehittyessä.
"Kaikki laskennat, joita voimme tehdä tulevaisuudessa, sisältävät kvanttitietokoneita", sanoi Crépeau. "Joten hyvänä vainoharhaisena kryptografina, kun arvioimme järjestelmän turvallisuutta, haluamme varmistaa, että järjestelmämme on turvallinen."
Toimittajan huomautus: Shafi Goldwasser on saanut rahoitusta Simons Foundationilta, joka myös rahoittaa tätä toimituksellisesti riippumaton julkaisu. Simons Foundationin rahoituspäätökset eivät vaikuta kattavuuteemme.
