Hozzáadva: 2022. Június 04.
Olyan protokollokról lesz szó, amelyek lehetővé teszik egy bizonyító számára, hogy egy ellenőrzést végző félnek be tudja bizonyítani, hogy valamilyen ellenőrizhető titkos információ birtokában van anélkül hogy az ellenőrzést végző fél bármit is megtudna a titkos információról. A titok valószínűségi alapon és determinisztikusan is ellenőrizhető és elegendő megkötni azt, hogy vagy az ellenőrző vagy a bizonyító rendelkezzen véges számítási kapacitással. Ez a cikk a szerzők által már bemutatott módszereket egyesít és rendszerez valamint ezeket hasonlítja össze már meglévő munkákkal.
Tegyük fel, hogy Peggy be szeretné bizonyítani, hogy valamilyen információ a birtokában van. Lehet ez például egy feltevés bizonyítéka vagy egy nagy egész prímfelbontása. Azt is feltesszük továbbá, hogy a Peggy információja ellenőrizhető olyan értelemben, miszerint létezik egy módszer, amely bizonyítványt képes adni erről. Peggy ekkor Vic-et meg tudná győzni ha felfedné előtte az információt és Vic saját maga futtatná le az ellenőrző algoritmust. Ezt hívjuk “teljes felfedési” bizonyításnak, mivel így Vic mindent megtudna az információról. Ezek után Vic meg is mutathatná másnak is az információt és úgy kezelhetné mintha az a sajátja lenne.
Minimum Disclosure Proofs of Knowledge (Gilles Brassard, David Chaum és Claude Crépeau)
Ebben a munkában “minimális felfedési” protokollokról valamint azok implementációjáról lesz szó. Ezen protokollok lehetővé leszik Peggy számára, hogy meggyőzze Vic-et, hogy birtokában van valamiféle információ olyan módon, hogy csak minimális mértékben fedi fel azt. Például ha Peggy be tud bizonyítani egy tételt akkor Vic számára nincs más, mint hogy bízik abban, hogy ez tényleg így is van és ebből arra következtet, hogy a tétel helytálló, viszont Vic-nek gőze sincs a bizonyításról (max a hosszúságát tudja). Peggy tétele bizonyítható, viszont Vic meggyőződését nem tudjuk bizonyítani, hiszen ez hit kérdése. Ekkor a protokoll nem adhat lehetőséget arra, hogy Vic egy harmadik személyt is meggyőzzön.
A miminális felfedési protokoll ötlete a valószínűségi alapon ellenőrizhető információk ötletét egészíti ki. Képzeljük el például azt, hogy Peggy generál két egészt, ami nagy valószínűséggel prím. Ezeket valamilyen valószínűségi algoritmus adta ki. Peggy összeszorozza őket, publikálja és állítása szerint ismeri a prímfelbontásukat. Ekkor mondhatjuk-e azt, hogy Peggy valóban tudja egy nagy egész prímfelbontását ha még az sem biztos, hogy a számok amiket összeszorzott azok prímek? Ilyen esetben annak ellenére, hogy a bizonyító eljárása valószínűségi alapú van értelme annak, hogy Vic számára egy minimális felfedési protokoll segítségével bizonyít. A jelen munkában szereplő módszer a valószínűségi alapokon ellenőrizhető információk ötletére épít.
Az ötlet legfontosabb építőeleme szerint bitekhez kötik magukat a résztvevők. Peggy bit értékekkel kapcsolatban foglal állást olyan módon, hogy Vic ezekről ne tudjon Peggy segítsége nélkül. A bitekkel kapcsolatos állásfoglalást a jelen munkában “blob”-nak nevezik. Az eredményekből kiderül, hogy a blobok univerzális primitíveket jelentenek a minimális felfedési protokollok számára. Peggy minden blob segítségével vagy 0 vagy 1 mellett teszi le a voksát. A blob milyenségét ebben a munkában nem kötik meg, ha annak hasznossága bizonyított, akkor akár tündérporból is lehet őket csinálni. Amikor azt mondjuk, hogy Peggy egy blob mellett tette le a voksát, akkor azt értjük alatta, hogy Peggy fejében kialakult egy blob és a jövőben az alapján fog viselkedni, hogy ez reflektálódjon. Ha a blob egy bitsor (és általában ez a gyakorlati megvalósítása), akkor a voksolás egyszerűen annyi, hogy megmutatjuk a bitsorozatot. A blobokat a következő absztrakt módon lehet definiálni:
(i) Peggy leteheti a voksát egy blob mellett – ekkor biteket állít be magának
(ii) Peggy felfedheti bármelyik blobot: meggyőzheti Vic-et, arról hogy épp hogyan választotta meg a biteket. Ebből következik, hogy nem lehet felfedni egy blob-ot és azt mondani, hogy az 0 is volt meg 1 is
(iii) Vic nem tudja, hogy Peggy hogyan nyitja fel a blobokat, és ez még igaz marad a blobok felnyitása után is
(iv) a blobok nem hordoznak magukban egyéb más információt, sem belőlük sem a felnyitási folyamatból nem derül ki extra információ Vic számára a titokról
Vegyük például a következő megvalósítását a blobnak. Peggy szeretne állást foglalni egy bit értékével kapcsolatban. Anélkül hogy azt Vic láthatná felírja a padlóra és szigetelőszalaggal leragasztja azt. Vic ekkor nem tudja a szalag alatt lévő bit értékét és ekkor már Peggy sem tudja megváltoztatni. A blob felnyitását a szalag eltávolítása jelenti. A bit felírásának módja, a szalag és a pozíció nem hordoz semmilyen információt a titokról, amit Peggy nem szeretne elárulni Vicnek.
A következő részben feltételezzük, hogy ilyen blobok léteznek és megmutatjuk hogyan kell őket felhasználni minimális felfedési protokollok megvalósítására. A 2-es és a 3-as rész a determinisztikusan ellenőrizhető információkról szól. A 4-es részben bonyolultságelméleti bevezető található és az 5-ös részben egy általános protokolról lesz szó a valószínűségi alapokon ellenőrizhető információkról. A 6-os részben különböző feltételezéseket téve a blobok megvalósításáról beszélünk, majd ezek relatív megbízhatóságáról beszélünk. Kiderül majd az is, hogy ezen protokollok között vannak olyanok, amelyek feltétel nélkül megvédik Peggy információját, azonban bizonyos kriptográfiai feltételezéseket valós időben megdöntvén lehetőséget adnak Peggynek arra, hogy átverje Vic-et. Egy apró finomságot kell felfedeznünk abban, hogy a blobok nem feltétlenül kódolnak egyedi biteket. Erre a szigetelőszalagos példa sem hívja fel a figyelmet. Csak Peggy tudja, hogy mely bitek vannak kódolva. A duális blobos megvalósítások biztonságot jelentenek Vic számára, azonban ezek segítségével, lehet hogy csak nagyon hosszú idő elteltével, de elvileg fel tudja törni Peggy titkát. Az egyéb más implementációk nem rendelkeznek ezen hátrányokkal, de vagy kvantumfizikai dogmák kellenek hozzájuk, vagy további felek bevonását igénylik. Az utolsó szekciókban ezeket hasonlítjuk össze.
Ahogyan ezt gyakran tapasztalhatjuk a tudományban, az itt bemutatott módszereket egyéb más, független helyeken is fejlesztik. Rabin [R2] például beszél interaktív bizonyítási eljárásról. [GMR]-ben az ötletet formlizálják és egy tudást nem igénylő (zero knowledge) protokollt mutatnak itt be. [Ba]-ban egy hasonló interaktív bizonyítási eljárásról beszélnek. A [GMR, Ba] megoldások elméleti szempontból érdekesek, de a bizonyító oldalán végtelen számítási kapacitást feltételeznek. Ha feltesszük, hogy léteznek biztonságos valószínűségi alapú kódolási eljárások ([GM] módján), akkor [GMW] meg tudta mutatni, hogy minden NP-ben található nyelv rendelkezik tudást nem igénylő interaktív bizonyítási rendszerrel, amelyben a bizonyító egy valószínűségi alapú polinom idejű automata és ennek segéd bemenete egy NP bizonyítás. Ha erősebb megkötéseket teszünk akkor [BC1] is hasonló eredményeket hoz ki. [Ch4] ettől függetlenül hasonló következtetésekre jutott, viszont nagyon más modellt használt és a bizonyító titkának feltétel nélküli titokban tartását hangsúlyozza arra az esetre is ha az ellenőrzőnek végtelen számítási kapacitás áll rendelkezésére. Ezt a modellt [Ch2] dolgozta ki és [Ch4] eredményei a [Ch1] model speciális esetének tekinthetők, amelynek részleteit a [Ch2] taglalja. Végezetül pedig [BC2] egy olyan modellt mutatott be, amelyben minden résztvevőnek van elegendő számítási kapacitása. A jelen munka egyesíti ezeket a sémákat.
A modellek közötti különbséget a következő példával lehet szemléltetni. Vegyük megint Peggy prímfelbontásos példáját. A [GMR] modellben Peggynek nem kell idő tölteni azzal, hogy erről Vic-et győzködi, mert Vic számára ez egyértelmű bizonyítéka a korlátlan számítási kapacitásnak. A [Ch4] modellben amit kikerül a két prím szorzata a titkos felbontás már nem lesz feltétel nélkül biztonságos szóval akkor így akár úgy is meggyőzheti Vic-et, hogy átadja neki a számokat. Viszont abban az esetben ha Peggy csak azt állítja, hogy ismeri n nem triviális osztóit és n az néhány prím szorzata [Ch4] alapján Peggy meg tudná győzni Vic-et anélkül, hogy elmondaná, hogy melyik osztókat ismeri még akkor is ha Vic-nek korlátlan számítási kapacitás áll rendelkezésére. Ha a [Bc2] munkát vesszük azonban, akkor kiderül, hogy Peggynek mindenképp jó lenne egy olyan protokoll, aminek segítségével úgy tudja Vic-et meggyőzni, hogy közben nem árul el olyan információt, amely közelebb juttatná Vic-et a prímtényezős felbontáshoz. Vagyis a protokollt úgy tervezték meg, hogy Vic számára a prímtényezős felbontás legalább olyan nehéz legyen eleinte mint annak lefutása után.
A 7. részből pedig kiderül az is, hogy érdekes lehet megvizsgálni a felek számítási kapacitását a protokoll futása alatt és végén is. A jelen munka fő eredménye egy olyan protokoll, amely feltétel nélkül biztonságos akkor ha feltesszük, hogy Peggy nem képes egy nagy egész prímtényezős felbontását (vagy diszkrét logaritmust számolni, vagy mindkettő) megtalálni amíg a protokoll fut. Amit a protokoll lefut senkinek sincs lehetősége a csalásra, mindegy mennyi számítási kapacitás áll a rendelkezésükre. Ez az eredmény nagyon eltér [GMW,BC1]-től, amelyek NP teljes problémákkal foglalkoznak. Ezek lehetőséget adnak Vic-nek, hogy tetszőlegesen hosszú időt tölthessen Peggy titkának offline feltörésével.
Tegyük fel, hogy Peggy ismer egy boole-algebrai kifejezést az és azokat az értékeket, amelyek igazzá teszik azt. A protokollunk lehetőséget ad Peggynek arra, hogy ezt bebizonyítsá Vic-nek, anélkül hogy felfedné az értékeket. Itt nagyon hasonlóan járunk el mint [Ch4]. [GMW,BC2] is hasonló módszert mutat be, de [GMW] gráf színezési problémára vezet vissza, [BC2] pedig egyéb elvárásokat is támaszt a blobokkal szemben. Vegyük például a következő boole-algebrai kifejezést:
Psi = [(p és q) xor (q’ vagy r)] és [(r’ xor q) vagy (p és r’)]’
Peggy titkos megoldása pedig {p = igaz, q = hamis, r = igaz}. Ez egy játékos példa, mivel a megoldás túl egyszerű. Bárki meg tudja adni ezeket az értékeket néhány perc számolás után.
Az első lépésben Peggy és Vic megegyeznek egy boole hálózat tervében, amely megvalósítja a függvényt. Az egyszerűség kedvéért egyszerű bináris kapukat és csak negálást használunk az áramkörben. Természetesen a negálásra sincs szükség, hiszen bármely boole-algebrai képlet megvalósítható pusztán NAND kapukkal. A megvalósítás a következő ábrán látható:
Fent látható továbbá Peggy megoldása és az igazságtáblák is. Vegyük észre, hogy egy sor minden táblában ki van emelve. Ezek a sorok jönnek létre ha Peggy beadja az megoldását. A csak ezeket a sorokat tekintjük, akkor kiderül, hogy a fent definiált boole-algebrai függvény kielégíthető, csak egymástól függetlenül meg kell vizsgálni minden egyes vezetéket. A bal felső ÉS kapu kimenete 0 és valóban ez megy bele a középső KIZÁRÓ-VAGY kapuba. Látjuk továbbá, hogy a bal felső és a jobb felső kapuk bemenete azonos, hiszen ide ugyan azon bemeneti változó kell. Végezetül pedig az utolsó kapu kimenete 1. Vegyük észre azt is, hogy a kiemelt sorokat látván tisztában vagyunk az adott boole-algebrai kifejezést kielégítő bitkombinációkkal (még akkor is ha az nincs leírva). A jelen protokoll lehetőséget ad arra, hogy Peggy meggyőzze Vic-et arról, hogy tudja hogyan kell kiemelni a sorokat, anélkül hogy elárulná melyek azok.
Ezt egy interaktív megoldással tudjuk elérni, amely több lépésben zajlik. Peggy minden körben összekeveri az adott áramkör igazságtábláját és állást foglal az adott blobok mellett. Ekkor Vic a következő két kihívás közül egyet választ és Peggy-nek szegezi:
1. Peggy-nek meg kell mutatni, hogy a blobok valóban egy hiteles keverését kódolják az igazságtáblának.
2. Feltételezvén, hogy a keverés hiteles Peggynek fel kell fednie a kiemelt sorokat.
Ezeket a kihívásokat tehát úgy terveztük meg, hogy Peggy csak akkor tudjon rájuk érdemben válaszolni, ha valóban ismeri a boole-algebrai kifejezés megoldását, viszont akkor amikor az egyikre válaszol, akkor az adott válasz nem mond el semmit a megoldásáról. Továbbá mivel Peggy sosem tudja megjósolni, hogy Vic épp melyik kérdést fogja feltenni Vic bizalma Peggy-ben minden egyes körrel nő. Valójában Peggy-t minden egyes körben 50%-os valószínűséggel csaláson lehet érni ha nem képes válaszolni a két lehetséges kérdésre. k körben tehát 2^(-k) exponenciálisan csökkenő valószínűséggel tudja majd átverni Vic-et.
Az ilyen jellegű megoldásokat “te-vágsz-én-választok” technikáknak hívjuk, mert ez nagyon hasonló ahhoz, mint amikor két gyerek tortát vág fel. Ami ebben nagyon jó, az az hogy a körök számának lineáris növekedésével a biztonság exponenciálisan nő. Az általunk ismert első ilyen protokollokat Rabin dolgozta ki 1977-ben [R2].
Az igazságtábla összekeverése Peggy által a következő módon történik. Peggy véletlenszerűen összekeveri a sorokat és negálja az oszlopokat. A következő ábrán egy ÉS kapu (2a) összekeverése látszódik:
A 2b. táblázat a megkevert sorokat mutatja be. A 24 lehetséges keverésből egyenlő valószínűséggel választunk. Ezek után 1 bitet véletlenszerűen kiválasztunk az igazságtábla 3 sorából. Végezetül pedig minden oszlopot negálunk, de csak akkor ha a kiválasztott bit 1 volt benne. Ez a folyamat a három középső táblában látható. A végső tábla a 2c ábrán látható. Vegyük észre, hogy az összekevert igazságtábla továbbra is félreismerhetetlenül reprezentálja a boole-algebrai összefüggést ha a negáló biteket úgy valósítjuk meg, ahogyan azt az ábra mutatja.
A negálást konzisztens módon kell megváltoztatni. Vagy minden oszlopot negálunk, amely azonos vezetékhez csatlakozik, vagy minden marad a régiben. Ezt úgy érhetjük el ha mindent vezetékhez véletlenszerűen és függetlenül választunk negáló bitet. Az egyszerűség kedvéért a végső kimenetet sosem negáljuk. A következő ábrán látható az eredeti áramkör véletlenszerű keverése és negálása:
A fenti ábrán látható módon tehát egy új áramkört generálunk és Peggy emelett teszi le a voksát, vagyis minden egyes bitet lerögzíti magának. Peggy továbbá megválasztja a felnyitható blobokat is. A negálások mellett nem kell állást foglalnia a jelen pillanatban, de ezeket titokban kell tartani. Ha megint vesszük a szigetelőszalagos példát, akkor ez olyan mintha Peggy felrajzolnál a fenti ábrát a padlóra, de Vicnek elől eltakarná a biteket az ábrán. Peggy ezzel tehát felvágta a tortát és most Vic vághat. Ekkor Vic próbára teheti Peggy-t a következő 2 féle kihívással:
(i) Kihívás A: Peggy-nek fel kell nyitnia minden egyes blobot, amik mellett állást foglalt. Továbbá fel kell fednie a negáló biteket is, amiket a keverési folyamat során használt. Peggy tehát olyan mintha felszedné a leragasztott szalagokat a fenti ábráról. Ezzel Vic le tudja ellenőrizni a szalagok alá rejtett információ helyességét, ergó azt, hogy ezek helyes permutációkhoz és negálásokhoz tartoznak az adott boole-algebrai igazságtáblában.
(ii) Kihívás B: Peggy csak az egy sorhoz tartozó blobokat nyitja fel. Itt azokra a sorokra lesz szükség, amiket az első ábrán jelöltünk meg, vagyis azokra a helyekre, amiket a véletlenszerű permutáció kijelöl. Ez egyenértékű a következő ábra felfedésével:
Vic tehát ellenőrzi a vezetékek konzisztenciáját és azt is, hogy az áramkör végül 1-et ad ki.
A következő három tulajdonságnak kell teljesülni a protokoll helyes működéséhez. A következőknek kell teljesülni (vagy exponenciálisan csökkenő valószínűséggel nem teljesülni):
(i) Peggy képes minden lépést végrehajtani ha ismeri a boole-algebrai formulát kielégítő kombinációt. Természetesen egyetlen protokoll sem képes Vic-ek kötelezni arra, hogy elhiggye azt amit Peggy mond, még akkor sem ha megadják neki a helyes kombinációt mert dönthet úgy hogy nem hallgatja meg azt.
(ii) Ha Peggy nem ismeri a helyes kombinációt, mindegy mennyire is próbálja követni a protokollt, Vic egyszer úgy is csaláson fogja érni.
(iii) Ha Peggy ismeri a helyes kombinációt és a mindent a protokoll szerint csinál, akkor Vic számára semmi nem derül ki a titokból (még részben sem) és ez igaz akkor is ha Vic tetszőleges mértékben megpróbál eltérni a protokolltól.
Az első és a második feltétel segítségével Peggy blobok mellett tud állást foglalni és lehetősége van azokat felnyitni, amikor úgy adódik. Továbbá bárki össze tudja keverni az igazságtáblákat és negálhatja az oszlopokat. Ha Peggy ismeri a helyes kombinációt, akkor képes az összekevert táblákban is kijelölni a megfelelő sorokat. Ehhez csak meg kell jegyeznie, hogy mely oszlopok lettek negálva és követnie kell hogy hova kerültek a permutáció során az eredetileg kijelölt sorok. Az első feltétel tehát teljesül.
A második feltétel teljesül a blobok (ii) tulajdonsága folyamán. Tegyük fel, hogy Peggy nem ismeri a helyes kombinációt. Minden körben leteheti voksát az igazságtábla egy valós sora és egy valós permutáció mellett vagy megpróbálhat csalni. Az első esetben a B kihívásra nem fog tudni érdemileg válaszolni hacsak nem tudja a helyes boole-algebrai kombinációt. A második esetben az A kihívásra nem tud válaszolni anélkül hogy ellentmondana a blobok tulajdonságainak. Így tehát ha feltételezzük, hogy nem képes megjósolni, hogy Vic épp milyen kérdést fog neki feltenni minden körben legalább 50% lesz a valószínűsége annak hogy tetten érik. Ahogyan már említettük tehát, k egymást követő körben 2^(-k)-on lesz legjobb esetben annak a valószínűsége hogy nem csípik fülön.
A harmadik feltétel bebizonyítása kicsit nehezebb. Első körben tegyük fel, hogy Vic nem szerezhet meg számára semmilyen hasznos információt a boole-algebrai kifejezésről csupán a 3-mas vagy a 4-es ábra ismeretével azon kivül, hogy megtudja, hogy Peggy ismeri őket. Ekkor ha Vic az A kérdést teszi fel, akkor válaszként az egy véletlenszerűen permutált és negált igazságtáblát kap. Ezzel Vic semmit nem tud kezdeni, hiszen akár ő maga is előállíthatta volna. Még akkor is ha a boole-algebrai kifejezésnek nincs megoldása. Másfelől ha Vic a B kérdést teszi fel, akkor a 4-es ábrát fogja visszakapni. Ezen Peggy egyszer használatos értékei lesznek, amik segítségével a vezetékek olyan értékeket vesznek fel, amelyek kielégítik a kifejezést. A kimeneti vezeték értéke mindig 1. Mivel az ilyen egyszer használatos érték kombináció minden más információt elrejt, ennek segítségével Vic nem tudja meg a kifejezést. Más szóval Vic csak akkor tudna meg valamit a kifejezésről ha egy körben meglátná mind a 3-mas mind a 4-es ábrát, de Peggy természetesen egy körben mindig csak egy kérdésre fog válaszolni.
A blobok (iii) tulajdonságából következik az is, hogy Vic amikor a B kérdést teszi fel és rá válaszként a 4-es ábrát kapja meg nem tudja azt összepárosítani a 3-mas ábrával. A (iii)-as tulajdonság nem lényeges, amikor Vic az A kérdést teszi fel, mert ekkor Peggy felnyitja az összes blobot. Végezetül pedig a (iv)-es tulajdonságból fakadóan Vic számára a titokból semmi nem derül ki akkor amikor Peggy blobokat választ és azokat később felnyitja.
A harmadik feltétel teljesüléséből még nem következik az, hogy Vic abszolút semmit nem tud meg Peggyről. A helyes bitsorozatot ugyan nem tudja meg, de lehet például az is, hogy csak Peggy rendelkezik annyi számítási kapacitással, hogy megtalálja a formula kielégítséhez szükséges bitkombinációt. Ekkor például Vic olyan információ birtokába jut, amit maga nem tudott volna kisilabizálni. Egy érdekes helyzet áll elő, amikor is az ellenőrzést párhuzamosan végezzük: Peggy egyszerre választ blobokat k áramkörnek megfelelően és megkapja a 3-mas ábrát. Vic egyszerre elküldi a kérdéseit és Peggy felnyitja a kérdéses blobokat. Ez az eljárás bizonyos esetekben hatékonyabb lehet. Az ilyen módon módosított protokoll tehát lehetőséget ad Vic-enk arra, hogy a kérdéseit a megkapott összes blob függvényében tegye fel. Ettől még nem tud meg semmit Peggy titkáról, viszont lehetőség nyílik arra, hogy meggyőzzön másokat arról hogy a boole-algebrai formula kielégíthető. Ehhez csak meg kell mutatni a kommunikációs logokat Peggyvel. Más szóval ez a protokoll minimális felfedésű viszont lehet hogy nem teljesíti a 0-tudáscsere (zero knowledge) tulajdonságot, ahogyan az [GMR]-ben van definiálva.
Intuitívan azt mondhatjuk tehát, hogy egy protokoll akkor 0-tudáscsere tulajdonságú ha a harmadik tulajdonság olyannyira teljesül, hogy Vic azon kívül, hogy megtudja hogy Peggy ismeri a helyes bitsorozatot semmi mást nem tud meg. Ha precízebben akarunk fogalmazni, akkor Vic-nek anélkül kell tudnia szimulálni az egész kommunikációs folyamatot, hogy valaha is beszélt volna Peggyvel. A [GMR]-ben erre formális definíciót találunk. Ettől függetlenül az itt felvázolt protokoll 0-tudáscsere típusú ha a blobok (iv) tulajdonsága meg van erősítve és ezzel Vic számára semmi nem derül ki csupán abból hogy Peggy blobokat választ és Vic csak és kizárólag a neki szánt biteket szerzi meg akkor amikor Peggy felnyitja azokat. A [GMR] bizonyítási módszerét követvén a blobokat szimulálhatónak hívjuk akkor ha a (i), (ii), (iii) és (iv) tulajdonságok mellett a következőt is teljesítik:
(iv’) Vic képes szimulálni azt, hogy mit kapott volna ha Peggy blobokat választ, amiket később 0 vagy 1-ként fed fel. Képes továbbá szimulálni a folyamatot, amelynek során Peggy felnyitja a blobokat miután azokat megválasztotta.
Vegyük észre, hogy ez az új tulajdonság magában foglalja a (iv)-es tulajdonságot, mivel Vic képes kell hogy legyen szimulálni a megválasztott blobokat valamit azok felnyitását akkor is ha nem is ismeri Peggy titkát. Ha szimulálható blobokat használunk tehát, akkor Vic könnyen tudja szimulálni a protokoll lépéseit, anélkül hogy Peggyvel beszélne. Ekkor 50% valószínűséggel nem fogja eltalálni a helyes megoldást. A protokollt ekkor a következő módon hajthatjuk végre:
(i) Vic feldob egy érmét és ha fej, akkor az A kérdést teszi fel, ha írás, akkor a B-t (ii) az érmefeldobás eredménye alapján vagy a 3-mas vagy a 4-es ábrát generálja le (iii) ekkor a (iv’) tulajdonásgot használva szimulálja hogy Peggy hogyan választana blobokat és hogy hogyan nyitná fel azokat hogy meg tudja mutatni vagy a 3-mas vagy a 4-es ábrát (iv) majd felteszi magának őszintén azt a kérdést, hogy most melyik kérdést tenné fel Peggynek miután megkapta a Peggy által választott blobokat (v) ha olyan kérdést tett fel, amire tud is válaszolni, akkor szimulálja azt, hogy Peggy felnyitja a blobokat, máskülönben elbukik
Itt a legfontosabb mozzanat az, hogy a blobok (iii) tulajdonságából fakadóan nincs korreláció a Vic által saját magának feltett kérdés és a saját maga által megválaszolható kérdés között. Ha a k körös protokollt szeretnénk lejátszani, akkor a fentiekben felvázoltakat 2k-szor kell megismételni, úgy mintha a szerencsétlen kimenetelek nem történtek volna meg.
Ez az indoklás a protokoll párhuzamos variációjával kapcsolatban nem állja meg a helyét. Az egyszerűség kedvéért tegyük fel hogy a blobokat bitsorokkal valósítjuk meg és hogy Peggy úgy választja őket hogy közben meg is mutatja azokat. Vegyük a következő stratégiát Vic számára: miután megkapta a véletlenszerűen összekevert és negált igazságtáblákat valamint a k áramkörhöz tartozó blobokat Peggytől összefűzi a blobokat és egy nem invertálható függvény bemeneteként felhasználja őket, majd a kimenet k bitjéval eldönti azt a k darab kérdést, amit fel fog tenni Peggynek. Vic megpróbálhatja úgy formálni ezt a technikát hogy az a protokoll működését szimulálja, de ekkor a nem invertálható függvény de így függőség jön létre az általa megválaszolandó kérdések és a valóban feltettek között és ez exponenciálisan csökkenti a siker valószínűségét. Igaz ugyan, hogy a protokoll nem segít Vic-nek megtudni semmilyen információt Peggy titkáról, azonban a lefolytatott beszélgetés kivonata segítségével másokat meg tud győzni a titok létezéséről, mert a kivonat nagyvalószínűséggel csak így keletkezett. Ez egy érdekes jelenséghez vezet minket. A beszélgetés kivonata Shannon információ [S] elmélete szerint értelemben nem árul el ugyan információt Peggy titkáról amikor a protokollt párhuzamosan hajtjuk végre, de ettől még fel lehet használni arra hogy egy harmadik személynek bebizonyítsuk a titok létezését. Más szavakkal élve, a protokoll párhuzamos verziója minimális felfedésű, viszont lehet hogy nem 0-tudáscserés még akkor sem ha szimulálható blobokat használunk.
Ha valakinek fontos a párhuzamos végrehajtás, mondjuk hatékonysági érvek szólnának emellett, akkor a protokollt lehet 0-tudáscseréssé tenni, de ehhez a (iv)-es tulajdonságot kell erősíteni. Kaméleonnak hívjuk az olyan blobokat, amelyek az (i), (ii) és az (iii) mellett megfelelnek a következő feltételeknek is:
(iv’’) Vic képes szimulálni a Peggy blobválasztási folyamatát és Vic szimulálni képes mind azt is, amikor Peggy egy 0-s és mind azt is amikor egy 1-es blobot nyit fel.
Más szavakkal élve a kaméleon blobok Vic számára lehetővé teszik azt, amit a (ii)-es tulajdonság meggátol Peggynek. A 6.1-es szekcióból ki fog derülni az is, hogy ha Vic és Peggy nagyjából hasonló számítási kapacitással rendelkeznek, akkor ez a tulajdonság megvalósítható. A kaméleon blobok előnye abban rejlik, hogy Vic így képes a Peggyvel folytatott teljes párbeszédet lefolytatni úgy hogy közben nem éri hiba a rendszert és ez akkor is igaz marad ha Vic el akar térni az előírt működéstől. A jelen tárgyalásmódban azonban erre csak egy lehetőség van ha feltesszük hogy Peggy nem szakítja meg a protokollt mégpedig az ha a kérdéseket Peggy blobválasztásaihoz igazítva és nem pedig véletlenszerűen teszik fel. Ettől függetlenül ha kaméleon blobokat használunk akkor ennek a stratégiának Vic számára nincs semmi haszna.
A protokoll működését a következő módon lehet szimulálni: Vic legenerál annyi kiválasztott blobot, amennyit Peggy szeretne használni. Mivel kaméleon blobokról van szó Vicnek nem kell állást foglalni azzal kapcsolatban, hogy Peggytől milyen válaszokat fog majd várni. Ekkor Vic rápillant ezen választásokra és olyan módon választja meg mintha azok igazándiból Peggy-től jöttek volna. Amikor az A kérdést tenné fel, akkor az igazságtáblákat véletlenszerűen összekeveri és megnegálja hogy így egy olyan képet kapjon mint a 3-mas ábra, majd felnyitja a megfelelő blobokat. Amikor pedig a B kérdést választja, akkor minden táblában kiválaszt egy sort és minden boole-algebrai változónak ad egy értéket a vezetékeken. A kimenet mindig 1. Ezek után az adott sorokban felnyitja a blobokat, úgy hogy azok tükrözzék a vezetékeknek választott értéket. Így a 4-es ábrához hasonlót fog kapni.
Mivel a boole-algebrai kifejezések kielégíthetőségének problémája NP teljes [Co, GJ] a fentiekben felvázolt protokollt egy NP-ben található tetszőleges nyelvre fel lehet használni, hogy abban tudásról minimális felfedési bizonyítékokat adhassunk meg. L legyen tetszőleges bináris sorozatok halmaza. Az NP definíciójából következik, hogy létezik egy bizonyítási rendszer, amely:
Vagyis amikor x benne van L-ben, akkor létezik egy tömör bizonyíték “c”, amely teljesíti ezt a feladatot és ennek valódiságát bárki gyorsan le tudja ellenőrizni és ezzel bizonyítja hogy x benne van L-ben. A jelen munka kifejezéseivel élve c egy olyan ellenőrizhető információ, amely arról tanúskodik hogy x része L-nek. Cook elméletét felhasználva [Co] Peggy és Vic is gyorsan tudnak olyan boole-algebrai kifejezést generálni, amely kielégíthető és ez csak akkor igaz ha x része L-nek. Továbbá mivel Crook bizonyítása egymásra épül, elég ha Peggy ismer egy tömör c-t, úgy hogy {x,c} benne legyen Q-ban és ekkor gyorsan le tud vezeti magának egy a boole-algebrai kifejezést kielégítő bemenetet.
Szóval ha L benne van NP-ben, x része L-nek és Peggy birtokában van egy tömör c, amely azt bizonyítja hogy x benne van L-ben, akkor Peggy a fent felvázolt protokoll segítségével Vic-et meg tudja győzni a boole-algebrai kifejezés kielégíthetőségéről, vagyis arról hogy x benne van L-ben és Peggy ismeri ennek a bizonyítását. Ez így egy minimális felfedési protokoll, feltételezvén persze hogy Vic ismeri az L-hez szükséges bizonyítási rendszert és a jelen protokollt, máskülönben túl sok információ jutna birtokába akkor amikor Peggy kommunikál vele. A gyakorlatban jobban járunk ha egy speciálisan erre a feladatra tervezett ad hoc áramkört használunk az ellenőrzésre, semmint hogy egy a Cook eredményeit megvalósító masinát használnánk.
Ahogyan ez [FFS]-ben is ki van emelve lehet, hogy érdemes lenne az ilyen protokollokat nem 0-tudásátadásosoknak hívni, mert Vic valóban birtokába jut némi tudásnak. Ebben az esetben például megtudja, hogy x benne van L-ben. [GHY]-n alapulva mi inkább a minimális felfedési protokoll elnevezést alkalmazzuk, mivel Vic megtudja hogy x benne van L-ben, de annak bizonyításáról nem tud meg semmit. Továbbá a felfedés kifejezést és nem a tudást kifejezést használjuk, mert Vic megtudhat egyéb más információkat is, akkor amikor a protokollt párhuzamosan hajtják végre vagy a blobok nem szimulálhatók.
Érdemes lehet az NP-re vett megszorításokat és kiegészítéseket is áttekinteni a minimális ismeret birtok bizonyítékokkal együtt áttekinteni.
Az egyik érdekes megszorítás lehet ha az L az NP és a co-NP metszetében van. Ebben az esetben bárki könnyedén tud generálni két olyan boole-algebrai formulát Al(x)-et és Bl(x)-et, amelyek közül az egyik kielégíthető ha x benne van L-ben és a másik kielégíthető ha x nincs benne L-ben. Világos, hogy Cl(x) = Al(x) vagy Bl(x) mindig kielégíthető. Tegyük fel most, hogy Peggy tudja, hogy x benne van-e L-ben és erről van is egy NP bizonyítéka. Így tehát is meri vagy Al(x) vagy Bl(x) helyes bitsorozatát és így Cl(x)-t is meg tudja oldani. Nézzük meg mi történik akkor, amikor az itt felvázolt protokollt arra használja, hogy meggyőzze Vic-et arról, hogy ismeri Cl(x) megoldását. Ez biztos hogy semmit nem fog elárulni Vic-nek x-ről, mert Cl(x) mindig megoldható. Ettől függetlenül Vic meg tud győzödni arról, hogy Peggy tudja, hogy x része-e L-nek vagy nem. Ez a megoldás [FFS]-ben van felvázolva és ott használják, de az ilyen rendszereket körültekintéssel kell implementálni, mert nem mindig biztonságosak [BBDGQ].
A minimális felfedési protokollokat az NP-nél tovább is kiterjeszthetjük ha a bizonyító eljárást valószínűségi alapokra helyezzük. Emlékezzünk vissza, hogy a BPP rövidítést olyan eldöntési feladatok osztályára használtuk, amelyek valószínűleg polinom időben megoldhatók és korlátos hibavalószínűséggel rendelkeznek [G]. Jó okunk van tehát a BPP-t a kezelhető problémák tényleges osztályaként való kezelésére (P helyett), mivel a hiba valószínűsége tetszőlegesen lecsökkenthető (delta) ha az algoritmust alpha * log (delta^(-1))-szer ismételjük és a többségi választ vesszük eredményként. Itt az alpha konstans kizárólag az eredeti véletlenszerű hiba valószínűségétől függ. A matematikusok általában úgy gondolják, hogy az NP és a BPP osztályok között nincs beillesztési reláció, avagy a determinizmus hiánya és a véletlenszerűség összehasonlíthatatlan erőknek bizonyulnak. Ezeket az erőket különböző módokon kombinálhatjuk. Babai László osztálya Ma [Ba] legyen a legtermészetesebb és ezt mi inkább NBPP-nek hívnánk. Ezt Babai László úgy hozta létre, hogy az NP és a BPP osztályok uniója benne van NBPP-ben és ebből következik, hogy az NP osztály mindig szigorúan részhalmaza NBPP-nek.
Az NBPP osztály pontosan ugyan úgy lehet definiálni mint az NP-t, azzal a különbséggel hogy megelégszünk egy BPP algoritmus létezésével, amikor azt döntjük el, hogy egy adott x és c esetén ezek benne vannak-e Q-ban (vagyis Q legyen benne BPP-ben). Amikor pedig ez teljesül, akkor c-re úgy hivatkozunk mint egy meggyőző erővel bíró érvelés arról, hogy x benne van L-ben. Ekkor már nem hívhatjuk bizonyítéknak, mert nem lehet leellenőrizni.
Az 5. szekcióban megmutatjuk hogyan lehet közel minimum felfedési protokollokat tervezi az NBPP-ben lévő bármely nyelv számára. Ahogyan mindig is, most is feltesszük, hogy Peggy és Vic épeszű számítási kapacitással és hasonló algoritmikus tudással rendelkezik, viszont azt is feltesszük, hogy Peggy először egy tömör érvelést kap arról, hogy x benne van L-ben. Ezzel Peggy minden kétséget eloszlatva meg tudja magát győzni, hogy x valóban benne van L-ben azzal ha lefuttatja a BPP algoritmust {x,c}-n. A protokollunk célja tehát az hogy Peggy meg tudja győzni Vic-et arról, hogy birtokoában van egy c és mindeközben nem fecseg ki semmit a birtokában lévő információról.
Az NBPP osztály Babai László MA osztálya. Ezt ő az “Arthur-Merlin” játékai [Ba] céljára hozta létre és ez nagyon hasonló Papadimitriou sztochasztikus kielégíthetőségi problémájához a természet elleni játékok-ban [Pa]. Babai szerint a másik osztálya, az AM egy sokkal jobb variáns az NP általánosításához valószínűségi számításokhoz. Igazándiból Babai László be is bizonyított, hogy MA része AM-nek. Egyre többen érdeklődnek az AM osztály iránt, mióta bizonyítást találtak arra is, hogy bármely k-ra, ami nagyobb mint kettő az AM megegyezik IP(k)-val. IP(k) val jelölik az olyan interaktív protokollokat, amelyek maximum k körös információcserét igényelnek [GS]. Ezek az eszmefuttatások elméleti szempontból nagyon érdekesek lehetnek.
Azt is állítjuk továbbá, hogy ezektől függetlenül az MA (vagyis az NBPP) egy sokkal természetszerűbb osztály lehet a gyakorlati felhasználások szempontjából, vagy legalább is kriptográfiai szempontból. Ha egy L benne van NBPP-ben és x része L-nek, Peggy-nek elegendő ismernie egy tömör meggyőző érvelést ( c ) ha bizonyítani szeretne. A gyakorlatban Peggy számára természetesen nem Isten fogja adni ezt a c-t. Ahogyan már említettük az előbb is, bizonyos nyelvek esetében x-et és c-t is könnyedén lehet generálni valószínűségi algoritmusokkal. Vegyük például az olyan egészek halmazát, amelyeknek mindösszesen 2 prím osztója van. Peggy ekkor vesz két prímet, amelyek számára elfogadható módon átmennek egy valószínűségi prímtesztelésen [SS, R1], így meggyőződik arról, hogy n = pq benne van B-ben és számára a meggyőző érvelést {p,q} jelenti. Az 5-ös szekcióban felvázolt protokoll segítségével Peggy meg tudja győzni Vic-et arról, hogy n benne van B-ben, anélkül hogy annak prímtényezős felbontásáról bármit is elárult volna. Ebben az esetben B NP része, mert a prímek halmaza NP-ben van [Pr], de ez még nem von le semmit a mi ötletünk gyakorlati felhasználásából, hiszen Peggy valószínűleg nem fogja tudni az NBPP érvelését {p,q} NP bizonyítékká {p, c(p), q, c(q)} konvertálni. Itt c(*) egy olyan NP bizonyítékot jelöl, ami az argumentumról elárulja, hogy az prím. Ez a gondolat igaz marad a gyakorlatban még akkor is ha az [GK, AH] eredményeket vesszük figyelembe.
A fentiek ellenére Peggy-t valószínűleg nem lehet megkérni arra, hogy egy AM protokollt hajtson végre, még akkor sem ha figyelembe vesszük a minimális felfedési tulajdonságot és akkor sem ha az első lépésben valamiféle tippet adunk neki. Egy AM protokoll általánosságban Peggy-től megkövetelné azt, hogy előállítson egy NP jellegű bizonyítékot, amelynek bemenete egy Vic által előállított véletlenszerű karaktersorozat lenne. Ez sajnálatos, hiszen a mi általunk kidolgozott protokoll segítségével bármely AM protokollt át lehet konvertálni egy minimális felfedési protokollá. A [GMW] magyarázata alapján miután Arthur feldobott egy érmét Merlin számára Merlin-nek már csak egy NP állítás megoldását kell elmondania. Ezt meg tudja tenni minden további információ felfedése nélkül ha a második részben kifejtett protokollt használja szimulálható blobokkal.
Vegyünk egy tetszőleges nyelvet NBPP-ből. Legyen továbbá x egy olyan állítás, amelyről Peggy ismer egy c-t és ez bizonyítja, hogy x benne van L-ben. Mivel c ugyan nem egy NP bizonyíték Peggy nem lehet 100%-ban biztos arról, hogy x valóban benne van L-ben, de BPP segítségével a hiba valószínűségét tetszőlegesen alacsony szintre le tudja szorítani. A minimális felfedési protokoll lényege abban rejlik, hogy Peggy úgy győzi meg az állításáról Vic-et, hogy az közben semmit nem tud meg az érvelésről és nem kap segítséget ahhoz, hogy valamilyen módon meg tudja azt később állapítani. Ha a felhasznált blobok szimulálhatók, akkor ezt a folyamatot “nem tranzitív bizalom átruházásnak” hívjuk, mivel ez képes Vic-et meggyőzni arról, hogy x benne van L-ben (erről Peggy már maga meggyőződött), de Vic ezek után mást erről már nem tud meggyőzni. Nyilván Vic-et sokféleképp át lehet verni ezzel a protokollal. Peggy hazudhat is. Ekkor ha szerencséje van, minden körben olyan kérdést tesznek fel neki, amire tud válaszolni. Ennek a valószínűsége exponenciálisan csökken (hasonlóan a determinisztikus esethez). Lehet tovább az is, hogy Peggy nem szeretne hazudni, de a BPP algoritmus átverte őt. Ebben az esetben nagyon valószínű, hogy Peggy rá fog jönni a hibára miközben megpróbálja meggyőzni Vic-et, de az is lehet, hogy a bizonyítási algoritmus hibázik majd megint. Végezetül pedig az is elképzelhető, hogy Peggy őszinte, helyes az állítása is, viszont a Vic-el való kommunikáció során a bizonyítási algoritmus hibázik.
A legelső lépésben Peggy és Vic meg kell hogy egyezzenek egy hiba határban. Ekkora hibát fognak tolerálni a bizonyítási algoritmusban. Ezzel a megegyezéssel úgy módosítják az eredeti algoritmust, hogy annak várható hibája ne legyen nagyobb, mint az előre definiált küszöb. A [BB] alapján megválasztják azt a szükséges ismétlési számot, ahányszor az eredeti algoritmust le kell futtatni, hogy a válasz minden bizonnyal helyes legyen. Innentől kezdve a teljesség igényével mondhatjuk, hogy a bizonyítási algoritmus hibája elhanyagolható.
Igazándiból arról van szó, hogy Peggy meg szeretné győzni Vic-et arról, hogy ismer egy olyan titkos bemenetet ( c ), amelyet a bizonyító algoritmus x-el nagy valószínűséggel el fog fogadni. Legy n x mérete és m c mérete. Az általános esetre is vonatkoztatva tegyük fel, hogy m egyértelműen kiszámolható n-ből és emiatt a protokollnak nem kell m-et elrejtenie Vic elől. Legyen továbbá r a felső korláta azon pénzérem feldobásoknak, amelyet a bizonyító algoritmus bármilyen {x, c’}-on el tud végezni, ahol c’ m méretű. Ha hasonlóan gondolkodunk, mint Crook, akkor rájöhetünk, hogy így egy olyan boole-algebrai kifejezést kapunk, amelynek legalább m+r változója lesz. Ha a kifejezés első m változója c-t reprezentálja és a következőr változót egymástól független pénzérme feldobással határozzuk meg, akkor a maradék változókat (ha egyáltalán kell) könnyedén megválaszthatjuk úgy, hogy azok kielégítsék boole-algebrai kifejezést, de csak akkor ha c bizonyítja hogy x benne van L-ben. A formulát fel tudjuk építeni ha ismerjük x-et és a bizonyító eljárást és nincs szükség c-re. Így ezt tehát akár publikussá is lehet tenni. Ahogyan már az előbb is eljártunk, ebből Peggy és Vic részére egy boole-algebrai hálózatot fogunk generálni.
A 2-es részben felvázolt minimális felfedési protokoll az eredeti formájában nem használható, mert Vic nem bízhatja Peggy-re a teljesen véletlenszerű r-ek generálását. Másfelől pedig Peggy sem bízhatja Vic-re ezen változók megválasztását, mert Vic így kiügyeskedhetné Peggy c-jét (vagy legalább is arról valamiféle információt). Emiatt tehát szükség van egy pénzérme feldobós Peggy-től és Vic-től független alprotokollra, amely a véletlenszerű változókat beállítja. Továbbá Vic nem láthatja majd a véletlenszerű pénzérme feldobások kimenetelét, mert máskülönben információt tudhatna meg a bizonyításról ( c ). A pénzérem feldobást egy kútban kell elvégezni [B1]. Ha tehát úgy szeretnénk az éremefeldobások eredményeit felhasználni, hogy azokat közvetlenül ne mutassuk meg Vic-nek, akkor blobokat kell alkalmazni. Végezetül pedig az is fontos lesz, hogy Peggy ne az érmefeldobások eredményei alapján számolja ki c-t.
Ezeknek a követelményeknek sokkal könnyebb megfelelni, ha a blobok tulajdonságait az alábbi kettővel kiegészítjük:
(v) Ha adott két felnyitatlan blob, amit Peggy már kiválasztott, akkor Peggy meg tudja győzni Vic-et arról, hogy az azonos biteket akár fel is nyithatja vic számára 0-információcserés módon (vi) Ha adott két felnyitatlan blob, amit Peggy már kiválasztott, akkor Peggy meg tudja győzni Vic-et arról, hogy a különböző biteket akár fel is nyithatja vic számára 0-információcserés módon
A 6.5-ös részben meg is mutatjuk, de itt előrebocsátjuk, hogy a 6. tulajdonság az 1-5 tulajdonságok következménye, az 5. tulajdonság pedig az 1-4 tulajdonságok következménye.
A 4. tulajdonság felhasználásával nagyon könnyű olyan pénzérme feldobást definiálni, amely blobokat valósít meg: Peggy megválaszt két különböző blobot és ezeket fel is tudja nyitni, amd meggyőzi Vic-et arról, hogy ez így is van. Ezek után Peggy megkéri Vic-et, hogy válasszon egyet. Vic választ egyet és ezzel az érmefeldobás kimenetele eldől és Peggy megtudja az eredményt. Ez az a bit lesz, amit azon blob felnyitásával látna meg Vic, amit választott. Vic azonban nem fogja megtudni a végeredményt, csak akkor ha Peggy folytatja a blobok felnyitását (ezt viszont az alábbi protokollban nem fogja megtenni). A 3-as tulajdonság miatt Vic nem képes befolyásolni az érmefeldobások kimenetelét. Hasonló a helyzet Peggy számára a 2-es és a 6-os tulajdonságok miatt.
Most már végre ott tartunk, hogy bemutathatjuk azt az általános protokollt, amelyet a valószínűségi alapon ellenőrizhető információ esetére fejlesztettünk ki. Emlékezzünk vissza arra is, hogy Peggy és Vic megállapodnak egy boole-algebrai hálózatban, amely a valószínűségi alapon bizonyító algoritmust (Peggy állítását, hogy x benne van L-ben) reprezentálja. A következő lépés soron Peggy akkor végleg megválasztja azokat a blobokat (m bit), amelyeket ha felnyitna, akkor elárulná c-t. Ezek után Peggy és Vic elkezdenek egy kútban érméket dobálni (hogy az eredményt ne lássa senki) és egy elő fog állni r darab megválasztott blob. Ezek után Peggy egy módosított protokollt fog használni arra, hogy meggyőzze Vic-et, arról hogy hogyan kell megválasztani a hálózat maradék bemeneteit ahhoz, hogy az végül egyet adjon ki.
Az előbbiekben felvázolt protokollt olyan módon kell módosítani, hogy az Peggy-t kötelezze arra, hogy a c-hez és az érmefeldobásokhoz tartozó bitekhez megfelelő biteket válasszon és ezt úgy kell megtenni, hogy Vic ne tudjon meg semmit ezekről a bitekről. Ezt a 2-es szekcióban bemutatottt példával fogjuk szemléltetni. Feltételezésünk szerint Peggy megválasztott egy b blobot és ezt 1 ként tudná felnyitni, de erről Vic nem tud. Peggy ekkor meg szeretné győzni Vic-et arról, hogy ki tudja elégíteni a boole hálózatot és a kielégítő formulában az első bit az előbb említett blob felnyitásából származna. Ezen eljárás során Peggy véletlenszerűen permutálja és negálja a boole hálózatot és így legyártja a 3-mas ábrát, majd biteket választ ahogyan eddig is. Továbbá minden egyes Peggy által megválasztott bemeneti bithez (most az első bit, de az általános esetben m+r bit) negáló biteket választ a megfelelő vezetéken, ahogyan az a 3-mas ábrán van.
Ha Vic az A kérdést teszi fel Peggy felnyitja az általa kiválasztott összes blobot és felfedi a negáló biteket is. Ezzel tehát megmutatja Vic-nek a 3-mas ábrát, hasonlóan mint ahogyan azt a determinisztikus esetben tette volna. Ha viszont Vic a B kérdést teszi fel, akkor nem elegendő csupán a 4-es ábrát megmutatni, mert ez semmit nem mondana a boole algebrai kifejezést kielégítő első bitről. Mivel a vezeték, amely az első bitet reprezentálja a 4-es ábrán (bal felső igazságtábla első bitje) Peggy az 5-ös tulajdonságot fogja kihasználni és ezzel meggyőzi Vic-et arról, hogy felnyithatta volna a negált vezetéket is hasonlóan, mint ahogyan felnyitotta a b blobot. Ha pedig ez a bemenet 1 lett volna, akkor a 6-os tulajdonságot használta volna ki.
Ezzel tehát végeztünk a valószínűségi alapokon nyugvó protokoll leírásával. Az általános esetben elméleti szempontból ez a protokoll nem minimális felfedésű. A nehézség abban keresendő, hogy a bizonyító algoritmus a különböző állításokkal eltérő valószínűséggel fog elhasalni. Mivel Vic nem fogja tudni megjósolni ezt a valószínűséget, nem fogja tudni leszimulálni a Peggy-vel történő kommunikációt sem. Továbbá ha Vic exponenciálisan sokszor le tudja futtatni az algoritmust, akkor vissza tudja fejteni Peggy titkát csupán az elhasalásokból. A gyakorlatban viszont, mivel a hibatűrést jó alacsonyra választjuk, ez nem jelenthet biztonsági rést és a protokollt biztonságosan lehet használni.
A módszert lehet módosítani úgy, hogy az szinte mindig minimális felfedésű legyen. Ehhez az eredeti BPP módszert kell átírni. Elegendő számú ismétlést kell előírni és többségi eredményt kell venni, így tehát exponenciálisan kevés lesz az olyan véletlenszerű eredmények előfordulása, amely akár egyetlen bemenethez is rossz kimenetet ad majd. Ennek a lehetőségét be lehet bizonyítani ha finomítunk kicsit a bizonyításon mely szerint MA AM része [Ba]. Ha ez sikerül, akkor akár az eredeti protokollt is lehet használni, nem kell kútban pénzérméket dobálni és a blobok 5-ös és 6-os tulajdonságára sincs szükség.
Szerző: LB
Figyelem: A bejegyzésben található információk tartalmazhatnak hibát. A szerző az abból eredő károkért nem vállal felelősséget!
