Zéró tudásbizonyítás - Zero-knowledge proof

A kriptográfiában a nulla tudás bizonyítás vagy nulla tudás protokoll olyan módszer, amellyel az egyik fél (a bizonyító) bizonyítani tudja egy másik félnek (a hitelesítőnek), hogy egy adott állítás igaz, anélkül, hogy bármilyen információt továbbítana azon kívül, hogy a az állítás valóban igaz. A nulla tudású bizonyítások lényege az, hogy triviális annak bizonyítása, hogy valaki rendelkezik bizonyos információk ismeretével, egyszerűen felfedve azokat; a kihívás az ilyen birtoklás bizonyítása anélkül, hogy magára az információra vagy bármilyen további információra fény derülne.

Ha egy állítás bizonyítása megköveteli, hogy a hitelesítő rendelkezzen valamilyen titkos információval, akkor a hitelesítő nem fogja tudni bizonyítani az állítást senki másnak a titkos információ birtokában. A bizonyítandó állításnak tartalmaznia kell azt az állítást, hogy a hitelesítő rendelkezik ilyen ismeretekkel, de anélkül, hogy magába foglalná vagy továbbadná az állítást. Ellenkező esetben az állítás nem lenne nulla tudással bizonyítva, mert a protokoll végéig további információkat szolgáltat a hitelesítőnek az állításról. A tudás zéró bizonyítéka különleges eset, amikor a nyilatkozat csak abból áll , hogy a hitelesítő rendelkezik a titkos információval.

Az interaktív, nulla tudású bizonyítások megkövetelik a tudásukat bizonyító egyén (vagy számítógépes rendszer) és a bizonyítást érvényesítő személy közötti interakciót.

A zéró tudás nélküli bizonyítékokat megvalósító protokollhoz szükségszerűen interaktív bevitelt kell igényelnie a hitelesítőnek. Ez az interaktív bemenet általában formájában egy vagy több olyan kihívásokra, mint, hogy a válaszok a prover fogja győzni a hitelesítő akkor és csak akkor, ha az állítás igaz, vagyis, ha a prover nem rendelkezik az igényelt tudás. Ha ez nem így lenne, a hitelesítő rögzítheti a protokoll végrehajtását, és újrajátszhatja, hogy meggyőzze valaki mást arról, hogy rendelkezik a titkos információval. Az új párt elfogadás vagy indokolt, mivel a visszajátszás nem rendelkezik az információ (ami azt jelenti, hogy a protokoll kiszivárgott információk, és így nem bizonyított zero-knowledge), vagy az elfogadás hamis, azaz elfogadták valaki, aki nem valóban birtokolja az információt.

A nem interaktív nulla tudás bizonyítékok bizonyos formái léteznek, de a bizonyítás érvényessége számítási feltevésekre támaszkodik (jellemzően egy ideális kriptográfiai hash függvény feltételezései ).

Absztrakt példák

Peggy véletlenszerűen az A vagy B utat választja, míg Victor kint vár

Victor a kilépési utat választja

Peggy megbízhatóan megjelenik a kilépési Victor neveknél

Ali Baba barlang

Van egy jól ismert történet, amely bemutatja a nulla tudás bizonyításának alapvető elképzeléseit, amelyet először Jean-Jacques Quisquater és mások publikáltak a "Hogyan magyarázzam el a nulla tudás jegyzőkönyveit gyermekeinek" című dokumentumukban. Általánosan elterjedt gyakorlat, hogy a két felet nulla tudású bizonyításban Peggy ( a kijelentés bizonyítója) és Victor ( a nyilatkozat hitelesítője ) címkével látják el .

Ebben a történetben Peggy felfedte azt a titkos szót, amellyel varázslatos ajtót nyitnak egy barlangban. A barlang gyűrű alakú, egyik oldalán a bejárattal, a másik oldalon pedig a varázslatos ajtóval. Victor tudni akarja, hogy Peggy ismeri -e a titkos szót; de Peggy, mivel nagyon magánember, nem akarja felfedni tudását (a titkos szót) Victor előtt, vagy általában elárulni a tudása tényét a világ előtt.

Az A és B bejárat felől a bal és jobb utat jelölik. Először Victor a barlangon kívül várakozik, amikor Peggy belép. Peggy vagy az A, akár a B utat választja; Victor nem láthatja, hogy melyik utat választja. Ekkor Victor belép a barlangba, és elkiáltja annak az útnak a nevét, amelyet szeretne, hogy a véletlenszerűen kiválasztott A vagy B útra térjen vissza. Feltéve, hogy valóban ismeri a varázsszót, ez könnyű: szükség esetén kinyitja az ajtót, és visszatér a kívánt úton.

Tegyük fel azonban, hogy nem ismerte a szót. Ekkor csak akkor térhet vissza a megnevezett úton, ha Victor ugyanazon út nevét adja meg, amelyen belépett. Mivel Victor véletlenszerűen választotta az A -t vagy a B -t, 50% esélye lenne a helyes találgatásra. Ha sokszor megismétlik ezt a trükköt, mondjuk 20 -szor egymás után, akkor az esélye, hogy sikeresen előre látja Victor összes kérését, eltűnően kicsi lesz (körülbelül egy a millióból).

Így ha Peggy többször megjelenik a kijáratnál Victor neveknél, arra a következtetésre juthat, hogy rendkívül valószínű, hogy Peggy valóban ismeri a titkos szót.

