A tudás nulla közzétételének bizonyítéka

A zéró tudás közzététele bizonyítási építőköve használt Cryptology a hitelesítés és azonosítás . Ez a kifejezés egy biztonságos protokollt jelöl , amelyben egy entitás, amelyet „bizonyítási szolgáltatónak” neveznek, matematikailag bebizonyítja egy másik entitásnak, a „hitelesítőnek”, hogy egy állítás igaz, anélkül azonban, hogy a javaslat valódiságán kívül más információt fedne fel.

A gyakorlatban ezek a sémák gyakran olyan protokollok formájában érkeznek, mint a "kihívás / válasz" ( kihívás-válasz ). A hitelesítő és a bizonyíték szolgáltatója információt cserél, és a hitelesítő ellenőrzi, hogy a végső válasz pozitív vagy negatív.

Az angolul beszélők a ZKIP rövidítést használják a Zero Knowledge Interactive proofhoz .

Vannak interakció nélküli változatok is ( nem interaktív null-tudásbiztos ). Ezeket a véletlenszerű orákulum modellben a Fiat-Shamir heurisztika készítheti el .

Példák

Ali Baba barlangja

Jean-Jacques Quisquater és Louis Guillou 1989-ben publikált egy cikket "Hogyan magyarázzuk el a nulla tudású protokollokat gyermekeinek" (vagy "Hogyan magyarázzuk el gyermekeinek a protokollokat a tudás hozzájárulása nélkül"). Az „ Ali Baba és a negyven tolvaj ” című mese alapján oktatási bevezető olvasható a bizonyítás fogalmába, zéró ismeretfeltárás nélkül . Két emberre gondolunk: Alice -re (próba) és Bobra (hitelesítő). A villával ellátott barlangot is figyelembe vesszük: A és B. A varázsszó segítségével ajtót nyitva A-ból B-be vagy B-ből A-ba mehetünk. Alice be akarja bizonyítani Bobnak, hogy ismeri az ajtó kinyitásának varázsszavát, de nem akarja, hogy Bob megtudja. A "tudás bizonyításáról" szól (Alice bebizonyítja Bobnak, hogy ismeri a kulcsot), de "nem járul hozzá az információkhoz" (Alice titkolja). Ehhez Alice és Bob többször megismétlik a következő forgatókönyvet.

Elkötelezettség. Bob (zöld színnel) a barlang bejáratánál vár, és nem látja az alagút belsejét. Alice (lila színben) belép a galériába, és véletlenszerűen választja ki a bal vagy jobb oldali zsákutcát, például dob egy kockát vagy érmét.
Kihívás. Bob belép az alagútba és vár az elágazásnál. Dob egy érmét. Attól függően, hogy az érme melyik oldalára esik, Bob „A” vagy „B” kiáltást tesz.
Válasz. Alice-nek most be kell bizonyítania, hogy a bizonyíték birtokában van, meg kell jelennie a Bob által kért kijárat felé.

Számos forgatókönyv merül fel:

Alice ismeri a varázsszót:
- ha az A -ban van, és Bob azt mondja, hogy "B", akkor kielégíti a kérést
- ha B -ben van, és Bob "A" -t mond, akkor kielégíti a kérést
- ha az A pontnál van, és Bob „A” -t mond, akkor kielégíti a kérést
- ha B-ben van, és Bob azt mondja, hogy "B", akkor kielégíti a kérést

Alice nem ismeri a varázsszót:
- ha A-ban van, és Bob azt mondja, hogy "B", akkor nem felel meg a kérésnek
- ha a B -ben van, és Bob azt mondja, hogy „A”, akkor nem elégíti ki a kérést
- ha az A pontnál van, és Bob „A” -t mond, akkor kielégíti a kérést
- ha B-ben van, és Bob azt mondja, hogy "B", akkor kielégíti a kérést

Ha Alice nem ismeri a varázsszót, Bobot félrevezethetik azok az esetek, amikor kérése megegyezik Alice jelenlegi helyzetével. Feltételezve, hogy betartja a protokollt (konzisztencia kritérium), Alice hibáját a nem tudás bizonyítékának tekintik. Bob azonnal leállhat, biztos abban, hogy Alice nem ismeri a varázsszót.

Ha többször kezdi az első lépést, Bob elegendő információt gyűjthet, hogy biztos lehessen benne, hogy Alice-nek van varázsszava. Minden új próbálkozással javítja az önbizalmát. Ha Alice nem rendelkezik a varázsszóval, akkor 50% az esélye, hogy hibázik. Az N megpróbálja a valószínűsége, hogy Bob azt mondják, hogy Alice-nek a titkos amikor nincs meg . ${\ frac {1} {2 ^ {N}}} ~$

