Loading
Note di Apprendimento
Study Reminders
Support
Text Version

Funzioni pseudo - casuali

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

    +

Fondamenta di CryptographyProf. Dr. Ashish Choudhury (Ex) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology-BangaloreLecture-14Pseudo Random Functions PRFsHello tutti, benvenuti alla lezione 13. (Fare Slide Time: 00 :31) Il piano per questa lezione è il seguente. Introdurremo un blocco edificio molto importante per la crittografia chiave simmetrica ovvero la funzione pseudo casuale. E più tardi vedremo che come la funzione pseudo casuale funge da blocco di costruzione fondamentale per progettare molti splendidi primitivi simmetrici. Discuteremo anche varianti di pseudo funzione casuale e cioè la permutazione pseudo casuale e la forte permutazione pseudo casuale. Vedremo come costruire dei generatori pseudo casuali dalla funzione pseudo casuale. (Fare Slide Time: 01 :01) Quindi, iniziamo la nostra discussione su pseudo funzione casuale. Su un livello molto alto, una funzione pseudo casuale è un algoritmo deterministico con due input e un singolo outputdove e. E presumiamo che la dimensione chiave sia n e n è qualche parametro di sicurezza. Ecco perché spesso chiamiamo la funzione F come una funzione di keyed perché sarà operata da una chiave. In pratica, le dimensioni di n, l e L possono essere tutte molto e successivamente su di noi vedremo varie instantiazioni di pseudo funzione casuale. Effettivamente n, l, L tutti sono diversi, ma asintoticamente tutto deve essere una qualche funzione polinomiale del vostro parametri.Now, come utilizzeremo questa pseudo funzione casuale. Quindi, ogni qualvolta stiamo progettando dei primitivi crittografici, il modo in cui utilizziamo questa pseudo funzione casuale è il seguente: all'inizio delle istanziazioni della primitiva crittografica, che utilizza questa funzione F, il mittente o il destinatario genererà una chiave uniformemente casuale. E in qualche modo sarà stabilito anche con la parte ricevente e non sarebbe noto all'aggressore. Una volta che la chiave è stata fissata, non cambieremo la chiave in tutta quella sessione o in tutta quella istanziazione. La chiave rimarrà la stessa. Ora, una volta che abbiamo fissato la chiave, dove k sta per essere fissato e non sarebbe noto all'aggressore. Questo è il modo in cui utilizzeremo una funzione pseudo casuale. Ora, qual è esattamente la proprietà di sicurezza che richiediamo dalla funzione pseudo casuale. E informalmente richiediamo quanto segue: se la chiave k è sconosciuta, e uniformemente scelta casualmente dal dominio dello spazio chiave, allora fondamentalmente ci chiediamo che il funzionamento o l'output della funzione chiave di Fk debba quasi assomigliare all'output di qualsiasi funzione realmente casuale. Quindi, ricordate, una funzione davvero casuale è una funzione senza chiave. Quindi, quello che fondamentalmente vuole è che la funzione di keyed Fk, una volta che la chiave è stata scelta casualmente, il suo comportamento dovrebbe quasi assomigliare al comportamento di una pseudo funzione casuale. (Fare Slide Time: 03 :53) Quindi, andiamo un po' più a fondo in quello che intendo esattamente con la dichiarazione formale. Immaginate di avere una funzione davvero casuale che è una funzione senza chiave, non ha nessuna chiave, basta un input di dimensioni l bit e produce un output di dimensioni L bit. Quindi, è facile immaginare il comportamento di una funzione davvero casuale come segue: ciò che fa funzionare davvero casualmente è un input di dimensioni x, e produce un output di dimensioni L bit. E si può immaginare che fondamentalmente questa funzione davvero casuale mantiene una tabella composta da 2lrows, dove sostanzialmente i negozi di prima fila. Il secondo - rowstores e gli ultimi negozi di fila .Quindi, ogni volta che questa funzione davvero casuale riceve un input x, quello che praticamente fa è controllare internamente se c'è già una voce per il valore di questa funzione davvero casuale all'ingresso x. Se non c'è, poi riempire quella riga, ovvero F (x) da. Per i futuri richiami di queste funzioni davvero casuali ha detto che y è l'uscita di questa funzione davvero casuale sull'input x. D'altra parte, se il valore x che è stato superato, si ha già una voce corrispondente a quella chiave x in questa tabella poi basta passare sul valore che viene memorizzato in quella riga corrispondente come l'output y. Ecco così che si può immaginare il comportamento di una funzione davvero casuale. La cosa importante qui è che dato che questa funzione è una funzione davvero casuale, ogni riga qui è una stringa indipendente di lunghezza L. Questo significa e sono indipendenti l'uno dall'altro, per qualsiasi. Questo significa, se esiste un algoritmo, che è stato notyet visto il valore della funzione veramente casuale su qualche input x, non può prevedere quale sia esattamente il valore della funzione per quell' input x, tranne che indovinare l'output, e l'indovinare avrà successo con probabilità 1/2L. A parte questo, non c'è modo di prevedere l'esito della funzione realmente casuale su alcuni input x. E questo vale anche se quell' algoritmo che sta effettivamente cercando di prevedere l'esito di questa funzione davvero casuale sull'input x ha già visto l'output di questa funzione davvero casuale su diversi valori x precedenti, che potrebbero essere correlati a questo nuovo x valori. Ma questo perché ogni riga nella tabella di questa funzione davvero casuale è indipendente l'una dall'altra. La proprietà di sicurezza che richiediamo da una funzione pseudo casuale è che una volta che fissiamo la chiave selezionando la chiave uniformemente in modo casuale allora quella funzione di keyed dovrebbe avere anche le proprietà simili tranne con una probabilità trascurabile. (Fare Slide Time: 07 :02) Quindi, cosa esattamente questo significa che sul tuo lato sinistro hai una funzione di keyed Fk, dove la descrizione della funzione F è pubblicamente nota. Sottolineo la descrizione della funzione è nota pubblicamente e ciò che non è noto è sostanzialmente il valore della chiave. Sul lato destro si ha una funzione davvero casuale che consiste sostanzialmente in 2Lrows ogni voce costituita da una stringa uniformemente casuale di lunghezza L bit. E quando dico che la mia funzione F è una pseudo funzione casuale, ciò che in sostanza intendo è che non esiste un test statistico temporale o un algoritmo statistico in grado di distinguere in modo significativo un output dell'algoritmo Fk dall'output di questa funzione davvero casuale. Il che significa, se il nostro distinguo o il test statistico sono in sostanza date outputs della funzione Fk o dell'output della funzione casuale su diversi input di caratteri avversari o scelta distinguo. Dal punto di vista del distinguo, tali output potrebbero provenire dalla funzione Fk come è probabile che provenga da questa funzione davvero casuale. Ora, prima di andare oltre, questa condizione è simile al modo in cui abbiamo definito la nozione di generatore pseudo casuale. Quindi, ricordati nel generatore pseudo casuale che la sicurezza è definita dicendo che non esiste un test statistico, che quando un campione non può distinguere se quel campione viene generato eseguendo un generatore pseudo casuale, oppure eseguendo un generatore davvero casuale. In quell' esperimento, quel distinguo è stato dato solo un campione perché il nostro pseudo generatore casuale è una singola funzione di input. Per ogni richiamo del generatore pseudo casuale, il campione sarà diverso perché la chiave per il generatore di pseudo random sarà diversa. Ma nel contesto di una funzione pseudo casuale, il modo in cui utilizzeremo una funzione pseudo casuale nella vera applicazione mondiale è che la chiave verrà fissata una volta per tutte all'inizio della sessione. E poi gli input x saranno variegati. E ogni richiamo della funzione sarà con la stessa chiave. (Fare Slide Time: 09 :14) Quindi quello che stiamo per fare è che nella nostra definizione formale, sostanzialmente l'avversario verrà dato molti campioni, e deve distinguere se quei campioni sono generati eseguendo una funzione di keyed Fk o eseguendo una funzione davvero casuale. Vediamo quindi quali sono esattamente i dettagli formali. Così ti viene data la descrizione di una funzione pubblicamente conosciuta, e l'esperimento che chiamiamo indistinguibilità sperimenta un PRF rispetto a un algoritmo di distinguo contro la funzione F e l è il parametro di sicurezza. Le regole dei giochi sono le seguenti: il distinguo è consentito richiedere l'output della funzione a molti x input della sua scelta, e può chiedere in modo adattabile alle sue query che significa che può prima chiedere l'output della funzione sull'input x1. Poi in base alla risposta, può decidere cosa deve essere x2. E poi in base alla risposta, può decidere cosa deve essere x3, e così via. Non poniamo assolutamente alcuna restrizione su quale tipo di query distinguiamo è asking.Now, una volta che il distinguo sottopone le sue query, lo sfidante qui deve trovare la risposta, ovvero l'output delle funzioni a quegli input. E il modo in cui lo sfidante avrebbe preparato quelle risposte è il seguente: in sostanza, lo sfidante sta per lanciare una moneta uniformemente casuale, che va in uscita 0 o 1 con probabilità 1/2. Se il gettone di moneta è 0, allora tutte queste risposte y1, .., yq sono fondamentalmente generate eseguendo una funzione davvero casuale su quegli input x. In un più dettaglio tutte queste stringhe di y sono fondamentalmente indipendenti l'una dall'altra e ognuna di esse è sostanzialmente una stringa di bit uniformemente casuale di lunghezza L. D'altra parte, se il gettone di moneta dello sfidante è 1, allora questa y outputs è sostanzialmente l'uscita di una funzione di keyed Fk, dove la chiave viene scelta uniformemente casualmente dallo sfidante. E ora la sfida per il distinguo è scoprire come sono generate esattamente queste risposte y1, .., yq, se sono generate dal meccanismo 0 o se sono generate bymeccanismo 1. Questa è una sfida per il nostro distinguo. Così, distinguo in questo caso outputs b il quale sarà un po' che dice in sostanza se si sente che un campione y1, .., yq sono generati dai meccanismi 0 o dal meccanismo 1. E la nostra securitydefinition è che diciamo che la funzione F è una funzione pseudo casuale se per ogni algoritmo di tempo polinomiale probabilistico D che partecipa a questo esperimento, esiste una funzione trascurabile come quella della probabilità che il distinguo identifichi correttamente l'etichetta o la natura dei campioni y1, .., yq è superiore delimitato da ½ + negl (n). Ancora, la probabilità viene presa qui sopra la scelta casuale dello sfidante e le query casuali del distinguo. Un'altra formulazione equivalente della stessa definizione è che diciamo che la funzione F è un PRFse il vantaggio distintivo del nostro distinguo è delimitato da una funzione trascurabile. Il che significa che non importa se b = 0 o se b = 1 il che significa che non importa se i campioni di y sono generati da una funzione davvero casuale o se sono generati da una pseudo funzione casuale. In entrambi i casi distinguo dovrebbe emettere la stessa uscita, dire b = 1 salvo con probabilità trascurabile. E ancora, possiamo dimostrare che se abbiamo una pseudo funzione casuale che soddisfa la prima condizione, allora si applica anche la seconda condizione e viceversa. Quindi a seconda della nostra convenienza, possiamo utilizzare una di queste due definizioni. Ecco allora che è la definizione di una pseudo casu.Basically, l'intuizione in questo esperimento è che stiamo dando al nostro distinguo un accesso oracolo alla funzione in cui la funzione è una funzione davvero casuale o una funzione di keyed. E distinguo deve distinguere se si interagisce con un oracolo di funzione davvero casuale o se si interagisce con un oracolo funzione a chiave. Questa definizione di sicurezza esige che tranne con probabilità trascurabili non debba essere in grado di distinguere. Avviso che qui, siamo tenuti a rispettare la probabilità di successo dell'avversario da parte di ½ + negl (n). Non possiamo mettere una definizione in cui si dice che una probabilità di successo del distinguo dovrebbe essere 0 perché c'è sempre la possibilità che distinguere chi può solo indovinare che si interagisce con dire TRF o PRF e con la probabilità che la metà possa effettivamente identificare o la probabilità metà della sua ipotesi potrebbe essere correggia, non possiamo mai mettere una condizione che la probabilità di successo del distinguo debba essere di 0. L'ulteriore vantaggio trascurabile è fondamentalmente dovuto al male necessario associato al fatto che siamo nel mondo computazionale. (Vedi Slide Time: 14 :25) Quindi, ora vediamo, che sia facile o se sia facile o quanto sia difficile costruire una pseudo funzione casuale. Quindi, immaginate di progettare una funzione F come segue e per semplicità, presumo che la lunghezza chiave e la lunghezza del blocco e la lunghezza di uscita siano di stessa dimensione cioè dire n bitstringhe e il modo in cui viene definita l'uscita della funzione. Questo è il modo in cui viene calcolata la produzione. Il nostro obiettivo è quello di provare o smentire se questa funzione è una pseudo funzione casuale. In realtà vogliamo smentire questa costruzione non è un PRF. E per questo, in sostanza, vogliamo argomentare se effettivamente le uscite di questa funzione F produrrà delle uscite pseudo casuali una volta che fissiamo la chiave. E se si va un po' più in profondità nell'algoritmo, si può chiaramente vedere il seguente fatto: se abbiamo una mappatura delle funzioni davvero casuale n bit stringhe a n bit stringhe allora l'output della funzione veramente casuale su 2 input diversi x1 e x2 sarà completamente indipendente l'uno dall'altro. D'altra parte, per la funzione di cui stiamo considerando,, per qualsiasi e qualsiasi. Ciò significa che ora avete un test che passerà sempre o che terrà sempre per i campioni generati dalla funzione Fk. E si ha un test, lo stesso test potrebbe non essere sempre applicabile per i campioni generati da una funzionalit davvero casuale. Questo praticamente ci dà un'intuizione per progettare un distinguo che sappia distinguere l'esito di questa funzione F dall'esito di una funzione davvero casuale. Ecco quindi l'istanza del distinguo: in sostanza chiede il valore della funzione all'ingresso x1, x2 che sono diverse. In risposta, lo sfidante risponde con outputs y1 e y2. Il modo in cui è y1 e y2 sarebbe stato generato come per il gioco di indistinguibilità PRF è il seguente: lo sfidante avrebbe praticamente trainato una moneta se il gettone di moneta è 0 poi y1 e y2 sono stringhe di bit casuali. Mentre, se il gettone di moneta è 1 allora y1 e y2 gli esiti della funzione di keyed Fk per la chiave uniformemente casuale conosciuta solo allo sfidante. E ora distinguo può agire in modo intelligente e fondamentalmente distinguere se y1 e y2 sono generati da una funzione davvero casuale o da una pseudo funzione casuale semplicemente eseguendo questo test. Si verifica se x1 e x2 il loro XOR è lo stesso di XOR di y1 e y2. Se è così, allora dice che, i campioni y1 e y2 sono generati dal meccanismo b = 1, ovvero, sottopone b = 1. Mentre se il test fallisce, e dice, i campioni y1 e y2 sono generati dal meccanismo 0, ovvero b = 0. Ora, analizziamo qual è il vantaggio distintivo di questo particolare distinguo. Per prima cosa analizziamo qual è la probabilità che il nostro distinguo sia etichettare correttamente i campioni y1 e y2 generati da una pseudo funzione casuale effettivamente essendo i campioni di una pseudo funzione casuale cioè il pr [ D outputs b = 1 / b = 1]. Affermo che questa probabilità è pari a 1. Perché se effettivamente b = 1, cioè un caso, i campioni y1 e y2 sono come per le uscite di una pseudo funzione casuale. E in quel caso, questa condizione, il controllo che l'avversario o il distinguo si esibisce passerà sempre. Ecco perché la probabilità 1, se b = 1, la strategia del distinguo arriverà effettivamente b = 1.On l'altra mano, calcoliamo la seconda probabilità che quella che è la probabilità che il nostro distinguo etichette erroneamente campioni veramente casuali y1 e y2 siano i campioni di una pseudo funzione casuale. Beh, se b = 0, significa che i nostri campioni y1 e y2 sono indipendenti l'uno dall'altro. Poi l'unico modo in cui il distinguo può ancora produrre b = 1 è che per una condizione uniformemente casuale y1 e y2this o in altre parole, il pr [ D output b = 1/b = 0] = 1/2n.So che ci dà il vantaggio distintivo del distinguo che abbiamo progettato. E se si prende la differenza assoluta, è quasi pari a 1 che fa con quasi il 100% di probabilità. Se n diventa più grande allora questo 1 – 1/2nalmost diventa 1. Ecco perché con quasi il 100% di probabilità un distinguo può distinguere l'esito della funzione chiave F dall'output di una funzione davvero casuale. Ed è per questo che questa funzione F non è la pseudo funzione casuale. Quindi questo significa progettare una funzione pseudo casuale è effettivamente un compito impegnativo. Vedremo le case costruttive in seguito. (Fare Slide Time: 19 :56) Ora definiamo solo alcune altre varianti di funzioni pseudo casuali con proprietà più forti e garanzie di sicurezza. Così la prima variante è chiamata come la pseudo permutazione casuale, nota anche come cifratura di blocco. E qui di nuovo abbiamo una funzione di keyed F. L'unica differenza qui è che la funzione keyed Fk dovrebbe essere ora una proiezione,. Questa è l'unica differenza.Informalmente, la proprietà di sicurezza che richiediamo qui è che richiediamo che una volta sistemate la chiave selezionando una chiave uniformemente casuale, e la chiave non sia nota all'aggressore o a un distinguo. Poi, nessun distinguo per tempo polinomiale può distinguere il funzionamento in uscita o la natura di questa funzione chiave Fk da una mappatura di una mappatura davvero casuale L bit stringhe a L bit stringhe, che possono essere modellate di nuovo come un esperimento indistinguibile. (Fare Slide Time: 20 :53) Quindi questo è l'esperimento indistinguibile che chiamiamo come esperimento di indistinguibilità PRP e abbiamo una biiezione qui, biproiezioni a chiave. Vogliamo catturare l'intuizione che nessun distinguo dovrebbe essere in grado di distinguere il comportamento di questa biiezione keyed da una biiezione davvero casuale. Quindi le regole degli esperimenti sono le seguenti: distinguono le query per diversi x input della sua scelta e in risposta lo sfidante restituisce le risposte. Le risposte sono preparate tirando una delle seguenti regole: attacca una moneta e se la moneta è 0, poi tutti questi campioni y1, .., yq sono fondamentalmente generati percorrendo una permutazione davvero casuale. Mentre se il gettone di moneta è il 1 che tutti questi campioni vengono generati eseguendo la funzione di keyed F su una chiave uniformemente casuale non nota al distinguo. La sfida per il distinguo è scoprire qual è esattamente il modo in cui vengono generati i campioni. Il che significa che deve produrre un po' e la nostra definizione di sicurezza è che diciamo che la biproiezioni F è un PRP, se la probabilità che qualsiasi distinguo in tempo polinomiale possa identificare correttamente la natura del campione è delimitata da ½ + negl (n). Equivalentemente a dire che il vantaggio distintivo del nostro distinguo dovrebbe essere superiore delimitato da una funzion.Quindi, in essenza tutto è uguale per il caso di pseudo funzione casuale, l'unica differenza è che ora siamo sostanzialmente in questo caso di funzione PRP. (Fare Slide Time: 22 :34) Quindi, è interessante vedere il rapporto tra questi 2 primitivi pseudo funzione casuale e la pseudo permutazione casuale. Quindi, sulla tua parte di sinistra hai una funzione pseudo casuale. La differenza qui è una funzione, questo significa la lunghezza di ingresso, la lunghezza del blocco e la lunghezza di uscita potrebbero essere diverse. Mentre in caso di permutazione pseudo casuale, si abita. Il che significa, nel caso di funzioni pseudo casuali, potrebbe essere una moltitudine a una funzionaria mentre nel caso di una permutazione pseudo casuale si tratta di una mappatura. Dal momento che il nostro PRF potrebbe non essere una biezione, è facile vedere che un PRF potrebbe non essere un PRP. E il contrario? Curiosamente, possiamo dimostrare che se la dimensione di uscita L è maggiore di uguale a l, o in termini più generici, se la dimensione in uscita è qualche funzione polinomiale del parametro di sicurezza n allora possiamo visualizzare una pseudo permutazione casuale come una pseudo funzione casuale. E l'intuizione per questa affermazione è la seguente: immaginate di ricevere una permutazione a chiave. Quindi, questo Fk è una bisatura a chiave. E visto che è un PRP sicuro che non significa nessun distinguo tempo polinomiale può distinguere e l'interazione con questa funzione di keyed Fk da una biiezione davvero casuale senza chiave, quel senso sia questi primitivi Fk che FTRP sono computazionalmente indistinguishable.Now, se confrontiamo una funzione veramente casuale di mappatura L bit stringhe a L bit stringhe, come esattamente sarà diverso da una permutazione davvero casuale, beh, l'unica differenza tra una funzione davvero casuale da una funzione davvero casuale e una permutazione davvero casuale è che una funzione non ha bisogno di una proiezione. Il che significa che ci sono possibilità di collisioni che significa che potrebbe essere una moltitudine in una funzione in cui diversi input x potrebbero darvi la stessa emissione y. considerando che in caso di permutazione davvero casuale non ci sono possibilità di collisioni. Quindi l'unico modo in cui qualsiasi distinguo può distinguere a prescindere dalla funzione davvero casuale da questa bisatura a chiave è quanto segue. Se così accade che il nostro distinguo si interagisce con una funzione davvero casuale senza chiave e se così accade che alcune delle sue query ti danno la stessa uscita e si può chiaramente identificare che si interagisce con una funzione davvero casuale senza chiave. Perché se interagisce con questa Fk di biproiezioni a chiave, le collisioni non accadono. Il che significa che possiamo dire che condizionato all'evento che le nostre query distinguono non porteranno mai a una collisione, allora l'interazione del nostro distinguo con Fk e FTRF è quasi la stessa che se il distinguo interagisce con Fk versus FTRP e dato che la nostra funzione Fk è una permutazione a chiave. Sappiamo che quell' interazione è computazionalmente indistinguibile. Quindi, la condizione sull'evento al nostro distinguo non sta ottenendo collisioni dalle sue query, l'interazione del nostro distinguo con la funzione davvero casuale e la biproiezioni a chiavi in mano sono quasi identiche. Ora la domanda è qual è la probabilità che il distinguo ottenga una collisione effettuando delle query q casuali attraverso la funzione davvero casuale?Se sta effettuando delle query q casuali poi usando un risultato ben noto, che chiamiamo paradosso del compleanno, che discuteremo più rigorosamente nel contesto della funzione hash, possiamo dimostrare che le possibilità di ottenere una collisione possono essere superiori delimitate dalla probabilità q2 /2L. E questo è il motivo per cui se la tua L è una qualche funzione polinomiale del parametro di sicurezza n, allora chiaramente, si tratta di una quantità trascurabile. Questo significa che le possibilità di collisioni che avvengono sono trascurabili. Ed è per questo che possiamo dire, oppure possiamo trattare la Fk di biproiezioni a chiave anche come una pseudo funzione casuale. Ecco allora il rapporto tra le funzioni pseudo casuali e le permutazioni pseudo casuali. (Fare Slide Time: 27 :00) Ora vediamo la variante finale di funzioni pseudo casuali che chiamiamo una forte permutazione pseudo casuale o SPRP, che è un tipo speciale di permutazione pseudo casuale. E fondamentalmente qui ci si richiede che la bisatura a base di chiavi debba essere indistinguibile da una permutazione davvero casuale anche se il distinguo ottiene l'accesso oracolo all'inverso della permutazione. Quello che intendo con questo è dimostrato in questo speriment.Così, questo esperimento indistinguibile si chiama Experiment. E qui il distinguo dà ora accesso o risposta per 2 tipi di query. Ha avuto oracolo l'accesso ai valori delle permutazioni, e ha anche l'accesso oracolo all'inverso della permutazione. Ciò che intendo dire con questo è che può adattarsi in modo adattabile al valore delle permutazioni a diversi x input della sua scelta e in risposta, richiama corrispondenti y outputs. E si può anche chiedere l'inverso della permutazione di diversi valori di y del suo choc e vedere i valori x corrispondenti. E il modo in cui lo sfidante avrebbe risposto è il seguente: avrebbe pedalato una moneta uniformemente casuale se il gettone di moneta è 0, poi tutte queste query sono risapprese valutando una permutazione davvero casuale. Questo significa che tutti questi valori x sono valutati come per questa permutazione davvero casuale. E tutte queste inverse query vengono anche chiarite chiedendo l'inverso di quella corrispondente permutazione davvero casuale. D'altra parte, se la moneta toss b = 1, allora tutti questi valori di y e tutti questi valori inverso vengono calcolati eseguendo la funzione keyed Fk e inversamente di quella funzione di keyed Fk. E la sfida per il distinguo come di consueto è quella di individuare se ha interagito con oracolo che rappresenta una permutazione davvero casuale o se interviene con un oracolo a chiave. La nostra definizione di sicurezza è che diciamo che la funzione F è una forte permutazione pseudo casuale se nessun distinguo tempo polinomiale può identificare correttamente la natura del suo oracolo, tranne con la probabilità ½ + negl (n) o metterla in altre parole, che distinguere il vantaggio del nostro distinguo debba essere delimitato da una quantità trascurabile. Si scopre che, se abbiamo una forte permutazione pseudo casuale, poi per definizione, è anche una pseudo permutazione casuale. E possiamo dare costruzioni dove la costruzione sarà una pseudo permutazione casuale. Questo significa che sarà sicuro solo quando l'avversario ottiene l'accesso alle query oracolo per l'output della funzione. Ma potrebbe non essere una forte permutazione pseudo casuale che significa, non appena forniamo l'accesso distinguo all'oracolo inversa l'avversario può distinguere a parte. Questo significa che la forte permutazione pseudo casuale è più forte della permutazione casuale rispetto alla permutazione pseudo casuale. (Vedi Slide Time: 30 :01) Ora, fatemi terminare questa lezione dando un esempio di come costruire un generatore pseudo casuale da una pseudo funzione casuale. Quindi immaginate di ricevere un PRF sicuro,. Ora, usando questo posso costruire uno pseudo generatore casuale G, .E fondamentalmente, il modo in cui opera questo algoritmo G è il seguente: prende il seme k per l'algoritmo G e crea il k per la funzione pseudo casuale F. E la funzione pseudo random F viene ora valutata in input pubblicamente noti 1 2 3 fino a t. Questo significa che gli input di blocco che vengono utilizzati all'interno di questo algoritmo G sono pubblicamente noti sono 1 fino a t fino a t, è solo la chiave che non si fa conoscere al distinguo. E ogni richiamo di questa funzione F è con la stessa chiave, che è in realtà l'input dei nostri pseudo generatori casuali. E l'uscita del generatore pseudo casuale è sostanzialmente la concatenazione delle singole uscite che si ottengono eseguendo le istanze t della funzione di keyed Fk, ovvero il modo in cui il nostro pseudo generatore casuale verrà operato. Ora vogliamo dimostrare che se la funzione di keyed Fk è un PRF sicuro come per la nostra nozione di indistinguibilità, allora l'algoritmo G che abbiamo costruito è anche un PRG sicuro. Come per il gioco indistinguibile PRG fornito, il numero di volte in cui abbiamo invocato la pseudo funzione random Fk, ovvero t, che è una qualche funzione polinomiale del parametro di sicurezza. Per dimostrarlo, prima comprendiamo la nostra intuizione. In sostanza consideriamo un'altra versione dell'algoritmo G, che io chiamo come GTRG, dove ogni istanza di funzione di keyed Fk viene sostituita da un'istanza di una mappatura di funzioni davvero casuale l bit stringhe a L bit stringhe. Abbiamo introdotto il concetto di funzione pseudo casuale; abbiamo visto la definizione. E abbiamo introdotto varie varianti di funzioni pseudo casuali come la permutazione pseudo casuale, una forte permutazione pseudo casuale e avevamo visto come costruire un generatore di pseudo random sicuro dalla funzione pseudo random sicura. Grazie!