Zero Knowledge Proof

A nulla tudásigazolás (információ) a kriptográfiában ( eng.  Zero-knowledge proof ) egy interaktív kriptográfiai protokoll , amely lehetővé teszi, hogy az egyik interakcióban részt vevő fél ("The verifier" - ellenőrző) ellenőrizze bármely (általában matematikai) állítás érvényességét anélkül ennek birtoklása nem más információ a második féltől („A bizonyító” – bizonyítva). Sőt, az utolsó feltételre is szükség van, mivel általában triviális annak bizonyítása, hogy egy fél rendelkezik bizonyos információkkal , ha joga van egyszerűen nyilvánosságra hozni. Az egész nehézséget annak bizonyítása jelenti, hogy az egyik fél információval rendelkezik anélkül, hogy felfedné annak tartalmát. A jegyzőkönyvnek figyelembe kell vennie, hogy a bizonyító csak akkor tudja meggyőzni a hitelesítőt , ha az állítás valóban beigazolódik. Ellenkező esetben ez lehetetlen, vagy rendkívül valószínűtlen a számítási bonyolultság miatt .

A protokoll interaktivitása a felek közötti közvetlen információcserére vonatkozik [1] [2] .

Így a vizsgált protokoll interaktív bevitelt igényel a hitelesítőtől , általában feladat vagy probléma formájában. A jogi bizonyító (a bizonyíték birtokában ) célja ebben a jegyzőkönyvben az, hogy meggyőzze az ellenőrzőt arról, hogy van megoldása, anélkül, hogy a „titkos” bizonyíték egy részét is feladná („nulla tudás”). A hitelesítő célja annak biztosítása, hogy a bizonyító fél "nem hazudik" [2] [3] .

Kifejlesztettek olyan nulla tudás-ellenőrző protokollokat [4] [5] is, amelyek nem igényelnek interaktív bevitelt, és amelyek bizonyítása jellemzően egy ideális kriptográfiai hash függvény feltételezésére támaszkodik , vagyis azt feltételezik, hogy egy egy kimenete -way hash -függvény nem jósolható meg, ha a bemenete nem ismert [6] .

A nulla tudásalapú bizonyítást több blokkláncban alkalmazzák, emellett az információ meglétének ellenőrzésére szolgál anélkül, hogy magát az információt továbbítanák [7] [8] .

Definíció

A zéró tudás bizonyítása egy interaktív valószínűségi protokoll , amely lehetővé teszi annak bizonyítását, hogy a bizonyított állítás igaz, és a Prover ismeri ezt a bizonyítást, ugyanakkor magáról az állítás bizonyításáról nem ad információt [9] . Ennek a kriptográfiai protokollnak három tulajdonsággal kell rendelkeznie:

  1. Teljesség : Ha az állítás valóban igaz, akkor a bizonyító az ellenőrzőt bármilyen előre meghatározott pontossággal meggyőzi erről.
  2. Helyesség : ha az állítás hamis, akkor a Prover nem tudja meggyőzni a Hitelesítőt, kivéve ha elhanyagolható valószínűséggel , még "becstelen" is .
  3. Nulla tudás : ha az állítás igaz, akkor bármely, még a "becstelen" ellenőrző sem fog mást tudni, csak azt a tényt, hogy az állítás igaz [10] .

A zéró tudású bizonyítások a fogalom matematikai értelmében nem bizonyítások , mert van némi esély arra, hogy a bizonyítót meg lehet csalni, hogy meggyőzze a hitelesítőt egy hamis állításról ( helyességi hiba ). Más szóval, a nulla tudású bizonyítások valószínűségi bizonyítások, nem determinisztikusak . Vannak azonban módszerek a helyességi hiba elhanyagolható értékre való csökkentésére [11] [12] .

Különféle típusú nulla tudás

A nulla tudásalapú bizonyítási protokoll futtatása Elfogadás/Elutasítás eredményt ad , és a bizonyítás átiratát is generálja . A zéró tudás különféle változatai határozhatók meg úgy, hogy magát a fogalmat formalizáljuk , és a különböző modellek információinak eloszlását összehasonlítjuk a protokollal a következő módokon [13] [14] :

Fejlesztési előzmények