Ezt párhuzamosan a kriptográfiai primitívekkel a "kihívás / válasz" protokoll részeként, mindig van esély, bármennyire is kicsi, hogy a bizonyíték szolgáltatójának válasza véletlenszerűen készült, és hogy "megfelel annak, amit a az igazoló.

A színvak és a színes golyók

Ebben a példában két egyforma tárgyat veszünk figyelembe, amelyeknek azonban van egy jellemzőjük, amely megkülönbözteti őket, tehát két hasonló gömböt, de különböző színűek. A példa Oded Goldreichtől származik, aki két különböző színű kártyát használt.

A példa egy fiktív helyzeten alapszik, amikor két ember avatkozik be: az egyik színvak , a másik megkülönbözteti a színeket. A színeken kívül két megkülönböztethetetlen golyó van, a piros és a zöld. A színvak esetében teljesen azonosak. A cél az, hogy bebizonyítsuk a színvaknak, hogy az, aki látja a színeket, képes megkülönböztetni a golyókat a színeik alapján, de anélkül, hogy színeik lennének (vörös vagy zöld felfedve).

A színvak vak a háta mögé helyezi a golyókat, majd elveszi az egyik gömböt, és megmutatja a másiknak. A háta mögé teszi, majd úgy dönt, hogy az egyik golyót, akár ugyanazt, akár a másikat mutatja meg 50%-os valószínűséggel. Aztán megkérdezi: "Cseréltem labdát?" ". Az eljárást annyiszor ismételjük, ahányszor szükséges. Ha a protokollt elégszer megismétlik, és ha a nem színvak nem mindig adja meg a helyes választ, akkor a színvak nagyon nagy valószínűséggel meg lesz győződve arról, hogy partnere valóban képes megkülönböztetni a golyókat színük alapján. Ez nulla tudásbiztos protokoll, mivel soha nem fedi fel a golyók színét.

Más példák

A létező rejtjeles bizonyítékok közül megemlíthetjük:

A protokoll Schnorr , bizonyítani ismerete a logaritmus diszkrét elemeként csoport nyilvános ; $x$ ${\ displaystyle h = g ^ {x}}$
A Guillou-Quisquater protokoll , amely lehetővé teszi az RSA titkosítás mögött álló egyértelmű üzenet ismeretének bizonyítását .

Tulajdonságok

Három tulajdonságnak kell megfelelnie:

következetesség ( teljesség ): ha a bizonyíték szolgáltatója és a könyvvizsgáló betartja a protokollt, miközben az auditornak mindig el kell fogadnia a bizonyítékot.
robusztusság ( megalapozottság ): Ha hamis, egyetlen szállító rosszindulatú bizonyítéka sem tudja meggyőzni az igazoló hitelesítőt arról, hogy az ajánlat igaz, és ez nagy valószínűséggel
nincs információ bevitele ( nulla ismeret ): a hitelesítő a bizonyítás szállítójától nem tanul meg mást, csak a javaslat valódiságát, a beszállítói igazolás bevitele nélkül nem szerez olyan információt, amelyet még nem tudott. Ha a hitelesítő nem követi az eljárást, ez a meghatározás mindaddig érvényes marad, amíg a bizonyíték szolgáltatója követi az eljárást.

Az első két tulajdonság ugyanaz, amelyet interaktív bizonyítási rendszer definiálására használnak , ami általánosabb fogalom. Ez a harmadik tulajdonság, amely nulla tudást eredményez .

Biztonság

A bizonyítékok biztonsága több kategóriába sorolható, a korábban meghatározott különféle biztonsági koncepciók által elvárt biztonság, vagyis a megalapozottság és az ismeretek hiánya szerint. Ezután a következőkről beszélünk:

"számítási" bizonyíték: a megfigyelő képtelenség egy polinom időben megkülönböztetni a hiteles bizonyítást a hamisított vagy véletlenszerű bizonyítástól
"statisztikai" vagy tökéletes bizonyítás : a hiteles bizonyítékok eloszlása megegyezik a véletlenszerű vagy hamisított bizonyítékokéval. Ez ugyanúgy látható, mint a számítási bizonyításoknál, ha végtelen (vagy korlátlan) számítási erőt ad a diszkriminátornak.

Az első nem utasítja el a módszer létezését (de ez, ha létezik, nem lesz polinomiális összetettségű), míg a tökéletes bizonyíték biztosítja, hogy egyetlen módszer sem létezik ( az információelmélet szerint ).

Hasonlóképpen, ha a megbízhatóság statisztikai, akkor a "bizonyítás" kifejezést kell használni, ellenkező esetben, ha ez számítási, az "érv" kifejezést használjuk a bizonyítás jelölésére.

Általános építés

