Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

Varázslók titkai – a nem feltáró bizonyítás

Varázslók titkai – a nem feltáró bizonyítás

Wettl, Ferenc


1. Varázslók titkai

1.1. Történet egy varázslóról

A régi korok nagy titkokat tudó varázslóinak nehéz volt a sorsa: egész életük félelemben telt, rettegtek, hogy kincsként őrzött titkuk kitudódik. A Nagy Zöld Sárkány uralkodásának 125. éve azonban olyasmit hozott, ami megváltoztatta a varázslók életét. Történt pedig, hogy Bebió, a „békából királyfit” varázsigéit olyan szintre fejlesztette, hogy bármilyen állatot szinte bármivé át tudott változtatni. A varázslás történetében először olyan varázsigét használt, ami minden alkalommal más, és más volt, szavai nemcsak az állat fajtájától, de még a nap pillanatnyi állásától is függtek. Egy este például hatalmas nézősereg előtt csak annyit mondott: „beáz nih lókista!”, mire a kezében tartott patkány kösöntyűvé vált. Kisvártatva így szólt: „viszka!”, s a patkány ismét ott ficánkolt ujjai között. Másnap reggel farkánál fogva lóbált egy hermelint, amiből a közönség kívánságára tepsi lett, amint kimondta a „röcsi hánya távé!” szavakat. A visszavarázsláshoz – mint mindig – most is elég volt csak annyit mondania: „viszka!”.

Reménytelennek tűnt, hogy akad aki megfejti e titkot. Voltak, akik nem is hittek Bebiónak, csalást szimatoltak. Azt sejtették, hogy Bebio csak a saját, varázsszerekkel előre preparált állataival mesterkedik. Ellea, a kétkedéséről ismert híres boszorka ravasz tervet eszelt ki. Sokak jelenlétében meghívta Bebiót saját tanyájára, hogy a következő hét minden napján napkeltekor, és napnyugtakor változtassa át azokat az állatokat, amiket ő tesz elé, s azzá, amit ő akkor kitalál. „Elhiszem, hogy nem olcsó bűvészmutatvány az egész, ha ezt az egyhetes próbát kiállod!” – mondta. Bebió kényszeredett mosolya jelezte, nehezen tud mit válaszolni. Ha visszautasítja a kérést, azt fogják gondolni, hogy csalás van a dologban. Ha elfogadja a meghívást, akkor arra számíthat, hogy gondosan megtervezett kísérletekben kell részt vennie, például ugyanazokat az állatokat kell majd többször hasonló körülmények között átváltoztatnia, így Ellea megtudhat valamit titkaiból. Bebió csapdába esett, nemigen mondhatott nemet, ha viszont igent mond, féltve őrzött titkai kerülhetnek veszélybe. Reménykedve, hogy a hátralévő napok alatt lesz még valami mentő ötlete, végül elfogadta a meghívást.

Bebió látta, a csapdából csak úgy mászhat ki, ha meg tudja győzni Elleát arról, hogy tudja a bármilyen állatból bármit varázslás titkát, de ezt nem az Ellea által előkészített állatokkal teszi. Sok töprengés után Bebió kitalált valami furfangosat. A következő ötlettel kereste fel Elleát:

– Ellea! Arra gondoltam, hogy amikor majd elém raksz egy állatot, én átmegyek vele egy másik szobába, ahol senki sem láthat, ott átváltoztatom a te állatodat valamilyen másik állattá. Ezután visszajövök, és ezt az állatot azzá változtatom, amivé te csak akarod. Így majd láthatod a varázslatot, de nekem sem kell félnem attól, hogy kifürkészel valamit a titkomból.

– Nem, nem! – válaszolta Ellea. – Lehet, hogy te csak a saját preparált állataiddal tudod a „varázslatot”. A másik szobában eltünteted az enyémet, és a tiéddel jössz vissza! Ez így nem varázslat, csak olcsó, gyerekeknek való régi trükk! Rotulfo Varázsdoboz I-ében van is egy ilyen játék fehér egér.

