Lexiq

Zero-knowledge proof

A zero-knowledge proof (vagy magyarul nem feltáró bizonyítás) egy kriptográfiában használt módszer, aminek lényege, hogy valaki úgy bizonyítja másvalakinek, hogy tud egy dolgot, hogy az adott dologról semmilyen más információt nem ad ki.

Ha például van egy színvak barátod, és egy piros, valamint egy zöld golyód, és te be szeretnéd bizonyítani a barátodnak, hogy különböző színűek, anélkül, hogy elmondanád neki, hogy melyik a piros, és melyik a zöld, akkor ez megoldható nem feltáró bizonyítással. Ehhez kérd meg a barátodat, hogy vegye a két kezébe a golyókat, mutassa meg, hogy melyikben melyik van, majd rakja őket a háta mögé. Ezután szabadon dönthet arról, hogy megcseréli őket vagy nem. Mutassa meg ismét a golyókat, te pedig a színek alapján megmondod neki, hogy meg lettek‑e cserélve. Ha nem látnád a színeket, akkor 50% esélyed lenne arra, hogy eltaláld a helyes választ, mivel azonban látod őket, mindig helyes választ fogsz adni. Elég sokszor próbálgatva a tesztet a barátod egyre biztosabb lehet benne, hogy a golyók különböző színűek.

Egy másik ismert példában egy leendő főnöködnek szeretnéd bebizonyítani, hogy nagyon ügyes vagy a Where is Waldo? feladatokban, amikben egy nagy, összetett képen kell megtalálnod egy figurát. A főnököd nem hisz benne, hogy te tényleg képes vagy rá, te viszont nem akarod fizetés nélkül elárulni neki a megoldást. A nem feltáró bizonyítás ez esetben úgy néz ki, hogy fogsz egy, a Where is Waldo? feladatot tartalmazó képhez képest sokkal nagyobb lapot, kivágsz rajta egy kis lyukat, amin keresztül éppen látható a figura, és a lap mögé helyezed a képet úgy, hogy a lyukon át csak az általad megtalált figura legyen látható. Így a leendő főnököd látja, hogy megoldottad a feladatot, de maga a megoldás rejtve marad előtte.

Bővebben: Nem feltáró bizonyítások és alkalmazásaik (ELTE, pdf)