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 – Bangalore Lezione – 53 Schemi di identificazione (Riferimento Slide Time: 00.39) Ciao a tutti, benvenuti a questa lezione. Il piano per questa lezione è il seguente. In questa lezione introdurremo la definizione di schema di identificazione, che è un noto primitivo criptografico e vedremo un instanziamento di schema di identificazione, ovvero vedremo la descrizione dello schema di identificazione di Schnorr basato sull'assunzione di log Discrete. Nella lezione successiva vedremo che come usare l'euristico di Fiatt-Shamir, possiamo convertire lo schema di identificazione Schnorr in un'istanza di schema di firma digitale basato su ipotesi di log discreto. (Riferimento Slide Time: 01 :01) Quindi cerchiamo di capire la motivazione dietro il regime di identificazione. Quindi, ancora un esempio, che ho dichiarato durante la nostra prima lezione. Così, questo è un noto episodio di Sunderkand a Ramayana. Così, Ram è in India ed è molto deluso. Manca mamma Sita, così istruisce il suo messaggero che ti preghiamo di passare il mio messaggio a Sita che mi manca. Il messaggero e cioè Lord Hanuman dice che come desiderate il mio signore e poi Ram dice che visto che incontrate Sita per la prima volta, potrebbe chiedervi di provare la vostra identità. Così puoi prendere questo anello come prova perché solo Sita sa di questo anello e il messaggero prende l'anello e va in Sri Lanka e poi inizia l'interazione con mamma Sita dicendo che io sono il messaggero di Lord Ram e ho un messaggio per te. Ma Sita è così spaventata lì, quindi non è disposta a credere a Hanuman, poi chiede come posso fidarmi di te e dimostrare la tua identità e Hanuman dimostra la sua identità mostrando l'anello che Lord Ram ha dato a Hanuman e una volta che Madre Sita vede l'anello, lei accetta l'identità del messaggero. Così, in questo esempio, l'anello funge da prova e conferma l'identità e la prova di Hanuman. La prova che Hanuman ha dato è mostrata in chiaro, ma si scopre, che è estremamente pericoloso mostrare la prova in chiaro nell'era attuale di Kalyuga dove la prova è molto volatile e le persone potrebbero non fidarsi a vicenda. Quindi, lo schema di identificazione è un primitivo crittografico, sostanzialmente è un protocollo n-interactive tra due entità, che permette a un provino di dimostrare la propria identità. In questo esempio, Hanuman senza rivelare le credenziali segrete e cioè l'anello. Quindi, passiamo nei dettagli formali del regime di identificazione e siamo interessati alla costruzione dello schema di identificazione nell'impostazione della chiave pubblica, e più precisamente ci concentreremo su tre piani di identificazione della risposta di sfida rotonda o impegnativo, ma non è necessario che il vostro schema di identificazione abbia tre round. Ma siamo interessati a studiare solo lo schema di identificazione costituito da tre round di interazione, perché più avanti vedremo come costruire schemi di firma da tre schemi di identificazione tonda. Così un sistema di identificazione è costituito da quattro protocolli. Così abbiamo algoritmo di generazione chiavi e avremo due algoritmi, P1 e P2 per il prover che vuole dimostrare la sua identità. E avremo un protocollo o un algoritmo per il verificatore utilizzando il quale il verificatore può verificare l'identità del provino. Quindi, il modo in cui usiamo uno schema di identificazione è il seguente. Quindi, abbiamo un prover e un verificatore. L'algoritmo di generazione chiavi sarà gestito perlopiù dal prover e eseguirà l'algoritmo di generazione della chiave per ottenere una chiave di verifica e una chiave segreta. La chiave di verifica sarà disponibile in ambito pubblico per verificare l'identità del cosiddetto prover mentre la chiave segreta sarà disponibile solo al prover e utilizzando questo schema di identificazione, l'obiettivo del prover è quello di convincere il verificatore che è a conoscenza della chiave di verifica che effettivamente il prover conosce la corrispondente chiave segreta associata a questa vk chiave di verifica e il modo in cui questo avviene è di un protocollo di 3 round. Così durante il primo turno, il prover esegue l'algoritmo P1, che prende una chiave segreta di input e outmette l'impegno, che noi denottiamo da I, e l'impegno viene dato al verificatore. Il prover invia l'impegno al verificatore e insieme a che l'algoritmo P1 outmette informazioni di stato, che prover tiene con se stesso. Ora vedendo l'impegno, il verificatore sceglie una sfida, che dengo di r. Questa sfida viene selezionata da uno spazio di sfida e la sfida viene prelevata uniformemente dallo spazio di sfida e nel vedere la sfida r dal verificatore, il prover deve arrivare con una risposta, e la risposta è denotata da s, che viene calcolata eseguendo l'algoritmo P2, che prende il tasto segreto, le informazioni dello stato e la sfida. Nel vedere la risposta, il verificatore deve verificare se il prover ha risposto correttamente in risposta alla sfida r, rispetto all'impegno I, che prover ha commesso al round 1 e a verificare il verificatore esegue l'algoritmo V, che prende la chiave di verifica, la sfida e la risposta e l'obiettivo del verificatore è verificare se l'output di questo algoritmo V sia uguale all'impegno I o meno. Se l'output corrisponde all'impegno sottoscritto poi diciamo che il verificatore accetta l'identità del prover, questo significa verificatore è convinto che effettivamente il prover sia la persona che conosce la chiave segreta corrispondente alla chiave di verifica pubblicamente disponibile, mentre se questa prova che l'uscita dell'algoritmo V dovesse essere uguale a me fallisce, allora il verificatore non è convinto che il prover che ha effettivamente partecipato a questo protocollo conosce il corrispondente tasto segreto. Quindi un'esecuzione di successo in questo protocollo implica che la comunicazione sia avvenuta effettivamente con il provino e non un impostore. Più precisamente richiediamo le seguenti due proprietà da uno schema di identificazione. Quindi, la prima proprietà è la proprietà di correttezza, che dice che per ogni coppia di chiavi che il vostro algoritmo di generazione di chiavi potrebbe produrre e ogni trascrizione, generata percorrendo un'istanza dello schema di identificazione, il seguente dovrebbe tenere. Se il verificatore esegue l'algoritmo di verifica rispetto alla chiave di verifica e alla componente r e s della trascrizione, dovrebbe dare il componente I della trascrizione. Ciò significa che la verifica dovrebbe avere successo nel lato verificatore. Quindi, ecco la proprietà di correttezza. La proprietà di sicurezza in modo informale richiede che un impostore o un eavesdropper che abbia eavesato un'interazione tra un numero polinomiale di prover e verificatore dei tempi non debba essere in grado di arrivare ad accettare la trascrizione e ottenerlo correttamente al lato verificatore e questo dovrebbe tenere se il mio avversario è computazionalmente delimitato. Quindi praticamente quello che significa è, se l'avversario ha visto il numero polinomiale di conversazioni tra un prover onesto e un verificatore onesto allora anche dopo aver assistito a un numero polinomiale di conversazioni in assenza del tasto segreto di sbalzo e solo con la conoscenza della chiave di verifica vk, non dovrebbe essere possibile per l'eavesdropper computazionalmente finto un prover e arrivare con una conversazione accettante, che viene accettata al lato verificatore. (Riferimento Slide Time: 08 :48) Così, modelliamo questo requisito questo requisito informale da un esperimento di sicurezza. Così in questo esperimento, che chiamiamo come esperimento di identificazione Ident (, abbiamo un avversario delimitato dal punto di vista computazionale e lo sfidante e la descrizione dello schema di identificazione è noto pubblicamente, quindi lo sfidante va per primo e gestisce l'algoritmo di generazione chiave, mantiene la chiave segreta con se stesso, e invia la chiave di verifica all'avversario. Ora, quello che l'avversario può esigere è, può chiedere l'accesso oracolo al servizio di trascrizione e questo modello il fatto che nel mondo reale potrebbe esserci un avversario che potrebbe aver visto il numero polinomiale di interazioni, o il numero polinomiale di istanze dello schema di identificazione che vengono eseguite tra un onesto prover e un onesto verificatore. Quindi, quell' avversario potrebbe aver visto il numero polinomiale di trascrizioni sotto il tasto sconosciuto, che potrebbe essere disponibile solo con il prover. Quindi, per modellare che, diamo all'avversario qui Oracle l'accesso al servizio di trascrizione, per rispondere a questo accesso Oracle, quello che lo sfidante deve sostanzialmente fare quanto segue. Così, conosce il tasto di verifica vk, e conosce anche il tasto segreto, quindi gestisce l'istanza di questo schema di identificazione, simulando nella sua mente il ruolo del prover e del verificatore. Quindi, in sostanza, gestisce solo l'istanza di questo schema di identificazione come interpreta il ruolo del prover stesso. Giocando il ruolo del verificatore stesso e genera il corrispondente I, r, s e che la trascrizione viene restituita in risposta al servizio di accesso Oracle che l'avversario ha chiesto e dato che l'avversario potrebbe chiedere l'accesso Oracle al servizio di trascrizione per un numero di volte polinomiale, ogni volta che arriva tale accesso Oracle o Oracle, lo sfidante deve generare una trascrizione simulata come questa e data all'avversario. Una volta che l'avversario viene allenato vedendo il numero polinomiale della trascrizione, cerca di arrivare con una trascrizione forgiata e cercare di farla accettare dallo sfidante. Quindi per farlo, pretende come se fosse il provino e cerca di inventarsi la trascrizione accettata senza nemmeno conoscere il corrispondente sò segreto, quindi sottopone un impegno, che io dengo da I*. In risposta lo sfidante sottopone una sfida, che io dengo di r *, e in risposta alla sfida l'avversario sottopone una risposta s *. Questa tripletta I*, r *, e s * è una trascrizione forgiata, che l'avversario sta cercando di produrre rispetto a questo intero esperimento e la definizione dell'esperimento dice che l'avversario è in grado di forgiare una trascrizione, che è denotato dicendo che l'output di questo esperimento è uno, se e solo se l'algoritmo di verifica v, quando gestito dal sfidante rispetto alla chiave di verifica, e r * componente, e s * componente di questa trascrizione forata effettivamente dà I*. Il che significa, I*, r *, s * costituisce una trascrizione accettante, e la nostra definizione di sicurezza è che diciamo che un sistema di identificazione è sicuro se per ogni avversario polare che partecipa a questo esperimento, la possibilità che possa vincere l'esperimento è delimitata da qualche funzione trascurabile. (Riferimento Slide Time: 12 :42) Quindi, ecco la nostra definizione del nostro schema di identificazione. Ora, vediamo se riusciamo ad arrivare con una istanziazione di un simile schema e c'è un ben noto schema di identificazione dovuto a Schnorr, e si basa sulla seguente idea. Così, sostanzialmente il prover in questo schema di identificazione cerca di dimostrare la propria identità dicendo che conosce il registro discreto di un valore noto pubblicamente sotto la base g DLog (, e di verificare la rivendicazione del provino, il verificatore sfida sostanzialmente il prover a mostrare una combinazione lineare casuale del log discreto di y, dove i combinatori casuali per la combinazione lineare saranno selezionati dal verificatore. Quindi, l'idea qui è che effettivamente se il prover conosce il log discreto di y, allora dovrebbe essere in grado di produrre una combinazione lineare casuale del log discreto di y con qualsiasi altro valore dalla gamma corrispondente del log discreto, e questa interazione intera avviene nella moda a conoscenza zero nel senso che durante tutta l'interazione, sarà garantito che effettivamente il prover conosce il discreto log di y alla base g, poi il log discreto non viene appreso da un verificatore dannoso. Quindi, l'algoritmo di generazione chiavi di questo schema è il seguente. Esso outmette una chiave di verifica e la chiave segreta, dove la chiave di verifica è la descrizione di un gruppo ciclico di ordine q e una descrizione del generatore e l'elemento casuale y dal gruppo dove y è sostanzialmente gx, dove x è selezionato dal set da 0 a q - 1 e la chiave di verifica cioè il log discreto di y, che è x sarà disponibile con il prover, mentre la chiave di verifica sarà disponibile con il verificatore. Così, il prover va per primo in questo schema di identificazione e commette un valore k dal set selezionato Zq mediante calcolo gk, quindi questo è un valore casuale che dà al verificatore e la sfida scelta dal verificatore è un valore casuale r, selezionato dal set Zq e per rispondere alla sfida, in sostanza il prover deve arrivare con una combinazione lineare del log discreto x della y. Il valore k che ha selezionato nel girone 1 e la combinazione lineare casuale qui è (r * x + k) modulo q e per verificare se la risposta del prover è corretta o meno, il verificatore deve verificare se gs * y - r = I o meno, cosa che dovrebbe effettivamente essere il caso se effettivamente il prover sa x e ha inviato gk durante la prima rotonda, vediamo una definizione qui, diciamo un triplice I, r, s dove sono un elemento di gruppo, e r e s sono elementi di Zq è una trascrizione accettante se gs * y - r = I detiene e la proprietà di correttezza dello schema di identificazione sono di Schnorr consegue dal fatto che effettivamente il prover e il verificatore sono onesti e prover conosce quel discreto registro di y. E cioè sa x, poi la trascrizione generata percorrendo un'istanza dello schema di identificazione Schnorr sarà effettivamente una trascrizione accettante. Quindi la verifica alla fine del verificatore avrà successo. Così che dimostra la proprietà di correttezza. Ora, cerchiamo di capire la proprietà di sicurezza qui. Quindi, consideriamo per la prima volta un eavesdropper qui e immaginate prover e verificatore sono onesti e c'è un eavesdropper che ha monitorato il numero polinomiale di esecuzioni dello schema di identificazione Schnorr. Quindi immagina che abbia eavesato su una trascrizione, che sia io, r, s, e affermo qui che vedendo la trascrizione non imparare nulla sul tasto segreto sk, ovvero il discreto registro di y alla base g, che è x, e questo è perché se si vede la distribuzione dell'impegno cioè il I, è indipendente da x perché l'impegno I è gk, dove k viene prelevato indipendente da x. Allo stesso modo, il componente r della trascrizione, è completamente indipendente da x e viene prelevato dal verificatore, quindi non rivela nulla sul segreto x. Tuttavia, se si vede il valore s, allora il valore è (r * s + k), quindi si potrebbe sentire che vedendo s, l'eavesdropper potrebbe imparare qualcosa su x, ma questo non è il caso qui perché la distribuzione di s qui è indipendente da x perché il k che viene utilizzato nella combinazione lineare s è indipendentemente e casualmente scelto dal prover, e se il prover è onesto, allora il valore k, utilizzato nella combinazione lineare, sarà uniformemente casuale e sconosciuto all'avversario. Il che significa solo vedere l'avversario, di nuovo non si può capire nulla di x e questo significa un eavesdropper che vede una trascrizione accettante I, r, s, non imparerà nulla del segreto sottostante x. Quello che l'avversario o l'eavesdropper impareranno solo che la trascrizione I, r, s è una trascrizione accettante e la sua distribuzione è indipendente da x. Quindi in base a questa osservazione possiamo fare una rivendicazione molto forte qui che, possiamo dire qualsiasi eavesdropper può simulare una trascrizione accettante basata sulla conoscenza della chiave di verifica stessa. Il che significa, è bello come dire che anche se non accade nessuna interazione tra il prover e il verificatore l'eavesdropper potrebbe benissimo arrivare con una distribuzione di probabilità della trascrizione, che si vedrebbero intravezionando una vera conversazione tra il prover e il verificatore e come questo possa essere possibile, ecco il modo in cui l'avversario o l'eavesdropper potrebbe arrivare con una trascrizione simulata da sola senza nemmeno origarne la conversazione tra il prover e il verificatore. Quindi, quello che l'eavesdropper potrebbe fare è, potrebbe scegliere casualmente un valore r e s valore da Zq e poi una volta picchia il valore r e s valore, potrebbe impostare il valore I come gs value ha scelto, moltiplicato per y - r value che ha scelto, e si scopre che se si confronta la distribuzione di probabilità delle trascrizioni reali, e da veri trascrizioni, intendo le trascrizioni, che sono effettivamente generate dalla vera esecuzione di questo schema di identificazione Schnorr dove un onesto prover e un verificatore onesto partecipa al protocollo. Se consideriamo la distribuzione di probabilità delle trascrizioni simulate, in base alla quale le trascrizioni simulate, intendo, le trascrizioni generate dall'eavesdropper con questo metodo, dove non si vede la reale esecuzione del protocollo, ma si arriva con i valori di I, r, s usando il metodo, di cui ho discusso poco adesso. Quindi se considero la distribuzione di probabilità di queste due trascrizioni, sono esattamente identiche. Questo perché se si vede la distribuzione di probabilità del valore r nelle trascrizioni reali e la distribuzione di probabilità del valore r sotto trascrizioni simulate sono identiche. In una esecuzione reale, r sarà scelto casualmente dal set Zq, e nella trascrizione simulata anche i valori r vengono prelevati casualmente dal set Zq. Allo stesso modo nella trascrizione vera e propria s si intende un valore uniformemente casuale da Zq perché k sarebbe stato scelto uniformemente casualmente dal provino. Lo stesso vale per il valore s nelle trascrizioni simulate e se si vede la distribuzione di probabilità del valore I nelle trascrizioni reali così come nelle trascrizioni simulate in entrambi i casi I = (gs * y - r) parti delle trascrizioni e questo vale sia per la trascrizione vera sia per la trascrizione simulata. Quindi se si vede la distribuzione saggia, il modo in cui le trascrizioni sarebbero state generate in una vera e propria esecuzione del protocollo e il modo in cui le trascrizioni sono generate dall'avversario nella sua mente senza vedere realmente alcuna conversazione hanno esattamente la stessa distribuzione. Il che significa che solo origliando la comunicazione tra un prover onesto e un verificatore non aiuterà l'avversario a imparare qualcosa sulla sottostante chiave segreta x. Ora ecco un alimento per il pensiero per voi. Dal momento che sto affermando qui che se eavesdropper potrebbe simulare e arrivare con una trascrizione accettante da solo senza nemmeno conoscere il tasto segreto sk, vuol dire che usare la strategia, che il simulatore sta usando o l'eavesdropper sta usando per arrivare con la trascrizione simulata, potrebbe forgiare una trascrizione accettante e partecipare ad un'istanza dello schema di identificazione Schnorr e finire per convincere un verificatore onesto che effettivamente conosce il valore x, cosa che non è esattamente il caso. Si scopre che non è il caso perché il motivo è se si vede la strategia di simulazione qui, il modo in cui l'avversario è arrivato con la trascrizione simulata, sta fissando il valore r e s valore per cominciare. Il che significa che nella sua mente si indovina che questo potrebbe essere il valore r o il valore di sfida, che il verificatore sceglierebbe e solo dopo aver aggiustato il valore r e s valore, sta arrivando con il suo impegno I. Quindi, se con questa strategia cerca di partecipare a un'esecuzione dello schema di identificazione Schnorr con un verificatore onesto, allora la probabilità che effettivamente sia in grado di arrivare con una trascrizione accettante che viene accettata dal verificatore è uguale alla sfida r, che l'avversario sta pensando bene in avanti nella sua mente corrisponde esattamente alla trascrizione che un onesto verificatore sta effettivamente andando a prendere durante la reale esecuzione del sistema di identificazione Schnorr. Ma la probabilità che il valore di r simulato, che l'avversario indovina nella sua mente ben più avanti corrisponde al valore esatto della sfida r che va scelto dal verificatore è uno sulla dimensione di Zq set, ovvero il suo 1/q e se q è sufficientemente grande, allora si tratta di una quantità molto ridotta una funzione trascurabile nel parametro di sicurezza. Quindi, questo significa che questa strategia di simulazione non aiuterà l'eavesdropper a vincere o a forgiare o a rompere questo schema di identificazione. Quindi quello che abbiamo dimostrato fino ad ora è che l'eaveschi non aiuterà sicuramente l'avversario a rompere la sicurezza del sistema di identificazione Schnorr, quindi solo così potrebbe attaccare questo schema di identificazione, senza sapere la chiave segreta è che deve interagire con un verificatore onesto come segue. Così deve arrivare con qualche impegno rispetto ad una qualche strategia che l'avversario ha nella sua mente, e una volta che il verificatore lancia una sfida, deve arrivare con una risposta s, tale che gs * y - r effettivamente uguale a I e se vogliamo che l'avversario sia in grado di rompere la sicurezza del sistema di identificazione Schnorr con alta probabilità, allora dovrebbe essere il caso che questo avversario che sta cercando di spezzare la sicurezza dovrebbe arrivare con la sua risposta s indipendentemente da quale valore di r sia usato come una sfida da parte del verificatore. Questo significa, quello che sto cercando di dire qui è che una volta avversario ha commesso qualche valore e ha presentato il suo impegno I, e se effettivamente quell' avversario è in grado di spezzare la sicurezza di questo schema di identificazione con ottime probabilità, allora non importa quale sia esattamente la sfida. Potrebbe essere r1, potrebbe essere r2, potrebbe essere qualsiasi cosa. Per qualsiasi valore di sfida, dovrebbe essere possibile che l'avversario arrivi con la risposta rispondendo s tale che gs moltiplicato per y - r debba essere uguale all'impegno dell'avversario. Il che significa, una volta che l'avversario ha presentato il suo impegno, non importa se la sfida è r1, corrispondente al r1 l'avversario dovrebbe essere in grado di arrivare con s1 tale che questa proprietà o questa verifica abbia successo o non importa se il verificatore lancia lo sfidante come r2, ancora dovrebbe essere possibile per l'avversario che per lo stesso impegno io e la sfida r2 l'avversario possa arrivare con la corrispondente risposta s2, tale che la verifica abbia successo al verificatore si finisce perché se l'avversario sa solo arrivare con la risposta per alcuni valori specifici della sfida, allora non è una buona strategia avversaria. provare questa affermazione formalmente. Quindi per questo vi presento qualche notazione. Quindi, lascia che ω denoti la casualità utilizzata in questa intera riduzione tranne i valori di sfida r1, r2 prelevati dal solutore di log discreto. Così, l'ω denota la casualità utilizzata dallo sfidante nell'esperimento di log discreto. Denota la casualità usata dall'avversario contro lo schema di identificazione, e denota anche la casualità utilizzata dal solutore di log discreto tranne che per la casualità usata per raccogliere le sfide r1 e r2 in questo intero esperimento. Ora, io uso questa quantità V (ω r) e dico che questa funzione V (ω r) = 1, se corrispondente alla casualità ω e corrispondente alla sfida r, l'avversario contro lo schema di identificazione potrebbe arrivare con una trascrizione accettante. Se è così, allora dico che l'uscita della funzione V (ω r) è 1, altrimenti è zero e rispetto a una casualità fissa ω questa quantità δ ω è definita la probabilità che l'output della funzione V rispetto alla casualità fissa ω su tutte le possibili challenge r = 1. Ecco la mia quantità δ ω quindi è sostanzialmente la probabilità dell'avversario contro lo schema di identificazione che arriva con una trascrizione accettante rispetto a una casualità fissa ω su tutta la possibile sfida la casualità r, e poi mi faccia chiamare questa funzione δ (n) a essere la probabilità con cui questo avversario contro lo schema di identificazione può vincere il gioco di sicurezza contro lo schema di identificazione in questa riduzione. Così, come per le nostre notazioni che abbiamo introdotto fino ad ora questo δ (n) non è altro che probabilità di tutte le casualità ω la probabilità su tutta la sfida di casualità r, la probabilità che V (ω, r) = 1, e se la allarmiamo ulteriormente, non è altro che sommatoria di tutte le casualità ω che quella che è la probabilità che ω sia la casualità utilizzata in questa intera riduzione tranne che per la sfida casualità e rispetto a quella casualità fissa ω, qual è la probabilità di δ ω Così è così che espandiamo la nostra funzione δ (n). Ora, se si vede questa intera riduzione, il nostro discreto tronco di log può estrarre con successo il log discreto x solo se queste tre condizioni tratteggiano cioè I, r1, s1 è una trascrizione accettante e io, r2, s2 è una trascrizione accettante e le sfide r1 e r2 sono diverse dove le sfide r1 e r2 sono scelte casualmente dal discreto log solutore. Così, possiamo affermare formalmente che la probabilità che il nostro discreto log solutore possa risolvere il log discreto è la probabilità che se si prende la probabilità su tutta la casualità ω e tutta la sfida casualità r1 e r2, V (ω, r1) = 1. Questo cattura il fatto che io, r1 e s1 dovrebbero accettare la trascrizione e V (ω, r2) dovrebbe essere 1. Questo cattura il fatto che io, r2 e s2 dovrebbero accettare la trascrizione e r1 dovrebbe essere diverso da r2. Questo cattura la terza condizione. Quindi ora quello che dobbiamo fare è semplicemente espandere questa espressione di probabilità perché questa probabilità supera tutte le candidate casualità ω sfida casualità r1 e sfida casualità r2. Quindi, usando le regole di probabilità se risolgo, poi questa quantità r1 non uguale a r2, posso sostituire con la probabilità r1. Posso prendere questa probabilità di ω r1 e r2 all'interno e poi posso sostituirmi a questa condizione AND da questa condizione di sottrazione e ciò che posso fare è sapere che questa cosa che posso fare è sapere che questa cosa con probabilità che la mia sfida casualità r1 e r2 sia diversa è 1/q perché sia r1 che r2 sono prelevati casualmente dal set Zq e ora quello che posso fare è, posso espandere questa prima quantità e la seconda quantità rispetto a r1 e r2 a valori fissi ω, questi due eventi di V (ω r1) dovrebbero essere 1 e V (ω, r2) dovrebbero essere 1, sono indipendenti l'uno dall'altro, perché r1 e r2 vengono scelti in modo indipendente da il solutore di log discreto. Quindi, se sistemiamo la casualità ω e prendi l'ω dentro e cerco di espandersi rispetto alla casualità r1 e r2, la disuguaglianza qui poi praticamente ho capito che la disuguaglianza sopra si spegne a questa cosa e ora posso applicare la ben nota disuguaglianza di Jensen, che non sto affermando qui. Puoi usare qualsiasi riferimento standard per scoprire la formula di Jensen di disuguaglianza di Jensen, quello che posso fare è che posso prendere la piazza qui dentro l'espressione probabilità di casualità ω accada qui. Se ora vedete che questa intera grande parentesi qui, la piazza di questa grande parentesi non è altro che δ (n), ecco qual è la definizione di δ (n), δ (n) non è altro che la probabilità con cui l'avversario contro lo schema di identificazione può vincere la partita qui nella riduzione e questo è quello che è l'affermazione che volevamo dimostrare. Abbiamo dimostrato che il vantaggio del solutore di log discreto qui è maggiore o uguale alla piazza del vantaggio dell'avversario del regime di identificazione meno 1/q. Se q è una qualche funzione esponenziale nel parametro di sicurezza, allora questo 1/q è trascurabile e come per l'assunzione che si avvantaggia del solutore di log discreto dovrebbe essere una funzione trascurabile che dimostra che anche la piazza del vantaggio dell'avversario contro lo schema di identificazione dovrebbe essere trascurabile. Quindi, questo mi porta alla fine di questa lezione. Tanto per riepilogare, in questa lezione abbiamo introdotto lo schema di identificazione, che è un primitivo crittografico ben noto e abbiamo visto un'istanziazione dello schema di identificazione