1986- ban Silvio Micali , Oded Goldreich és Wigderson leírták a nulla tudásalapú bizonyítékok használatát olyan kriptográfiai protokollok létrehozására , amelyeknek biztosítaniuk kell a felek "tisztességes viselkedését" a titkosság megőrzése mellett [19] .

A nulla tudásalapú bizonyítást a következő tudósok alkották meg és fejlesztették ki: Shafi Goldwasser , Silvio Micali és Charles Reckoff, és ők publikálták a "Knowledge and Complexity of an Interactive System with Proof" [20] című tanulmányában 1989 -ben . Ez a munka az interaktív bizonyítási rendszerek hierarchiáját mutatta be, amely azon bizonyítási információ mennyiségén alapul, amelyet át kell adni a Prover-től a Verifier-nek. Javaslatot tettek egy konkrétan meghatározott zéró tudás bizonyítására, egy négyzetes maradék modulo m első bizonyítására is [21] . Ezt követően munkájukat kiegészítve 1993 - ban elnyerték az első Gödel-díjat [22] .

Ezenkívül a Goldwasser-Micali titkosítási rendszer , amely a figyelembe vett interaktív protokollon alapul, amely egy nyilvános kulcsú kriptográfiai rendszer , amelyet Shafi Goldwasser és Silvio Micali fejlesztett ki 1982 -ben, az első olyan nyilvános kulcsú valószínűségi titkosítási séma , amely a szabványos kriptográfiai feltételezések mellett bizonyíthatóan biztonságos . . A javasolt rendszert a zsűri nagyra értékelte: Goldowasser és Micali a 2012 -es Turing-díj kitüntetettjei lettek [23] , egy valószínűségi titkosítással rendelkező kriptorendszer létrehozásáért, amelyet a jelölésben innovatív alkotásként jegyeztek meg, amely jelentős hatással volt a modern világra. kriptográfia . A titkosítási rendszer azonban nem hatékony, mivel az általa generált titkosított szöveg több százszor hosszabb lehet, mint a titkosított üzenet .

A kriptorendszer biztonsági tulajdonságainak bizonyítására Goldwasser és Micali bevezette a szemantikai biztonság fogalmát [24] [25] .

2021-ben Lovas László és Avi Wigderson Abel-díjat kapott az elméleti számítástechnika területén végzett munkájukért , amelyek nagymértékben hozzájárultak a számítási komplexitás-elmélet, a gráfelmélet, az elosztott számítási módszerek és a nulla tudásalapú bizonyítások koncepciójának fejlesztéséhez . 26] .

A nulla tudású bizonyítások általános szerkezete

Minden forduló, vagy bizonyítási akkreditáció három szakaszból áll. Sematikusan a következőképpen ábrázolhatók:

Először A kiválaszt egy elemet egy előre meghatározott nem üres halmazból , amely a titkos- magán kulcsa lesz . Ezen elem alapján a rendszer kiszámítja a nyilvános kulcsot , majd közzéteszi . A titok ismerete meghatározza azt a kérdéssort, amelyre A mindig helyes választ tudja adni. Ezután A kiválaszt egy véletlenszerű elemet a halmazból, bizonyos szabályok szerint (az adott algoritmustól függően) kiszámítja a bizonyítást, majd elküldi B -nek . Ezt követően B választ egy kérdést az egész halmazból, és megkéri A -t, hogy válaszoljon rá (kihívás). A kérdéstől függően A választ küld B - nek [27] . A kapott B információ elegendő annak ellenőrzésére, hogy valóban A birtokolja-e a titkot. A köröket tetszőleges számú alkalommal meg lehet ismételni, amíg annak a valószínűsége , hogy A „kitalálja” a válaszokat, elég kicsi lesz. Ezt a megközelítést "cut-and-choose"-nek is nevezik, először Michael Rabin [28] [29] használta a kriptográfiában .

Példák

Zero Knowledge Cave

Ezt a példát először Jean-Jacques Kiskater „Hogyan magyarázd el a zéró tudás-ellenőrzési protokollt a gyerekeidnek” című jól ismert zéró tudásellenőrző dokumentumban.[30] .

