Fondamenta della crittografia Prof. Dr. Ashish Choudhury (Ex) Infosys Foundation Career Development Chair Professor International Institute of Information Technology – Bangalore Collezione – 31 Random Oracle Model – Parte I (Riferirsi Slide Time: 00.30) Ciao a tutti, benvenuti a questa lezione. Solo un breve recap. Nell'ultima lezione abbiamo discusso di alcuni degli attacchi generici che possono essere lanciati sulle funzioni hash, ovvero gli attacchi di compleanno, e abbiamo anche discusso alcune applicazioni delle funzioni hash come catene di Block, alberi di Merkel e così via. In questa lezione proseguiremo la nostra discussione sulla funzione hash crittografica. In sostanza, introdurremo un modello di prova molto interessante quello che chiamiamo modello Random - Oracle. (Riferimento Slide Time: 00 :58) Quindi, iniziamo con la nostra discussione su modello Random - Oracle chiamato anche ROM. Ci sono quindi diversi scenari in cui progettiamo primitivi crittografici dove si utilizzano le funzioni di hash resistenti alle collisioni e quelle costruzioni sono altamente pratiche in natura e sono altamente efficienti. Alcuni esempi di tali primitivi sono la funzione di derivazione chiave, lo schema di impegno, i primitivi a chiave pubblica e così via, ma purtroppo si scopre che non possiamo dimostrare la sicurezza di questi primitivi crittografici in base alle proprietà standard della funzione hash. Quello che intendo per proprietà standard della funzione hash è la proprietà di resistenza alle collisioni, giusto. Quindi quello che fa esattamente Random - Oracle modello ti dà un modello in cui puoi provare la sicurezza dei primitivi crittografici progettati in base alle funzioni hash in cui non è possibile dare i test di sicurezza appena basati sulla proprietà di resistenza alla collisione della funzione hash sottostante e ciò che facciamo in questo modello Random - Oracle stiamo facendo un presupposto molto forte sulla funzione hash sottostante. Ovvero, facciamo una supposizione idealizzata e l'assunzione esatta che facciamo della funzione hash sottostante verrà discussa presto e ciò che questo modello Random - Oracle fa è che agisce da terra di mezzo per te dove non hai alcuna prova di sicurezza in una mano e mentre l'altra mano hai una rigorosa prova di sicurezza proprio in base alle ipotesi di crittografia standard. Dato che non si può dare la prova di sicurezza delle costruzioni in base alle proprietà standard della funzione hash crittografica. Quindi ipotizziamo che siamo nel modello Random - Oracle serve tipo un terreno di mezzo dove facendo supposizioni idealizzate sulla vostra funzione hash sottostante, è possibile completare la prova di sicurezza. (Riferimento Slide Time: 02.47) Così andiamo nei dettagli sottostanti del cosiddetto modello Random - Oracle. Quindi quello che facciamo in questo modello Random - Oracle è supporre che stiamo progettando un primitivo crittografico basato su una funzione hash mapping arbitrario di lunghezza bit a stringhe di dimensioni fisse delle stringhe di bit. Quindi quello che facciamo è ipotizza che le funzioni di hash sottostanti si comportino come una funzione casuale mappando l'input di lunghezza arbitraria alle uscite a lunghezza fissa e immaginate di progettare una primitiva crittografica dove utilizziamo questa funzione hash sottostante modellata come una funzione davvero casuale. Supponiamo che ogni partecipante del sistema abbia accesso oracolo alla funzione hash. Ciò significa che nessun partecipante al sistema incluso l'utente genuino così come l'avversario non conoscerà i dettagli interni e il codice e la logica della funzione hash sottostante. Quindi, questo è un presupposto molto forte che stiamo facendo in merito alla funzione hash sottostante in questo modello perché in realtà quando progettiamo una primitiva crittografica, stiamo per istanziare questa funzione hash per qualche funzione di hash pratico. Quando utilizziamo una qualche funzione hash pratico ogni entità del sistema sarà conoscendo il codice esatto o la logica della funzione hash, ma quando stiamo dando la prova nel modello Random - Oracle, supponiamo che nessuna entità nel sistema conosca i dettagli esatti della funzione hash sottostante. Anche le chiamate tra l'oracolo e i partecipanti sono private. Questo significa, immaginate se ho un primitivo crittografico che coinvolge l'utente 1, l'utente 2 e l'utente 3 e ognuno di essi deve utilizzare questa funzione hash a dire l'utente 1 vuole valutare la funzione hash sottostante su alcuni input x. Poi supponiamo che nel modello Random - Oracle l'interazione tra l'utente 1 e l'interfaccia o l'oracolo H sia attraverso un canale privato tra l'utente 1 e l'oracolo H. Così l'utente 2 e l'utente 3 non starebbero conoscendo gli input esatto su cui l'utente 1 sta andando a valutare la funzione hash sottostante o l'oracolo. Si ipotizza inoltre che l'oracolo H sia mantenuto come una tabella composta da diversi x, y value e il modo in cui questa tabella è mantenuta è la seguente. Se qualche entità interroga questo oracolo su un input x, allora quello che la tabella fa o l'oracolo fa è sostanzialmente verifica nella tabella esistente che è un elenco di diversi valori (xi, yi) se esiste una voce xi con il valore essere x. Questo significa in sostanza, la tabella verifica se il valore dell'oracolo sull'input x è già presente in tavola o meno. Se c'è già, allora i corrispondenti yi vengono restituiti indietro come l'uscita dell'oracolo sull'input x, mentre se non c'è una voce esistente xi con corrispondente il valore x, allora cosa fa l'oracolo? Crea una nuova voce nella tabella in cui memorizza il valore della x e contro quella x memorizza un valore y uniformemente casuale dove il valore y è una stringa di bit uniformemente casuale e che serve come riferimento o l'output della funzione o il valore oracolo o l'uscita oracolo per l'input x per le successive chiamate verso l'oracolo. Quindi mantenendo questo oracolo come un tavolo (x, y) come questo, è garantito che effettivamente l'oracolo soddisfi le proprietà richieste da una funzione davvero casuale, giusto. (Riferimento Slide Time: 06 :06) Quindi ci sono alcune importanti proprietà nel modello Random - Oracle e questo sarà cruciale quando daremo prove nel modello Random - Oracle. Quindi la prima proprietà è che se qualche input x non è stato querizzato all'oracolo H, allora il valore dell'oracolo su questo input x sarà un valore pari a un bit uniformemente casuale e questo vale anche se l'input x è noto a un'entità o ad una parte della x è noto all'entità o anche se x non è uniformemente valore casuale. Questo significa anche se x è qualche input dove tutti i bit dell'input tranne l'ultimo bit sono noti e se l'oracolo non è stato querizzato su quell' input x, allora l'uscita dell'oracolo su quell' input x sarà un valore uniformemente casuale l bit, e sottolineo che questo è diverso dalla proprietà pseudo casualità del generatore di pseudorandom. Diciamo che se abbiamo un generatore di pseudo casualità G, allora la proprietà pseudo casualità ci richiede che la produzione del generatore di pseudorandom G su qualche input x debba essere quasi uguale a un valore uniformemente casuale solo se l'input x per il generatore di pseudorandom è un valore uniformemente casuale e sconosciuto, mentre nel contesto del modello Random - Oracle ci sono proprietà pseudo casualità che richiediamo sono diverse. Qui, qui, richiediamo che se l'oracolo non viene querizzato per l'input x e anche se l'x non è un valore uniformemente casuale ed è noto a voi, il valore di uscita H (x) sarà un valore uniformemente casuale dal co - dominio. Ecco allora una delle proprietà importanti. (Riferimento Slide Time: 07 :41) La seconda proprietà importante nel modello Random - Oracle è di proprietà estrattiva che sarà una proprietà molto cruciale successivamente quando vedremo le prove dei primitivi crittografici nel modello Random - Oracle. Quindi supponiamo di avere una costruzione di crittografia di qualche primitivo, diciamo che questo primitivo C che coinvolge determinate entità, potrebbe essere una comunicazione sicura, un protocollo o potrebbe essere solo qualsiasi tipo di protocolli di crittografia. Ad esempio, immaginate che questa crittografia primitiva C coinvolga 3 entità e questo primitivo richieda anche chiamate ad una funzione hash sottostante e supponiamo di dare una prova di riduzione basata su una prova di riduzione che effettivamente questa primitiva crittografica soddisfa qualche proprietà, qualche proprietà di sicurezza come per qualche definizione, e diciamo che stiamo dando una prova di riduzione a base di riduzione e sostanzialmente quando stiamo dando una prova di riduzione per dimostrare che effettivamente i cosiddetti primitivi di crittografia soddisfano determinate proprietà di sicurezza come per qualche data definizione nel modello Random Oracle allora quando diamo la riduzione sonda a base di sonda quello che in sostanza stiamo andando a fare è che ipotizziamo che diciamo che abbiamo un avversario Un attaccante della tua primitiva crittografica C, poi usando quell' avversario il nostro obiettivo sarà quello di progettare un altro avversario dire che attacca un altro primitivo, giusto. Ecco cosa tiriamo tipicamente nella prova di riduzione a base di riduzione. Ora come parte della sua strategia di attacco, questo avversario A potrebbe aver bisogno di chiamare la funzione hash sottostante, giusto, perché potrebbe essere una parte della sua strategia di attacco sottostante. Ma visto che ora siamo nel modello Random - Oracle, questo avversario ha bisogno di fare oracolo chiamate alla funzione H. Così quando questo avversario A che stiamo progettando come parte della riduzione, sta richiamando questo avversario già esistente A come subroutine, arriverà a sapere che l'avversario A o l'avversario esistente A ha bisogno di invocare l'oracolo H su diversi input x della sua scelta. Quindi quegli input, l'uscita dell'oracolo su quegli input che l'avversario A vuole interrogare sarà ora imparato dall'avversario A come parte della riduzione. Ecco, questo è ciò che intendiamo per la proprietà estrattiva. Questo significa che l'avversario A ora può vedere le x query che l'avversario esistente A vorrebbe fare all'Oracolo H. Questo non contraddice la proprietà che come accennato prima dove ho detto che le chiamate tra ogni entità e oracolo si mantengono o sta accadendo attraverso un canale privato. Nella prova di riduzione, l'avversario A sta praticamente invocando l'avversario A nella sua mente. Questo significa che quando si richiama l'avversario esistente A come subroutine, arriverà automaticamente a sapere che come parte della sua strategia di attacco, quali sono le x query o i valori x per cui l'avversario esistente A vorrebbe fare le chiamate di oracolo H, giusto. Quindi non sta violando la proprietà esistente del modello Random - Oracle, ma il punto importante qui è che in quanto parte della riduzione, il nuovo avversario che stiamo cercando di costruire precisamente A, può estrarre gli input x per i quali l'avversario esistente vorrebbe fare le oracole chiamate. Ecco allora che si tratta di una delle proprietà importanti del modello Random - Oracle e della seconda proprietà. (Riferirsi Slide Time: 11.02) La terza proprietà del modello Random - Oracle che di nuovo sarà molto cruciale quando faremo delle prove dei primitivi crittografici nel modello ROM è la proprietà di programmabilità, e cosa intendo esattamente per la proprietà di programmabilità come ho accennato che se stiamo dando una riduzione basata su dimostrazioni, poi il nuovo avversario A che stiamo progettando quando richiama l'avversario esistente A, imparerà le query H cioè gli input x per cui l'avversario esistente vorrebbe fare le chiamate all'oracolo, giusto. Ma visto che ora stiamo facendo una riduzione qui a destra, non esiste una funzione H che sia effettivamente disponibile sia all'avversario A che all'avversario A perché ora non stiamo invocando un'istanza del primitivo C, giusto. Quando in realtà stiamo istanziando un richiamo del primitivo C, le parti avranno accesso ad un oracolo H, ma ora quello che stiamo facendo qui è che stiamo dando una prova di riduzione basata sulla prova, quindi non c'è alcuna istanziazione del primitivo C. Così, non c'è oracolo disponibile né all'avversario A né all'avversario A, ma dal momento che come parte della riduzione la nostra strategia avversaria A è quella di fare oracolo chiamate per l'oracolo H a diversi input x input fondamentalmente il nostro avversario A deve simulare l'interazione dell'avversario esistente con H. Basically, l'avversario A deve impostare l'output della oracolo H a questi x input che l'avversario A è esigente. Quindi, quello che l'avversario A può fare come parte della riduzione che essa stessa può impostare o può fingere come se la sua stessa abbia l'accesso all'oracolo e ciò che può fare è poter selezionare casualmente alcuni valori di y dal co - dominio dell'oracolo H sottostante e restituirlo come output della query oracolo che l'avversario A ha chiesto. Ecco cosa intendiamo per la proprietà di programmabilità. La chiamiamo come proprietà di programmabilità perché nella riduzione, il nuovo avversario A può programmare, può impostare l'uscita dell'oracolo agli input x per cui l'avversario A ha chiesto la risposta dall'oracolo. Ecco, questa è un'altra importante proprietà del modello Random Oracle che utilizzeremo quando otterremo le prove basate sulla riduzione per i primitivi crittografici nel modello Random - Oracle. (Riferimento Slide Time: 13 :21) Quindi ora confrontiamo una prova data o prova di sicurezza per qualche primitivo crittografico dato nel modello Random - Oracle versus la prova di sicurezza indicata nel modello standard. Quindi ancora immaginare di avere dei primitivi crittografici dire C e implica dire più entità e dove richiediamo a ogni entità di utilizzare alcune funzioni di hash sottostanti. Quindi nel modello standard quando diciamo che abbiamo una prova di sicurezza nel modello standard, non astringiamo la funzione hash sottostante come Random - Oracle. Supponiamo invece che si tratti di una funzione hash standard e di ogni entità ha libero accesso alla funzione hash sottostante. Questo significa, conosce il codice completo, la descrizione completa della funzione hash sottostante. Non facciamo che supponiamo che le entità interagiscono con la funzione hash per oracolo, mentre nel modello Random - Oracle quando ci assumiamo che se si progetta si dice un altro primitivo C che coinvolge la funzione hash. Se diciamo che stiamo dando una prova nel modello Random - Oracle, allora cosa intendiamo esattamente con questo è che ogni volta che stiamo instancando il primitivo C all'inizio una nuova funzione casuale H sarà istanziata e nessuna delle entità saprà cosa esattamente è quella particolare funzione hash, a destra. Ecco, questa è una grande differenza per una prova di sicurezza data nel modello Random Oracle. Questo significa che ogni volta che instanziamo il primitivo C non sarebbe il caso che lo stesso Random - Oracle o la stessa istanziazione dell'oracolo H saranno disponibili come era presente nel precedente richiamo. In ogni successiva invocazione in ogni nuova invocazione o un richiamo indipendente di C °, un oracolo indipendente H sarà fissato all'inizio e ogni istanza avrà accesso a quell' oracolo tramite canali privati in cui nessuna entità saprà cosa esattamente sia la descrizione del sottostante o l'oracolo instanziato. La definizione di sicurezza nelle 2 prove che abbiamo dato qui differirà come segue. Così, daremo una certa definizione di una certa sicurezza, quindi in sostanza la definizione di sicurezza nel modello standard sarà che per tutti i tempi polinomiali avversari o cercando di attaccare il primitivo C, la definizione sarà che la probabilità di un determinato evento dovrebbe essere trascurabile che sarà la definizione di sicurezza per il primitivo C, giusto, nel modello standard e più o meno lo stesso vale anche per una definizione di sicurezza data nel modello Random - Oracle. Ovvero, la definizione di sicurezza sarà che per tutti gli avversari a tempo determinato che tentano di attaccare il modello C primitivo nel modello Random - Oracle, la probabilità di certi eventi dovrebbe essere trascurabile. Ciò che esattamente quell' evento è che dipende dal sottostante primitivo C e sottostante primitivo C che stiamo cercando di costruire. Ad esempio se il primitivo C è un processo di crittografia sicuro, allora sostanzialmente quell' evento è l'evento di distinguibilità. Mentre se il primitivo C è una crittografia molto complicata, allora quell' evento che definisce se l'avversario è in grado di vincere il gioco o meno potrebbe essere un evento complicato, ma indipendentemente da questo, l'intuizione sottostante è che nella definizione standard di sicurezza del modello significa che la probabilità di avversari avversari o la rottura certa o la probabilità che un avversario garantisca che un determinato evento si verifichi con qualche probabilità è trascurabile mentre nel modello ROM la definizione di sicurezza più o meno rimane la stessa. La differenza è che nel modello standard la probabilità viene presa sulla scelta casuale delle parti e non sulla funzione hash sottostante perché la funzione hash sottostante sarà una funzione hash fissa perché ogni volta che andremo a instanziare il primitivo C nel modello standard, la stessa funzione hash verrà utilizzata ancora e ancora, ma quando stiamo valutando la probabilità che quel determinato evento sia trascurabile nel modello Random Oracle allora la probabilità viene presa non solo sulle query casuali sulle parti ma anche sulla scelta casuale dell'oracolo H che è istanziato all'inizio dell'istanziazione del primitivo C. Quindi, ecco un'altra differenza importante nella prova di sicurezza nel modello Random - Oracle contro una prova di sicurezza nel modello standard. (Riferimento Slide Time: 17 :29) Quindi questo significa che nel modello Random - Oracle, la sicurezza è garantita non per ogni possibile istanziazione Oracle. Significa che la sicurezza non può essere garantita per una particolare istanziazione di H, ma potrebbe essere garantita per altre istanziazioni di H, mentre nella definizione standard quando stiamo dando la prova appena basata sulla proprietà di resistenza alla collisione della funzione hash sottostante, la prova di sicurezza detiene per qualsiasi istanziazione di H che sia garantita collisione resistente, ma che non sia il caso nel modello Random Oracle. Il che significa che potrebbe essere difficile argomentare che qualsiasi istanziazione concreta dell'oracolo H da parte di specifiche funzioni hash del mondo reale che siano deterministiche in natura produrrà uno schema sicuro, giusto, e il punto importante è che anche se diamo una prova di sicurezza nel modello Random Oracle quando effettivamente distribuiamo quel regime nel mondo reale, l'oracolo H sottostante deve essere istanziato da una funzione hash deterministica concreta e non appena instanziamo l'oracolo H da una funzione hash deterministica ogni entità nel sistema, il mittente, il destinatario, il partito onesto e l'avversario anche avere accesso al codice dell'istanziazione sottostante dell'H. Che significa avversario non può essere limitato ad un semplice accesso oracolo a H, a destra. Ecco quindi le importanti proprietà del modello Random - Oracle. (Riferimento Slide Time: 18 :48) Ora, vediamo rapidamente un esempio per capire come funzionano esattamente le cose nel modello Random Oracle. Immaginate quindi di avere una funzione hash che impiega input di dimensioni di lino e vi dà output di dimensioni lout e utilizzando questa funzione hash supponiamo di progettare una funzione G che prenda un input di dimensioni in lino e vi dia un output di dimensioni lout e sostanzialmente ciò che questa funzione G fa è solo valuta la funzione hash sull'input x. Ora, affermo che se siamo nel modello Random - Oracle e se interpretiamo questa funzione hash sottostante come Random - Oracle che viene istanziato all'inizio di ogni istanziazione della funzione G, allora questa funzione G può essere vista come un generatore di pseudorandom e dimostrare che effettivamente la funzione G che abbiamo costruito qui è un generatore pseudo - Oracle nel modello Random - Oracle, dobbiamo modificare il gioco indistinguibile, il gioco indistinguibile standard che usiamo per definire la sicurezza del generatore di pseudo - Oracle per incorporare il modello Random - Oracle. Il cambiamento che sta per accadere qui è che se si ricorre nel gioco indistinguibile standard per PRG, la sfida per l'avversario è quella di distinguere un campione di pseudorandom da un campione davvero casuale, ma ora dato che stiamo per dare una prova nel modello Random - Oracle, dobbiamo anche modellare l'accesso oracolo alla funzione hash sottostante del Random - Oracle a cui il distinguo potrebbe avere accesso. Quindi, vediamo il gioco indistinguibile modificato per il PRG nel modello Random - Oracle. Così all'inizio di questo esperimento, questo esperimento indistinguibile, si realizzerà una ricorrenza casuale di H e nessuno avrà accesso al codice di questo H, quindi per questo io lo sto denunziando come una scatola qui, né l'esperimento né il distinguo conosceranno i dettagli esatti dell'H, entrambi avranno oracolo l'accesso a H. Now come per il gioco indistinguibile PRG, l'esperimento dello sfidante picchia un campione di bit lout e sfida il distinguo per scoprire come viene generato, sia che sia casuale o pseudorandom. In sostanza, il modo in cui questa y sarebbe stata generata è lo sfidante avrebbe scelto una moneta uniformemente casuale e gettandola e a seconda del valore di quella moneta se è 0, allora y è davvero casuale mentre se la moneta è 1, allora sostanzialmente lo sfidante avrebbe prelevato un x input dal dominio e avrebbe valutato l'oracolo H su quell' input x e per valutare che Oracle sull'input x, lo sfidante o l'esperimento avrebbero fatto una query privata all'oracolo che il distinguo non può vedere. Ora, una volta che viene dato il campione y, la sfida per il distinguo è scoprire se il campione y è generato con metodo b = 0 o se il campione di sfida y è generato con metodo b = 1, ma ora dato che siamo nel modello Random - Oracle, diamo l'accesso oracolo distinguo alla funzione hash sottostante, poi cioè può rendere il numero polinomiale di query all'oracolo H sottostante, può chiedere ai valori H (x) per diversi x della sua scelta e poi deve decidere se il campione y è generato con metodo b = 0 o con metodo b = 1. Ovvero, le uscite distinguibili sono un po' e la definizione di sicurezza per il modello PRG nel modello Random - Oracle è che diciamo che la funzione G è un generatore pseudo - Oracle nel modello Random - Oracle se per ogni avversario o distinguo che partecipa a questo gioco modificato, il comportamento del distinguo rimane quasi lo stesso indipendentemente dal fatto che il campione sia pseudorandom o se sia davvero casuale. Il che significa, non importa se il campione y è generato con metodo b = 0 o con il metodo b =1, in entrambi i casi la risposta del distinguo s risposta cioè b deve essere quasi identica tranne che con la probabilità trascurabile. (Riferirsi Slide Time: 22 :44) Così ora, quello che stiamo per provare è che la costruzione G che abbiamo progettato qui soddisfa effettivamente questa nuova definizione di indistinguibilità PRG se ci troviamo nel modello Random Oracle, giusto. Quindi supponiamo che ci venga dato un distinguo di poly arbitrale arbitrario D e let Q denota il set di x query che il distinguo ha fatto all'Oracolo, giusto, e il punto importante qui è che dal momento che il tempo di esecuzione di un distinguo è polenta il tempo, il numero di query che questo distinguo potrebbe apportare è qualche funzione polinomiale nel parametro di sicurezza. Quindi ora, qual è la probabilità che il distinguo D abbia queriato per il valore oracolo sull'input x che lo sfidante ha scelto per il caso b = 1 a destra. Ricordate quindi che ognuno dei valori x, a destra, il valore x che il fondamentalmente sfidante ha utilizzato, se il campione y viene generato con metodo b = 1 a destra, è un valore uniformemente casuale di dimensioni di lino. Quindi la probabilità che il distinguo D possa indovinare correttamente il valore di x nel suo insieme è massimo di | Q|/2lin, giusto. La dimensione di Q, ovvero la dimensione della query impostata su 2lin e se garantiamo che la lino sia qualche funzione polinomiale nel parametro di sicurezza, allora sostanzialmente quello che otteniamo è che questa probabilità che il nostro distinguo D querelare l'oracolo per l'input x sia effettivamente una quantità trascurabile. Quindi ora, cosa significa che se il campione y che viene gettato come una sfida viene generato dal metodo b = 1, questo significa, è un valore pseudorandom o è output di G allora nulla sul valore x viene rivelato da y perché quello che stiamo assumendo qui è che nel modello Random - Oracle la funzione H è come una funzione davvero casuale. Il che significa anche se y sarebbe stato generato rendendo la query oracolo all'oracolo H su alcuni input x, il valore di quella x non verrà rivelato dall'output y. Il che significa, possiamo dire che se siamo nel caso in cui b = 1 questo significa che la sfida y è generata dall'algoritmo G, poi condizionata all'evento che l'input x non appartiene al set di query del distinguo. Il che significa che il distinguo non ha querizzato per il x input giusto, il distinguo non ha chiesto il valore dell'oracolo H sulla condizione di ingresso x su quell' evento dal punto di vista di questo distinguo, questo campione y è come una stringa davvero casuale perché ci assumiamo che nel modello Random - Oracle, H sia come una funzione davvero casuale. Questo significa condizione su questo evento, non importa se siamo nel caso b = 0 o b = 1. Dal punto di vista del distinguo in entrambi i casi il campione di sfida y è un campione davvero casuale e da qui la sua produzione sarà la stessa, e abbiamo già sostenuto che quella che è la probabilità che effettivamente x non appartiene a Q, beh è la probabilità di questo è la dimensione di Q over 2lin (|Q|/2lin) che è effettivamente una funzione trascurabile, che dimostra chiaramente che la funzione G che abbiamo costruito qui utilizzando la funzione hash può essere vista come un generatore di pseudorandom se entriamo nel modello Random - Oracle. Così questo mi porta alla fine di questa lezione. Tanto per riassumere in questa lezione, abbiamo introdotto un modello Random - Oracle. Questo in sostanza viene utilizzato per dare la prova di sicurezza dei primitivi crittografici in base ad alcune funzioni hash dove non possiamo completare una prova di sicurezza di quel primitivo proprio utilizzando le proprietà standard delle funzioni hash ovvero la proprietà di resistenza agli urti e abbiamo visto anche una dimostrazione del modello Random - Oracle, ovvero abbiamo visto che se prendiamo una funzione hash e la modelliamo come un Random Oracle, allora possiamo utilizzarlo per costruire un generatore di pseudorandom. Grazie.