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 International Institute of Information Technology – Bengaluru Collezione – 57 Zero Knowledge Protocolli Parte I (Riferimento Slide Time: 00.30) Benvenuti in questa lezione. Così in questa lezione proseguiremo la nostra discussione sui protocolli interattivi dove abbiamo voluto risolvere un problema più grande piuttosto che il problema della comunicazione sicura. Così in questa lezione introdurremo protocolli di conoscenza zero. Vedremo alcune motivazioni prima nei protocolli di conoscenza zero e una definizione formale. E vedremo un protocollo a conoscenza zero per il problema dell'isomorfismo grafico. (Riferimento Slide Time: 00.52)Ora iniziamo cercando di capire una motivazione per le prove a conoscenza zero. Quindi immaginate di avere due feste Alice e Bob e diciamo che Alice aveva scelto due numeri primi casuali p e q dicono ciascuno di dimensioni 512 e ha calcolato il prodotto di p e q per ottenere il prodotto N e lei va e sostiene Bob che conosco i fattori primi di N. Ora se effettivamente vuole dimostrare a Bob che sa che i primi fattori di N poi un modo semplice per dimostrare che è quello di mostrare i valori di p e q. Perché se i valori di p e q sono dati a Bob, Bob stesso può moltiplicare quei due numeri e vedere se le sue partite N o meno. Ma quello è stato che chiamiamo come prova in chiaro. Perché p e q sono qui testimone di Alice per la dichiarazione che sa riconoscere i fattori primi del N. Un modo per dimostrare la sua dichiarazione è mostrare i testimoni in chiaro ma quale protocollo zero - conoscenza sta per fare qui è la sua intenzione di permettere ad Alice di convincere Bob che effettivamente conosce i primi fattori di N senza mostrare realmente i testimoni cioè p, q. Perché p e virgola q potrebbero venire informazioni segrete per Alice e in questo intero processo di prova a conoscenza zero praticamente Alice finisce per convincere Bob che conosce p e q senza rivelare davvero p e q. Ora potrebbe chiedersi dove sia utile questo p e q. Quindi se ricordate nel contesto di RSA public-key cryptosystem, il valore N non è altro che una parte della public-key di Alice e p, q non sono altro che parte di una chiave di decodifica. Quindi se effettivamente Alice vuole convincere Bob che N è la sua chiave pubblica e conosce la chiave segreta corrispondente senza mostrare i componenti legati alla chiave segreta cioè p e q; lei possiamo convenienza Alice usando questa prova a conoscenza zero. (Riferimento Slide Time: 02.45) Vediamo un'altra motivazione. Immagina Alice ha due grafici qui. E pittoricamente questi due grafici sono disegnati in modo diverso. I nomi dei vertici sono diversi; i nomi edge sono diversi allora così. Ma si scopre che le informazioni sagge i due grafici sono isomorfi o strutturalmente i grafici sono isomorfi l'uno all'altro e ciò che intendo per i grafici isomorfi qui è che, se si considera questi due grafici poi per questi due grafici esiste una proiezione dal vertex set del primo grafico al vertice del secondo grafico. E quella biezione ha la proprietà che se c'è un bordo tra i nodi u e v nel primo grafico poi nel secondo grafico esiste un bordo compreso tra il set di u mappato e mappato v impostato. E questo è un se e solo se comunicato. Il che significa nello stesso modo se si ha un bordo compreso tra il vertice u vertex mappato e il vertex mappato nel secondo grafico poi un bordo esiste tra il vertex u vertex e il v vertex nel primo grafico. Così in tal senso questi due grafici sono isomorfi anche se pittoricamente si guardano diversi. Quindi immaginate Alice abbia due grafici isomorfi, quindi fa la descrizione dei due grafici a disposizione di Bob e fa la dichiarazione che afferma a Bob che questi due grafici sono isomorfi. Quindi questa è la dichiarazione. Ancora Bob non può controllare direttamente se i due grafici sono isomorfi o non e verificare Alice asserendo perché il suo impraticabile verificare se due grafici sono isomorfi o non in assenza della biezione che è disponibile o che associa la serie di vertex del primo grafico alla serie di vertex del secondo grafico. Così un modo per Bob di verificare la dichiarazione di Alice è che può chiedere ad Alice che la prego di darmi la sua testimonianza ovvero la biezione Π. Se mi dai la biezione Π allora posso verificare se effettivamente per ogni bordo presente nel grafico, primo grafico i corrispondenti vertici mappati costituiscono anche un bordo nel secondo grafico e così via. Ma quella sarà una prova in chiaro. Così che una prova a conoscenza zero o un protocollo a conoscenza zero permetterà ad Alice di farlo; permetterà ad Alice di convincere Bob che effettivamente questi due grafici sono isomorfi senza mostrare realmente il testimone cioè la biezione Π. (Riferimento Slide Time: 05.10) Quindi questo significa una prova a conoscenza zero è una sorta di protocollo interattivo tra due entità un prover e un verificatore che permette a un prover di provare una dichiarazione da verificare senza mostrare nulla sul testimone sottostante. Quindi ora formalizziamo questa dichiarazione. Quindi immaginare R è una relazione binaria e l'interpretazione di questa relazione è la seguente. Quindi se ho una coppia (x, w) presente in questa relazione R che deve essere interpretata come se x è un'istanza di qualche problema computazionalmente difficile. Quando dico problema computazionalmente difficile informalmente significa in polpa quantità di tempo non è noto come risolvere quel problema. Ma ancora questa è una dichiarazione molto vaga ma che è una comprensione intuitiva del problema computazionalmente difficile qui e una w qui è una soluzione per quell' istanza di problema x e cioè si può considerare la w un testimone per l'istanza di problema x. Quindi per capire questa relazione R consideriamo qui la relazione dell'isomorfismo grafico. Quindi una coppia (x, w) nella relazione isomorfica grafica RGI sembrerà questa {(G1 = (V1, E1), (G2 = (V2, E2))} e l'interpretazione degli elementi presenti in questa relazione di isomorfismo grafico dovrebbe essere la seguente. Quindi la prima parte qui è la descrizione dei due grafici cioè è un'istanza di problema. Questo significa che qualcuno vuole dimostrare o smentire questi due grafici sono isomorfi. E il corrispondente testimone non è altro che l'isomorfo o la biezione dalla serie di vertex del primo grafico al vertice del secondo grafico. Quindi per esempio se si considerano questi due grafici qui questi due grafici sono effettivamente isomorfi. Così il primo grafico è il tuo grafico G1 e il secondo grafico qui è il tuo grafico G2. Ecco quindi la componente x della qualsiasi x, w che potrebbe essere presente in questa relazione di isomorfismo grafico. E un corrispondente testimone rispetto a questo specifico grafico G1 G2 non è altro che la biezione dalla serie di vertex del grafico G1 alla serie di vertex del grafico G2 e così via. (Riferirsi Slide Time: 07.18)D'altra parte, se considero questi due grafici il mio G1 e G2, si scopre che questi due grafici non sono isomorfi l'uno all'altro e di conseguenza se questo è il mio candidato x allora per questo candidato x non ho alcun candidato w tale che x, w appartiene a questo rapporto RGI, giusto. Questo significa solo quelle x, w sarà presente in r dove l'istanza x ha un corrispondente testimone w. Se per un'istanza x non esiste un testimone w tale che x, w soddisfi quel rapporto allora diciamo che, (x, w) non è presente nella relazione R. (Fare Slide Time: 07.57) Così ora lasciamoci entrare nella definizione formale delle prove a conoscenza zero. Quindi ci viene data qualche relazione nota pubblicamente che avrà elementi del modulo x, w dove x è un'istanza di qualche problema computazionale difficile e w è la soluzione o il testimone per tale istanza. Poi un sistema a prova di conoscenza zero per la relazione R è costituito da due algoritmi di tempo polati due algoritmi randomizzati uno per il provino e uno per il verificatore. L'input per il prover sarà una coppia x, w e l'obiettivo del prover è quello di dimostrare che sa una w tale che x, w appartiene a r mentre l'input per l'algoritmo del verificatore sarà l'istanza di problema x. E l'obiettivo del verificatore è verificare se effettivamente Alice conosce un w tale che x, w appartiene a R o no. Così nel sistema a prova di conoscenza zero il prover invierà dei messaggi o interagirà con il verificatore dove verranno calcolati i messaggi per il prover come per il protocollo P e la casualità interna che vengono utilizzati dal prover. E alla fine del protocollo il prover outmette nulla mentre l'algoritmo verificatore interagirà con il prover dove verranno calcolati i messaggi del verificatore come per l'algoritmo V e la casualità interna scelta dal verificatore e il verificatore sta andando in uscita ad accettare o rifiutare. Accetta significa che accetta il fatto che Alice conosce qualche testimone, rifiuta significa che non crede nell'affermazione di Alice. Ora quali sono le proprietà che richiediamo da un sistema a prova di conoscenza zero, la prima proprietà è la proprietà di completezza che pretende che se sia il prover che il verificatore sono onesti e se effettivamente il prover conosce una x, w tale che x, w appartiene a R ed entrambi i prover e verificatore partecipa, esegue tutte le loro azioni come per il protocollo P e V. Poi con una probabilità molto alta l'output del verificatore deve essere accettato. Questo significa che il verificatore deve accettare la dichiarazione di prover. La seconda proprietà è di proprietà Soundness che consideriamo rispetto a un provino corrotto. Quindi quello che ci chiediamo qui è che se il mio prover è corrotto e non ha una x, w tale che x, w appartiene alla relazione R poi indipendentemente da ciò che partecipa al protocollo la produzione del verificatore dovrebbe essere rigata. Questo significa un prover malintenzionato che non ha x, w o che non ha un testimone tale che x, w appartiene alla relazione R con molto meno probabilità il prover dovrebbe essere in grado di convincere il verificatore che conosce il testimone w. Il che significa con molta probabilità il verificatore dovrebbe essere in grado di catturare un provino maligno. Questo è il requisito della solidità. (Riferimento Slide Time: 10.50)E la terza proprietà è una proprietà a conoscenza zero che è rispetto a un verificatore corrotto e a un provino onesto. Quindi la proprietà zero - conoscenza esige che se il prover è onesto e il verificatore è corrotto allora indipendentemente dal modo in cui l'algoritmo del verificatore o il verificatore partecipa a questo protocollo il verificatore impara assolutamente nulla sul testimone w che è disponibile con il prover. Quindi qui niente è in - preventivo, unpreventivo “ niente ”. Non è formale. Che cosa intendiamo esattamente per nulla viene appreso sul testimone. Se volete poco più formale possiamo dire che, diciamo che il protocollo ha la proprietà zero - conoscenza se la distribuzione di probabilità delle trascrizioni visto dal verificatore è indipendente dal testimone effettivo che è disponibile con il provino. Ancora non sto dimostrando formalmente cosa significhi esattamente dire che la distribuzione di probabilità delle trascrizioni viste dal verificatore è indipendente da w. Il formalismo reale è poco sottile e coinvolto. Quindi non andiamo nel dettaglio effettivo ma per la vostra comprensione potete immaginare che il verificatore non debba imparare nulla sul testimone se il verificatore è corrotto partecipando a questo protocollo. (Riferimento Slide Time: 12.06)Così ora vediamo un sistema a prova di zero conoscenze per un problema di isomorfismo grafico. Quindi l'input comune che è disponibile sia per il prover che per un verificatore è un'istanza di un problema di isomorfismo grafico cioè la descrizione di due grafici. E Alice vuole convincere Bob o il verificatore qui il prover; l'Alice è prover e il Bob è verificatore. Così Alice vuole dimostrare a Bob che effettivamente questi due grafici sono isomorfi. E sostiene di conoscere l'isomorfismo tra questi due grafici, questo significa che lei sostiene di avere un input privato mappato il vertex set del primo grafico al vertice del secondo grafico rispetto al quale questi due grafici sono isomorfi e l'obiettivo qui è quello di progettare un protocollo che permetta a Bob di imparare se effettivamente questi due grafici sono isomorfi o non senza effettivamente imparare l'isomorfismo. E dovrebbe essere suono nel senso che se il prover non conosce l'isomorfismo o i grafici non sono isomorfi al primo posto allora dovrebbe essere catturata mentre dà la prova con una probabilità molto alta. (Riferimento Slide Time: 13.07)Così vediamo come è progettato esattamente il protocollo di conoscenza zero qui. Così questa casella rettangolo ho evidenziato l'informazione pubblica così le informazioni pubbliche disponibili sia ad Alice che a Bob sono la descrizione dei due grafici. E le informazioni private disponibili con Alice, il prover è il testimone Π o la mappatura dal vertice del primo grafico al vertice del secondo grafico. Così il primo round del protocollo a conoscenza zero è il seguente. Quindi quello che fa Alice, crea una copia isomorfica casuale del secondo grafico G2. E questo è molto facile da fare, quello che deve fare è che deve praticamente arrivare con una permutazione casuale che dice σ mappando il set di vertex del secondo grafico e i vertici mappati i vertici le daranno un altro grafico H. Così una volta che compila una copia casuale isomorfica del secondo grafico invia la descrizione della copia isomorfica casuale del secondo grafico a Bob. Quindi questo è un tipo di impegno. Quindi sottolineo σ è scelto casualmente e conosciuto solo ad Alice qui. Ora quello che fa Bob, Bob picchia una moneta casuale e con probabilmente il 1/2 la moneta casuale potrebbe dare l'uscita 1 o con probabilità 1/2 potrebbe dare l'output 2. E ora ciò che Bob fa sfida è, Bob sfida Alice a mostrare un isomorfismo tra il grafico ith e il nuovo grafico H che Alice ha commesso. Quindi se io = 1 allora praticamente Bob sta sfidando Alice a mostrare un isomorfismo tra il grafico G1 e il nuovo grafico H mentre se io = 2 allora Bob sta impugnando Alice per mostrare un isomorfismo tra il grafico G2 e il nuovo grafico H. Lo sottolineo qui che quando Alice stava commettendo il grafico H, non sa bene in anticipo se si sfiderà a mostrare un isomorfismo tra G1 e H o tra G2 e H. Lei non lo sa in anticipo. Da qui punto di vista con probabilità 1/2 potrebbe essere sfidata a mostrare un isomorfismo tra G1 e H e con la probabilità 1/2 potrebbe essere sfidata a mostrare un isomorfismo tra G2 e H. Now una volta che Bob lancia la sfida Alice deve rispondere. E la risposta sarà diversa a seconda che io = 1 o se i = 2. Namely se la sfida è i = 2 che significa che se Alice viene sfidata a mostrare l'isomorfismo tra G2 e H allora può semplicemente fornire la biezione σ che ha usato per calcolare H dal grafico G2 grafico. Quindi quella sarà la sua risposta. Quindi sto denotando la risposta di ρ qui. Così ρ sarà; la risposta ρ non sarà altro che la mappatura σ se io = 2. Dall'altra parte, se Bob ha sfidato Alice a mostrare un isomorfismo tra il grafico G1 e H, allora sostanzialmente Alice può rispondere componendo la mappatura Π che ha scelto di passare dal grafico G2 a H. Perché se comporiamo Π da G1 arriviamo a G2, Alice arriva da G1 a G2 e poi si compone di nuovo con la mappatura σ da G2 può andare al grafico H. Quindi il modo di passare da G1 a H è quello di comporre la mappatura Π con la mappatura σ. E se effettivamente Alice conosce Π dovrebbe essere in grado di comporre Π e σ e può rispondere con questa risposta ρ. Ora Bob deve verificare se effettivamente Alice ha risposto correttamente o meno. Quindi quello che Bob controlla è che Alice si supponga di mostrare un isomorfismo tra il grafico ith e H e la risposta di Alice sta mappando ρ e Bob deve solo verificare se effettivamente il grafico Gi porta Bob al grafico H come per questa mappatura ρ oppure no. Se poi è Bob è convinto che Alice abbia superato con successo questo round altrimenti Bob dice che Alice ha fallito in questo round. E quello che Bob sta andando a fare è Bob che ripeterà tutto questo processo e cioè Alice che sta impegnando qualcosa di Bob impugnando e Alice di nuovo presentando la risposta k numero di volte e per ognuno di questi round Alice deve scegliere l'impegno casuale H che significa che sarà freschissima a scegliere il grafico H per ogni round o ogni iterazione e nello stesso modo Bob raccoglierà casualmente le sfide i per ogni round, indipendente da ogni round precedente. Il che significa che non sarà il caso che in ogni round Bob sarà picking i = 1 o i = 2. E il verificatore Bob andrà in uscita 1 e cioè dirà che effettivamente Alice conosce la mappatura segreta Π, se tutti i round hanno successo dal punto di vista di Bob, questo significa in tutti i round che Alice ha presentato con successo le risposte ρ. Mentre se uno dei round Alice fallisce allora Bob outmette rifiuto. Questo significa che Bob respinge la rivendicazione di Alice. Ecco il protocollo zero - conoscenza qui per il problema del grafico isomorfismo. (Riferimento Slide Time: 18.47) Ora facciamo l'analisi, vediamo se questo protocollo isomorfismo grafico soddisfa i requisiti di correttezza, solidità e zero - conoscenza o completezza, solidità o conoscenza zero. Quindi la proprietà di completezza o la proprietà di correttezza qui è semplice, se effettivamente Alice è onesta vuol dire che conosce la mappatura segreta Π tra il grafico G1 e G2 e se sta seguendo le istruzioni di protocollo onestamente e se anche il verificatore è onesto allora ogni round avrà successo. Perché non sa se Bob sfida con i = 1 o con i = 2. Alice sarà sempre in grado di rispondere con successo con la giusta mappatura ρ e da qui tutti i round avranno successo. (Riferirsi Slide Time: 19.30) Ora analizziamo la proprietà di solidità qui e ricordiamo per la proprietà fondiaria che dobbiamo considerare il caso quando Alice è potenzialmente corrotta. E non conosce la mappatura tra G1 e G2 o al primo posto potrebbe non esserci alcuna mappatura tra G1 e G2 che mostrano che sono isomorfi e quindi da quando è danneggiata potrebbe non seguire il protocollo, e ricordarsi come per il protocollo che dovrebbe inviare una copia isomorfica di G2 in ogni round ma non lo fa anche lei. Quindi per la solidità dobbiamo analizzare che con quanta probabilità riesce a tradire con successo anche se non segue il protocollo e non ha l'isomorfismo tra il grafico G1 e G2 disponibile con lei. Si scopre che l'unico modo in cui può barare in un giro è indovinare in anticipo quale sarà la sfida dall'onesto Bob. Perché se riesce a indovinare correttamente bene in anticipo se i = 1 o se i = 2 allora al primo posto stesso può creare una copia isomorfica di Gi. Quindi ricordati che come per i passi di protocollo che avrebbe dovuto creare una copia isomorfica di G2 ovvero H dovrebbe essere una copia isomorfica di G2. Ma se Alice è corrotta potrebbe non essere in grado di seguire il protocollo, potrebbe provare a indovinare in anticipo che potrei essere 1, potrei essere 2 e rispetto a quella indovina può creare un isomorfo di quel grafico Gi. E se effettivamente la sua ipotesi è corretta sarà in grado di inoltrare correttamente la risposta ρ. Ma la probabilità che lei riesca a indovinare correttamente se ho intenzione di essere 1 o se andrò a 2 è 1/2. Il che significa con solo probabilità 1/2 può barare in un solo turno e finire con successo passando quel giro. Ma dal momento che ripetiamo questo processo k numero di volte, proprio perché ricordare Bob non è convinto solo facendo questo protocollo una volta; a seconda di quanta fiducia voglia essere nella rivendicazione di Alice, potrebbe ripetere il protocollo k numero di volte. Quindi qual è la probabilità che in ciascuna di k iterazione una brutta Alice che non conosce l'isomorfismo tra G1 e G2 finisca con successo superando tutti i k round. La probabilità che abbia successo al primo turno è di 1/2; la probabilità che abbia successo nel secondo giro è anche il 1/2. E ricordate, la probabilità di successo; ottenere successo nel secondo turno è indipendente dalla probabilità di ottenere successo al primo turno. Perché al secondo turno anche la sfida di Bob sarà indipendente dalle sfide che Bob ha scelto al primo turno. Ecco allora che la probabilità che Alice abbia successo nel secondo turno è di 1/2 e piace che la probabilità che Alice riesca a tradire Bob in tutti i round indovinando in anticipo la sfida di Bob in tutti i round è 1/2 * 1/2 * 1/2 * 1/2 … k volte che non è altro che 1/2k. Quindi se k è significativamente grande dire immagina k = 100 e se una Alice non conosce l'isomorfismo tra G1 e G2 allora sicuramente esiste almeno uno dei round con molto alta probabilità dove Alice verrà catturata e da qui Bob rifiuterà la dichiarazione di Alice. L'unico caso Alice avrà successo in tutti i round è quando è in grado, quando è abbastanza fortunata da indovinare la sfida di Bob in tutti i k round in anticipo che può accadere solo con probabilità 1/2k che è molto piccola se k diventa significativamente grande. (Riferirsi Slide Time: 23.11)Ora cerchiamo di capire la proprietà zero - conoscenza qui dove; ricordate per zero conoscenze dobbiamo considerare il caso in cui Alice è onesta e Bob è corrotto, il verificatore è corrotto. E l'obiettivo del verificatore corrotto è quello di analizzare la trascrizione del protocollo e imparare la permutazione segreta Π che mappa il grafico G1 al grafico G2 ovvero l'isomorfismo tra il grafico G1 e G2. Si scopre che in ogni round il verificatore corrotto non impara nulla sulla mappatura Π, perché se la sfida da Bob è i = 2 allora la risposta che Alice lancia è la mappatura dal grafico G2 a H che non rivela nulla di una mappatura segreta Π. D'altra parte, se il verificatore sfida Alice con i = 1 allora in quel caso Alice risponde con la composizione della mappatura segreta Π con un'altra mappatura scelta casualmente σ. E dato che σ è scelto casualmente; nell'iterazione si può immaginare che σ si stia comportando come qualche tipo di maschera qui, perché da quando σ viene scelto casualmente e Π è qualsiasi quanto scelto casualmente e disponibile solo con Alice; questa mappatura complessiva σ non rivela nulla sulla mappatura segreta Π perché la masking qui ovvero la mappatura segreta σ viene scelta casualmente da Alice. E siccome σ viene scelto casualmente in ogni iterazione indipendente da tutte le iterazioni anche se un prover malevolo continua a impugnare Alice con i = 1 non mancherà di imparare la mappatura segreta Π e questo trattiene anche se il verificatore è computazionalmente delimitato. Così in quel senso un Bob malevolo non impara nulla sul testimone segreto Π disponibile con Alice. Così dimostra che questo sistema a prova di conoscenza zero che abbiamo progettato per il problema dell'isomorfismo grafico soddisfa infatti tutti i requisiti di un sistema a prova di zero conoscenze per un problema di isomorfismo grafico. Così questo mi porta alla fine di questa lezione. Tanto per riassumere in questa lezione abbiamo introdotto il problema del sistema a prova di conoscenza zero, abbiamo formalmente dichiarato i loro requisiti cioè la completezza, la solidità e l'obbligo di conoscenza zero e abbiamo visto anche un'istanza