Egy mellékes megjegyzés a harmadik féltől származó megfigyelőkhöz: még akkor is, ha Victor rejtett kamerát visel, amely rögzíti az egész tranzakciót, az egyetlen dolog, amit a kamera rögzít, az az egyik esetben, hogy Victor „A!” Kiált. és Peggy megjelenik A -n, vagy a másik esetben Victor "B!" és Peggy megjelent B. -nél. Egy ilyen típusú felvétel triviális lenne, ha két ember hamisítana (csak annyit kell tennie, hogy Peggy és Victor előzetesen megállapodnak az A és B sorrendben, amelyet Victor kiáltani fog). Egy ilyen felvétel minden bizonnyal soha nem lesz meggyőző senkinek, kivéve az eredeti résztvevőket. Valójában még az a személy sem lenne meggyőződve, aki megfigyelőként jelen volt az eredeti kísérletben , mivel Victor és Peggy levezényelhette az egész "kísérletet" az elejétől a végéig.

Felhívjuk továbbá a figyelmet arra, hogy ha Victor úgy dönt, hogy A-ját és B-jét egy érmét forgatja a kamerán, akkor ez a protokoll elveszíti zéró tudású tulajdonságát; a fényképezőgépen levő érmefordítás valószínűleg meggyőző lenne minden olyan személy számára, aki később nézi a felvételt. Így bár ez nem árulja el Victor számára a titkos szót, lehetővé teszi, hogy Victor meggyőzze a világot általában arról, hogy Peggy rendelkezik ezzel a tudással - ellentétben Peggy megfogalmazott kívánságaival. A digitális kriptográfia azonban általában "felforgatja az érméket" egy ál-véletlenszám-generátorra támaszkodva, amely egy olyan érméhez hasonlít, amelynek fej- és farokmintája csak az érme tulajdonosa számára ismert. Ha Victor érme így viselkedne, akkor ismét lehetséges lenne, hogy Victor és Peggy hamisítsák a "kísérletet", így egy ál-véletlenszám-generátor használata nem fedné fel Peggy tudását a világnak ugyanúgy, mint egy feldobott érme használatával. megtenné.

Figyeljük meg, hogy Peggy egyetlen tárgyalás során be tudja bizonyítani Victornak, hogy ismeri a varázsszót, anélkül, hogy felfedné neki. Ha Victor és Peggy is együtt mennek a barlang torkolatához, Victor nézheti, ahogy Peggy belép A -n, és kijön B. -n keresztül. Ez biztosan bizonyítaná, hogy Peggy ismeri a varázsszót, anélkül, hogy felfedné a varázsszót Victornak. Az ilyen bizonyítékot azonban harmadik fél is megfigyelheti, vagy Victor rögzítheti, és ez a bizonyíték meggyőző bárki számára. Más szavakkal, Peggy nem tudta megcáfolni az ilyen bizonyítást azzal, hogy azt állította, hogy összejátszott Victorral, és ezért már nem tudja irányítani, hogy ki van tudatában tudásának.

Két golyó és a színvak barát

Képzeld el, hogy a barátod vörös-zöld színvak (míg te nem), és két golyód van: egy piros és egy zöld, de egyébként azonos. A barátod számára teljesen azonosnak tűnik, és szkeptikus, hogy valóban megkülönböztethetők. Be akarod bizonyítani neki, hogy valójában más színűek , de semmi más; különösen nem akarja felfedni, melyik a piros és melyik a zöld golyó.

Itt a bizonyítási rendszer. A két golyót odaadod a barátodnak, ő pedig a háta mögé teszi. Ezután előveszi az egyik golyót, előhozza a háta mögül, és megjeleníti. Ezután ismét a háta mögé helyezi, majd úgy dönt, hogy a két golyó közül csak az egyiket tárja fel, és véletlenszerűen kiválasztja a kettő közül az egyiket, azonos valószínűséggel. Majd megkérdezi: "Én váltottam a labdát?" Ezt az egész eljárást ezután megismétlik, ahányszor szükséges.

Ha megnézzük a színeiket, akkor természetesen biztosan megmondhatja, hogy ő váltotta -e őket vagy sem. Másrészt, ha azonos színűek és így megkülönböztethetetlenek, akkor semmiképpen sem lehet helyesen kitalálni 50%-nál nagyobb valószínűséggel.

Mivel annak a valószínűsége, hogy véletlenszerűen sikerült azonosítania minden kapcsolót/nem kapcsolót, 50%, a valószínűsége annak, hogy minden kapcsoló/nem kapcsoló véletlenszerűen sikeres lesz, megközelíti a nullát ("megbízhatóság"). Ha Ön és barátja többször megismétli ezt a "bizonyítást" (pl. 100 -szor), akkor a barátjának meg kell győződnie arról ("teljesség"), hogy a golyók valóban különböző színűek.

A fenti bizonyíték nulla tudás, mert a barátod soha nem tanulja meg, melyik golyó zöld és melyik piros; valójában nem szerzett tudomást a golyók megkülönböztetéséről.

Hol van Wally?

Hol van Wally? (címmel Hol Waldo? ben Észak-Amerikában ) egy képeskönyv, ahol az olvasó megtámadta találni egy kis karakter neve Wally rejtett valahol a kettős spread oldal, ami tele van sok más karakter. A képeket úgy tervezték, hogy nehéz megtalálni Wally -t.

Képzeld el, hogy profi vagy Hol van Wally? megoldó. Egy társaság hol van Wallyval? könyv, amelyet meg kell oldani. A cég azt akarja, hogy bizonyítsa be, hogy valóban profi Hol van Wally? megoldó, és ezért arra kéri, hogy találja meg Wallyt a könyvükben található képen. A probléma az, hogy nem akarsz helyettük munkát végezni fizetés nélkül.

