Dowody, argumenty i wiedza zerowa

Oryginalny tytuł:

Proofs, Arguments, and Zero-Knowledge

Zawartość książki:

Niniejsza monografia dotyczy weryfikowalnych obliczeń (VC). VC odnosi się do protokołów kryptograficznych zwanych interaktywnymi dowodami (IP) i argumentów, które umożliwiają weryfikatorowi zagwarantowanie, że weryfikator poprawnie wykonał żądane obliczenia. Niniejsza monografia obejmuje różne pojęcia dowodów matematycznych i ich zastosowania w informatyce i kryptografii. Nieformalnie przez dowód rozumiemy wszystko, co przekonuje kogoś, że dane stwierdzenie jest prawdziwe, a "system dowodu" to dowolna procedura, która decyduje o tym, co jest, a co nie jest przekonującym dowodem.

Wprowadzone w latach 80. ubiegłego wieku, IP i argumenty stanowiły znaczące koncepcyjne rozszerzenie tego, co stanowi "dowód" prawdziwości stwierdzenia. Tradycyjnie, dowód jest statycznym obiektem, który można łatwo sprawdzić krok po kroku pod kątem poprawności. W przeciwieństwie do tego, IP pozwalają na interakcję między weryfikatorem a dowodzącym, a także na niewielkie, ale niezerowe prawdopodobieństwo, że nieważny dowód przejdzie weryfikację. Argumenty (ale nie IP) pozwalają nawet na "dowody" fałszywych stwierdzeń, o ile te "dowody" wymagają wygórowanej mocy obliczeniowej do znalezienia. W pewnym stopniu pojęcia te naśladują osobiste interakcje, których matematycy używają, aby przekonać się nawzajem, że twierdzenie jest prawdziwe, bez przechodzenia przez żmudny proces pisania i sprawdzania tradycyjnego statycznego dowodu.

Znane wyniki teoretyczne z lat 80. i 90. XX wieku, takie jak IP = PSPACE i MIP = NEXP, pokazały, że w zasadzie zaskakująco skomplikowane stwierdzenia można skutecznie zweryfikować. Co więcej, każdy argument można zasadniczo przekształcić w taki, który ma zerową wiedzę, co oznacza, że dowody nie ujawniają żadnych informacji poza ich własną ważnością. Argumenty o zerowej wiedzy mają niezliczone zastosowania w kryptografii.

W ciągu ostatniej dekady argumenty zerowej wiedzy ogólnego przeznaczenia przeszły z teorii do praktyki. Otworzyło to nowe drzwi w projektowaniu systemów kryptograficznych i wygenerowało dodatkowy wgląd w moc IP i argumentów (o zerowej wiedzy lub innych). Obecnie istnieje nie mniej niż pięć obiecujących podejść do projektowania wydajnych argumentów wiedzy zerowej ogólnego przeznaczenia. Niniejsza monografia omawia te podejścia w ujednolicony sposób, podkreślając podobieństwa między nimi.