Prove, argomentazioni e conoscenza zero

Titolo originale:

Proofs, Arguments, and Zero-Knowledge

Contenuto del libro:

Questa monografia riguarda il verifiable computing (VC). La VC si riferisce ai protocolli crittografici chiamati prove interattive (IP) e agli argomenti che consentono a un prover di fornire a un verificatore la garanzia che il prover ha eseguito correttamente un calcolo richiesto. Questa monografia copre diverse nozioni di prove matematiche e le loro applicazioni in informatica e crittografia. Informalmente, si intende per prova qualsiasi cosa che convinca qualcuno che un'affermazione è vera, e un "sistema di prova" è una qualsiasi procedura che decide cosa è o non è una prova convincente.

Introdotti negli anni '80, gli IP e gli argomenti hanno rappresentato un'importante espansione concettuale di ciò che costituisce una "prova" che un'affermazione è vera. Tradizionalmente, una prova è un oggetto statico che può essere facilmente verificato passo dopo passo per verificarne la correttezza. Al contrario, gli IP consentono l'interazione tra prover e verificatore, nonché una probabilità minima ma non nulla che una prova non valida superi la verifica. Gli argomenti (ma non gli IP) permettono persino di avere "prove" di affermazioni false, a patto che queste "prove" richiedano una potenza di calcolo esorbitante per essere trovate. In un certo senso, queste nozioni imitano le interazioni personali che i matematici usano per convincersi l'un l'altro che un'affermazione è vera, senza passare attraverso il processo minuzioso di scrivere e verificare una prova statica tradizionale.

Celebri risultati teorici degli anni '80 e '90, come IP = PSPACE e MIP = NEXP, hanno dimostrato che, in linea di principio, è possibile verificare in modo efficiente affermazioni sorprendentemente complicate. Inoltre, qualsiasi argomento può essere trasformato in linea di principio in un argomento a conoscenza zero, il che significa che le prove non rivelano alcuna informazione se non la loro stessa validità. Gli argomenti a conoscenza zero hanno una miriade di applicazioni in crittografia.

Nell'ultimo decennio, gli argomenti a conoscenza zero di uso generale sono passati dalla teoria alla pratica. Ciò ha aperto nuove porte nella progettazione di sistemi crittografici e ha generato ulteriori intuizioni sulla potenza degli IP e degli argomenti (a conoscenza zero o meno). Esistono oggi non meno di cinque approcci promettenti per la progettazione di argomenti a conoscenza zero efficienti e di uso generale. Questa monografia tratta questi approcci in modo unificato, sottolineando i punti in comune tra di essi.