Intro('Zero-knowledge proofs, neboli d∙kazy s ₧ßdn²m zve°ejn∞nφm. Oblast informaΦnφ bezpeΦnosti, o kterΘ se mßlo diskutuje, p°sto₧e v∞tÜφ teoretickΘ prozkoumßnφ a nßslednΘ nasazenφ v praxi by znamenalo skuteΦn² p°evrat v bezpeΦnosti. Vzdßlenou sptrßvou zaΦφnaje, biometrikami konΦe.');
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.
<UL STYLE="margin-right:50px;" Class=LinkItem><LI> <SPAN Class=CODE>Peggy (prover, "dokazovatel", ₧adatel) - mß jistou tajnou informaci</SPAN> a chce Viktorovi dokßzat ₧e ji mß, ni₧ by se ji on sßm dozv∞d∞l.</UL>
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
<UL STYLE="margin-right:50px;" Class=LinkItem><LI> 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φ.</UL>
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
<UL STYLE="margin-right:50px;" Class=LinkItem><LI> 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ß.</UL>
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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φ <SPAN Class=CODE>1:1</SPAN>, pak po <SPAN Class=CODE>n</SPAN> kolech je Üance, ₧e Peggy protokol obelstila <SPAN Class=CODE>1:2<sup>n</sup></SPAN>.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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φ).
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Viktor takΘ nem∙₧e podvΘst Peggy. To by se stalo v p°φpad∞, ₧e by postupoval v nesouladu s protokolem.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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.
