Amikor a tudatlanság ereje
Furcsa gondolat, hogy a matematika már majdnem száz éve tudja: vannak dolgok, amiket soha nem lehet bebizonyítani. Igaz állítások, amiknek nincs bizonyítása. Évtizedekig ezt gyengeségnek gondolták.
Aztán jött egy ötlet: mi van, ha ezt az ismeretlent használjuk fel valamire?
Pont ezt csinálták a kriptográfusok, amikor rájöttek, hogyan lehet bizonyítani, hogy tudunk valamit, anélkül hogy felfednénk. Ma már ez áll a modern titkosítások mögött.
A háromszínű rejtvény
Képzeljünk el egy bonyolult térképet. Színezzük ki három színnel úgy, hogy két szomszédos terület soha ne legyen egyforma színű. Nehéz feladat, de megoldható.
Most azt szeretnénk, hogy valaki elhiggye nekünk: tudjuk a megoldást. De ne mutassuk meg neki. Lehet, hogy az értékes. Lehet, hogy nem bízunk benne.
Sokáig azt hitték, ez lehetetlen. Vagy megmutatjuk a megoldást, vagy nem.
A nulla-tudás bizonyíték
1985-ben három kutató – Goldwasser, Micali és Rackoff – rájött, hogyan lehet ezt játékká alakítani.
A módszer egyszerű. Titokban kiszínezzük a térképet. Lefedjük az egész felületet, csak a határok látszanak. A másik fél egy véletlen határt választ ki, és kérdezi: „Mutasd meg ezeket a két területet.” Kinyitjuk őket. Ő ellenőrzi: valóban más színűek-e? Igen. Aztán újra lefedjük, és titokban átrendezzük a színeket.
Ezt százszor megismételjük. Minden alkalommal véletlenszerűen választ valaki. Ha mi hazudnánk, előbb-utóbb lebuknánk. De ha mindig átmegyünk a teszteken, a másik fél biztos lesz benne, hogy tudjuk a megoldást. Mégis semmi konkrétat nem látott.
Ez a lényeg: bizonyítunk valamit anélkül, hogy átadnánk belőle.
Az első korlátok
Évekig azt hitték, hogy ez a fajta bizonyítás csak kölcsönös beszélgetéssel működhet. Ha valaki csak egy papírt kapna, abból már kiszivároghatna minden. És ha titkosítanánk, akkor meg nem lehetne ellenőrizni.
1994-ben Goldreich és Oren matematikailag igazolták, hogy ez így van. Nem létezhet teljesen egyirányú nulla-tudás bizonyítás.
A váratlan fordulat
Aztán jött Rahul Ilango, egy doktorandusz. Összekapcsolta ezt a problémát Gödel 1931-es tételével.
Gödel bebizonyította, hogy minden matematikai rendszerben vannak igaz állítások, amiket a rendszer saját szabályaival nem lehet bizonyítani. A matematika alapvetően hiányos.
Ilango ötlete az volt, hogy ezt a hiányt használja ki. A titok nem abból származik, hogy a feladat nehéz. Hanem abból, hogy bizonyos dolgokat matematikailag nem lehet tudni.
Amikor Amit Sahai, a neves kriptográfus először látta Ilango munkáját, egyszerűen nem hitt benne. De működött.
Miért számít ez
A nulla-tudás bizonyítások már most is jelen vannak. Blockchainben használják, hogy tranzakciókat bizonyítsanak anélkül, hogy megmutatnák az összegeket. Bejelentkezésnél lehetnek, hogy valaki a jelszaváról tudjon,却