Ebben az esetben Peggy a Prover, a Victor pedig az ellenőrző szerepét tölti be (az angol irodalomban általában a felek Peggy és Victor nevét használják (a "Prover" és a "Verifier" szóból). Peggy ismeri a varázsszót ("kulcs"). "), bemenet, amely lehetővé teszi számára, hogy kinyitja az ajtót C és D között. Victor tudni akarja, hogy Peggy valóban tudja-e a jelszót, míg Peggy nem akarja magát a jelszót kiadni. A barlangnak kerek alakja van, ahogy az a ábra.A probléma megoldása érdekében a következőképpen járnak el: Amíg Victor az A pontban van, Peggy az ajtóhoz megy, majd miután eltűnt a látómezőből, Victor a villához, azaz a B ponthoz megy, és kiabál onnan: "Peggynek jobbra kell kilépnie" vagy "Peggynek balra kell kilépnie " Minden alkalommal azt kapjuk, hogy annak a valószínűsége, hogy Peggy nem tudja a jelszót, egyenlő 50%.Ha k -szer megismételjük a folyamatot, akkor a valószínűség a következő lesz . 20 ismétlés esetén ez a valószínűség 10 −6 nagyságrendű lesz , ami elegendő a méltányossághoz . Ezek a feltételezések, hogy Peggy ismeri a kulcsot [30] .

Ha Victor mindent rögzít, ami a kamerán történik, akkor a kapott videó nem lesz bizonyíték a másik fél számára. Hiszen előre megegyezhettek volna, hogy Peggy honnan jön. Ennek megfelelően képes lesz megtalálni a kiutat anélkül, hogy ismerné magát a kulcsot. Van egy másik út: Victor egyszerűen kivágja Peggy összes sikertelen próbálkozását. A fenti lépések bizonyítják, hogy a barlangi példa kielégíti a teljesség , a helyesség és a nulla tudás tulajdonságait [31] .

Hamilton-ciklus nagy gráfokhoz

Ezt a példát Manuel Blum találta ki, és 1986 -ban írt cikkében [32] . Nevezzük Victornak a tesztelőt és Peggynek. Tegyük fel, hogy Peggy ismer egy Hamilton-ciklust egy nagy G gráfban . Victor ismeri a G gráfot , de nem ismeri a benne lévő Hamilton-ciklust. Peggy be akarja bizonyítani Victornak, hogy ismeri a Hamilton-ciklust, anélkül, hogy felfedné magát a ciklust vagy bármilyen információt róla (lehet, hogy Victor információt akar vásárolni Peggytől erről a Hamilton-ciklusról, de előtte meg akar bizonyosodni arról, hogy Peggy valóban ismeri őt ).

Ehhez Victor és Peggy közösen hajtják végre a protokoll több körét :

Victor minden körben választ egy új véletlenszerű bitet , amelyet Peggy nem ismer, így ahhoz, hogy Peggy mindkét kérdésre válaszoljon, H -nak valóban izomorfnak kell lennie G -vel , és Peggy-nek ismernie kell a Hamilton-ciklust H -ban (és így G -ben is ). Ezért Victor kellő számú kör után biztos lehet benne, hogy Peggy valóban ismeri a Hamilton-ciklust G -ben . Másrészt Peggy nem árul el semmilyen információt a G -beli Hamilton-ciklusról . Sőt, Victornak nehéz lesz bebizonyítania másnak, hogy ő vagy Peggy ismeri a Hamilton-ciklust G -ben [32] .

Tegyük fel, hogy Peggy nem ismeri a Hamilton-ciklust G -ben, de be akarja csalni Victort. Ekkor Peggynek szüksége van egy nem izomorf G - gráfra G′ , amelyben még ismeri a Hamilton-ciklust . Minden körben átadhatja Victornak H′-t  – G -vel izomorf , vagy H -t – G  -vel izomorf . Ha Victor a gráfok izomorfizmusának bizonyítását kéri, és H -t adták neki , akkor a megtévesztés nem derül ki. Hasonlóképpen, ha egy Hamilton-ciklust kér, és H′ -t kapott . Ebben az esetben annak a valószínűsége, hogy Peggy k kör után mégis megtéveszti Victort, egyenlő , ami kisebb lehet bármely előre meghatározott értéknél megfelelő számú kör mellett [32] .

Tegyük fel, hogy Victor nem ismeri fel a Hamilton-ciklust, de be akarja bizonyítani Bobnak, hogy Peggy ismeri. Ha például Victor videóra veszi a protokoll összes menetét, Bob aligha hinné el neki. Bob feltételezheti, hogy Victor és Peggy kahooban vannak, és Victor minden körben elmondja Peggynek, hogy véletlenszerűen választott bitet, hogy Peggy átadhassa neki H -t az izomorfizmusteszteknél és H′-t a Hamiltoni ciklusteszteknél. Így Peggy részvétele nélkül csak úgy lehet bizonyítani, hogy ismeri a Hamilton-ciklust, ha bebizonyítjuk, hogy a protokoll minden fordulójában valóban véletlenszerű biteket választottak [33] .

Alkalmazás a gyakorlatban

Oded Goldreich , Silvio Micali és Avi Wigderson [ 19] bizonyítja azt a tételt, amely szerint bármely NP-teljes probléma esetén létezik nulla tudású bizonyítás, míg az egyirányú függvények használatával korrekt kriptográfiai protokollokat lehet létrehozni. 34] . Vagyis bármely szkeptikusnak bebizonyíthatja, hogy rendelkezik valamilyen matematikai tétel bizonyításával, anélkül, hogy magát a bizonyítást felfedné. Ez azt is mutatja, hogyan használható ez a protokoll gyakorlati célokra [13] .

