Dovezile, argumentele și cunoașterea zero

Titlul original:

Proofs, Arguments, and Zero-Knowledge

Conținutul cărții:

Această monografie se referă la calculul verificabil (VC). VC se referă la protocoale criptografice numite dovezi interactive (IP) și argumente care permit unui prover să ofere o garanție unui verificator că prover a efectuat corect un calcul solicitat. Această monografie acoperă diferite noțiuni de dovezi matematice și aplicațiile acestora în informatică și criptografie. În mod informal, înțelegem prin dovadă orice lucru care convinge pe cineva că o afirmație este adevărată, iar un "sistem de dovezi" este orice procedură care decide ce este și ce nu este o dovadă convingătoare.

Introduse în anii 1980, IP-urile și argumentele au reprezentat o extindere conceptuală majoră a ceea ce constituie o "dovadă" că o afirmație este adevărată. În mod tradițional, o dovadă este un obiect static care poate fi ușor verificat pas cu pas pentru corectitudine. În schimb, IP-urile permit interacțiunea dintre prover și verificator, precum și o probabilitate mică, dar diferită de zero, ca o dovadă invalidă să treacă de verificare. Argumentele (dar nu și PI) permit chiar să existe "dovezi" ale afirmațiilor false, atât timp cât aceste "dovezi" necesită o putere de calcul exorbitantă pentru a fi găsite. Într-o anumită măsură, aceste noțiuni imită interacțiunile în persoană pe care matematicienii le folosesc pentru a se convinge reciproc că o afirmație este adevărată, fără a trece prin procesul minuțios de redactare și verificare a unei dovezi statice tradiționale.

Rezultatele teoretice celebre din anii 1980 și 1990, precum IP = PSPACE și MIP = NEXP, au arătat că, în principiu, afirmațiile surprinzător de complicate pot fi verificate eficient. Mai mult, în principiu, orice argument poate fi transformat într-unul cu zero cunoștințe, ceea ce înseamnă că dovezile nu dezvăluie nicio altă informație în afară de propria lor validitate. Argumentele cu cunoaștere zero au o multitudine de aplicații în criptografie.

În ultimul deceniu, argumentele cu cunoaștere zero de uz general au trecut de la teorie la practică. Acest lucru a deschis noi uși în proiectarea sistemelor criptografice și a generat informații suplimentare cu privire la puterea IP-urilor și a argumentelor (cu cunoaștere zero sau nu). În prezent, există nu mai puțin de cinci abordări promițătoare în ceea ce privește conceperea unor argumente eficiente, de uz general, cu cunoaștere zero. Această monografie acoperă aceste abordări într-o manieră unificată, subliniind punctele comune dintre ele.