Az egyik módszer a bizonyítékok konstruálására tudásfeltárás nélkül úgynevezett Σ protokollokat használ (ezt a háromirányú kommunikáció miatt nevezték el, amely a görög Sigma betűre emlékeztet ). A Σ protokoll egy interaktív protokoll egy közmondás és egy hitelesítő között, amely három cserét tartalmaz:

Az elkötelezettség , amely a közmondás által a hitelesítőnek küldött első üzenet;
A kihívás , amely a hitelesítő által küldött válasz;
A válasz , amely a Prover utolsó üzenete.

A protokoll biztonsága close nagyon közel áll a tudásfeltárás nélküli bizonyítás biztonságához: következetesség, különleges robusztusság és nulla információbevitel egy becsületes hitelesítővel. Ezután az általános felépítés abból áll, hogy őszinteséget kényszerítenek a hitelesítőre azzal, hogy arra kényszerítik, hogy a kihívást az elkötelezettségtől függetlenül egy kriptográfiai zálogos rendszeren keresztül generálja .

Ezen a konstrukción alapul több bizonyítás is, amelyek ismeretek feltárása nélkül történnek , például a Schnorr protokoll vagy a Guillou-Quisquater azonosítási séma . Ennek egyik oka az lehet, hogy könnyebb dolgozni a Σ protokollokon, amelyek szintén jó szabályszerűségi tulajdonságokkal rendelkeznek: vannak konstrukciók a protokollok összekapcsolásának és eloszlásának végrehajtására. Tulajdonságok, amelyek nincsenek a bizonyítékokon az általános ismeretek nyilvánosságra hozatala nélkül.

Sztori

Ezek Shafi Goldwasser , Silvio Micali és Charles Rackoff , akik 1985-ben használták először 1985-ben a "proof zero-knowledge of tudás" kifejezést , pontosabban annak angol formáját, "zero knowledge proof" az alapanyagukban. Shafi Goldwasser és Silvio Micali 2012 - ben megkapta a Turing-díjat munkájáért.

Ez volt Oded Goldreich , Silvio Micali és Avi Wigderson akik felfedezték, hogy feltételezve, hogy a létezése kriptográfiai primitívek, a zéró-ismeret közzétételi bizonyítási rendszer a gráf színezése probléma lehet létrehozni. Ez azt jelenti, hogy az NP összes problémája rendelkezik ilyen bizonyítékokkal.

Shafi Goldwasser most a QED-it keretein belül alkalmazza munkáját , amely a ZKIP-t tette fő üzleti tevékenységévé.

Jegyzetek és hivatkozások

Damgård 2010 .
Groth és Sahai 2008 .
Quisquater és Guillou 1989 .
Ez a példa Konstantinos Chalkias és Mike Hearn blokklánc konferenciájának köszönhető, [1] 2017. szeptember.
(in) " Megjelenítés nélkül " itt: https://wis-wander.weizmann.ac.il/ ,1 st november 2003(megtekintés : 2020. november 23. )
Dodis és De Souza 2009 .
Goldwasser, Micali és Rackoff 1985 .
Goldreich, Micali és Wigderson 1991 .
" HighTech. Izraelben született QED - ez egy "BtoB" Blockchain induló vállalkozás. - Israelvalley ” , a www.israelvalley.com oldalon (elérhető : 2017. október 31. )

Mellékletek

Kapcsolódó cikkek

Bibliográfia

[Quisquater és Guillou 1989] (en) Jean-Jacques Quisquater és Louis Guillou, „ Hogyan magyarázzuk el a nulla tudás protokolljait gyermekeinknek ” , Crypto , lNCS,1989( online olvasás )Aláírták a szerzők családjával.
[Goldwasser, Micali és Rackoff 1985] (en) Shafi Goldwasser, Silvio Micali és Charrles Rackoff, „ A tudás összetettsége interaktív bizonyítási-rendszerek ” , Szimpózium elmélet számítási (STOC) ,1985
[Goldreich, Micali és Wigderson 1991] (en) Oded Goldreich, Sivlio Micali és Avi Wigderson: „ Bizonyítékok, amelyek nem adnak semmit, csak érvényességüket ” , Journal of the ACM , vol. 38,1991, P. 680-728
[Groth és Sahai 2008] (en) Jens Groth és Amit Sahai, „ Hatékony, nem interaktív bizonyítási rendszerek a bilineáris csoportok számára ” , Eurocrypt ,2008( DOI 10.1007 / 978-3-540-78967-3_24 , olvassa el online )

Külső linkek

[Dodis és De Souza 2009] (en) Yevgeniy Dodis és Bianca De Souza , „ Advanced Cryptography ” , Előadási jegyzetek [PDF] ,2009. október 14.
[Damgård 2010] (en) Ivan Damgård, „ On Σ-Protocols ” , Előadási jegyzetek [PDF] ,2010