A következő módszer, ahol a nulla tudásszintű bizonyítást alkalmazhatjuk, az identitás-meghatározás, melynek során Peggy privát kulcsa az úgynevezett „identitásjelző”, és a szóban forgó protokoll segítségével igazolható a személyazonossága. Vagyis különböző fizikai eszközök és adatok (szimbólumok), például útlevél, különféle személyi kép (retina, ujjak, arc stb.) használata nélkül is igazolhatja személyazonosságát, de alapvetően más módon [35] . Ennek azonban számos hátránya van, amelyek segítségével megkerülheti a védelmet. A fent leírt módszert először Amos Fiat , Adi Shamir és Uriel Feige javasolta 1987 - ben [36] .

A nulla tudásalapú igazolások is használhatók bizalmas számítási protokollokban , amelyek lehetővé teszik több résztvevő számára, hogy ellenőrizze, hogy a másik fél becsületesen követi-e a protokollt [19] .

A nulla tudásalapú igazolásokat a Zcash , a Byzantium ( az Ethereum egyik villája), a Zerocoin és mások kriptovaluták blokkláncaiban használják . Létrehozták a nulla tudásalapú protokollok megvalósítását, különösen a QED-IT szoftverfejlesztő készletet. A holland ING bank létrehozta a protokoll saját verzióját, a ZKRP-t ( Zero-Knowledge Range Proof ), és ennek segítségével igazolta, hogy az ügyfélnek elegendő fizetése van anélkül, hogy felfedné a valódi méretét [7] [8] .

A legelterjedtebb protokollok a zk-SNARK-ok, ennek az osztálynak a protokolljait használják a ZCash, Zcoin és az Ethereum blokklánc Metropolis protokollja [37] [8] .

A zk-SNARK rövidítés a   zéró tudás tömör, nem interaktív argumentumát jelenti [37] [8] . A zk-SNARK algoritmus egy kulcsgenerátorból, egy bebizonyítóból és egy ellenőrzőből áll, szükségszerűen támogatja a nulla tudást, rövid (rövid időn belül számítva), nem interaktív (az ellenőrző csak egy üzenetet kap a bizonyítótól) [8] .

Visszaélés

Számos módszert javasoltak a nulla tudásszinttel való visszaélésre, amelyek kihasználják a protokoll bizonyos gyengeségeit:

Nagymester probléma

Ebben a példában néhány fél bizonyítani tudja a titok birtoklását anélkül, hogy ténylegesen birtokában lenne, vagy más szóval, utánozni tudja azt a személyt, aki a titok tényleges tulajdonosa [38] . Jelenleg Thomas Beth és Ivo Desmedt javasolta a probléma megoldásának módját [39] .