Ön és a vállalat is együttműködni akar, de nem bíznak egymásban. Úgy tűnik, nem lehet kielégíteni a vállalat igényeit anélkül, hogy ingyenes munkát végeznének helyettük, de valójában létezik egy nulla tudás bizonyíték, amely lehetővé teszi, hogy bebizonyítsa a vállalatnak, hogy tudja, hol van Wally a képen anélkül, hogy elárulta volna hogyan találta meg, vagy hol van.

A bizonyítás a következő: Megkérem a cég képviselőjét, hogy forduljon meg, majd egy nagyon nagy kartonlapot helyez a képre úgy, hogy a karton közepe Wally fölé kerüljön. Kivágtál egy kis ablakot a karton közepén, hogy Wally látható legyen. Most megkérheti a cég képviselőjét, hogy forduljon meg, és tekintse meg a nagy kartonlapot, amelynek közepén lyuk van, és figyelje meg, hogy Wally látható a lyukon keresztül. A karton elég nagy ahhoz, hogy ne tudják meghatározni a könyv helyzetét a karton alatt. Ezután megkérheti a képviselőt, hogy forduljon vissza, hogy eltávolíthassa a kartont és visszaadhassa a könyvet.

A leírtak szerint ez a bizonyítás csak illusztráció, és nem teljesen szigorú. A cég képviselőjének biztosnak kell lennie abban, hogy nem csempészett be Wally képét a szobába. Szigorúbb bizonyításhoz valami szabotázsálló kesztyűtartót használhat. A fenti bizonyíték azt is eredményezi, hogy Wally testhelyzetét kiszivárogtatják a cég képviselőjének, ami segíthet megtalálni Wally -t, ha a testhelyzete megváltozik mindenhol Hol van Wally? kirakós játék.

Meghatározás

A nulla tudású bizonyításnak három tulajdonságnak kell megfelelnie:

Teljesség : ha az állítás igaz, akkor a becsületes hitelesítőt (vagyis a protokoll megfelelő betartóját) erről a tényről egy őszinte bizonyító fogja meggyőzni.
Épesség : ha az állítás hamis, egyetlen csaló bizonyíték sem tudja meggyőzni a becsületes hitelesítőt, hogy igaz, csak kis valószínűséggel.
Nulla tudás : ha az állítás igaz, egyetlen hitelesítő sem tanul mást, mint azt, hogy az állítás igaz. Más szóval, pusztán az állítás ismerete (nem a titok) elegendő ahhoz, hogy elképzeljünk egy forgatókönyvet, amely azt mutatja, hogy a bizonyító tudja a titkot. Ezt úgy formalizálják, hogy megmutatják, hogy minden hitelesítőnek van valamilyen szimulátora, amely csak a bizonyítandó állításra tekintettel (és a hozzáféréshez nem fér hozzá) képes olyan átiratot előállítani, amely "úgy néz ki", mint a kölcsönhatás a becsületes bizonyító és a kérdéses hitelesítő között.

Ezek közül az első kettő az általánosabb interaktív bizonyítási rendszerek tulajdonságai . A harmadik az, ami a bizonyítást nulla tudássá teszi.

A nulla tudás bizonyításai nem bizonyítékok a szó matematikai értelmében, mert kicsi a valószínűsége, a megalapozottsági hiba , hogy egy csaló bizonyító képes meggyőzni a hitelesítőt egy hamis állításról. Más szóval, a nulla tudású bizonyítások inkább valószínűségi "bizonyítékok", mint determinisztikus bizonyítékok. Vannak azonban olyan technikák, amelyekkel a hangzási hiba elhanyagolhatóan kis értékekre csökken.

A nulla tudás formális meghatározásához valamilyen számítási modellt kell használni, a leggyakoribb a Turing-gép . Legyen ,, és legyen Turing -gép. Egy interaktív bizonyítási rendszer a program olyan nyelvi nulla tudás ha bármilyen valószínűségi polinomiális (PPT) hitelesítő létezik egy PPT-szimulátor , hogy ${\ displaystyle P}$ ${\ displaystyle V}$ ${\ displaystyle S}$ ${\ displaystyle (P, V)}$ ${\ displaystyle L}$ ${\ displaystyle {\ hat {V}}}$ ${\ displaystyle S}$

{\ displaystyle \ forall x \ in L, z \ in \ {0,1 \}^{*}, \ operatorname {View} _ {\ hat {V}} \ left [P (x) \ leftrightarrow {\ hat {V}} (x, z) \ jobb] = S (x, z)}

ahol egy rekord közötti kölcsönhatások és . A próbatestet korlátlan számítási képességgel modellezik (a gyakorlatban általában egy valószínűségi Turing -gép ). Intuitív módon a definíció kimondja, hogy az interaktív bizonyítási rendszer nulla tudású, ha bármely hitelesítő számára létezik egy hatékony szimulátor (attól függően ), amely képes reprodukálni a beszélgetést és az adott bemenetet. A definícióban szereplő segédlánc az "előzetes tudás" szerepét tölti be (beleértve a véletlenszerű érméket is ). A definíció azt sugallja, hogy semmilyen előzetes tudássorozatot nem használhat fel az információk kibontására a vele folytatott beszélgetésből , mert ha ezt az előzetes tudást is megkapja, akkor képes reprodukálni a beszélgetést és a korábbi módon. ${\ displaystyle \ operatorname {Nézet} _ {\ kalap {V}} \ bal [P (x) \ leftrightarrow {\ hat {V}} (x, z) \ right]}$ ${\ displaystyle P (x)}$ ${\ displaystyle {\ hat {V}} (x, z)}$ ${\ displaystyle P}$ ${\ displaystyle P}$ ${\ displaystyle (P, V)}$ ${\ displaystyle {\ hat {V}}}$ ${\ displaystyle S}$ ${\ displaystyle {\ hat {V}}}$ ${\ displaystyle P}$ ${\ displaystyle {\ hat {V}}}$ ${\ displaystyle z}$ ${\ displaystyle {\ hat {V}}}$ ${\ displaystyle {\ hat {V}}}$ ${\ displaystyle z}$ ${\ displaystyle P}$ ${\ displaystyle S}$ ${\ displaystyle {\ hat {V}}}$ ${\ displaystyle P}$