– Számítottam erre az ellenvetésre. Arra gondoltam, ha visszajövök az állattal, két lehetőséget kínálok fel neked. Egyik esetben arra kérhetsz, hogy a „viszka!” varázsszóval változtassam vissza az állatodat. Ha ezt választod, azonnal ellenőrizheted, hogy az állat valóban a tiéd-e, nem cseréltem-e ki a sajátomra. A másik lehetőséged az lenne, hogy megmondod mivé változtassam az állatot. Így meg azt ellenőrizheted, hogy tudom-e a varázslatot. Tehát ha én a saját állatommal állok eléd, te pedig azt kéred tőlem, varázsoljam vissza, le fogok bukni, ha pedig a te átváltoztatott állatoddal jövök vissza, de nem tudom a varázslatot, akkor nem leszek képes átváltoztatni azzá, amit kérsz. Ha rajtakapsz, világgá kürtölheted, hogy hazudtam.

– Nem, nem! Nem tetszik. Sosem lehetek biztos abban, hogy nem csak a szerencsén múlott-e az egész. Ha mindig épp akkor hozod a saját állatodat, amikor arra kérlek varázsolj, és pont akkor hozod vissza az enyém, amikor arra kérlek, változtasd vissza, nem fogsz lebukni!

– Ez igaz! Ha csak egyszer próbálkozunk, 1/2 az esélye, hogy ez történjen, de ha mondjuk 10-szer, akkor már 1 / 2 10 , azaz 1 / 1024 . De tőlem próbálkozhatunk 50-szer is. Ha nem tudom a titkot, így már csak 1 / 1 125 899 906 842 624 az esélye[10] annak, hogy nem bukom le. Ez a valószínűség már olyan kicsi, hogy még varázslók közt sincs reális esély a bekövetkeztére.

– Hmm. Én nem szerencsejátékra hívtalak, azért szerveztem meg ezt a hetet, hogy megtudjak valamit!

– Egy hét múlva vagy biztosan tudni fogod, hogy én csaló vagyok, vagy elegendően nagy biztonsággal azt, hogy valóban tudom a titkot! Gondolom a barátaid, sőt az ellenségeid is jelezték már, hogy tanui szeretnének lenni annak, ami a történni fog nálad a jövő héten. Ha valami kiderül a titkaimból azt ők is megtudják, s így hamar tudni fogja mindenki. Ha viszont úgy járunk el, ahogy javasoltam, te meggyőződhetsz róla, hogy tudom a titkot, ők viszont még ezt sem tudják meg. Azt hihetik, hogy összebeszéltünk, és te mindig épp azt kéred tőlem, amiben előre megállapodtunk. Amit látnak, nekik semmit sem fog bizonyítani! Meg fogja őket ütni a guta!

Ez az érv végre hatott, s a következő héten Bebió bebizonyította Elleának, hogy valóban tudja a titkot, Ellea pedig ellenőrizhette mindezt, s a bizonyítást elfogadta, amint a bizonyossághoz számára is elegendően közel értek! És ami Bebiónak olyan fontos volt: titkaiból sem Ellea, sem vendégei nem tudtak meg semmi használhatót.

Bebió e módszerének különféle változatait a varázslók azóta is használják, ha egy varázstitok ismeretét akarják úgy bizonyítani, hogy közben a lehető legkevesebbet tárják fel tudásukból. Az ilyen bizonyítást legkevésbé feltáró bizonyításnak nevezik. Ha a bizonyítás olyan, hogy abból egyáltalán semmi sem derülhet ki a titokról, akkor nem feltáró bizonyításról[11] beszélünk.

Bár közvetlenül nem vág írásunk témájába, megemlítjük a történet folytatását is. Ellea a következő hónapokban többször is meghívta tanyájára Bebiót hasonló nyilvános bemutatókra. Hamarosan elterjedt a pletyka, hogy Ellea összejátszik Bebióval. Ellea ugyan határozottan tagadta a vádat, de olyan megfejthetetlen mosoly kísérte szavait, ami jót tett a pletyka terjedésének. Aztán másfél év múlva Ellea feleségül ment Bebióhoz, ő pedig megosztotta titkait hitvesével.

1.2. Mit tanulhatunk a varázslóktól?