Megtévesztés több identitással

Ha egy párt több titkot is létrehozhat, akkor ennek megfelelően "több identitást" is létrehozhat. Soha ne használjuk egyiküket. Ez a lehetőség egyszeri névtelenséget biztosít, ami lehetővé teszi például a felelősség kibújását: a fél soha nem használt személyként azonosítja magát, és bűncselekményt követ el. Ezt követően ezt az "identitást" soha többé nem használják. Szinte lehetetlen az elkövetőt felkutatni vagy bárkivel összehozni. Az ilyen visszaélések megakadályozhatók, ha a második titok létrehozásának lehetőségét eleve kizárják [40] .

A maffia által végrehajtott megtévesztés

Újabb példa arra, hogy az egyik oldal úgy tesz, mintha a másik lenne. Legyen 4 résztvevő: A , B , C , D . Sőt , B és C együttműködnek egymással („ugyanahhoz a maffiához tartoznak”). A személyazonosságát igazolja B -nek, C pedig A-t akarja személyesíteni D előtt . B -nek egy maffia tulajdonában lévő étterem, C  szintén a maffia képviselője, D  ékszerész. A és D nem tudnak a közelgő csalásról. Abban a pillanatban , amikor A kész fizetni a vacsoráért, és azonosítani magát B -vel , B értesíti C -t a csalás kezdetéről. Ez a köztük lévő rádiócsatorna jelenléte miatt lehetséges. Ekkor C kiválasztja a megvásárolni kívánt gyémántot, D pedig elkezdi azonosítani C személyét , aki A -t kiadja. C átadja a protokollkérdést B -nek, aki viszont felteszi A -nak. A válasz továbbítása fordított sorrendben történik. Így A nemcsak a vacsoráért fizet, hanem a drága gyémántért is. Amint a fentiekből kitűnik, az ilyen csalásnak vannak bizonyos követelményei. Amikor A elkezdi igazolni személyazonosságát B -nek, C  pedig D -nek , B és C cselekedeteit szinkronizálni kell. Ez a visszaélés is megengedett. Például, ha van egy Faraday-ketrec egy ékszerüzletben , akkor a "maffiózók" nem tudnak üzenetet váltani [41] .

Lehetséges támadások

Választott titkosított szöveges támadás

Ez a támadás megvalósítható egy nem interaktív interakciós módszerrel egy nulla tudás protokollban.

Számos probléma van ezzel a protokollal. Először is el kell döntenie, hogyan kíván interakciót folytatni, miközben magának a protokollnak az alapvető jellemzőit meg kell őriznie: teljességet, helyességet és „nulla tudást”. Amellett, hogy a zéró tudást elég könnyű bizonyítani a másik félnek, ha le lehet hallgatni a csatornát, vagyis szembesülni a nagymesteri problémával .

Tehát maga a támadás a következő: a támadó a tudás birtoklásának bizonyításának összetettségét felhasználva tartalmazza a „támadó” rejtjelszöveget , becsúsztatva egy csomó más rejtjelezett szövegbe, amelyeket meg kell fejteni. Ezt a támadást "playback" támadásnak nevezik [42] .

Egy lehetséges megoldás Moni Naor és Moti Yung munkáján alapul , ami a következő: Prover and Verifier titkosítja az üzeneteket nyilvános kulccsal , ez okozza a fenti támadás meghiúsulását [43] .

Támadás egy többprotokollú nulla tudású rendszer ellen

Chida és Yamamoto a zéró tudás protokoll megvalósítását javasolta, amely jelentősen megnöveli a nulla tudás bizonyításának sebességét, miközben több állítást egyszerre bizonyít, és ennek eredményeként a teljes rendszer teljesítményét [44] . A legfontosabb jellemző az iterációk számának korlátozása a bizonyításhoz. Amint azt K. Peng [45] munkája mutatja , ez az algoritmus teljesen instabilnak bizonyult a következő támadásra. Több jól megválasztott iteráció használatával a támadó átmegy az ellenőrzésen , és megsértheti a protokoll főbb rendelkezéseit. Sőt, bebizonyosodott, hogy ez a támadás mindig megvalósítható egy ilyen rendszeren.