A megadott definíció a tökéletes nulla tudás. A számítási nulla tudást úgy kapjuk meg, hogy megköveteljük, hogy a hitelesítő és a szimulátor nézetei csak számításilag megkülönböztethetők legyenek , tekintettel a segédláncra. ${\ displaystyle {\ hat {V}}}$

Gyakorlati példák

Adott érték diszkrét naplója

Ezeket az ötleteket egy reálisabb kriptográfiai alkalmazáshoz is alkalmazhatjuk. Peggy be akarja bizonyítani Victornak, hogy ismeri az adott csoport diszkrét naplóját .

Például, ha adott egy érték , egy nagy prímszám és egy generátor , be akarja bizonyítani, hogy ismer olyan értéket , amely anélkül, hogy felfedné . Valójában a tudás felhasználható a személyazonosság igazolására, mivel Peggy rendelkezhet ilyen ismeretekkel, mert véletlenszerű értéket választott , amelyet nem árult el senkinek, kiszámította és kiosztotta minden lehetséges hitelesítőnek az értékét. később a tudás igazolása egyenértékű a Peggyként való személyazonosság bizonyításával. ${\ displaystyle y}$ ${\ displaystyle p}$ ${\ displaystyle g}$ ${\ displaystyle x}$ ${\ displaystyle g^{x} {\ bmod {p}} = y}$ ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle y = g^{x} {\ bmod {p}}}$ ${\ displaystyle y}$ ${\ displaystyle x}$

A protokoll a következőképpen halad: Peggy minden körben véletlenszerű számot generál , kiszámítja és közzéteszi Victornak. Miután megkapta , Victor véletlenszerűen ad ki egyet a következő két kérés közül: vagy azt kéri, hogy Peggy tegye közzé a (z ) vagy a (z) értékét . Bármelyik válasz esetén Peggy csak véletlenszerű értéket közöl, így a protokoll egy fordulójának helyes végrehajtásával semmilyen információ nem kerül nyilvánosságra. ${\ displaystyle r}$ ${\ displaystyle C = g^{r} {\ bmod {p}}}$ ${\ displaystyle C}$ ${\ displaystyle r}$ ${\ displaystyle (x+r) {\ bmod {(p-1)}}}$

Victor ellenőrizheti bármelyik választ; ha kérte , akkor kiszámíthatja és ellenőrizheti, hogy megfelel -e . Ha kéri , akkor ellenőrizheti, hogy összhangban van -e ezzel, kiszámítva és ellenőrizve, hogy megfelel -e . Ha Peggy valóban ismeri az értékét , válaszolhat Victor egyik lehetséges kihívására. ${\ displaystyle r}$ ${\ displaystyle g^{r} {\ bmod {p}}}$ ${\ displaystyle C}$ ${\ displaystyle (x+r) {\ bmod {(p-1)}}}$ ${\ displaystyle C}$ ${\ displaystyle g^{(x+r) {\ bmod {(p-1)}}} {\ bmod {p}}}$ ${\ displaystyle C \ cdot y {\ bmod {p}}}$ ${\ displaystyle x}$

