Dimostrazione a conoscenza zero: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Funzionalità collegamenti suggeriti: 3 collegamenti inseriti. Etichette: Modifica visuale Modifica da mobile Modifica da web per mobile Attività per i nuovi utenti Suggerito: aggiungi collegamenti |
||
| (4 versioni intermedie di 3 utenti non mostrate) | |||
Riga 1:
In [[crittografia]] una '''dimostrazione a conoscenza zero''' o ''' protocollo a conoscenza zero''' è un metodo
== Esempio astratto ==
Riga 33:
In particolare la prima caratteristica risponde alla [[Completezza (logica matematica)|completezza]] come intesa comunemente in logica ("il vero è derivabile", informalmente), mentre la seconda non è direttamente legabile alla [[Correttezza (logica matematica)|correttezza]] (per la quale "il derivabile è vero": difatti la correttezza di una dimostrazione interattiva è definita proprio come sopra ed è diversa dalla nozione solita di ''soundness''); la componente saliente è ovviamente la terza.
La ricerca nell'ambito di prove a conoscenza zero è stata promossa dai sistemi di [[autenticazione]] in cui una parte vuole provare la propria identità ad una seconda parte attraverso una qualche informazione segreta (come ad esempio una [[password]]) ma vuole che la seconda parte non conosca nulla di questo segreto. Questa è chiamata "prova di conoscenza a conoscenza zero".
Le dimostrazioni a conoscenza zero non sono dimostrazioni in senso matematico poiché c'è sempre una piccola probabilità che un dimostratore imbroglione riesca a convincere un verificatore di una affermazione falsa. In altre parole, questi tipi di algoritmi sono probabilistici e non deterministici. Tuttavia, ci sono tecniche per ridurre questa probabilità a valori piccoli a piacere.
Riga 47:
Ad ogni modo, una password è tipicamente troppo corta od insufficientemente casuale per essere usata, in molti schemi di dimostrazione a conoscenza zero. Una dimostrazione a conoscenza zero di password è un tipo speciale di prova a dimostrazione a conoscenza zero specifica per password di lunghezza limitata.
Uno degli usi più affascinanti delle dimostrazioni a conoscenza zero nei protocolli crittografici è rafforzare il comportamento onesto ed allo stesso tempo mantenere la privacy. Grossomodo, l'idea è di forzare l'utente a provare, usando una dimostrazione a conoscenza zero, la correttezza del suo comportamento rispetto al protocollo. Per via della correttezza, sappiamo che l'utente deve comportarsi in modo veramente onesto per essere abile nel fornire una dimostrazione valida. E per via della conoscenza zero, sappiamo che l'utente non compromette la privacy dei suoi segreti nel processo in cui fornisce la dimostrazione. Quest'applicazione delle dimostrazioni conoscenza zero fu usata per la prima volta nella sconvolgente pubblicazione [[Shafi Goldwasser]], [[Silvio Micali]], e Charles Rackoff, sulla computazione sicura multiparte.
== Esempio concreto ==
Riga 84:
Il problema in oggetto ha sia un algoritmo risolutivo ''[[NP (complessità)|NP]]'' sia uno ''[[co-NP]]'', è all'intersezione tra le due classi, e lo stesso vale per molti altri problemi per cui si sono scoperte successivamente dimostrazioni conoscenza zero (ad esempio<ref>Oded Goldreich. A zero-knowledge proof that a two-prime moduli is not a Blum integer. Unpublished manuscript. 1985.</ref>).
[[Oded Goldreich]], et al., hanno portato il discorso ad un livello ancora superiore mostrando che, assumendo l'esistenza di una crittatura inattaccabile, si può costruire una prova conoscenza zero per il problema NP-completo della colorazione di un grafo a tre colori. Poiché ogni problema in ''NP'' può essere efficientemente ridotto a questo problema, ciò significa che, sotto tale assunzione, tutti i problemi in ''NP'' possono avere dimostrazioni conoscenza zero (cioè ancora algoritmi risolutivi;<ref>Oded Goldreich, Silvio Micali, Avi Wigderson. [https://portal.acm.org/citation.cfm?id=116852 Proofs that yield nothing but their validity]. ''Journal of the ACM'', volume 38, issue 3, p.690-728. July 1991.</ref>).
La motivazione per l'assunzione è che, come nell'esempio di sopra, i loro protocolli richiedono cifratura. Una situazione sufficiente comunemente citata per l'esistenza di una crittografia invincibile è l'esistenza di funzioni ad una via (ossia facili da calcolare su qualsiasi input ma difficili, in termini computazionali, da invertire datane un'immagine), ma è concepibile che un qualche mezzo fisico possa raggiungerla di per sé.
| |||