Loading
Note di Apprendimento
Study Reminders
Support
Text Version

Ipotesi Di Durezza Crittografica

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 Collezione - 39 Cryptographic Hardness Presupposti nei Gruppi ciclici Ciao a tutti, benvenuti a questa lezione. Tanto per ricordare nell'ultima lezione avevamo visto le idee sottostanti che sono coinvolte nel protocollo Diffie – Hellman Key Exchange Protocol. Tuttavia non avevamo ancora visto i passi esatto del Diffie – Hellman Key Exchange Protocol. (Riferimento Slide Time: 00.42) Così in questa lezione introdurremo varie ipotesi di durezza crittografica nel contesto dei gruppi ciclici ovvero l'assunzione discreta di log, Diffie computazionale – Hellman assunzione e l'assunzione di Diffie – Hellman e poi in base a queste supposizioni vedremo i passi esatto del Diffie – Hellman Key Exchange Protocol. (Riferimento Slide Time: 01.00)Quindi iniziamo innanzitutto con il problema del log discreto e l'assunzione discreta dei log. Quindi il problema del log discreto è sostanzialmente quello di dover calcolare in modo efficiente il registro discreto di un elemento casuale di gruppo in cui si è appena data la descrizione del generatore e un elemento casuale del gruppo. Così questo è modellato da un esperimento qui che ha giocato tra un avversario delimitato computazionalmente e un ipotetico verificatore dell'esperimento. Dove la descrizione del gruppo ciclico è pubblicamente conosciuta e ciò che intendo con la descrizione del gruppo ciclico è che si conosce l'operazione di gruppo sottostante che c'è nel gruppo e la dimensione del gruppo cioè il numero di elementi e il generatore perché ci si dà un gruppo ciclico e noi assumiamo qui che la presente notazione (| |q| |) doppia barra questa notazione significa sostanzialmente che i numeri di bit che richiediamo per rappresentare il valore q è n. Ovvero significa che ogni elemento del gruppo G richiede n numero di bit per la rappresentazione e supponiamo anche di avere algoritmi in politempo per eseguire operazioni di gruppo e di esponenziazione e tempo polinico dove il polinomio nel numero di bit che si legge per rappresentare il valore q. Quindi i passi o le regole dell'esperimento come segue. Così lo sfidante o l'esperimento picchia un indice casuale α nell'intervallo 0 a q – 1. E una volta picchia l'indice α calcola il valore u che è g α e lo dà allo sfidante. Quindi prima di procedere qui vorrei sottolineare che questo intero esperimento questo discreto esperimento di log sto formulando assumendo una rappresentazione di gruppo moltiplicativo, ma si può immaginare che l'esperimento corrispondente sia presente anche per un gruppo ciclico di gruppo in cui l'operazione sottostante è additiva. Così da quando l'indice α viene scelto casualmente dal set 0 a q – 1 che significa automaticamente che l'elemento u che viene gettato come una sfida all'avversario è anche un elemento di gruppo casuale ok e ora la sfida per l'avversario è scoprire il discreto log di u ovvero il valore α. Quindi deve produrre un valore α e nella gamma 0 a q – 1 e le regole dell'esperimento dicono che l'avversario ha vinto l'esperimento o la produzione dell'esperimento è di 1 se e solo se la α che l'avversario ha presentato effettivamente è un discreto log del valore u, ovvero se g αmt = u detiene e diciamo che l'assunzione discreta di log detiene nel gruppo (G, o) se per ogni avversario politempo che partecipa a questo esperimento c'è qualche funzione trascurabile tale che l'avversario di probabilità vince il sperimentare o la produzione dell'esperimento è sconfinata da quella funzione trascurabile e lì si scopre che ci sono diversi gruppi candidati, dove effettivamente l'assunzione discreta di log è fortemente ritenuta vera. Sottolineo che si crede solo che in quei gruppi candidati il problema del log discreto sia effettivamente difficile da risolvere, ma non è ancora formalmente dimostrato che significa negli ultimi 30, 40 anni anche dopo aver eseguito una ricerca rigorosa nessuno è in grado di trovare un algoritmo in politempo o un algoritmo efficiente in grado di risolvere o calcolare un discreto log per elementi scelti casualmente da quei gruppi candidati. Ecco perché crediamo fortemente che il problema del log discreto sia effettivamente duro in quei gruppi ed è per questo che chiamiamo tutto questo problema come l'assunzione discreta dei log. (Riferimento Slide Time: 04.42)Ora vediamo un presupposto correlato che chiamiamo come l'assunzione computazionale Diffie – Hellman o l'assunzione di CDH e per questo ci permette di introdurre per la prima volta la nozione di funzione Diffie – Hellman. Immaginate quindi di avere la descrizione di un gruppo ciclico dove il generatore g è conosciuto e le dimensioni del gruppo sono q e dicono che ci vengono dati elementi u e v dal gruppo. Vi chiedo il vostro pardon, la funzione Diffie – Hellman dell'input u, v rispetto al generatore g DH   è definito il valore g al log discreto di u moltiplicato per discreto log di v: (Dlog). Di nuovo questa funzione Diffie – Hellman viene definita ipotizzando che l'operazione di gruppo sottostante sia molteplice, ma è possibile immaginare la corrispondente funzione Diffie – Hellman in cui l'operazione sottostante nel gruppo è un'operazione additiva. Se si guarda da vicino poi il modo in cui abbiamo definito questa funzione Diffie – Hellman poi si scopre che dato che u e v sono elementi del gruppo allora u può essere espresso come alcuni g α. E allo stesso modo l'elemento v può essere espresso come qualche g β questo significa se dico il modo in cui la funzione Diffie – Hellman sull'input u, v non è nulla, ma g alla potenza il log discreto di (g α β). Ora qual è esattamente il problema computazionale Diffie – Hellman o problema CDH ben il problema qui è che ti viene data la descrizione di un gruppo ciclico e il generatore e ti viene dato un paio di elementi scelti casualmente dal gruppo e la sfida o il problema che ci interessa risolvere è quello di calcolare le funzioni di Diffie – Hellman rispetto a quelle coppie di input. E l'assunzione di CDH afferma sostanzialmente che esistono gruppi candidati o esistono un gruppo in cui il problema del CDH è effettivamente difficile da risolvere in quantità polinomiale. Quindi modelliamo formalmente questo requisito da un esperimento che chiamiamo come esperimento CDH giocato tra un avversario delimitato computazionalmente e un esperimento o un verificatore quello che è pubblicamente noto è la descrizione del gruppo, l'operazione di gruppo, il generatore e le dimensioni del gruppo. E ipotizziamo che il numero di bit che dobbiamo rappresentare il valore q sia n, dove n è il parametro di sicurezza. Le regole dell'esperimento sono le seguenti. La sfida prepara la sfida per l'avversario scegliendo indici casuali α, β nella gamma 0 a q – 1 e calcola l'elemento g α e g β Quindi potreste chiedervi che sia efficiente da calcolare. È noto come efficienza computa g α g β se dato α e β e g sì che si scopre è sì che è quello che sto assumendo qui che per il gruppo sottostante abbiamo algoritmi in politempo per l'esecuzione dell'esponenziazione del gruppo a causa della mancanza di tempo non sto discutendo di quegli algoritmi esatti come calcolare g α in poli di n quantità di tempo. E potete vedere il libro di Katz & Lindell o qualsiasi riferimento standard in cui potete vedere i dettagli di come esattamente per calcolare o eseguire l'esponenziazione di gruppo in quantità di tempo polinomiale. Così una volta che l'esperimento o lo sfidante ha preparato o calcolato gli elementi u, v la coppia (u, v) viene lanciata come una sfida per l'avversario e la sfida per l'avversario è quella di calcolare la funzione Diffie – Hellman su questa coppia di input (u, v). Così da quando quell' output della funzione Diffie – Hellman sarà anche un elemento di gruppo sostanzialmente l'avversario deve presentare un elemento o un output un elemento dal gruppo che io denota come questo wand le regole dell'esperimento dice che l'avversario ha vinto l'esperimento o l'output dell'esperimento CDH è 1 se e solo se l'output winoltrato dall'avversario è esattamente uguale al valore della funzione Diffie – Hellman sulla coppia di input (u, v) ovvero è uguale a g α β Questo significa che la sfida qui per l'avversario è quella di compattarsi g α β senza realmente conoscere α e β che sono scelte casualmente dallo sfidante qui e l'assunzione di CDH dice sostanzialmente che il presupposto CDH detiene nel gruppo (G, o) se per ogni avversario politempo che partecipa a questo esperimento rispetto al gruppo (G, o) la probabilità che l'avversario possa vincere questo esperimento o risolvere il problema CDH è in alto delimitato da qualche funzione trascurabile nel parametro di sicurezza. E si scopre che ci sono diversi gruppi di candidati in cui l'assunzione del CDH è fortemente creduta per essere di nuovo vero sottolineo che ha solo fortemente creduto che non esista un avversario politempo che possa risolvere in modo significativo, che possa risolvere il problema del CDH con una probabilità significativa, ma non è ancora formalmente dimostrato che sia solo un presupposto. In un periodo di tempo anche dopo rigorosi tentativi non sono stati ottenuti algoritmi di politempo. Ed è per questo che abbiamo creduto che in quei gruppi candidati il problema del CDH sia effettivamente difficile da risolvere ed è per questo che diciamo che in quei gruppi candidati l'assunzione di CDH detiene. (Riferimento Slide Time: 09.54) E infine vediamo un altro problema correlato o supponente che chiamiamo come DDH o Decisionale Diffie – Hellman presupposto e per questo vi presento la definizione di Diffie – Hellman triple. Quindi una tripletta di elemento dal gruppo che dico denota come g α, g β e g γ si chiama Diffie – Hellman triple if γ = il prodotto di α e β Ancora questa definizione di Diffie – Hellman triplet è rispetto a un gruppo ciclico dove l'operazione sottostante è in multiplicità, ma questa definizione può essere modificata rispetto ad un gruppo ciclico dove l'operazione sottostante è l'operazione di aggiunta. Ora il problema del DDH è quello di distinguere in modo efficiente una tripletta di Diffie – Hellman scelte casualmente da una tripletta scelta casualmente sul gruppo. Il che significa un avversario o un algoritmo sarà dato un tripletto che potrebbe essere un tripletto di Diffie – Hellman o potrebbe essere una tripletta arbitraria scelta casualmente e deve distinguere se si sta vedendo un tripletto di Diffie – Hellman o una tripletta scelta casualmente e questo requisito viene formalizzato da un esperimento che chiamiamo come esperimento DDH e l'esperimento è giocato tra uno sfidante matematico e arbitrario delimitato o l'esperimento in cui l'informazione pubblica che è disponibile è la descrizione di un gruppo ciclico ovvero l'operazione o la dimensione del gruppo e il generatore e la sfida per l'avversario è preparata come segue. Lo sfidante sceglie alcuni indici casuali α, β, γ uniformemente in modo casuale nel set da 0 a q -1 e calcola i primi 2 componenti della tripletta che verrà lanciata come una sfida all'avversario. Ovvero u è calcolato come g α e v è calcolato come g β. Dato che α e β sono scelti casualmente, implica automaticamente che gli elementi u e v sono anche elementi casuali del gruppo e ora per generare la terza componente della sfida che va gettata all'avversario lo sfidante picchia o lancia una moneta uniformemente casuale con probabilità metà potrebbe essere 0 con probabilmente la metà potrebbe essere 1. Se il gettone di moneta è 0 allora il terzo componente della tripletta cioè w si dice di g γ che significa w è un elemento uniformemente casualmente indipendente da u e v mentre se il gettone coin è 1 allora w è impostato per essere g α e ora una volta che la w viene decisa la tripletta u, v, w viene lanciata come una sfida all'avversario e la sfida per l'avversario è decidere o distinguere o identificare se si sta vedendo una tripletta di Diffie – Hellman. O se si sta vedendo una tripletta davvero casuale sul gruppo; questo significa che deve individuare se la tripletta u, v, w viene generata secondo il metodo b = 0 o se viene generata secondo il metodo b = 1 così l'avversario sottopone la sua risposta e cioè si genera un bit b e le regole dell'esperimento e la definizione dell'esperimento è che diciamo che l'avversario ha vinto l'esperimento o l'output dell'esperimento è 1, se e solo se l'avversario è correggente per identificare se ha visto una tripletta con il metodo b = 0 o con il metodo b = 1 cioè ha identificato correttamente bI = b e diciamo che l'assunzione di DDH detiene nel gruppo (G, o) se per ogni avversario politempo che partecipa a questo esperimento esiste una qualche funzione trascurabile tale che la probabilità che l'output di esperimento del DDH sia del 1 rispetto a quella avversaria è superiore a metà + trascurabile. Così notiamo che per l'esperimento DLog e per l'esperimento del CDH la definizione era che l'uscita dell'esperimento è di 1 minuti dovrebbe essere delimitata da qualche funzione trascurabile perché lì l'obiettivo dell'avversario era quello di non distinguere qualcosa contro qualcosa. Se la sfida per l'avversario era quella di calcolare qualcosa, ma in questo esperimento DDH o in questo problema DDH l'obiettivo dell'avversario è quello di distinguere un tipo di tripletta contro un altro tipo di tripletta. Ed è per questo che stiamo dando una definizione di tipo indistinguibile e per questo motivo la definizione è che diciamo che l'assunzione di DDH detiene solo se nessun avversario politempo può distinguere una tripletta di Diffie – Hellman da una tripletta non Diffie – Hellman eccetto con probabilmente la metà + trascurabile. Equivalentemente la stessa condizione può essere messa in questo modo. Possiamo dire che l'assunzione di DDH detiene nel gruppo se non importa se la tripletta che viene lanciata come una sfida a quell' avversario viene generata con metodo b = 1 o con il metodo b = 0. La risposta dell'avversario è quasi identica cioè dire bmt = 1 in entrambi i casi salvo con qualche probabilità trascurabile e si può dimostrare che entrambe queste condizioni sono equivalenti l'una all'altra. Ancora una volta si scopre che ci sono diversi gruppi candidati in cui l'assunzione di DDH è fortemente ritenuta vera e di nuovo sottolineo che è solo fortemente creduto che in quei gruppi l'assunzione di DDH o il problema del DDH sia difficile da risolvere non è matematicamente dimostrato. Solo perché non abbiamo nessun algoritmo in politempo fino ad ora per risolvere il problema del DDH in quei gruppi che è il motivo per cui crediamo che il problema del DDH sia effettivamente difficile da risolvere in quei gruppi candidati. (Riferimento Slide Time: 15.26) Così ora vediamo la relazione tra l'assunzione DLog, assunzione di CDH e assunzione DDH. Quindi per il vostro riferimento ho scritto l'esperimento per l'assunzione di DLog con assunzione di CDH e assunzione di DDH e in tutto questo esperimenti le informazioni pubbliche sono la descrizione di un gruppo ciclico di nuovo per semplicità presumo che l'operazione sottostante sia operazione molteplice. La dimensione del gruppo è q e il generatore è g che è noto pubblicamente e un numero di bit che serve a rappresentare il valore q è n e io uso la notazione Zq per denotare il set da 0 a q – 1 a destra. Così in tutto questo esperimento ogni volta che lo sfidante stava raccogliendo o cercando di generare un elemento uniformemente casuale dal gruppo stava fondamentalmente raccogliendo un indice casuale dal set 0 a q – 1. Tutti quei passaggi in cui lo sfidante stava raccogliendo un indice casuale dal set 0 a q – 1 può essere rappresentato come se lo sfidante scegliesse un indice casualmente dal set Zq. Quindi ora vediamo innanzitutto il rapporto tra l'assunzione di Dlog e l'assunzione di CDH. Si scopre che se l'assunzione di CDH detiene nel gruppo G allora implica che l'assunzione di DDH detiene anche in quel gruppo. Metti in altro modo se si vede la contrapposizione di questa implicazione se il problema di DLog è effettivamente facile da risolvere computazionalmente facile da risolvere nel gruppo allora usando quell' algoritmo è molto facile per qualsiasi avversario politempo risolvere il problema del CDH così come in quel gruppo perché se si può calcolare la DLog di un elemento casuale in poly quantità di tempo e poi se si utilizza quell' algoritmo nell'esperimento CDH, quindi usando quell' algoritmo, l'avversario, A può calcolare il DLog di u e può estrarre il Dlog di v e cioè può estrarre i valori α e β in polarità quantità di tempo e una volta sa α e β poi stesso può compere g α β correttamente. Questo significa che sarà effettivamente l'output della funzione Diffie – Hellman sulla coppia casuale di input u, v. Questo significa che se il problema di DLog è facile allora è il problema del CDH. Quindi questo dimostra l'implicazione in prima direzione. Ora che ne è dell'implicazione nell'altra direzione inversa che significa possiamo dire che se l'assunzione di DLog detiene nel gruppo allora implica anche che anche l'assunzione di CDH detiene nel gruppo la risposta è che la risposta è che non sappiamo nulla di questo fatto. Infatti, crediamo fortemente che ci possano essere gruppi in cui il problema del CDH è più facile da risolvere anche se il problema DLog è difficile da risolvere. Il motivo è che se si vede la descrizione dell'esperimento CDH del problema CDH l'obiettivo dell'avversario è quello di calcolare g α β dove non conosce α e β Un modo di computing g α β potrebbe essere quello di calcolare α da u e β da v e cioè risolvere il problema del log discreto, ma questo non deve essere l'unico modo con cui un algoritmo avversario o politempo potrebbe tentare di calcolare il valore di g α β Potrebbe esserci qualche shortcut o qualche altro modo per calcolare g α β senza effettivamente calcolare α e β ed è per questo che potrebbe essere il caso che anche se nel tuo gruppo il problema CDH sia più facile da risolvere il problema del log discreto potrebbe essere ancora difficile da risolvere. Ed è per questo che assumere saggi diciamo che CDH che fa supporre che un problema CDH sia difficile da risolvere nel tuo gruppo è un'assunzione più forte rispetto a rendere il presupposto che il problema di DLog sia difficile da risolvere nel tuo gruppo perché sembra che quel problema CDH sia relativamente più facile da risolvere rispetto al problema del log discreto. Quindi presupposto saggio l'assunzione di CDH è una supposizione più forte. Perché il problema difficoltoso del problema CDH potrebbe essere più facile da risolvere rispetto al problema del log discreto. Ecco quindi che si tratta di una relazione tra l'assunzione discreta di log e l'assunzione di CDH. Ora vediamo il rapporto tra l'assunzione di CDH e l'assunzione di DDH. Così si scopre che se nel tuo gruppo l'assunzione di DDH detiene allora l'assunzione di CDH detiene anche e questo può essere dimostrato facilmente da un contrapposto. Nello specifico, se si dispone di un algoritmo in politempo che può risolvere il problema del CDH con notevole probabilità allora usando quell' algoritmo è molto facile anche risolvere qualsiasi istanza di problema DDH in quel gruppo. Praticamente quello che il solutore DDH deve fare è che deve, dato la coppia u, v, w ciò che deve fare è che deve invocare il solutore CDH sulla coppia u, v e ottenere il valore dell'output della funzione Diffie – Hellman sulla coppia di input u, v. E confronta quell' output con w e di conseguenza il solutore DDH può decidere se si sta vedendo un tripletto di Diffie – Hellman o una tripletta scelta casualmente sul gruppo in modo che sia l'implicazione in una direzione ora cosa che riguarda l'implicazione nell'altra direzione. Possiamo dire che se l'assunzione di CDH detiene nel gruppo allora così è l'assunzione di DDH e la risposta in questo caso è chiara no. Si scopre che abbiamo alcuni gruppi specifici in cui sappiamo risolvere il problema del DDH in polpa quantità di tempo, ma anche se sappiamo come risolvere un problema DDH in polpa quantità di tempo in quei gruppi non abbiamo ancora alcun algoritmo in politempo per risolvere il problema del CDH con una probabilità significativa in quei gruppi che significa che il problema del DDH è difficile da risolvere in un gruppo è un'assunzione più forte rispetto al presupposto che un problema CDH sia difficile da risolvere in quel gruppo. Perché la difficoltà saggia sentiamo che un problema DDH è più facile da risolvere per risolvere il problema del CDH che significa se consideriamo queste 3 assunzioni discrezioni discrete è l'ipotesi più grande perché la difficoltà a risolvere il problema del log discreto è il problema più difficile mentre rendere l'assunzione del DDH è l'assunzione più forte perché difficile risolvere il problema del DDH potrebbe essere computazionalmente meno costoso rispetto a risolvere il problema CDH rispetto a risolvere il problema DLog. (Riferimento Slide Time: 21.48) Così ora abbiamo i 3 presupposti il CDH l'assunzione discreta di log, l'assunzione di CDH e l'assunzione di DDH e ora vedremo gli esatti passi matematici o i passi concreti del Diffie – Hellman Key Exchange Protocol. Ricordate quindi nell'ultima lezione che abbiamo visto i passi del Diffie – Hellman Key Exchange Protocol ipotizzando che ci sia data qualche funzione speciale E e F a destra. Così solo per riassumere il requisito dalla funzione E dovrebbe essere che dovrebbe essere facile da calcolare, dovrebbe essere un modo e non solo quello dato α e il valore della funzione E (β) anche senza conoscere β dovrebbe essere facile da calcolare F (α, β) se conosci α e avevamo anche visto che se vuoi ottenere un protocollo Diffie – Hellman Key Exchange con la nozione di privacy debole allora il requisito dalla funzione E e F dovrebbe essere che se qualcuno ti dà il valore di E (α) e E (β) poi solo conoscando E (α) e E (β) dovrebbe essere difficile per te calcolare F (α, β) nella sua interezza, ma se si vuole ottenere una nozione più forte di segretezza cioè la forte privacy da parte del Diffie – Hellman Key Exchange Protocol allora abbiamo bisogno di ulteriori requisiti dalla funzione E e F ovvero ci chiediamo che il valore di F (α β) deve essere computazionalmente indistinguibile da qualsiasi valore casuale dal set y. Anche se si è dati con il valore di E (α) e con il valore di E (β).   Ma eseguendo questo Diffie – Hellman Key Exchange Protocol un mittente e il destinatario possono essere d'accordo solo su un elemento di gruppo pseudo casuale non su una stringa di bit casuale pseudo. Quindi una soluzione potenziale per risolvere o aggirarsi in questo problema è quella di utilizzare una funzione di derivazione chiave che avevamo visto durante la nostra discussione sulla funzione hash e possiamo utilizzare qualsiasi funzione di derivazione standard basata sulla funzione hash. E ipotizzando che l'elemento di gruppo pseudo casuale risultante che mittente e destinatario sta andando in uscita alla fine del Diffie – Hellman Key Exchange Protocol ha un'entropia sufficientemente ampia poi applicando la funzione di derivazione chiave su quella pseudo uscita comune casuale sia mittente che destinatario possono ottenere localmente una stringa di bit pseudo casuale che possono ora utilizzare come chiave per qualsiasi primitivo crittografico. E incontreremo di nuovo questa idea e di nuovo in seguito, quando discuteremo la nozione di sistema di crittografia pubblica e di sistema di crypto ibrido. La seconda limitazione che c'è nel Diffie – Hellman Key Exchange Protocol è che ti dà sicurezza solo contro un eavesdropper che monitora la comunicazione tra il mittente e il destinatario. Si scopre che se il nostro avversario è un avversario attivo dove può intercettare il pacchetto o dove può cambiare il contenuto dei messaggi comunicati tra il mittente e il destinatario, allora può lanciare vari tipi di attacchi come l'attacco di imitazione, l'uomo nell'attacco di mezzo e così via. Ecco perché nel vero protocollo mondiale non usiamo il protocollo Diffie – Hellman Key Exchange come è nella sua forma di base. Facciamo modifiche in cima al Protocollo di Scambio Chiavi di Diffie – per garantire che ci prendiamo cura anche di un avversario attivo. Così questo mi porta alla fine di questa lezione. Tanto per riassumere in questa lezione abbiamo introdotto varie ipotesi crittografiche in gruppo ciclico ovvero l'assunzione discreta di log, l'assunzione di CDH e l'assunzione di DDH e basata su queste ipotesi