Ha Peggy tudta volna vagy sejtette volna, hogy Victor milyen kihívást fog küldeni, akkor könnyen megcsalhatja és meggyőzheti Victort arról, hogy tudja, amikor nem: ha tudja, hogy Victor kérni fogja , akkor normálisan jár el: válogat , számol és felfedi Victornak; képes lesz válaszolni Victor kihívására. Másrészt, ha tudja, hogy Victor kérni fogja , akkor kiválaszt egy véletlenszerű értéket , kiszámítja és közzéteszi Victornak azt az értéket, amelyet elvár. Amikor Victor vitatja neki, hogy felfedje , feltárja , melyek Victor ellenőrzi következetesség, hiszen ő viszont számítási , amely mérkőzést , mivel Peggy szorozva a moduláris reciprok az . ${\ displaystyle x}$ ${\ displaystyle r}$ ${\ displaystyle r}$ ${\ displaystyle C = g^{r} {\ bmod {p}}}$ ${\ displaystyle C}$ ${\ displaystyle (x+r) {\ bmod {(p-1)}}}$ ${\ displaystyle r '}$ ${\ displaystyle C '= g^{r'} \ cdot \ left (g^{x} \ right)^{-1} {\ bmod {p}}}$ ${\ displaystyle C '}$ ${\ displaystyle C}$ ${\ displaystyle (x+r) {\ bmod {(p-1)}}}$ ${\ displaystyle r '}$ ${\ displaystyle g^{r '} {\ bmod {p}}}$ ${\ displaystyle C '\ cdot y}$ ${\ displaystyle y}$

Ha azonban a fenti forgatókönyvek bármelyikében Victor más kihívást állít elő, mint amire számított, és amelyre az eredményt készítette, akkor nem tud válaszolni a kihívásra, feltételezve, hogy a diszkrét napló megoldása nem lehetséges ez a csoport. Ha ő választja és nyilvánosságra hozza , akkor nem tud olyan igazolványt bemutatni , amely átmenne Victor ellenőrzésén, mivel nem tudja . Ha pedig olyan értéket választana , amely így jelenik meg , akkor az általa közölt érték diszkrét naplójával kell válaszolnia - de Peggy nem ismeri ezt a diszkrét naplót, mivel az általa közölt C értéket ismert értékekkel rendelkező számtani módszerrel szerezték meg, és nem úgy, hogy egy ismert kitevővel kiszámítjuk a teljesítményt. ${\ displaystyle r}$ ${\ displaystyle C = g^{r} {\ bmod {p}}}$ ${\ displaystyle (x+r) {\ bmod {(p-1)}}}$ ${\ displaystyle x}$ ${\ displaystyle r '}$ ${\ displaystyle (x+r) {\ bmod {(p-1)}}}$

Így egy csaló bizonyítónak 0,5 valószínűsége van, hogy sikeresen csal egy körben. Elég nagy számú kör végrehajtásával önkényesen alacsonyra tehető a csaló bizonyító sikerének valószínűsége.

Rövid összefoglaló

Peggy bizonyítja, hogy ismeri x értékét (például a jelszavát).

Peggy és Victor megegyeznek a mező multiplikatív csoportjának prímszámában és generátorában . ${\ displaystyle p}$ ${\ displaystyle g}$ ${\ displaystyle \ mathbb {Z} _ {p}}$
Peggy kiszámítja az értéket, és átadja Victornak. ${\ displaystyle y = g^{x} {\ bmod {p}}}$
A következő két lépést (nagy) számú alkalommal megismételjük.
1. Peggy többször kiválaszt egy véletlenszerű értéket, és kiszámítja . Átadja az értéket Victornak. ${\ displaystyle r \ in U [0, p-1]}$ ${\ displaystyle C = g^{r} {\ bmod {p}}}$ ${\ displaystyle C}$
2. Victor kéri Peggy -t, hogy számítsa ki és vigye át az értéket vagy az értéket . Az első esetben Victor ellenőrzi . A második esetben ellenőrzi . ${\ displaystyle (x+r) {\ bmod {(p-1)}}}$ ${\ displaystyle r}$ ${\ displaystyle (C \ cdot y) {\ bmod {p}} \ equiv g^{(x+r) {\ bmod {(p-1)}}} {\ bmod {p}}}$ ${\ displaystyle C \ equiv g^{r} {\ bmod {p}}}$

Az érték a (z) titkosított értéke . Ha valóban véletlenszerű, egyenlően oszlik el nulla és között , ez nem szivárog ki semmilyen információról (lásd egyszeri lap ). ${\ displaystyle (x+r) {\ bmod {(}} p-1)}$ ${\ displaystyle x {\ bmod {(}} p-1)}$ ${\ displaystyle r}$ ${\ displaystyle (p-1)}$ ${\ displaystyle x}$

Hamilton -ciklus egy nagy gráfhoz

A következő séma Manuel Blumnak köszönhető.

Ebben a forgatókönyvben Peggy ismer egy Hamilton -ciklust egy nagy $G$ grafikonra . Victor ismeri $G-t,$ de nem ismeri a ciklust (pl. Peggy $G-$ t generált, és feltárta neki.) Hamilton-ciklus megtalálása nagy gráf alapján számításilag nem megvalósítható, mivel a megfelelő döntési változata NP-teljes . Peggy bebizonyítja, hogy ismeri a ciklust anélkül, hogy egyszerűen felfedné azt (talán Victor érdeklődik a vásárlás iránt, de először ellenőrzést akar, vagy talán Peggy az egyetlen, aki ismeri ezeket az információkat, és bizonyítja Victor személyazonosságát).

Hogy megmutassa, hogy Peggy ismeri ezt a Hamilton -ciklust, ő és Victor több fordulóban játszanak.

Az elején minden kör, Peggy teremt $H$ gráf, amely izomorf a $G$ (vagyis $H$ éppen olyan, mint $a G$ , kivéve, hogy a csúcsok különböző neveket). Mivel triviális egy ismert izomorfizmussal rendelkező izomorf gráfok között lefordítani egy Hamilton -ciklust, ha Peggy ismeri a $G$ -re vonatkozó Hamilton -ciklust, akkor $H$ -nak is tudnia kell .
Peggy vállalja, hogy $H$ . Ezt egy kriptográfiai elkötelezettségi rendszer segítségével tehette meg . Alternatív tudta számlálni csúcsainak $H$ , akkor minden éle $H$ write egy kis darab papírt tartalmazó két csúcsa a szélén, majd ezeket papírdarabokat lefelé egy asztalra. Ennek az elkötelezettségnek az a célja, hogy Peggy nem képes megváltoztatni $H$ -t, miközben Victornak nincs információja $H$ -ról .
Victor ekkor véletlenszerűen választ egyet a két kérdés közül, amelyeket fel kell tennie Peggynek. Megkérheti, hogy mutassa meg a $H$ és $G$ közötti izomorfizmust (lásd a grafikon izomorfizmus problémáját ), vagy megkérheti, hogy mutasson egy Hamilton -ciklust $H -ban$ .
Ha Peggy kérte, hogy azt mutatják, hogy a két gráf izomorf, ő először feltárja az összes $H$ (pl elforgatásával az összes darab papírt, hogy ő az asztalra), majd megkapjuk a vertex fordítások leképező $G$ a $H$ . Victor ellenőrizheti, hogy valóban izomorf -e.
Ha Peggytől azt kéri, hogy bizonyítsa be, hogy ismeri a Hamilton -ciklust $H -ban$ , akkor lefordítja Hamilton -ciklusát $G$ -ben $H$ -ra, és csak a Hamilton -ciklus éleit fedezi fel. Ez elég ahhoz, hogy Victor ellenőrizze, hogy a $H$ valóban tartalmaz -e Hamilton -ciklust.

Fontos, hogy a gráf iránti elkötelezettség olyan legyen, hogy Victor a második esetben ellenőrizni tudja, hogy a ciklus valóban $H$ -ból származó élekből áll $-e$ . Ezt úgy tehetjük meg, hogy például minden szegélyre (vagy annak hiányára) külön -külön vállalunk.

Teljesség

Ha Peggy nem tudom, egy Hamilton-kör a $G$ , akkor könnyen kielégíteni Victor iránti kereslet akár a gráfizomorfizmus termelő $H$ származó $G$ (amit követtek az első lépés), vagy a Hamilton-kör a $H$ (amit lehet építeni alkalmazásával izomorfizmus a ciklushoz $G$ ).

Nulla tudás

Peggy válaszok nem mutatják az eredeti Hamilton ciklus $G$ . Victor minden körben csak $H$ izomorfizmusát tanulja meg $G$ -ig, vagy egy Hamilton -ciklust $H -ban$ . Mindkét válaszra lenne szüksége ahhoz, hogy egyetlen $H$ felfedezze a ciklust $G$ -ben , így az információ ismeretlen marad mindaddig, amíg Peggy minden körben külön $H$ -t tud generálni . Ha Peggy nem tud Hamilton -ciklusról $G$ -ben , de valahogy előre tudta, mit kér Victor, hogy lásson minden fordulót, akkor csalhat. Például, ha Peggy előre tudta, hogy Victor megkéri a Hamilton -ciklus megtekintését $H -ban,$ akkor létrehozhat egy Hamilton -ciklust egy független gráfhoz. Hasonlóképpen, ha Peggy előre tudta, hogy Victor megkéri az izomorfizmus megtekintését, akkor egyszerűen létrehozhat egy $H$ izomorf gráfot (amelyben szintén nem ismer Hamilton -ciklust). Victor egyedül (Peggy nélkül) szimulálhatná a protokollt, mert tudja, mit fog kérni. Ezért Victor nem szerez információt a Hamilton -ciklusról $G$ -ben az egyes körökben feltárt információkból.

Épesség

Ha Peggy nem ismeri az információt, akkor kitalálja, melyik kérdést teszi fel Victor, és generál egy $G$ -re izomorf gráfot, vagy egy Hamilton -ciklust egy nem kapcsolódó gráfhoz, de mivel nem ismeri a $G$ -hez tartozó Hamilton -ciklust, nem teheti meg mindkettőt. Ezzel a találgatással esélye van arra, hogy becsapja Victort $2 - n$ , ahol $n$ a körök száma. Minden reális célból elképzelhetetlenül nehéz ilyen módon legyőzni egy nulla tudású bizonyítást ésszerű számú körrel.

A nulla tudás változatai

A nulla tudás különböző változatai definiálhatók, ha formális formába öntik, hogy mit jelent a szimulátor kimenete, "úgy néz ki", mint a valódi bizonyítási protokoll végrehajtása a következő módokon:

Tökéletes nulla tudásról beszélünk, ha a szimulátor és a próbaprotokoll által előállított eloszlások pontosan azonosak. Ez a helyzet például a fenti első példában.
A statisztikai nulla tudás azt jelenti, hogy az eloszlások nem feltétlenül egyeznek meg, de statisztikailag közel állnak egymáshoz , vagyis statisztikai különbségük elhanyagolható függvény .
Számítási nulla tudásról beszélünk, ha egyetlen hatékony algoritmus sem képes megkülönböztetni a két eloszlást.

Nulla tudástípus

A tudás bizonyítása : a tudás a kitevőben rejtőzik, mint a fenti példában.
Párosításon alapuló kriptográfia : adott $f (x)$ és $f (y)$ , $x$ és $y$ ismerete nélkül lehetséges $f (x \times y)$ kiszámítása .
Tanú megkülönböztethetetlen bizonyíték : a hitelesítők nem tudhatják, hogy melyik tanút használják a bizonyítás előállításához.
Többpárti számítás : bár minden fél meg tudja őrizni saját titkát, együtt hoznak eredményt.
Csengő aláírás : a kívülállóknak fogalmuk sincs, melyik kulcsot használják az aláíráshoz.

Alkalmazások

Hitelesítő rendszerek

A nulla tudású bizonyításokkal kapcsolatos kutatásokat olyan hitelesítési rendszerek motiválták, amelyekben az egyik fél valamilyen titkos információ (például jelszó) útján be akarja bizonyítani személyazonosságát egy másik félnek, de nem akarja, hogy a második fél bármit is megtudjon erről a titokról. Ezt nevezik " a tudás zéró bizonyítékának ". A jelszó azonban tipikusan túl kicsi vagy nem kellően véletlenszerű ahhoz, hogy sok sémában használhassák a tudás nulla tudásának bizonyítására. A nulla tudású jelszóbiztosítás a zéró tudás bizonyításának egy speciális fajtája, amely a jelszavak korlátozott méretével foglalkozik.

2015 áprilisában bevezették a Sigma protokollt (egy-a-sok bizonyítás). 2021 augusztusában a Cloudflare , egy amerikai webes infrastruktúra- és biztonsági vállalat úgy döntött, hogy az egyetlen bizonyítási mechanizmust használja a magánhálózati hitelesítéshez a gyártó hardverével.

Etikus viselkedés

A kriptográfiai protokollokon belüli nulla tudású bizonyítékok egyik felhasználása az őszinte magatartás kikényszerítése a magánélet megőrzése mellett. Nagyjából az ötlet az, hogy kényszerítsük a felhasználót, hogy nulla tudás bizonyítással bizonyítsa, hogy viselkedése helyes a protokoll szerint. A megalapozottság miatt tudjuk, hogy a felhasználónak valóban őszintén kell cselekednie ahhoz, hogy érvényes bizonyítékot tudjon szolgáltatni. A nulla tudás miatt tudjuk, hogy a felhasználó a bizonyítás benyújtása során nem veszélyezteti titkai titkosságát.

Nukleáris leszerelés

2016 -ban a Princetoni Plazmafizikai Laboratórium és a Princetoni Egyetem olyan technikát mutatott be, amely alkalmazható lehet a jövőbeli nukleáris leszerelési tárgyalásokra. Ez lehetővé tenné az ellenőrök számára, hogy megerősítsék, hogy egy tárgy valóban nukleáris fegyver -e, anélkül, hogy rögzítenék, megosztanák vagy felfednék a titkos belső működést.

Blokkláncok

A Zerocoin és Zerocash protokollokban nulla tudású bizonyítékokat alkalmaztak, amelyek a Zcoin (később Firo - ként 2020-ban átnevezett ) és a Zcash kriptovaluták 2016-os születésével tetőztek. az anonimitás biztosítása érdekében. A felhasználók bázis pénznemben köthetnek tranzakciókat, és válthatják a valutát nulla érmékbe. A Zerocash protokoll hasonló modellt használ (egy nem interaktív zéró tudásbizonyításként ismert változat ), azzal a különbséggel, hogy eltakarja a tranzakció összegét, míg a Zerocoin nem. Tekintettel a tranzakciós adatok jelentős korlátozására a Zerocash hálózaton, a Zerocash kevésbé hajlamos az adatvédelmi időzítési támadásokra, mint a Zerocoin. Ez a további adatvédelmi réteg azonban a Zerocash -kínálat potenciálisan észrevétlen hiperinflációját okozhatja, mivel a csalárd érmék nem követhetők.

2018 -ban vezették be a golyóálló anyagokat. A golyóálló képességek javulást jelentenek a nem interaktív zéró tudásbizonyítékhoz képest, ahol nincs szükség megbízható beállításra. Később beépítették a Mimblewimble protokollba (ahol Grin és Beam kriptovaluták alapulnak) és a Monero kriptovalutába . 2019 -ben a Firo bevezette a Sigma protokollt , ami a Zerocoin protokoll javítása megbízható beállítás nélkül. Ugyanebben az évben a Firo bevezette a Lelantus protokollt, a Sigma protokoll javítását, ahol az előbbi elrejti a tranzakció eredetét és összegét.

Történelem

A nulla tudás bizonyítását először 1985-ben alkották meg Shafi Goldwasser , Silvio Micali és Charles Rackoff "The Knowledge Complexity of Interactive Proof-Systems" című írásában. Ez a tanulmány bemutatta az interaktív bizonyítási rendszerek IP -hierarchiáját ( lásd az interaktív bizonyítási rendszert ), és megalkotta a tudás összetettségének fogalmát , amely a bizonyítóról a bizonyítóról a hitelesítőnek átadott tudás mennyiségét méri. Ők adták az első nulla tudás bizonyítékot is egy konkrét problémára, a másodfokú nemmaradványok mod m eldöntésére . Ez a mérföldkőnek számító papír Babai László és Shlomo Moran dolgozatával együtt interaktív bizonyítási rendszereket talált ki, amelyekért mind az öt szerző 1993 -ban elnyerte az első Gödel -díjat .

Goldwasser, Micali és Rackoff saját szavaival azt mondják:

Különösen érdekes az az eset, amikor ez a kiegészítő tudás lényegében 0, és megmutatjuk, hogy [interaktív módon] be lehet bizonyítani, hogy egy szám másodfokú nem maradék mod m, amely 0 további tudást bocsát ki. Ez meglepő, mivel nem ismert hatékony algoritmus a mod m másodfokú reziduitás eldöntésére, ha m faktorizálása nincs megadva. Ezenkívül a probléma összes ismert NP -bizonyítéka az m elsődleges faktorizációját mutatja . Ez azt jelzi, hogy az interakció hozzáadása a bizonyítási folyamathoz csökkentheti a tudás mennyiségét, amelyet közölni kell a tétel bizonyításához.

A másodfokú nonradidue probléma NP és co-NP algoritmussal is rendelkezik, és így az NP és a co-NP metszéspontjában rejlik . Ez igaz volt számos más problémára is, amelyekre később nulla tudású bizonyítékokat fedeztek fel, például Oded Goldreich kiadatlan bizonyítási rendszerével, amely igazolja, hogy a kétprímú modulus nem Blum egész szám .

Oded Goldreich , Silvio Micali és Avi Wigderson egy lépéssel tovább lépett , és megmutatta, hogy feltéve, hogy megszakíthatatlan titkosítás létezik , három színnel lehet létrehozni egy nulla tudásbiztos rendszert az NP-teljes grafikon színezési problémára . Mivel az NP minden problémája hatékonyan redukálható erre a problémára, ez azt jelenti, hogy e feltételezés szerint az NP minden problémája nulla tudású bizonyítékkal rendelkezik. A feltételezés oka az, hogy a fenti példához hasonlóan protokolljaik titkosítást igényelnek. A megtörhetetlen titkosítás létezésére általánosan hivatkozott elegendő feltétel az egyirányú függvények megléte , de elképzelhető, hogy bizonyos fizikai eszközök is elérhetik azt.

Ezen felül azt is kimutatta, hogy a gráf nonisomorphism probléma , a komplement a gráfizomorfizmus probléma , a zéró tudás bizonyítéka. Ez a probléma a ko-NP-ben van , de jelenleg nem ismert, hogy az NP-ben vagy bármely gyakorlati osztályban szerepel. Általánosabban Russell Impagliazzo és Moti Yung , valamint Ben-Or et al. tovább mutatná, hogy egyirányú függvényeket vagy feltörhetetlen titkosítást is feltételezve, hogy az IP = PSPACE minden problémájára nulla tudás bizonyíték áll rendelkezésre , vagy más szóval, bármi bizonyítható, amit egy interaktív bizonyítási rendszer bizonyíthat nulla tudással.

Mivel nem szeretett felesleges feltételezéseket tenni, sok teoretikus kereste a módját annak, hogy megszüntesse az egyirányú funkciók szükségességét . Ennek egyik módja volt a multi-prover interaktív bizonyítási rendszerek (lásd az interaktív bizonyítási rendszer ) használata, amelyeknek egyetlen független tesztelője van, és nem csak egy, így a hitelesítő elkülönítve „keresztvizsgálja” a bizonyítékokat a félrevezetés elkerülése érdekében. Kimutatható, hogy minden megoldhatatlan feltételezés nélkül az NP minden nyelve rendelkezik nulla tudású bizonyítékokkal egy ilyen rendszerben.

Kiderül, hogy egy internethez hasonló környezetben, ahol több protokoll is végrehajtható egyidejűleg, a nulla tudású bizonyítékok létrehozása nagyobb kihívást jelent. A párhuzamos zéró tudás bizonyításokat vizsgáló kutatások sorát Dwork , Naor és Sahai munkái kezdeményezték . Az egyik ilyen irányú fejlemény a tanúk által megkülönböztethetetlen bizonyítási jegyzőkönyvek kifejlesztése volt . A tanú-megkülönböztethetetlenség tulajdonsága a nulla tudással függ össze, de a tanúk által megkülönböztethetetlen protokollok nem szenvednek ugyanazoktól a párhuzamos végrehajtástól.

A nulla tudás bizonyításainak egy másik változata a nem interaktív nulla tudás bizonyítás . Blum, Feldman és Micali kimutatták, hogy a bizonyító és a hitelesítő között megosztott közös véletlen karakterlánc elegendő a számítási nulla tudás eléréséhez anélkül, hogy kölcsönhatásra lenne szükség.

Zéró tudást bizonyító protokollok

A legnépszerűbb interaktív vagy nem interaktív, nulla tudást bizonyító protokollokat nagyjából a következő négy kategóriába sorolhatjuk: A tudás tömör, nem interaktív érvei (SNARK), a skálázható átlátható tudás argumentuma (STARK), ellenőrizhető polinomiális delegáció (VPD), és tömör, nem interaktív ARGuments (SNARG). Az alábbiakban felsoroljuk a nulla tudást bizonyító protokollokat és könyvtárakat, valamint az átláthatóságon , az egyetemességen , a kvantum utáni rugalmasságon és a programozási paradigmán alapuló összehasonlításokat . Az Transparent olyan protokoll, amely nem igényel megbízható telepítést, és nyilvános véletlenszerűséget használ. Az Universal olyan protokoll, amely nem programspecifikus, és nem igényel új beállítást minden egyes áramkör számára. Végül, a kvantum utáni rugalmasság egy olyan protokoll, amely nem érzékeny a nagyméretű kvantumszámítógépek által ismert támadásokra.

Zéró tudásbiztos (ZKP) rendszerek
ZKP rendszer	Jegyzőkönyv	Átlátszó	Egyetemes	Kvantum utáni rugalmas	Programozási paradigma
Pinocchio	zk-SNARK	Nem	Nem	Nem	Eljárási
Geppetto	zk-SNARK	Nem	Nem	Nem	Eljárási
TinyRAM	zk-SNARK	Nem	Nem	Nem	Eljárási
Büfé	zk-SNARK	Nem	Nem	Nem	Eljárási
ZoKrates	zk-SNARK	Nem	Nem	Nem	Eljárási
xJsnark	zk-SNARK	Nem	Nem	Nem	Eljárási
vRAM	zk-SNARG	Nem	Igen	Nem	Összeszerelés
vnTinyRAM	zk-SNARK	Nem	Igen	Nem	Eljárási
DÉLIBÁB	zk-SNARK	Nem	Igen	Nem	Aritmetikai áramkörök
Szonikus	zk-SNARK	Nem	Igen	Nem	Aritmetikai áramkörök
Marlin	zk-SNARK	Nem	Igen	Nem	Aritmetikai áramkörök
PLONK	zk-SNARK	Nem	Igen	Nem	Aritmetikai áramkörök
Szuperszonikus	zk-SNARK	Igen	Igen	Nem	Aritmetikai áramkörök
Golyóálló	Golyóálló	Igen	Igen	Nem	Aritmetikai áramkörök
Hyrax	zk-SNARK	Igen	Igen	Nem	Aritmetikai áramkörök
Halo	zk-SNARK	Igen	Igen	Nem	Aritmetikai áramkörök
Szűz	zk-VPD	Igen	Igen	Igen	Aritmetikai áramkörök
Ligero	zk-SNARK	Igen	Igen	Igen	Aritmetikai áramkörök
Hajnal	zk-SNARK	Igen	Igen	Igen	Aritmetikai áramkörök
zk-STARK	zk-STARK	Igen	Igen	Igen	Összeszerelés
Zilch	zk-STARK	Igen	Igen	Igen	Objektum orientált

Languages

In other projects