Támadás kvantumszámítógéppel

2005- ben John Watrus mutatta be , hogy nem minden zéró tudású rendszer ellenáll a kvantumszámítógépes támadásoknak . Azonban bebizonyosodott, hogy mindig lehet olyan rendszert építeni, amely ellenáll a kvantumtámadásoknak, feltételezve, hogy léteznek "kötelezettségek eltitkolásával" rendelkező kvantumrendszerek [46] .

Lásd még

Jegyzetek

  1. ↑ Goldreich, 2013 .
  2. ↑ 1 2 Schneier, 2002 , pp. 87-92.
  3. ↑ Goldwasser, Micali, Rackoff, 1989 , pp. 186-189.
  4. ↑ Santis, Micali, Persiano, 1988 .
  5. ↑ Blum, Feldman, Micali, 1988 .
  6. ↑ Schneier, 2002 , pp. 90-91.
  7. ↑ 12 ForkLog , 2019 .
  8. ↑ 1 2 3 4 5 Gubanova, 2018 .
  9. ↑ Blum, 1988 , p. 1444.
  10. ↑ Menezes et al, 1996 , pp. 406-408.
  11. ↑ Schneier, 2002 , pp. 86-89.
  12. ↑ Goldwasser, Micali, Rackoff, 1989 , pp. 188-189.
  13. ↑ 1 2 Schneier, 2002 , pp. 91-92.
  14. ↑ Mao, 2005 , pp. 683-696.
  15. ↑ Mao, 2005 , pp. 684-688.
  16. ↑ Sahai, Vadhan, 2003 .
  17. ↑ Mao, 2005 , p. 696.
  18. ↑ Mao, 2005 , pp. 692-696.
  19. ↑ 1 2 3 Goldreich, Micali, Wigderson, 1986 .
  20. ↑ Goldwasser, Micali, Rackoff, 1989 .
  21. ↑ Goldwasser, Micali, Rackoff, 1989 , pp. 198-205.
  22. ↑ Goldwasser, Micali és Rackoff Gödel-díjat kapnak 1993-ban (a link nem érhető el) . ACM Sigact (1993). Az eredetiből archiválva: 2015. december 8. 
  23. ↑ Goldwasser, Micali megkapta az ACM Turing-díjat a kriptográfiai előrelépésekért (a link nem érhető el) . ACM. Letöltve: 2013. március 13. Az eredetiből archiválva : 2013. március 16.. 
  24. ↑ Goldwasser, Micali, 1982 .
  25. ↑ Mao, 2005 , pp. 524-528.
  26. ↑ Abel-díj – 2021 • Andrej Raigorodszkij • Tudományos hírek az „elemekről” • Matematika, tudomány és társadalom . Letöltve: 2021. május 17. Az eredetiből archiválva : 2021. június 3.
  27. ↑ Mao, 2005 , pp. 678-682.
  28. ↑ MORabin. digitális aláírások . — A biztonságos számítástechnika alapjai. - New York: Academic Press, 1978. - P. 155-168. — ISBN 0122103505 .
  29. ↑ Schneier, 2002 , pp. 87-89.
  30. ↑ 12 Quisquater et al, 1990 .
  31. ↑ Schneier, 2002 , pp. 87-88.
  32. ↑ 1 2 3 4 Blum, 1988 .
  33. ↑ Schneier, 2002 , pp. 89-90.
  34. ↑ Goldreich, Micali, Wigderson, 1987 .
  35. ↑ Schneier, 2002 , p. 92.
  36. ↑ Fiat, Shamir, 1987 .
  37. ↑ 12 Chain Media, 2017 .
  38. ↑ Schneier, 2002 , pp. 92-93.
  39. ↑ Beth, Desmedt, 1991 .
  40. ↑ Schneier, 2002 , pp. 93-94.
  41. ↑ Schneier, 2002 , p. 93.
  42. ↑ Rackoff, Simon, 1992 .
  43. ↑ Naor, Yung, 1990 .
  44. ↑ Chida, Yamamoto, 2008 .
  45. ↑ Peng, 2012 .
  46. ↑ Vizes, 2006 .

Irodalom

könyvek és monográfiák cikkeket

Linkek