Loading
Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fondamenti di Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bangalore Lecture – 58 Zero - knowledge Protocols Part II Ciao a tutti, benvenuti a questa lezione. Solo un rapido recap. Nell'ultima lezione avevamo iniziato la nostra discussione sui protocolli di conoscenza zero. Così in questa lezione continueremo la nostra discussione su protocolli di conoscenza zero specificamente introdurremo protocolli a conoscenza zero per la classe NP - completa. (Riferimento Slide Time: 00.44) Per questo introdurremo il problema di 3 colorazioni e vedremo un sistema di prova a conoscenza zero computazionalmente sicuro per problemi di colorazione da 3. (Riferimento Slide Time: 00.51)Quindi, ricordando che nell'ultima lezione abbiamo visto che esattamente come possiamo specificare una relazione. Ad esempio, se si ricorda il rapporto per il problema del grafico - isomorfismo allora la relazione consisterà in coppie (x, w) dove x è un'istanza di problema. Così in questo esempio se consideriamo un problema di isomorfismo grafico che l'istanza x è sostanzialmente la descrizione pubblicamente nota di 2 grafici e il componente testimone corrispondente a questa istanza x sarà la mappatura isomorfismo tra la serie di vertex del primo grafico al vertice del secondo grafico. E infatti se abbiamo un'istanza x o problema dove i 2 grafici sono isomorfi allora dovremmo avere un testimone corrispondente w. Nell'ultima lezione abbiamo visto che come possiamo arrivare con un sistema a prova di zero conoscenze che permette al prover di mostrare se un'istanza x ha un corrispondente testimone w disponibile con il provino e non senza rivelare nulla sul testimone w. Ma si scopre che il rapporto grafico - isomorfismo non è una relazione NP completa e la prossima domanda impegnativa è possibile avere un sistema di prove a conoscenza zero per qualsiasi relazione NP completa? Quindi, per le persone che potrebbero chiedersi cosa sia esattamente il problema NP - completo o la relazione NP completa. Un problema x è definito un problema NP - completo, se dato un testimone w possiamo verificare se effettivamente il testimone w è un testimone giusto per l'istanza di problema x e in quantità polinomiale. Nello specifico eseguendo il calcolo non deterministico per la quantità di tempo polinomiale. Questo è il primo requisito. Il motivo per cui chiamiamo tali problemi come NP - completi, l'aspetto di completezza qui denota che se abbiamo qualsiasi altro problema y appartenente alla classe NP allora quell' istanza di problema y può essere ridotta ad un'istanza del problema x in quantità polinomiale. In tal senso questo problema x sarà chiamato come relazione NP completa. Questo significa che se si ha una soluzione per risolvere l'istanza di problema x, questo significa che se si possono trovare i testimoni per l'istanza di problema x in quantità di tempo polinomiale, quindi semplicemente utilizzando la riduzione delle istanze di problema di y all'istanza di problema di x, è possibile ottenere soluzioni anche per le istanze di problema y. Ecco quindi una definizione grezza di relazione completa NP. Quindi, ora siamo interessati a vedere se riusciamo a trovare un sistema di prove a conoscenza zero per qualsiasi relazione che sia NP completa. Così, si scopre che l'isomorfismo grafico non è una relazione NP completa. (Riferirsi Slide Time: 03.35) Quindi, quello che stiamo per fare ora è che vedremo un sistema a prova di zero conoscenze per un altro problema computazionale che chiamiamo come problema di 3 colorazioni che è un noto problema completo NP. Vediamo quindi prima cosa intendiamo per un grafico 3-colorable? Diciamo che un dato grafico con n vertici è 3-colorable se ognuno dei suoi vertici può essere assegnato uno dei colori dai colori pubblicamente noti c1, c2, c3 tale che non venga assegnato un paio di vertici adiacenti lo stesso colore. Questo significa che dobbiamo colorare i vertici in modo tale che ogni coppia ogni due endpoint di ogni bordo debba avere colori diversi. Se si considera questo grafico per istanza, allora si tratta di un grafico 3-colorable. Così, per esempio se il mio {c1, c2, c3} sono {rosso, blu, giallo} allora possiamo colorare i vertici in questo grafico usando questi 3 colori per una di queste assegnazioni assegnando questi colori ai rispettivi vertici. E ora potete vedere che non sono assegnati 2 vertici adiacenti e cioè a 2 vertici adiacenti lo stesso colore qui. Per esempio, se considero questi 2 vertici, sono adiacenti nel senso che sono i punti di fine di un unico bordo dicono lo stesso bordo e stanno avendo colori diversi. Allo stesso modo se considero questo bordo i punti finali stanno ottenendo colori diversi e così via. D'altra parte, se considero il grafico sul tuo lato destro allora non è 3-colorable. Il che significa che non è affatto possibile colorare tutti i vertici di questo grafico con soli 3 colori che soddisfano la condizione che non venga assegnato lo stesso colore a nessuna coppia di vertici adiacenti. Il problema di 3 colorazioni o la relazione di colorazione 3 è una ben nota relazione NP completa e la voce (x, w) nella relazione di colorazione 3. Quindi, l'istanza x sarà la descrizione pubblica di un grafico cioè il numero di vertici e il set di vertex, e la serie edge del grafico sarà resa nota pubblicamente. Se effettivamente questa x istanza e precisamente questo grafico è 3-colorable allora il corrispondente testimone w sarà la mappatura o l'assegnazione del colore {c1, c2, c3} al vertex set che io chiamo a. E la colorazione il testimone dovrebbe soddisfare la restrizione che se il bordo (u, v) appartiene al bordo impostato poi il colore assegnato al nodo u e il colore assegnato al nodo v dovrebbero essere diversi. Se effettivamente è possibile arrivare con un tale assegnazione di colore per la determinata istanza di problema x allora (x, w) sarà considerata una voce valida o soddisfacendo la relazione 3-coloring. Se non riusciamo a trovare un testimone w, quindi corrispondente a un dato x allora che x non sarà presente nella relazione di colorazione 3. (Riferimento Slide Time: 06.29)Così ora vediamo come conosci il sistema di prova della conoscenza per il problema di colorazione 3. Quindi, immaginate una Alice è il prover e Bob è il verificatore. L'input comune sia per Alice che per Bob è la descrizione di un grafico. Diciamo che l'input privato per il prover ovvero Alice qui è un 3 da colorare del grafico pubblicamente noto e cioè un assegnazione che mappa il vertex impostato sul set di colori {c1, c2, c3} e quello che Alice vuole dimostrare a Bob che effettivamente il grafico dato è 3-colorable e ha un incarico a disposizione con lei. Quindi, l'obiettivo qui è quello di arrivare con un sistema di prove a conoscenza zero che dovrebbe convincere Bob che effettivamente Alice conosce la mappatura corrispondente senza rivelare nulla sull'effettiva mappatura. Allo stesso tempo il sistema di prove a conoscenza zero dovrebbe garantire che se il prover non conosce la colorazione 3 del dato grafico o se il grafico non è 3-colorable al primo posto poi con molto alta probabilità mentre dà la prova, Alice dovrebbe essere catturata da Bob. Di recente, che questa è la tua proprietà di solidità, il secondo requisito. E la prima proprietà cioè Bob non dovrebbe imparare nulla sulla 3 colorazione è la proprietà a conoscenza zero. (Riferimento Slide Time: 07.56)Così ora vediamo come sarà esattamente il sistema a prova di conoscenza zero per il problema da 3 colorazioni. Alice ha la colorazione privata 3 disponibile con lei. Quindi, quello che fa è che permuta casualmente il colore che ha a disposizione con lei cioè vedere che ha la mappatura segreta dispiace che abbia la colorazione originale del grafico. Quindi, quello che fa è che crea una permutazione casuale del set di colori. Per esempio, può dire creare una permutazione che siamo rossi viene mappato al blu, il blu viene mappato al rosso e il terzo colore rimane com' è come per la permutazione. In sostanza, ora quello che sta facendo è creare una nuova 3 colorazione del grafico disponibile con Bob rispetto ai nuovi colori mappati. Così ovunque nel grafico originale qualunque vertices fossero colorati con il colore rosso quei vertici nella nuova colorazione verranno assegnati colore blu perché il colore rosso viene mappato al colore blu. Allo stesso modo nella vecchia colorazione a prescindere dai vertici è stato assegnato il colore blu quei vertici nella nuova colorazione 3 verrà assegnato un colore rosso e così via. Tutto questo Alice sta facendo alla sua fine. Ora una volta che Alice calcola la nuova 3 - colorazione del grafico quello che fa è tiene i nuovi colori assegnati dei rispettivi vertici in una scatola chiusa. E qui bloccavano le scatole e citano le unquote. Vedremo in seguito quali sono esattamente le proprietà che richiediamo da queste caselle bloccabili e come lo instanziamo utilizzando primitivo crittografico. Quindi, su un livello molto alto quello che queste caselle bloccabili significa è che sembra che in questo esempio abbiamo 6 vertici. Quindi quello che sta facendo Alice è quello che è il nuovo colore assegnato al vertex che si conserva all'interno di questa casella chiusa dove il bloccato è disponibile con Alice. La sua scatola chiusa nel senso che senza avere accesso alla chiave, Bob non può aprire la prima scatola e vedere qual è il nuovo colore del primo vertice. Allo stesso modo il nuovo colore del secondo vertice è nella seconda lockbox il nuovo colore del terzo vertice è in quella terza scatola chiusa e così via. Bob in questo momento non può vedere i colori disponibili nelle caselle bloccabili. Così dal punto di vista del Bob se effettivamente Alice conosce l'originale 3 - colorazione poi dal punto di vista del Bob, Bob si sentirà come se ora stia vedendo una nuova 3 colorazione dello stesso grafico esistente pubblicamente con l'eccezione che in realtà non sa quali sono questi colori esatti ora perché tutti quei nuovi colori sono nella scatola chiusa. Così, questo primo giro di messaggi è come un impegno da parte di Alice a Bob. Questo significa che sta dicendo che “ okay! Ho ora calcolato un nuovo 3-coloring. Non vi mostrerò il nuovo 3-coloring. Quelle nuove 3 colorazioni sono effettivamente disponibili in queste caselle bloccabili. ” Questo è l'impegno dalla mia parte come per il sistema a prova di conoscenza zero. Ora una volta Bob riceve l'impegno di Alice, quello che Bob fa è che crea una sfida per Alice. La sfida è sostanzialmente un bordo casuale (i, j) dal grafico. Ricordate che Alice non si accorgerà di quello che esattamente è il bordo casuale che Bob sfiderà quando Alice sta commettendo i nuovi colori nelle scatole bloccabili. Così una volta che Bob picchia il bordo casuale, sfida Alice che “ si prega di aprire i nuovi colori nella scatola i e la scatola j. Voglio verificare se effettivamente sono colori diversi o meno. Perché se a tutti sai la colorazione originale 3 allora come per la tua mappatura la nuova colorazione dovrebbe essere anche una 3-coloring. ” E da qui da quando io e j sono nodi adiacenti il nuovo colore del nodo i e un nuovo colore del nodo j dovrebbe essere idealmente diverso così è quello che Bob sta impugnando Alice da mostrare. E per rispondere alla sfida di Bob quello che rivela Alice sono le chiavi per la scatola i e la scatola j. Ora ho bisogno di un'altra proprietà dalla scatola chiusa qui. Ricordate, quindi, una delle proprietà della boxesis bloccata che qualunque sia conservato all'interno della scatola chiusa Bob non può vedere il suo contenuto fino a quando e a meno che non riesca ad accedere alle chiavi della scatola. La seconda proprietà che esigo da queste caselle bloccabili è che una volta che Alice ha conservato qualcosa all'interno della scatola chiusa e se più tardi viene chiesto di rivelare il contenuto di una qualsiasi delle scatole in seguito non può cambiare il contenuto che ha già conservato all'interno di quella particolare scatola. Così in questo caso Bob sta impugnando Alice per aprire la scatola i e box j e Alice è costretta a dare le chiavi per la scatola i e box j. Come per le proprietà della lockbox qualunque cosa abbia commesso all'interno della scatola ith e la scatola di jima che non è autorizzata a cambiare. Ora Bob verificherà. Infatti Bob prenderà le chiavi per le ith box e la jima box, aprirà quelle scatole così sono i nuovi colori rispetto alla nuova colorazione 3 per il grafico. Bob lo considererà un round di successo se scoprirà che i nuovi colori del nodo i e il nodo j sono diversi che dovrebbero essere idealmente il caso. Se non è così, allora il round fallisce e Bob interromma il protocollo qui stesso. Ecco allora come funziona un giro del sistema di prove a conoscenza zero. Ora per rilanciare la fiducia in questa prova ciò che Bob può fare è Bob può ripetere questo processo k numero di volte in modo indipendente dove in ogni round Alice può utilizzare una diversa colorazione da 3 rispetto alle vecchie tecniche di colorazione 3. Questo significa che ogni rotonda raccoglierà una mappatura indipendente l'esistente 3 - colorazione a una nuova colorazione 3 e in modo indipendente Bob raccoglierà nuove sfide (i, j) in ogni round. Il che significa che non sarà il caso che (i, j) che viene prelevato come il margine di sfida da parte del Bob rimarrà lo stesso in tutti i turni. Verranno scelti in modo indipendente, e Alice non conoscerà nulla delle sfide per il successivo round in anticipo e se tutti questi k round avranno successo Bob valuterà che effettivamente Alice conosce l'effettiva o la colorazione originale a 3 per il grafico esistente. (Riferimento Slide Time: 14.18)Così si tratta di un sistema a prova di conoscenza zero. Ora cerchiamo di fare l'analisi per il sistema delle prove a conoscenza zero se soddisfa il requisito della correttezza, della solidità e dello zero - conoscenza. Correttezza o completezza, quindi ricordate la proprietà di completezza significa che se Alice e Bob sono onesti e se effettivamente Alice ha un testimone per il grafico cioè ha la colorazione originale 3 allora con alta probabilità la prova dovrebbe passare e Bob dovrebbe essere convinto. È facile vedere che se effettivamente Alice conosce l'originale 3 colorazione poi in tutti i round sarà in grado di convincere con successo Bob. Non fallirà e da qui ogni round avrà successo, e Bob accetterà la prova. (Riferimento Slide Time: 15.03)Ora consideriamo la proprietà di solidità. Quindi, ricordati per la proprietà solidale dobbiamo considerare il caso quando il provino è corrotto. Prover è corrotto nel senso che o il grafico non è 3-colorable, oppure potrebbe essere il caso che il grafico sia 3-colorable, ma Alice non sa cosa sia esattamente la 3 colorazione del grafico originale. Per semplicità e senza perdita di generalità ipotizza che il grafico non sia 3-colorable. Quindi ora analizziamo qual è la probabilità che qualsiasi round abbia successo rispetto ad una Alice potenzialmente corrotta che non conosce o che per un grafico dove il grafico non è 3-colorable. Si scopre che se Alice è corrotta e Bob è onesto allora l'unico modo in cui Alice riesce ancora a superare con successo il round è quando può indovinare in avanzato il bordo (i, j) che va scelto come la sfida di Bob. Perché se il grafico non è 3-colorable allora Alice non può creare alcuna nuova colorazione 3 per il grafico perché il grafico non è 3-colorable al primo posto. Allora l'unico modo che Alice può vincere è che possa indovinare. Può far finta nella sua mente che questo potrebbe essere il bordo (i, j) che Bob può sfidare a mostrarmi. Quindi, quello che può fare è poter assegnare la colorazione arbitraria ai punti finali del grafico. Infatti, può assegnare gli stessi colori a tutti i nodi del grafico tranne i punti finali i e j. Perché Alice può solo indovinare che questo potrebbe essere il bordo che Bob può chiedermi di aprire. Quello che può fare Alice per esempio può indovinare che potrei essere un detto 1 e j potrebbe essere uguale a qualsiasi cosa dica semantica numero 3? Così, per esempio, può immaginare che potrebbe essere sfidata a mostrare i nuovi colori per il grafico per il bordo (v1, v3) o per i punti di fine v1 e v3. Quello che può fare è per la prima scatola chiusa a chiave che riesce a tenere il colore blu e la terza scatola chiusa in grado di tenere il colore giallo e poi in tutte le altre scatole riesce a tenere gli stessi colori. E se effettivamente è fortunata, allora potrebbe essere il caso di chiedere di aprire la prima scatola chiusa e la terza scatola chiusa. Poi, mostrerà con successo a Bob che “ Hey! Ho assegnato diversi colori al nodo numero v1 e nodo numero v3. Ma qual è la probabilità di successo di Alice indovinare in anticipo che quello che sarà il casuale (i, j) che Bob sfiderà Alice ad aprire. La probabilità che Alice sia riuscita a indovinare la sfida casuale (i, j) non è altro che 1 sulle dimensioni del bordo impostato. Circa la dimensione di bordo impostata nel peggiore dei casi può essere n2. Il che significa che la probabilità di successo del girone di successo è delimitata da 1 oltre il bordo impostato ovvero 1 / n2. Ricordate che ci sono k simili round. Questo significa che l'unico modo in cui Alice senza nemmeno sapere la colorazione 3 del grafico può passare con successo tutti i k round è quando per ciascuno dei k - round riesce a indovinare correttamente in avanzato quella sfida (i, j) che Bob chiederà in ogni turno. E la probabilità di successo di indovinare che in un solo turno è di 1 /E. La probabilità che possa farlo in tutti i k round non è altro che 1/ |E|k. Impostando k per essere sufficientemente ampi si può garantire che questa quantità 1/ |E|k diventi molto piccola. Da qui definitivamente in uno dei k round Alice che si beccherà. Se viene catturata in uno di questi k round, Bob sospenderà il sistema di prova e la rivendicazione di Alice sarà respinta. Così che dimostra la proprietà della solidità. (Riferirsi Slide Time: 19.07) Ora analizziamo una proprietà a conoscenza zero e ricordiamo per la proprietà zero - conoscenza dobbiamo considerare il caso quando il nostro prover ovvero Alice è onesto e anzi, ha un testimone che vuole nascondersi da un verificatore maligno. Quindi in questo caso il verificatore è il tipo corrotto e l'obiettivo del verificatore è cercare di imparare a conoscere l'originale 3-coloring. Si scopre che anche se il verificatore è corrotto, impara assolutamente nessuna informazione sull'originale 3-coloring.This è perché quello che sta vedendo al primo turno. Sta vedendo la nuova 3 colorazione ma non l'esatta nuova 3-coloring, ma piuttosto il verificatore sta vedendo i nuovi colori assegnati ai vertici nel grafico tutti tenuti nelle scatole bloccabili. Si tratta solo di una coppia di scatole chiuse che viene aperta da Alice in risposta alla sfida lanciata dal nostro verificatore. Quindi anche se il verificatore vede il colore del nodo i e il nodo j, sono i nuovi 3-coloring. Corrispondono alla nuova colorazione 3 e impara solo i colori per il nodo ith e il nodo jth ma non l'intero nuovo 3-coloring. Ricordati in ognuno dei round, Alice sta raccogliendo una fresca scelta indipendente. In questo modo sta permutando casualmente l'esistente 3 colorante e creando un nuovo 3-coloring. Quindi questo significa che la nuova colorazione 3 al primo turno sarà indipendente dalla nuova colorazione di 3 minuti al secondo turno e come questa la nuova colorazione di 3 minuti nel girone sarà indipendente da tutte le nuove 3 colorazioni del round precedente. Questo significa in ogni round, il verificatore sta solo andando ad imparare che ok vedrò i nuovi colori del nodo i e nodo j che so saranno distinti. Ed è per questo che non rivela nulla sull'originale 3 colorante che era disponibile con Alice. Così che dimostra la proprietà a conoscenza zero. (Riferimento Slide Time: 21.01) Ora tornando alla domanda che quali sono le proprietà di cui abbiamo bisogno dalle scatole bloccette? Come ho detto abbiamo bisogno di 2 proprietà. Abbiamo bisogno fondamentalmente della proprietà nasale. E cioè se il prover è onesto, se Alice è onesta e se ha conservato dei contenuti all'interno della scatola, poi fino a quando e a meno che le chiavi per quelle scatole non siano date a Bob, non può aprire e vedere i contenuti conservati all'interno della scatola. Ecco cosa intendo per la proprietà nasale qui. Legare proprietà significa se Alice è corrotta allora non dovrebbe essere il caso di mettere qualcosa dentro la scatola ma quando dovrebbe aprire la scatola, può trasformarla o modificarla in qualsiasi nuovo contenuto. Quindi quella è una proprietà vincolante e ora sappiamo benissimo come istanziare questa scatola chiusa sia con entrambe queste proprietà del 2. In sostanza possiamo usare uno schema di impegno in modo che significhi quello che Alice deve fare in ogni round, deve calcolare una nuova colorazione 3 e un nuovo colore per i vertici. Deve impegnarsi utilizzando qualsiasi schema di impegno. Quando Bob sfida ad aprire i nuovi colori del nodo ith e del nodo jima, Alice deve dare le informazioni di apertura corrispondenti all'impegno dell'ith e all'impegno jima. Così, questo dimostra che ora abbiamo un 3-coloring. Ora abbiamo un sistema a prova di zero conoscenze per il problema di 3 colorazioni e il suo ben noto che il problema di 3 colorazioni è un problema NP - completo che significa ora disponiamo di un sistema a prova di zero conoscenze per qualsiasi relazione NP. (Riferimento Slide Time: 22.31)Ora vediamo la potenza del sistema a prova di conoscenza zero. Quello che possiamo ora fare è vedere un quadro molto bello e cioè un compilatore in grado di compilare qualsiasi protocollo passivamente sicuro in protocollo attivamente sicuro. Immagina, hai un compito di calcolo distribuito che dice f, può essere qualsiasi compito computazionale astratto. Si potrebbe dire, ad esempio, un compito che coinvolge più parti 2 parti, 3 partiti o diciamo 4 partiti o qualsiasi n numero di partiti dove ciascuna parte ha qualche input dire x1, x2, x3, x4. Mi prendo il caso in cui ho 4 partiti. L'obiettivo dei partiti è fondamentalmente quello di calcolare f (x1, x2, x3, x4) e in modo tale che anche se ci sono dei cattivi nel sistema, non imparano nulla sugli input x dei buoni altro che quello che possono imparare dal proprio input e dalla funzione output. Questo è un problema molto astratto. Questo problema si chiama anche come problema di calcolo multipartitico. Il modo in cui ogni protocollo di calcolo multi - partitico funzionerà come segue: le parti avranno i propri input e sceglieranno in qualche casualità locale diciamo r1, r2, r3, r4 rispettivamente e poi interagiranno tra loro come per le istruzioni di questo protocollo f. Alla fine otterranno la funzione output y dove y = f (x1, x2, x3, x4) e per il momento immagina che questo protocollo f sia passivamente sicuro. È passivamente sicuro nel senso che se anche se c'è un avversario che può controllare o chi può vedere l'input e la casualità locale di qualche frazione di questi n partiti e qualunque sia i messaggi che hanno scambiato durante il protocollo, vedendo i loro input l'output e i messaggi che hanno ricevuto e che hanno inviato durante il protocollo, il cattivo non impara nulla in più sugli input dei buoni. Ecco cosa intendo dire che questo protocollo f è passivamente sicuro. Ora immagina di voler compilare questo protocollo. Compilando questo protocollo nel senso voglio conservare il protocollo f e voglio garantire che il protocollo rimanga sicuro anche se c'è un avversario attivo o un avversario malintenzionato. Avversario attivo, questo significa che voglio compilare questo protocollo in un portale maleficamente sicuro dispiaciuto per il typo che dovrebbe essere un protocollo maleficamente sicuro. Quindi quello che intendo per sicurezza maliziosa qui è che anche se i cattivi che sono sotto il controllo del loro avversario cercano di discostarsi dalle istruzioni del protocollo, non dovrebbero imparare nulla sugli input del bravo ragazzo. Non voglio progettare un nuovo protocollo o un protocollo fresco. Voglio solo conservare il protocollo f che è garantito per essere sicuro contro l'avversario passivo. Quindi come possiamo compilare il protocollo passivamente sicuro in un protocollo malamente sicuro? Questa è una domanda che vogliamo conoscere la risposta. Ora vogliamo usare qui un sistema di prova a conoscenza zero. Così, si scopre che un modo generico per convertire il protocollo passivamente sicuro in un protocollo malicamente sicuro è il seguente: se ogni parte dimostra ad ogni altra parte che sta effettivamente seguendo le istruzioni del protocollo correttamente, poi in presenza di un avversario malintenzionato, il protocollo f ne conseguirà il compito. Ora la domanda è cosa intendiamo dire dicendo che una parte che si sta dimostrando ad altro partito che effettivamente sta seguendo correttamente l'istruzione di protocollo. Con questo intendo dire che ogni partito deve dimostrare a ogni altra parte che i messaggi che inviano sono effettivamente rispetto alla loro casualità e al loro input come per le istruzioni date dal protocollo f. Come possono le altre parti verificare se effettivamente ciascuna parte sta seguendo il suo insegnamento di protocollo o no? Beh può controllare i messaggi che un determinato partito sta inviando e il testimone se quella parte sta inviando o eseguendo correttamente la sua azione oppure non saranno gli input delle parti e la casualità locale. Per esempio, in questo caso se Alice vuole verificare se effettivamente questa terza parte sta seguendo correttamente l'istruzione di protocollo o no? poi un modo di verificare che sia Alice verifica i messaggi che questo terze parti sta inviando. Insieme a questo se questa terza parte mostra il suo input x3 e la sua casualità r3 che ha usato come parte di questo protocollo f ad Alice allora Alice può eseguire l'azione di questo terzo partito, perché la descrizione del protocollo è nota ciò che non era noto era x3 e r3. Ma ora x3 e r3 sono date anche ad Alice, così lei stessa può calcolare i messaggi che questa terza parte dovrebbe inviare come per il protocollo f. Se quei messaggi corrispondono ai messaggi che effettivamente questa terza parte ha inviato o comunicato durante la reale esecuzione del protocollo, that1 dimostra che effettivamente questa terza parte sta seguendo il suo passo come per il protocollo f. Come questo ogni partito può verificare ogni azione di ogni altra parte se stanno eseguendo le proprie azioni come per il protocollo f, se quel partito di invio rivela il suo input e la casualità locale. Ma si scopre che l'input e la casualità locale di ogni partito non possono essere date ad altri partiti perché è questo che assicura la sicurezza del protocollo f. Se imparo l'input e la casualità di ogni altra parte, allora non c'è modo di garantire la sicurezza del protocollo f. Così, si scopre che la dichiarazione che ogni partito vuole dimostrare ad ogni altro partito e cioè che seguo l'istruzione di protocollo non è altro che un'istanza di una dichiarazione NP. Le istanze di problema sono la serie di messaggi che ho inviato e voglio dimostrarti che corrispondente a questi messaggi ho qualche casualità e qualche input tale che questi messaggi sono effettivamente calcolati in modo coerente come per quegli input e la casualità come per l'istruzione di protocollo f. Quindi, quello che ogni partito ora deve sostanzialmente fare per convincere ad altro partito che sta effettivamente seguendo l'istruzione di protocollo deve sostanzialmente provare una dichiarazione NP. E molto interessante ora abbiamo un sistema a prova di zero conoscenze per il problema di 3 colorazioni che è una dichiarazione NP - completa. Trattandosi di un'istruzione NP - completa che significa qualsiasi istanza di problema NP o qualsiasi istruzione NP può essere ridotta ad un'istanza di questo problema di colorazione da 3. Questo significa che ora possiamo usare il sistema a prova di conoscenza zero per il problema di colorazione 3. Ciascuna parte può trasformare un'istanza dell'istruzione NP cioè che sta seguendo correttamente l'istruzione di protocollo in un'istanza del problema di 3 colorare e darci la prova a conoscenza zero per l'esistenza di 3 colorazioni e convincere agli altri partiti che effettivamente sta seguendo le istruzioni di protocollo. Se la prova viene soddisfatta che significa che dà la garanzia che ogni partito segua correttamente le istruzioni di protocollo. Se la prova non passa, possiamo semplicemente fermare il protocollo lì stesso. Così, in tal senso il sistema a prova di conoscenza zero, ti dà un paradigma molto potente di compilare un protocollo passivamente sicuro in un protocollo malamente sicuro. Così questo mi porta alla fine di questa lezione: basta riassumere in questa lezione abbiamo visto il sistema a prova di zero conoscenze per il problema della colorazione da 3. E 3 - problema di colorazione è un noto problema NP - completo e abbiamo visto che come usare il sistema a prova di zero conoscenze possiamo compilare qualsiasi protocollo passivamente sicuro per qualsiasi attività di calcolo distribuito in un protocollo che sarà sicuro anche contro un avversario malintenzionato.