Proofs, Arguments, and Zero-Knowledge
Ez a monográfia az ellenőrizhető számítástechnikáról szól. A VC az interaktív bizonyításnak (IP) nevezett kriptográfiai protokollokra és érvekre utal, amelyek lehetővé teszik a bizonyító számára, hogy garanciát nyújtson a hitelesítőnek arra, hogy a bizonyító egy kért számítást helyesen végzett. Ez a monográfia a matematikai bizonyítások különböző fogalmaival és azok alkalmazásaival foglalkozik a számítástechnikában és a kriptográfiában. Informálisan, bizonyítás alatt bármit értünk, ami meggyőz valakit arról, hogy egy állítás igaz, a "bizonyítási rendszer" pedig minden olyan eljárás, amely eldönti, hogy mi a meggyőző bizonyítás és mi nem az.
Az 1980-as években bevezetett IP-k és érvek jelentős fogalmi bővülést jelentettek abban a tekintetben, hogy mi minősül "bizonyítéknak" arra, hogy egy állítás igaz. Hagyományosan a bizonyítás egy statikus objektum, amelynek helyességét lépésről lépésre könnyen ellenőrizni lehet. Ezzel szemben az IP-k lehetővé teszik az interakciót a bizonyító és a hitelesítő között, valamint egy apró, de nem nulla valószínűséggel, hogy egy érvénytelen bizonyítás átmegy az ellenőrzésen. Az érvek (de nem az IP-k) még azt is lehetővé teszik, hogy hamis állítások "bizonyítékai" is létezzenek, amennyiben ezeknek a "bizonyítékoknak" a megtalálása túlzott számítási teljesítményt igényel. Ezek a fogalmak bizonyos mértékig utánozzák a személyes interakciókat, amelyeket a matematikusok arra használnak, hogy meggyőzzék egymást egy állítás igaz voltáról, anélkül, hogy végig kellene menniük a hagyományos statikus bizonyítás megírásának és ellenőrzésének fáradságos folyamatán.
Az 1980-as és 1990-es évek híres elméleti eredményei, például az IP = PSPACE és a MIP = NEXP megmutatták, hogy elvileg meglepően bonyolult állítások is hatékonyan ellenőrizhetők. Ráadásul elvileg bármilyen érv átalakítható zéró-tudásúvá, ami azt jelenti, hogy a bizonyítások a saját érvényességükön kívül más információt nem árulnak el. A zéró-tudás érveknek számtalan alkalmazása van a kriptográfiában.
Az elmúlt évtizedben az általános célú zéró-tudás érvek az elméletből a gyakorlatba ugrottak át. Ez új ajtókat nyitott meg a kriptográfiai rendszerek tervezésében, és további betekintést nyújtott az IP-k és érvek (zéró-tudás vagy más) erejébe. Jelenleg nem kevesebb, mint öt ígéretes megközelítés létezik a hatékony, általános célú zéró-tudás érvek tervezéséhez. Ez a monográfia egységesen tárgyalja ezeket a megközelítéseket, kiemelve a köztük lévő közös vonásokat.