Loading
Note di Apprendimento
Study Reminders
Support
Text Version

Costruzioni Generiche di Key Exchange Protocol

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

    +

37Foundations di CryptographyDr. Ashish ChoudhuryDipartimento di Computer ScienceInternational Institute of Information Technology – BangaloreCollezione -37I protocolli di scambio chiave parte II(Riferimento Slide Time: 00.28)Ciao a tutti, benvenuti a questa lezione. Bene solo per ricordare nell'ultima lezione che avevamo introdotto il problema di scambio delle chiavi e abbiamo visto varie nozioni di sicurezza e abbiamo visto anche l'idea coinvolta dietro il Diffie – Hellman Key Exchange Protocol sebbene, noi non abbiamo ancora visto i dettagli matematici esatti, ma abbiamo visto come date alcune funzioni speciali E e F come possiamo progettare il Diffie – Hellman Key Exchange Protocol. Ora quello che faremo qui è che continueremo la nostra discussione sui protocolli di scambio chiave e vedremo costruzioni generiche di protocolli di scambio chiave cioè vedremo costruzioni basate su funzioni trapporte unidirezionali che sono molto simpatiche primitive matematiche primitive o fondamentali che sono più potenti rispetto alla nozione di funzioni unidirezionali.(Fare Slide Time: 01.18)Quindi quali sono esattamente le funzioni di un trapdoor unico? Così prima di entrare nella definizione di un modo per le funzioni trapporta ci si fa ricordare innanzitutto la definizione di funzione unidiret o OWF. Quindi una funzione one-way F è una funzione pubblicicamente conosciuta, una funzione deterministica dal dominiox al co - dominio y e i requisiti da questa funzione a senso unico sono che dovrebbe essere facile da calcolare per qualsiasi valore x dal dominio x. considerando che dovrebbe essere difficile invertire in tempo polinomiale qualsiasi input casuale dalla gamma set di f che significa che se qualcuno mi dà una y che appartiene alla gamma di f e y è casualmente scelto che in politempo dovrebbe essere difficile trovare qualche almeno un'immagine per questo input . Ora qual è esattamente la funzione di trapporta a senso unico. Quindi suona come un tipo speciale di funzione.E infatti è un tipo speciale di funzione unidireiale che ha anche un'informazione trapdoor associata e cosa esattamente questa informazione trapporta ti aiuterà con bene ti aiuta a invertire qualsiasi input dall'intervallo della funzione f fornito di avere la conoscenza delle informazioni trapporta che significa qualsiasi entità che conosca la descrizione di questa informazione trapporta allora può facilmente invertire la funzione f su qualsiasi random y dalla serie di f. Ma in assenza delle informazioni trapelari la funzione sembra una funzione a senso unico a quella entità che non sarebbe possibile per quell' entità che non elabora questa trapporta informazioni per invertire questa funzione f su qualsiasi random y dalla gamma impostata della funzione f.(Fare Tempo di slide: 03.00)Quindi ora cerchiamo di affermare formalmente questo requisito cosa esattamente intendiamo per questa speciale trapporta informazioni ed è facile invertire la presenza delle informazioni trapporta e difficile da invertire in assenza delle informazioni trapporta. Così quando diciamo che abbiamo una funzione di funzione di trapdoor T allora è finita una coppia di serie finite dove x sarà dominio della funzione e y sarà co - dominio della funzione.E quando diciamo uno schema di funzione trapdoor fondamentalmente intendiamo una tripletta di algoritmi tutti gli algoritmi di politempo, polinomiale in qualche parametro di sicurezza il primo algoritmo è l'algoritmo di generazione di generazione o fondamentalmente di generazione di parametri (Gen) e la funzione f è la funzione in questo contesto sottostante sarà una funzione unidirezionali e corrispondente alla funzione f abbiamo un'inversione funzione (Inv). Così sintatticamente l'algoritmo di generazione dei parametri o l'algoritmo di chiavi di generazione è un algoritmo randomizzato che non prende alcun input esplicito, ma internamente ha una qualche casualità interna che genera monete casuali interne e basato sul valore della moneta casuale genera un paio di chiavi o coppia di valori che denota da pk e sk. Così pk sarà la chiave pubblica che sarà disponibile nel dominio pubblico.E sk è la chiave segreta che sarà conosciuta o che sarà disponibile solo con alcune entità designate. Ora qual è una funzione f? Beh è una funzione dal set x al set y. Quindi è una funzione parametrizzata da un pk di chiave pubblica in modo che chiunque possa valutare questa funzione purché conosca la descrizione della funzione e la descrizione del pk della chiave pubblica e la funzione prenda due input espliciti. Ovvero l'input x su cui la funzione deve essere valutata e la chiave pubblica e ti dà un output che io dengo di y e questo y sarà un elemento dal dominio co set y ed è un algoritmo deterministico che significa ogni volta che si valuta questa funzione f con lo stesso input x e con lo stesso pk chiave pubblica otterrete la stessa output y.Non c'è casualità che c'è nell'ambito dell'algoritmo. Ora l'algoritmo inverso che si chiama è anche una funzione di input da 2 che prende un input dal set y che vogliamo invertire e la chiave segreta sk che significa che questa funzione può essere invocata solo da un'entità che possiede la chiave segreta che in realtà nel nostro contesto è un'informazione trapporta. Se non si ha la chiave segreta o le informazioni trapporta, allora non si potrà invocare questa funzione.Quindi supponendo che l'entità, un'entità che conosce l'input y su cui questa funzione Inv deve essere richiamata conosce anche le informazioni trapporta, esegue la funzione con questo input sk e y e stia andando ad ottenere un output x o uno speciale status symbol che denota un diritto di input non valido. Quindi se l'output di questa funzione inversa non è bot allora si tratterà di un elementodal dominio della funzione f.Namely sarà elemento di x mentre se l'output è bot allora indica un input non valido e vedremo presto cosa intendiamo esattamente con un input non valido rispetto al contesto sottostante e questa funzione inversa sarà sempre l'algoritmo deterministico che significa se si richiama questa funzione inversa con la stessa y e lo stesso tasto segreto sk poi si otterranno di nuovo la stessa emissione. Ora quali sono le proprietà che richiediamo da questa funzione di trapporta a senso unico? La prima proprietà è la proprietà di correttezza che stabilisce che per ogni coppia di parametri o chiavi pk, sk generata dal tuo algoritmo di chiavi di generazione e per ogni input x dal tuo dominio della funzione f se si richiama la funzione sull'input x rispetto al pk chiave e l'output risultante viene indicato come y.E poi se si cerca di invocare la funzione Inv sull'input y e con il tasto segreto sk o l'sk informazioni trapdoor allora l'output dovrebbe essere lo stesso input x e questo dovrebbe tenere per ogni pk, sk generato dalla generazione di tasti o generazione dei parametri algoritmo. Ora notate che non appena lo dicessimo questo requisito di correttezza significa automaticamente che la tua funzione f che c'è come parte del tuo schema di funzione trapporta deve essere funzione uno a uno.Che significa se hai 2 input distinti x1 e un altro input x2 dove x1 non è uguale a x2e se si prova a valutare la funzione fpk sull'input x1 e sull'input x2 non è possibile ottenere lo stesso output y perché se entrambi x1 e x2 vengono mappati sullo stesso output y sotto la funzione fpk poi cosa succede quando si cerca di invertire l'input y con il tasto segreto. Tu puoi ottenere x1 con qualche probabilità puoi riottenere x2 con qualche probabilità.Ma che rigorosamente va contro il requisito di correttezza, il requisito di correttezza dice che dovresti ottenere indietro l'input esatto con cui hai valutato la funzione fpk e quindi cerca di eseguire l'algoritmo inverso senza ambiguità e che è garantito solo se la tua funzione fpk è una funzione one-to-one. Tuttavia, notato che anche se la funzione fpk è una funzione one-to-one che non significa che la funzione debba essere una mappatura. Ci potrebbero essere diversi input possibili dal tuo codominio set y che potrebbe non avere un'immagine presotto la funzione f ed è per questo che abbiamo una disposizione speciale per l'output della funzione inversa per essere un bot simbolo perché se stiamo cercando di invocare la funzione Inv su qualche elemento y che non ha una pre - immagine che significa questo y non è un elemento dell'intervallo della tua funzione f.Poi dovremmo ottenere l'output bot che indica che stiamo cercando di invertire qualcosa che non ha corrispondente in precedenza. Ecco quindi una definizione di funzione "one-way trapdoor ". (Riferirsi Slide Time: 09.42)Così abbiamo visto il requisito di correttezza ora dobbiamo modellare la proprietà One - Waynesse ricordare la proprietà One - Wayness richiede che qualsiasi entità che possegga la chiave segretao le informazioni del trapdoor debbano essere in grado di invertire la funzione o calcolare l'output della funzione Inv su qualsiasi y dall'intervallo impostato della funzione f, ma in assenza di le informazioni trapelate dovrebbero essere computazionalmente difficili da calcolare l'output della funzione inversa su qualsiasi y appartenente alla gamma impostata della funzione f a destra. E questo dovrebbe reggere anche se quell' entità o quell' algoritmo avverseriale conosce la descrizione di la chiave pubblica o il pk chiave pubblica. Proviamo dunque a modellare questo requisito da un esperimento che chiamiamo Inverti?, f n esperimento. Questo esperimento è quasi lo stesso dell'esperimento di tipo che abbiamo usato per modellare la proprietà One - Wayness per la funzione one-way che fa non avere un'informazione trapporta associata ad esso.Ma ora avrà qualche requisito di sicurezza diverso qui o l'output dell'esperimento è definito in modo diverso e le regole dell'esperimento sono anche leggermente diverse qui. Quindi quello che è noto pubblicamente è la descrizione di uno schema di trapdoor ovvero la tripletta di algoritmo (Gen, f, Inv) e il dominio e co - dominio della funzione f. Ora la sfida è generata per l'avversario è la seguente.Lo sfidante dello sperimentatore esegue l'algoritmo di generazione dei parametri per ottenere la coppia di chiave pubblica e la chiave segreta e sceglie un casuale x dal dominio della funzione fe la sfida lanciata all'avversario è la seguente. La chiave pubblica è data a l'avversario e il valore della funzione f sull'input casuale x cioè y è dato anche come una sfida all'avversario.E l'obiettivo dell'avversario è sostanzialmente quello di calcolare la pre - immagine di questa y senza conoscere la chiave segreta corrispondente o l'informazione trapporta. Quindi sostanzialmente avversaria dopo la quantità di tempo polinomiale sta andando a produrre alcuni x - dal dominio della funzione f e diciamo che l'output dell'esperimento è 1, cioè che l'avversario ha vinto l'esperimento se e solo se l'avversario A è in grado di arrivare correttamente con l'input x che ha dato l'output y. E la mia definizione di sicurezza è che diciamo che una funzione f che fa parte del tuo schema di funzione trapdoor è a senso unico se per qualsiasi avversario politempo che partecipa a questo esperimento c'è qualche funzione trascurabile nel parametro di sicurezza tale che la probabilità di ottenere che avversario questo esperimento sia superiore ad una qualche funzione trascurabile in cui la probabilità viene presa sulla scelta casuale dell'esperimento.Namely la casualità coinvolta nella generazione dei parametri pk, sk e la casualità utilizzata per la selezione del valore di x qui a destra. Quindi sostanzialmente l'essenza di questo esperimento è la sfida per l'avversario è quella di arrivare con un destro x anche senza conoscere la definizione di sk e sicurezza esige che se l'avversario non conosce le informazioni trapporta o il segreto key sk allora salvo con qualche piccolissima probabilità dovrebbe essere computazionalmente difficile perun avversario politempo per arrivare con un x corretto. Nella definizione non abbiamo legato una probabilità di successo dell'avversario che ha vinto l'esperimento di essere 0 perché c'è sempre una strategia indovinosa da parte dell'avversario che può solo indovinare qualche casuale x dal set x e con qualche probabilità non zero potrebbe così accadere che un indovino x si scopre effettivamente il corretto x. Quindi il meglio che possiamo sperare è che qualsiasi avversario politempo non debba essere in grado di fare qualcosa di meglio che indovinare il casuale x su cui viene valutata la funzione f.(Fare Slide Time: 13.34)Ora una volta che abbiamo la definizione di funzione di trapdoor one-way ci facciamo definire una nozione correlata e cioè una sola via trapdoor OWTP a destra. Quindi una permutazione di tipo a senso unico è un tipo speciale di tipo unidirezionalità dove il dominio e il co - dominio della tua funzione f sono uguali e il set y è uguale e questo automaticamenteimplica che la tua funzione fpk sia uno a uno su mappatura.Questo è perché sappiamo che se la funzione è una funzione trapporta a senso unico allora la proprietà di correttezza implica che la tua funzione f debba essere una funzione uno - a - una ma ha bisogno dinon essere su funzione, ma non appena garantisco che il mio dominio e il co - dominio siano uguali e se entrambi co - dominio e dominio sono set finiti che effettivamente si tratterà per la costruzione che vedremo in seguito. Poi se la mia x e la mia sono uguali e sono finite e se la mia funzione è una mappatura una tantum allora implica automaticamente che la funzione sia anche sulla mappatura, questo significa per ogni x che avrò un'immagine unica e non posso avere 2 differenti x mapping alla stessa y e per ogni y dal set y ho un distinto x tale che f (x) mi avrebbe dato quella y. Il che significa automaticamente che se sto considerando una permutazione di una sola via trapdoor allora l'output della mia funzione inversa non potrà mai essere un bot perché effettivamente invoglierò il mio algoritmo inverso su qualche input y appartenente al set y allora dato che la mia funzione è una funzione invertibile o è uno - a - uno sulla mappatura ottero sempre un elemento x appartenente al dominio della funzione f ovvero x. Quindi bot non può essere un possibile risultato qui. Ecco allora l'unica differenza per il caso di permutazione di una sola via trapana. (Riferirsi Slide Time: 15.30)Quindi ora supponiamo per il momento in cui hai dato una funzione di trapdoor a senso unico non abbiamo ancora visto come se effettivamente non abbiamo ancora visto una funzione di trapporta a senso unico in seguito a quando introdurremo il numero teoretico del numero e il numero teoretico di problemi difficili vedremo esempi di funzione di trapporta a senso unico, ma per il momento supponiamo di avere una funzione di trapelamento unidiremo che vedremo come usare quella funzione di trapelatore di sola andatapossiamo progettare un protocollo chiave di scambio di chiavi anonimo che realizzi la nozione di debole privacy. Così ciò che è pubblicamente noto è una descrizione dello schema di funzione di trapdoor one-way over alcune serie finite x, y e l'obiettivo qui è quello di progettare un protocollo di scambio chiave ovvero una coppia di protocolli uno per il mittente e uno per il destinatario che realizzi la nozione di privacy debole dove utilizzare questo schema di funzione di trapdoor unico e uno schema resultante sarà un elemento da questo set y. E dalla descrizione della funzione di trapdoor one-way cosa fa esattamente una funzione trapporta univocata : permette a chiunque di calcolare la funzione f, ma fino a quando e a meno che altra parte non possiate le informazioni trapporta non sarebbe possibile invertire l'output della funzione f. Quindi ora in base a questa intuizione è molto semplice arrivare con un protocollo di scambio chiave .Così il protocollo Π S e Π R per il mittente e il destinatario rispettivamente saranno i seguenti. Quello che il destinatario può fare qui è che può eseguire l'algoritmo di generazione dei parametri del sistema di funzioni "one-way" e ottenere la coppia di chiavi pubbliche e segrete e può dare la descrizione della chiave pubblica al mittente qui a destra e una volta che il mittente impara la descrizione del tasto pubblico ciò che fa è: prende il random x dal dominio della funzione f e conosce la descrizione della funzione f e ora conosce il tasto pubblico pk. Quello che può fare è solo valutare la funzione f utilizzando il pk chiave e l'input x e ottenere un output y che comunica al destinatario. Ora ciò che il destinatario può fare è dato che il ricevitore possegga la chiave segreta o l'sk informazioni trapdoor, può calcolare l'output della funzione inversa sull'input y sotto il tasto sk e può ottenere lo stesso x con cui è stato utilizzato dal mittente per calcolare un'emissione y ed entrambi mittente e destinatario possono ora emettere un valore comune o una chiave comune ovvero x. Ora la correttezza di questo protocollo di scambio chiave segue automaticamente la proprietà di correttezza del tuo schema di funzione di sportello unicodestra. Perché da quando siamo nel mondo passivo destra una copia del pk che è stata comunicata dal destinatario al mittente sarà una copia autenticata sarà lo stesso pk che il destinatario ha generato e corrispondente sk viene utilizzato dal destinatario per calcolare l'inversione di y sotto il tasto segreto sk: Invsk (y). Quindi la correttezza di questo protocollo di scambio chiave intero segue dalla proprietà di correttezza del tuo schema di funzione trapporta sottostante.E una privacy debole di questo protocollo di scambio di chiavi intero segue dalla proprietà One - Wayness della funzione sottostante f. Quindi se abbiamo un tempo polinomiale eavesdropper che eaveschi la comunicazione e prendiamo la trascrizione del protocollo in modo che sia esattamente il protocollo trascrizione per l'avversario. Dal punto di vista dell'avversario si tratta di un pk casuale la cui corrispondente informazione trapporta non è nota all'avversario.E l'avversario sta vedendo ora il valore y che è l'output della funzione fpk su alcuni random x dove il random x non è noto all'avversario e il requisito della privacy debole è che il risultato x che è l'output per il mittente e il destinatario qui non dovrebbe essere conosciuto nella sua interezza all'avversario. Non puntiamo qui per la definizione di segretezza in base all'indistinguibilità .In realtà puntiamo su tutti o nulla di requisito di sicurezza qui perché siamo in l'impostazione della privacy debole qui. Quindi se a tutto il tempo polinomiale avversario imparando il tasto public key pk e una funzione output y può arrivare con x in politempo con significativa probabilità allora vuol dire che abbiamo un'istanza della privacy debole o dell'esperimento Invert dove un avversario politempo può vincere quell' esperimento con probabilità non trascurabile che va contro l'assunzione che lo schema di funzione trapporta sia uno schema di funzione di trapdoor one-way. Così solo con probabilità trascurabile questo eavesdropper politempo potrebbe arrivare con il corretto x, altrimenti la x non sarà nota all'avversario e che garantisce che questo protocollo di scambio chiave vi dia effettivamente la nozione di privacy debole. Così questo mi porta alla fine di questa lezione. Tanto per riassumere in questa lezione abbiamo introdotto una nozione di funzione trapdoor unidirezionalità di tipoe abbiamo anche introdotto una nozione di permutazione trapana a senso unico. La funzione a senso unico è un tipo speciale di funzione a senso unico che è facile da invertire su qualsiasi casuale o qualsiasi valore dal co - dominio o dal range impostato della funzione fornita di avere una speciale informazione trapporta , ma in assenza di informazioni trapporta è molto difficile invertere qualsiasi input casuale dalla gamma impostata della funzione e abbiamo visto che se si èdate una funzione di trapdoor a senso unico allora possiamo progettare un protocollo di scambio chiave ottenendo la nozione di privacy debole. Grazie.