Kujutage ette, et teil on kasulikke teadmisi – võib-olla salaretsept või šifri võti. Kas saaksite tõestada sõbrale, et teil on need teadmised, ilma selle kohta midagi avaldamata? Arvutiteadlased tõestasid üle 30 aasta tagasi, et see on võimalik, kui kasutaksite nn nullteadmiste tõestust.
Selle idee lihtsaks mõistmiseks oletame, et soovite oma sõbrale näidata, et teate, kuidas labürindist läbida, ilma tee kohta üksikasju avaldamata. Sa võisid lihtsalt aja jooksul labürindist läbida, samal ajal kui teie sõbral oli keelatud vaadata. (Ajapiirang on vajalik, sest piisavalt aega saab igaüks katse-eksituse meetodil lõpuks väljapääsu leida.) Teie sõber teaks, et saate seda teha, kuid ta ei tea, kuidas.
Nullteadmiste tõestused on abiks krüptograafidele, kes töötavad salajase teabega, aga ka arvutusliku keerukuse uurijatele, kes tegelevad erinevate probleemide raskusastme klassifitseerimisega. "Paljud kaasaegsed krüptograafiad toetuvad keerukuse eeldustele - eeldusele, et teatud probleeme on raske lahendada, nii et kahe maailma vahel on alati olnud mingid seosed," ütles ta. Claude Crépeau, McGilli ülikooli arvutiteadlane. "Kuid [need] tõendid on loonud kogu ühenduse."
Nullteadmiste tõestused kuuluvad kategooriasse, mida nimetatakse interaktiivseteks tõestusteks, nii et esimese toimimise õppimiseks aitab see teist mõista. Esiteks kirjeldatud arvutiteadlaste 1985. aasta artiklis Shafi Goldwasser, Silvio Micali ja Charles Rackoff, interaktiivsed tõestused toimivad nagu ülekuulamine: Sõnumite seeria jooksul püüab üks osapool (tõestaja) teist (tõendajat) veenda, et antud väide on tõene. Interaktiivne tõestus peab vastama kahele omadusele. Esiteks veenab tõene väide alati ausat kontrollijat. Teiseks, kui antud väide on vale, ei suuda ükski tõestaja – isegi see, kes teeskleb teatud teadmiste omamist – tõendajat veenda, välja arvatud tühise tõenäosusega.
Interaktiivsed tõestused on oma olemuselt tõenäosuslikud. Tõestaja oskas ühele või kahele küsimusele õigesti vastata lihtsalt õnne tõttu, seega on vaja piisavalt palju väljakutseid, mis kõik peavad olema õigesti lahendatud, et tõendaja saaks veenduda, et tõestaja teab väite tõesust.
See interaktsiooniidee tekkis siis, kui Micali ja Goldwasser – tollal California ülikooli Berkeley magistrandid – mõtlesid võrgus pokkeri mängimise logistikasse. Kuidas saavad kõik mängijad kontrollida, et kui üks neist saab virtuaalsest kaardipakist kaardi, on tulemus juhuslik? Interaktiivsed tõendid võiksid juhatada. Aga kuidas saavad mängijad kontrollida, kas kogu protokolli – reeglite kogumit – järgiti õigesti, ilma et oleks paljastatud iga mängija käsi?
Selle eesmärgi saavutamiseks lisasid Micali ja Goldwasser kahele interaktiivse tõestuse jaoks vajalikule omadusele kolmanda: tõestus ei tohiks avaldada midagi teadmiste enda kohta, vaid ainult väite tõepärasust. "Seal on ettekujutus protokolli läbimisest, mille lõpus te arvate, et [pokkerimängijad] ei tea midagi enamat, kui nad peaksid teadma," ütles Goldwasser.
Vaatleme klassikalist näidet. Alice tahab Bobile tõestada, et teatud graafik G - ainulaadne tippude (punktide) kogum, mis on ühendatud servade (joontega) - sellel on "Hamiltoni tsükkel". See tähendab, et graafikul on tee, mis külastab iga punkti täpselt üks kord ja lõpeb sama punktiga, millest see algas. Alice saaks seda teha, näidates Bobile lihtsalt teed, mis seda teeb, kuid loomulikult teaks ka tema seda teed.
Siit saate teada, kuidas Alice saab Bobi veenda, et ta teab, et selline tee on olemas, ilma seda talle näitamata. Kõigepealt joonistab ta uue graafiku, H, see ei paista välja G kuid on olulisel viisil sarnane: sellel on sama arv tippe, mis on ühendatud samal viisil. (Kui G on tõesti Hamiltoni tsükkel, tähendab see sarnasus H ka.) Seejärel, pärast iga serva katmist H maalriteibiga ta lukustab H kasti ja annab kasti Bobile. See takistab tal seda otse nägemast, kuid takistab teda ka seda muutmast. Seejärel teeb Bob valiku: kas ta võib paluda Alice'il seda näidata H on tõesti sarnane Gvõi paluda tal näidata talle Hamiltoni tsüklit H. Eeldusel, et mõlemad taotlused peaksid olema Alice'i jaoks lihtsad H on tõesti piisavalt sarnane Gja et ta tõesti teab seda teed.
Muidugi, isegi kui Alice ei tea Hamiltoni tsüklit G, võib ta proovida Bobi petta, joonistades graafikuid, mis pole sarnased G, või esitades graafikud, mille teed ta ei tea. Kuid pärast seda, kui nad on mänginud mitu vooru, muutub Alice'i võimalus Bobi iga kord petta kaduvalt väikeseks. Kui ta saab kõik õigesti, on Bob lõpuks veendunud, et Alice teab graafikus Hamiltoni tsüklit G, ilma et Bob oleks seda kunagi näinud.
Pärast esialgset dokumenti, mis kirjeldas selliseid tõestusi, avastasid Micali ja kaks matemaatikut – Oded Goldreich ja Avi Wigderson – ootamatu tagajärje, millel on kaugeleulatuvad mõjud. See on seotud peaaegu võrdse raskusastmega probleemide peamise kategooriaga, mida nimetatakse NP-ks. Neid probleeme on raske lahendada, kuid nende lahendusi on lihtne kontrollida. Kolm teadlast leidis, et, kui see on tõeliselt turvaline krüptimine on võimalik, siis saab NP iga ülesande lahenduse tõestada ka nullteadmiste tõestusega. See uuring aitas teadlasi ette kujutada nullteadmiste tõestuste variandid, mis ei nõua isegi turvalist krüpteerimist; neid tuntakse mitme prooviga interaktiivsete tõestustena.
Ja 1988. aastal Micali jt näitas et kui tõestaja ja kontrollija jagavad lühikest juhuslike bittide jada, ei ole interaktsioon vajalik. See tähendas teoreetiliselt, et nullteadmiste tõestused ei pea olema interaktiivsed, mis tähendaks, et pidev suhtlus kahe osapoole vahel pole vajalik. See muudaks need uurijatele palju kasulikumaks, kuid sellised tõendid said hoo sisse alles pärast 21. sajandi vahetust.
"2000. aastate lõpus hakkasime nägema tõhusate tehnoloogiate arengut nullteadmiste tõendite loomiseks," ütles Matthew D. Green, John Hopkinsi ülikooli krüptograaf. "Jõudsime selleni, et mõistsime: "Oodake, võib-olla on võimalus seda praktikas kasutada.""
Nüüd võib tõestaja saata kontrollijale ühe sõnumi, ilma et mõlemad oleksid võrgus, ja teadlased saaksid luua väga lühikese tõendi, mida saab kiiresti kontrollida isegi väga keeruliste probleemide korral. See on toonud kaasa mitmeid praktilisi kasutusvõimalusi, näiteks võimaluse pärast krüptovaluutatehingut kiiresti plokiahelat kontrollida, varjates samal ajal tehingu üksikasju. Ja 2016. aastal füüsikute rühm näitas kuidas nullteadmiste tõendid võivad tuumadesarmeerimisel aidata: ilma tuumalõhkepea konstruktsiooni saladust avaldamata võib riik nüüd tuumainspektoritele tõestada, kas lõhkepea on aktiivne või passiivne.
Hiljuti on kvantarvutuse edusammud sundinud Crépeaud varasemaid uuringuid stressitestima, et veenduda, et nullteadmiste protokollid on endiselt elujõulised. 2021. aastal aitas ta näitama et mitme prooviga interaktiivsed tõestused säilitavad oma saladuse isegi kvantarvutite korral, kuid sama turvataseme saavutamine muudab protokolli palju aeglasemaks. Ta ütles, et leid oli hea uudis, kuid tehnoloogia arenedes tekivad uued mured.
"Iga tüüpi arvutus, mida me tulevikus teha võime, hõlmab kvantarvuteid, " ütles Crépeau. "Nii et heade paranoiliste krüptograafidena tahame süsteemi turvalisust hinnates olla kindlad, et meie süsteem on ohutu."
Toimetaja märkus: Shafi Goldwasser on saanud raha Simonsi fondilt, mis seda ka rahastab toimetuse poolest sõltumatu väljaanne. Simonsi fondi rahastamisotsused ei mõjuta meie katvust.