Titkaink nekünk hétköznapi embereknek is vannak, köztük olyanok is, melyek tudását nap mint nap bizonyítanunk kell. Gondoljunk csak a bankkártyára. Ahhoz, hogy pénzhez jussunk, be kell bizonyítanunk, hogy ismerjük a kártya pin-kódját. A módszer, amit jelenleg használunk, a lehető legprimitívebb. Kiadjuk teljes titkunkat, abban bízva, hogy a gépen keresztül senki nem fog hozzájutni. Jelenleg a legtöbb helyen ugyanez játszódik le egy központi számítógépre való belépéskor is. Begépeljük a saját azonosítónkat, majd saját jelszavunkat, amit a hálózaton, vagy a gépben számtalan módon el lehet lopni (mi pedig nyugodtak vagyunk, mert jelszavunkat nem látjuk kiíródni a képernyőre).

E dolgozat témája a kriptográfiának, azaz a titkosítás tudományának a nem feltáró bizonyításról szóló fejezete, mely az 1980-as évek közepén született. E téma tanulmányozása a matematika több területének elemi ismeretét igényli, ezek közül a legfontosabbak a számelmélet, az algoritmusok bonyolultságának elmélete és a valószínűségszámítás. Ennyi mindent e bevezető ismertetőben nem tudunk áttekinteni, ezért csak egy területre, a számelméletre koncentrálunk. Szükségünk lesz a számítási bonyolultság fogalmára. Erről bővebben esik szó Lovász László e könyvben megjelent cikke első részében. Azt fogjuk mondani, hogy egy számítási feladat hatékonyan vagy gyorsan elvégezhető, ha van olyan eljárás a feladat megoldására, melynek végrehajtásához szükséges idő bármely input esetén az input méretét jellemző számnak valamely polinomjával (például négyzetével) becsülhető. Ha egy számítási feladat megoldásához szükséges idő az input méretét jellemző szám exponenciális függvénye, akkor a számítási feladatot bonyolultnak fogjuk tekinteni. A továbbiakban ismertetendő titkosítási eljárások azon alapulnak, hogy egy konkrét számítási feladat jelen tudásunk szerint bonyolult (megoldása a gyakorlatban évszázadokig tartana a mai leggyorsabb számítógépekkel), míg valami további információ felhasználásával hatékonyan kiszámíthatóvá válik (a gyakorlatban pl. a másodperc törtrésze alatt).

A kriptográfia irodalmából csak két alapvető munkára, a [4] és [7] könyvekre hivatkozunk, melyek számtalan további hivatkozást tartalmaznak. Közülük a [4] könyv e mű írásakor az interneten legálisan és ingyen is elérhető. A magyar nyelvű kriptográfiai témájú könyvek közül kettőt említünk, Ködmön József [3] munkája az informatikai biztonság alapjaival és a PGP nevű titkosító rendszer használatával foglalkozik, míg Singh Kódkönyve a kriptográfia történetéről ad áttekintést [6].

E fejezet befejezéseként egy egyszerű, a kriptográfia népszerűsítő irodalmából ismert, matematikán kívüli nem feltáró bizonyítás megkonstruálását kérjük az Olvasótól.

1. feladat. A mellékelt térképen egy barlang járatai láthatóak. Az A pontnál van a barlang bejárata, B -nél egy elágazás, a két út C -nél egy körbe zárul, ahol egy kapu van. Az A pontból nem látszik B , és sem A -ból, sem B -ből nem látszik C . Bianka tudja a kapu kinyitásának titkos módját, Elemér nem. Hogyan bizonyíthatja Bianka Elemérnek, hogy ki tudja nyitni a kaput, ha nem akarja, hogy Elemér meglássa a kapu kinyitását. Mit tegyenek, ha ugyanakkor Elemér nem szeretné, ha a folyton nyomában járó, s minden lépését figyelő Fidél is meggyőződhetne arról, hogy Bianka tudja a titkot?

1. ábra.



[10] Bebió fiatal korában a nagy számok mágiájával foglalkozott, innen e varázslók közt ritka fejszámoló képessége.

[11] Angol nyelvterületről származó varázslók leggyakrabban a „zero knowledge proof” kifejezést használják e módszerre.