Dôkazy, argumenty a nulové poznanie

Pôvodný názov:

Proofs, Arguments, and Zero-Knowledge

Obsah knihy:

Táto monografia sa zaoberá overiteľnou výpočtovou technikou (VC). VC sa vzťahuje na kryptografické protokoly nazývané interaktívne dôkazy (IP) a argumenty, ktoré umožňujú overovateľovi poskytnúť záruku overovateľovi, že overovateľ vykonal požadovaný výpočet správne. Táto monografia sa zaoberá rôznymi pojmami matematických dôkazov a ich aplikáciami v informatike a kryptografii. Neformálne pod pojmom dôkaz rozumieme čokoľvek, čo niekoho presvedčí o pravdivosti výroku, a "systém dôkazov" je akýkoľvek postup, ktorý rozhoduje o tom, čo je a čo nie je presvedčivý dôkaz.

IP a argumenty, ktoré boli zavedené v 80. rokoch 20. storočia, predstavovali významné koncepčné rozšírenie toho, čo predstavuje "dôkaz" pravdivosti nejakého tvrdenia. Tradične je dôkaz statickým objektom, ktorého správnosť sa dá ľahko kontrolovať krok za krokom. Naproti tomu IP umožňujú interakciu medzi overovateľom a overovateľom, ako aj malú, ale nenulovú pravdepodobnosť, že nesprávny dôkaz prejde overením. Argumenty (ale nie IP) dokonca umožňujú existenciu "dôkazov" nepravdivých tvrdení, pokiaľ si tieto "dôkazy" vyžadujú nadmerný výpočtový výkon na ich nájdenie. Tieto pojmy do istej miery napodobňujú osobnú interakciu, ktorú matematici používajú na vzájomné presvedčenie sa o pravdivosti tvrdenia bez toho, aby museli absolvovať zdĺhavý proces písania a overovania tradičného statického dôkazu.

Slávne teoretické výsledky z 80. a 90. rokov minulého storočia, ako napríklad IP = PSPACE a MIP = NEXP, ukázali, že v princípe možno efektívne overovať prekvapivo komplikované tvrdenia. A čo viac, každý argument sa dá v princípe transformovať na argument, ktorý je nulový, čo znamená, že dôkazy neodhaľujú žiadne iné informácie ako svoju vlastnú platnosť. Argumenty s nulovou znalosťou majú nespočetné množstvo aplikácií v kryptografii.

V poslednom desaťročí sa všeobecné argumenty o nulovej znalosti dostali z teórie do praxe. To otvorilo nové dvere pri návrhu kryptografických systémov a prinieslo ďalšie poznatky o sile IP a argumentov (s nulovou znalosťou alebo iných). V súčasnosti existuje najmenej päť sľubných prístupov k návrhu účinných, všeobecne použiteľných argumentov s nulovou znalosťou. Táto monografia sa zaoberá týmito prístupmi jednotným spôsobom, pričom zdôrazňuje ich spoločné črty.