Zero-knowledge protokoly umožňují identifikaci, výměnu šifrovacích klíčů či jiné kryptografické operace bez zveřejnění jakékoliv utajované skutečnosti v průběhu přenosu. Přesný český ekvivalent slovního spojení zero-knowledge bychom asi marně hledali, šlo by patrně použít něco jako protokoly s nulovým odhalením či nulovou výpovědí. Jelikož pro svojí činnost obvykle potřebují daleko méně výpočetního výkonu než klasické algoritmy s relativně velkými veřejnými klíči, nachází svoje uplatnění především v různých čipových kartách a v aplikacích, které s nimi pracují. Přestože algoritmy, které využívají, nejsou nijak standardní, některé bezpečnostní problémy jsou pomocí nich řešitelné buď zčásti, nebo úplně. Vedle toho disponují navíc některými specifickými vlastnostmi, o kterých bude řeč dále.

• Peggy (prover, "dokazovatel", žadatel) - má jistou tajnou informaci a chce Viktorovi dokázat že ji má, niž by se ji on sám dozvěděl.

• Viktor (verifier, ověřovatel) - chce ověřit, zda Peggy danou informaci má. Jeho "vedlejším" úsilím je ji získat, dobře navržený protokol mu to neumožní.

• Eva (eavesdropper) - odposlouchává konverzaci mezi Peggy a Viktorem. Kvalitní protokol znemožní jakékoliv třetí straně jak zjištění tajemství, tak "opakované" ujištění někoho jiného, že Peggy danou informaci má.

Tajemství může být jakákoliv informace - heslo, tajný klíč nebo řešení nějakého matematického problému. Použití Zero-knowledge protokolu umožňuje aby žadatel dokázal ověřovateli že právě on je vlastníkem této informace a to bez toho, aby se ji (ověřovatel) dozvěděl. Cílem je tedy situace opačná, než vyplňování hesla či ukazování občanského průkazu v praxi.

V průběhu ověřování této skutečnosti nabývá Viktor stále větší a větší jistoty. Vypovídá-li jedno kolo ověřovacího protokolu o tom, že Peggy je ta za kterou se vydává či má to co říká s pravděpodobností 1:1, pak po n kolech je šance, že Peggy protokol obelstila 1:2ⁿ.

V praxi obvykle celý systém stojí a padá na nějakém matematickém problému a na jeho řešení. Peggy chce Viktorovi dokázat že ho zná, ale nechce mu ho odhalit. Říká se tomu Zero-knowledge proof ("důkaz s nulovým odhalením").

Celou situaci nejlépe ilustruje známý obrázek jeskyně (viz níže). Vede do ní jeden vchod (A), který ústí do kruhová chodby (B), která je však ve své polovině uzavřena dveřmi (C), které se otevřou jen když zadáme správný číselný kód. Peggy chce dokázat Viktorovi, že ho zná, ale nechce, aby se ho on dozvěděl. Proto s ním nemůže projít celou jeskyni. Jak bude postupovat? Nechá Viktora stát v místě A, dojde na "téčko" a vybere si jeden ze směrů (je úplně jedno jaký, správně by měla použít nějaký bezpečný generátor náhodných čísel). Až dojde ke dveřím (C), zavolá na Viktora, který se přijde na místo (B). Nyní si on vybere směr (ve vlastním zájmu by měl také použít generátor náhodných čísel) a zavolá na Peggy odkud si přeje, aby přišla. Tedy "Zprava!" či "Zleva!".

Nyní se vžijme do Peggy. Pokud kód zná tak buď musí nebo nemusí dveře otevírat a v každém případě přijde z toho směru, který si Viktor zvolil. Pokud ho nezná, má ale pravděpodobnost jen 50%, že si s Viktorem náhodou vybrali stejný směr a pro tentokrát se jí podaří ho obelstít. Po tomto jednom kole má tedy Viktor jistotu 50% (1:1), že Peggy kód zná. Při každém dalším opakování tohoto procesu se možnost, že by Peggy podvedla Viktora zmenší na polovinu. Viktor tak může znalost kódu u Peggy ověřit s jakoukoliv jistotou (pravděpodobností).

Jak je vidět, jedno jediné pochybení a je rozhodnuto, důkaz znalosti je celý neplatný. Říká se tomu cut&choose.

Tak především, jak už bylo zmíněno, Viktor nemá naprosto žádnou informaci o tom, jaký číselný kód Peggy použila. Ví pouze, že ho zná. to je základní Zero-knowledge-myšlenka : ten kdo ověřuje se z protokolu doví jen tolik, kolik by věděl i bez druhé strany. Žádná tajná informace či její část není mezi stranami přenášena.

Dále, Peggy nemůže Viktora podvést. Jinak řečeno, podvod je jen záležitost (nekonečného) štěstí. V praxi může být Viktor obelhán jen s jistou pravděpodobností, která ovšem exponenciálně klesá s počtem opakování. Tedy například 10 opakování znamená jistotu 1:1024, 20 opakování 1:1048576 a 128 opakování znamená pravděpodobnost takovou, že na první pokus uhádnu správný klíč do jakékoliv dnes běžně používané šifry (implementované např. v PGP, SSL...). Pokud je šance, že Peggy projde "testem" i když nezná klíč velká, stačí provést více kol. Již zmíněný exponenciální charakter "vyhoupne" pravou stranu poměru do astronomických výší tak jako tak za chvíli.

Viktor také nemůže podvést Peggy. To by se stalo v případě, že by postupoval v nesouladu s protokolem.

Jelikož se žádná tajná informace nepřenáší, nemůže se Viktor zamaskovat jako Peggy někomu třetímu. Man-in-the-middle attack je možný jen v některých protokolech.

A nakonec, Viktor již z principu nemůže ujistit o informovanosti Peggy nikoho třetího.

Abychom lépe pochopili fungování protokolu, ukažme si ještě dva případy. Oba z nich kopírují standardní schéma : je dán problém, Peggy k němu zná řešení a chce to dokázat Viktorovi, aniž by se ho on dověděl. Ze zadání vytvoří problém jiný, ukáže ho Viktorovi a ten se rozhodne : buď mi ukaž řešení problému nového, nebo mi ukaž převod z něj na problém původní. Pokud Peggy řešení zná, může udělat obě věci. Pokud nikoliv, je schopna provést vždy buď jedno nebo druhé, nikdy ale ne oboje.

Více či méně ilustrativní je příklad s bludištěm, ve kterém Peggy zná cestu z bodu A do bodu B (oba veřejně známé). Vybere si na něm bod C, ze kterého se umí dostat na "cestu" mezi A a B a ukáže ho Viktorovi. Ten se rozhodne, zda chce vidět cestu z A do C nebo z B do C. Pokud Peggy ví kudy z A do B, může zodpovědět obě otázky, v opačném případě vždy (maximálně) jednu.

Obdobně nám může posloužit Rubikova kostka. Peggy ví, jak jí z rozházeného stavu X dostat do původního (označme jej A). Z nějakého stavu mezi X a A dalším otáčením vytvoří stav Y a ukáže jej Viktorovi. Pokud umí složit X, bude umět jak složit Y, tak z něj složit X.

Pokračování příště.