Loading
Note di Apprendimento
Study Reminders
Support
Text Version

Public - Key Cryptosystems

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 Indian Institute of Science – Bangalore Lecture – 42 Applicazioni crittografiche della Discrete Acquista Ciao tutti, benvenuti a questa lezione. (Riferirsi Slide Time: 00.36) Così solo per recap abbiamo visto fino ad ora, abbiamo visto varie supposizioni crittografiche nel contesto dei gruppi ciclici ovvero l'assunzione di DLog, assunzione di CDH, assunzione di DDH e abbiamo visto anche gruppi ciclici candidati in cui crediamo che quei presupposti effettivamente tratteggiano cioè quei problemi siano effettivamente difficili da risolvere. In questa lezione vedremo alcune applicazioni crittografiche dell'assunzione discreta di log ovvero vedremo funzione di compressione provvibilmente - sicura nel modello standard. Vedremo inoltre che come basato su DLog supponi possiamo progettare uno schema di impegno dimostrabilmente sicuro nel modello standard. Allora, ricordate che avevamo già visto instantiere di funzione di compressione e anche instanziamenti di schema di impegno basato sulla funzione hash. Ma la loro prova non era nel modello standard, nel senso le prove sono state date nel modello di oracolo casuale che fa supporre fortissimamente la funzione hash sottostante. Ma in questa lezione vedremo che come possiamo instanziare funzione di compressione, schemi di impegno e dare prove senza fare supposizioni non convenzionali. (Riferimento Slide Time: 01.35) Così solo per ricordare il problema DLog e l'assunzione di DLog. Il problema DLog è che si dà la descrizione di un gruppo ciclico, l'operazione di gruppo e il generatore e si dà un elemento casuale dal gruppo. Il tuo obiettivo è sostanzialmente quello di arrivare con il registro discreto di quell' elemento casuale in quantità polinomiale. L'assunzione di DLog afferma che diciamo che l'assunzione di DLog detiene in quel gruppo se nessun algoritmo di tempo polare può risolvere la sfida DLog tranne con probabilità trascurabili. E ora conosciamo almeno 2 gruppi candidati in cui si crede che il problema di DLog sia duro e solo noi possiamo usare i gruppi Zp * con operazione sottostante essendo modulo di moltiplicazione modulo p o possiamo prendere un sottogruppo di prime ordine di Zp * oppure possiamo portare il gruppo ad essere il gruppo in base ai punti su curve ellittiche modulo p e operazione sottostante essendo l'operazione plus. Quindi assumeremo un gruppo moltiplicativo ma qualunque cosa andremo a discutere in questa lezione, i passi possono essere semplicemente modificati o i passi di quei primitivi di crittografia possono essere semplicemente modificati per un gruppo ciclico dove si aggiunge l'operazione sottostante. (Riferimento Slide Time: 02 :43) Quindi vediamo la prima applicazione cioè costruire funzioni di compressione resistenti a lunghezza fissa. E per questo mi fa ricordare il modo in cui abbiamo costruito funzioni di compressione di lunghezza arbitraria o di hash utilizzando la trasformazione Merkle-Damgard. Quindi, quello che la trasformazione Merkle Damgard fa per te è che prende un input arbitrario e ti dà un hash di dimensioni fisse per questo. Per questo trasformiamo l'input in un input imbottiti per garantire che ogni blocco del messaggio sia un multiplo di n bit e poi facciamo una colorazione qui. Compendiamo una catena di hash dove in ogni iterazione assumiamo un blocco corrente del messaggio e l'output del precedente hash o l'output della precedente istanza della funzione di compressione. E poi di nuovo applicare un'istanza della funzione di compressione della dimensione fissa e l'output complessivo della funzione hash viene assunto come output dell'ultima istanza della funzione di compressione. Abbiamo dimostrato che se la funzione di compressione sottostante h è resistente alla collisione che significa in tempo polare è difficile arrivare a scontrarsi per la funzione di compressione della dimensione fissa, allora la funzione di hash risultante che abbiamo ottenuto applicando questa trasformazione Merkle-Damgard è anche resistente agli urti. Ora la domanda è come costruiamo questa funzione di compressione resistente alla collisione a lunghezza fissa che impiega 2 input cioè un input di dimensioni l + n bit che può essere analizzato come 2 input uno di sizel bit e un altro di dimensione n bit e ti dà un output di n bit. Sappiamo 2 approcci per questo: un approccio si basa su ipotesi di numero - teorici che vedremo in questa lezione. Tuttavia, non sono utilizzati praticamente. La costruzione di cui siamo a conoscenza e che abbiamo dimostrato di essere sicura si basa su cimici a blocchi ovvero la costruzione di Davies - Meyer. Tuttavia, la prova di sicurezza di quella costruzione è cioè nel modello di oracolo casuale. (Riferimento Slide Time: 04.54) Così, in questa lezione vedremo la costruzione in base alle ipotesi teoriche del numero la cui sicurezza può essere data solo in base a quella discreta assunzione. Quello che ci viene dato qui è che ci viene data la descrizione di un gruppo ciclico conosciuto pubblicamente dove l'operazione di gruppo è un'operazione moltiplicativa. Questo è senza perdita di generalità e ci viene dato un generatore pubblicamente conosciuto. E come impostazione ci viene anche dato un elemento uniformemente casuale dal gruppo il cui log discreto non è noto a nessuno. Si tratta quindi di un setup di una tantum che supponiamo sia fatto da un'entità attendibile, non da un avversario. Ma una volta fatto questo setup, possiamo utilizzare questo setup per quantità di tempo polinomiale o polinomiale di istanze. Ora utilizzando questo setup, il nostro obiettivo è progettare una funzione resistente agli urti che io chiamo come HDL o HDL in base alla funzione di registrazione discreta. E ci vuole un paio di input dove il primo input viene dal set Zq e un altro input viene dal set Zq e l'output sarà un elemento del gruppo. E una sicurezza cioè la resistenza di collisione della costruzione che stiamo per progettare dovrebbe essere basata sull'assunzione di DLog. Così, è possibile interpretare la funzione HDL che stiamo cercando di costruire come funzione che impiega 2 input di dimensione n-1, codificando stringhe di bit n-1 ad elementi di Zq. Questo perché sto assumendo qui che la dimensione di q è n ovvero il numero di bit che ho bisogno di rappresentare q è n. Quindi esiste alcuni gruppi in cui non ho bisogno di codificare, naturalmente ogni stringa di bit di lunghezza n-1 può essere mappata su un elemento di Zq. Ma se non è così posso fare una specie di codifica e posso codificare ogni stringa di bit di lunghezza n-1 come elemento di Zq. Possiamo quindi immaginare che questa funzione HDL che siamo interessati a calcolare prenda un input di dimensioni complessive pari a 2 volte n-1 bit che possono essere passati come 2 porzioni di n-1 ciascuno e di nuovo che sono mappati a 2 rispettivi elementi di Zq. Supponiamo che gli elementi del gruppo siano codificati come stringhe l - bit poi si scopre che se 2n - 2 > l allora possiamo visualizzare questa funzione HDL che stiamo per costruire come funzione resistente agli urti e anzi ci sono diversi casi in cui effettivamente 2n – 2 > l. Ad esempio, se prendiamo il gruppo per essere un sottogruppo di prim'ordine di Zp * dove p si dice 2q + 1 ovvero è costituito da tutti i residui quadratici. Poi il tuo l non è altro che n + 1 perché le dimensioni di p saranno più delle dimensioni di q. E in quel caso chiaramente 2n - 2 > l e da qui se instanziato HDL su questo particolare gruppo di sottogruppi di prim'ordine di Zp * a base di residui quadratici, allora la funzione HDL risultante può essere visualizzata come funzione di compressione. (Riferimento Slide Time: 07 :52) Quindi prima di entrare nella costruzione della funzione di compressione, vediamo qui una definizione. Ricordati come parte di setup ti viene dato un elemento uniformemente casuale h dal gruppo, a parte il generatore. Ora definiamo quello che chiamiamo come rappresentazione di un elemento di gruppo relativo alla base g e h. Quindi per qualsiasi elemento di gruppo u appartenente al gruppo diciamo qualsiasi coppia (α, β) dal set Zq è chiamata come rappresentazione dell'elemento u rispetto alla base g e h se la relazione u = g α h β trattiene. Ripeto, sottolineo tutta questa discussione è rispetto al presupposto che il mio funzionamento sottostante sia un'operazione molteplice. Ma ancora, tutte queste definizioni e discussione possono essere portate avanti per il gruppo ciclico dove si aggiunge l'operazione sottostante. Quindi, abbiamo la definizione di una rappresentazione di un elemento relativo ad g e h. Ora rispetto a queste definizioni abbiamo certi fatti qui. Il primo fatto è che se si prende qualsiasi elemento u dal gruppo allora esistono esattamente q numero di rappresentazioni distinte dello stesso elemento u relativo ad g e h. Ciò che significa è che, se si fissa qualsiasi arbitrario β dal set Zq poi corrispondente a quello fisso β esiste un α univoco dal set Zq tale che la relazione g α = u * (h β) -1 trattiene. Ed è per questo che per β 1 si otterrà un corrispondente α 1 che sarà una rappresentazione tale che (α 1, β 1) sarà una rappresentazione di u. Allo stesso modo se si fissa un altro β diciamo β 2 che implicherà un altro α 2 tale che (α 2, β 2) è la rappresentazione dello stesso elemento u e così via. Quindi, come che quanti β s puoi sistemare? È possibile avere q numero di β s perché la gamma di β che è il set Zq. Ed è per questo che la gamma di corrispondenti α è anche Zq ed è per questo che hai esattamente q numero di rappresentazioni distinte di qualsiasi elemento u. Quindi questo è il primo fatto. Il secondo fatto è che se si hanno 2 rappresentazioni distinte per lo stesso elemento u, allora si può estrarre il registro discreto dell'elemento casuale h alla base g. Perché questo? Quindi, immaginate di ricevere 2 rappresentazioni distinte dello stesso elemento u say (α, β) è una delle rappresentazioni e (α cori, β) è un'altra rappresentazione che rappresenta entrambi lo stesso elemento u relativo ad g e h. Questo significa che queste 2 equazioni reggono e dice (α, β) e (α cori, β) sono distinti. Che significa coppia vice (α, β) è diverso da (α cori, β). Ora se entrambi questi rapporti si tengono, allora posso fare la sostituzione e ottenere quello g α - α il suo è lo stesso di h β - β E ora ho preteso che (β – β) è non 0 perché se (β – β) è 0, poi h0 è 1. E h0 è 1 che significa l'elemento di identità possibile solo se (α α) è anche 0 che implica automaticamente che α = α stesso e β = β che sia contraddizione con l'assunzione che (α, β) è diverso da (α cori, β). Che significa (β – β) è non zero. Dato che è diverso da zero, allora posso sempre calcolare l'inverso moltiplicativo di (β – β) che io denota da ichi modulo q. Dato β espresso e dato β, l'inverso cioè il valore Che Modulo q può essere calcolato in polenta (n) tempo. Esistono algoritmi ben noti per l'informatica di questo valore che non sto discutendo qui. Ma devi credermi che se (β – β) è non zero, poi l'inverso moltiplicativo di (β – β) cioè gli ichi modulo q esistono che possono essere calcolati in tempo polare. Quindi se possiamo calcolare gli arredi in polpa di tempo e se ci viene dato g e se ci viene dato α e α corallo, allora possiamo chiaramente vedere che g (α α) e nell'esponente moltiplicato per icco vi darà il valore h. Il che significa che il Dloggh non è altro che (α α) moltiplicato per ∆ modulo q. Quindi questo significa che se qualcuno può darti 2 rappresentazioni distinte per qualsiasi elemento u dal gruppo, quindi usando quell' algoritmo di elemento o usando la coppia (α β) e (α cori, β) possiamo calcolare bene anche il Dlogghas. E questo costituisce la base di calcolo della nostra funzione di compressione o di costruzione della nostra funzione di compressione a cui siamo interessati. (Riferimento Slide Time: 13.02) La costruzione della funzione di compressione resistente agli urti è la seguente: come impostazione ci viene dato un elemento uniformemente casuale e per comprimere la coppia di input (α β) come per questa funzione HDL quello che dobbiamo fare? In sostanza, dobbiamo calcolare il valore (g α, h β) che è l'output complessivo. E io affermo qui che se l'assunzione di DLog è vera nel gruppo sottostante che significa che il problema di DLog è effettivamente difficile da risolvere in polpa nel gruppo sottostante, allora questa funzione HDL è una funzione resistente alla collisione a lunghezza fissa Perché? Quindi questo perché trovare una collisione per questa funzione HDL significa arrivare con 2 rappresentazioni distinte per qualche elemento u dal gruppo correlato ad g e h. Come abbiamo visto nell'ultima slide se abbiamo 2 rappresentazioni distinte per qualche elemento di gruppo allora significa automaticamente sapere come calcolare il Dloggh che va contro l'ipotesi che il problema del log discreto sia difficile da risolvere nel gruppo. Quindi stabiliamo formalmente tutta questa implicazione con una riduzione qui. Immaginate quindi di avere un algoritmo in politempo che sappia trovare collisione nella funzione HDL. Utilizzando quell' algoritmo, costruiamo un altro algoritmo in grado di risolvere un'istanza di problema di log discreto nel gruppo. Così questo avversario ADL, partecipa a un richiamo dell'esperimento di log discreto rispetto al gruppo. Poi come parte della sfida per quell' esperimento lo sfidante dell'esperimento di log discreto picchia un x e dà la sfida h che è gx e l'obiettivo di questo avversario ADL è quello di estrarre questo x. Quello che fa è che richiama l'avversario e partecipa ad un'istanza dell'esperimento di resistenza alle collisioni e come parte di quell' esperimento ciò che fa è crea un setup dove la descrizione del gruppo è lo stesso gruppo dove l'avversario è ADL vuole risolvere il problema del log discreto e come parte di setup h viene dato come il setup pubblico dove h è uniformemente casuale. Così, si vede che h che viene gettato come una sfida al solutore di log discreto viene utilizzato ora come setup per questa funzione secondaria HDL. Ora come per la proprietà di questo algoritmo di finder collisione può arrivare con una collisione cioè si arriva con un valore hash u che potrebbe essere il valore hash di (α β) così come il valore hash di (α cori, β) tale che (α β) e (α cori, β) sono diversi ma i loro valori hash sono u. E come per la descrizione della funzione HDL dall'hash di (α β) e un hash di (α cori, β) è u che significa che questo rapporto detiene. Così ora quello che questa avversaria ADL fa non appena vede che l'avversario sta dando una collisione usando la matematica che avevamo visto nell'ultima slide, finisce il computing Dloggh e cioè calcola (α α) moltiplicato per l'inverso moltiplicativo di (β – β) modulo q. E si può vedere che il tempo di esecuzione dell'adversario ADL è esattamente lo stesso del tempo di esecuzione dell'avversario. E la relazione saggia, possiamo dire che la probabilità che il solutore di log D vinca il suo esperimento cioè vince l'istanza dell'esperimento di log discreto è esattamente la stessa con la probabilità con cui l'algoritmo di finder di collisione vince l'algoritmo di individuazione delle collisioni contro la funzione HDL. Ma dal momento che stiamo ipotizzando che l'assunzione di DLog sia titolare nel nostro gruppo, allora sappiamo che per qualsiasi algoritmo di tempo polare, la probabilità che possa vincere un'istanza di log discreto nel gruppo è trascurabile. Questo significa che la probabilità lato sinistro è sempre superiore delimitata da una funzione trascurabile che implica automaticamente che la probabilità nella parte destra dell'espressione sia delimitata anche da una probabilità trascurabile. Così che stabilisce il fatto che la funzione HDL che abbiamo costruito costituisce effettivamente una funzione di compressione resistente agli urti. (Riferimento Slide Time: 17.33) Ora vediamo la seconda applicazione di applicazione dell'assunzione discreta di log. Ecco quindi che ora vi instanziamo uno schema di impegno in cui la prova sarà nel modello standard. Solo per ricordare uno schema di impegno è uno schema o un primitivo crittografico che coinvolge due entità sono cioè un mittente e un destinatario ed è un protocollo a 2 fasi. Nella fase di committenza il mittente richiama un impegno di protocollo o com e la fase di apertura è eseguita un protocollo aperto. Così nella fase di impegno il mittente ha un messaggio m da qualche spazio di messaggio che vuole impegnare per il destinatario. Per fare quel mittente sostanzialmente calcola l'impegno a lunghezza fissa del messaggio che io denota da c e invia l'impegno c al destinatario R. E la proprietà di sicurezza che richiediamo da questo protocollo com è che se il destinatario è cattivo e computazionalmente delimitato poi vedendo l'impegno non deve imparare cosa esattamente è commesso all'interno c. Così dal suo punto di vista la c dovrebbe vista come una busta sigillata. Non può vedere cosa sia esattamente il messaggio che è stato mantenuto all'interno dell'impegno. (Riferimento Slide Time: 18 :41) Il secondo protocollo è il protocollo di apertura che implementa la fase di apertura in cui il mittente ha rilasciato un messaggio fornendo una qualche informazione di apertura. Una volta che l'informazione di apertura viene fornita o verifica l'apertura delle informazioni e apre la busta sigillata, in base a determinati criteri accetta o rifiuta il valore che si rivela ora nella fase di apertura. La proprietà di sicurezza che richiediamo qui è che se il mittente è cattivo e il destinatario è onesto allora non dovrebbe essere possibile per un mittente corrotto aprire un impegno c in due modi diversi e cioè che debba essere vincolato a qualunque cosa abbia commesso nella fase di impegno. (Riferimento Slide Time: 19.22) Così prima di entrare nella costruzione dello schema di impegno nel modello standard fatemi ricordare anche come modelliamo la proprietà di nascosto e la proprietà vincolante. Quindi il nascondere la proprietà è modulo dall'esperimento nascosto dove l'avversario sottopone una coppia di messaggi dallo spazio dei messaggi e uno di quei messaggi viene commesso casualmente scegliendo qualche casualità uniforme dalla fase di casualità da parte dello sfidante. L'impegno di sfida è c * che potrebbe essere un impegno di m0 o un impegno di m1 con pari probabilità e la sfida per l'avversario è individuare se si sta vedendo un impegno di m0 o se si sta vedendo un impegno di m1. E diciamo che la produzione dell'esperimento è 1 o l'avversario vince per sperimentare se riesce a identificare correttamente se si sta vedendo un impegno di m0 o m1. E una definizione di sicurezza è che diciamo che uno schema di impegno o un protocollo d'impegno com soddisfa la proprietà nasale, hanno la probabilità di qualsiasi avversario politempo all'interno di questo esperimento è delimitato da 1/2 + qualche probabilità trascurabile. O dichiarato diversamente, non importa se il c * è un impegno di m0 o se c * è un impegno di m1. L'output di questo avversario dovrebbe quasi essere lo stesso dire b = 1 salvo con probabilità trascurabile. E un modo abbiamo formalizzato l'esperimento vincolante: requisito vincolante è dall'esperimento vincolante in cui l'avversario sottopone semplicemente un impegno c e un paio di messaggi di messaggio, casualità (m, s) e un altro paio di messaggi, casualità il (m*, s *) tale che m e m * sono diversi ma ancora l'impegno di m rispetto alla casualità s e un impegno di m * rispetto alla casualità s * si scopre essere lo stesso valore c e diciamo che l'algoritmo com ha proprietà vincolanti. Se la probabilità che qualsiasi avversario politempo potesse arrivare con una coppia di messaggi diversi che si impegnino per lo stesso impegno è superiore delimitato da una probabilità trascurabile. Quindi ora quello che faremo è vedere uno schema di impegno molto bello che viene definito uno schema di impegno di Pedersen che ti fornisce la proprietà di nascondi, la proprietà vincolante e la sua sicurezza si basa solo sull'assunzione di DLog. (Riferimento Slide Time: 21 :40) Così il setup pubblico che viene dato come parte dello schema di impegno è la descrizione del gruppo ciclico, l'ordine di gruppo e l'elemento di gruppo uniformemente casuale dal gruppo il cui log discreto non è noto a nessuno. Questo è come un setup fidato fatto da un terzo partito fidato ed è fatto una volta per tutte. Una volta fatto, possiamo utilizzarlo per istanziare o invocare il numero polinomiale di richiami dello schema di impegno. Nello schema di impegno di Pedersen, lo spazio dei messaggi è sostanzialmente Zq. Questo significa che il mittente vorrebbe impegnare qualsiasi valore nella gamma da 0 a q - 1 e lo spazio casuali sarà anche il set Zq. Quindi la fase di impegno o il protocollo com è la seguente: supponiamo che il mittente voglia impegnare un valore α che potrebbe essere qualsiasi valore compreso nell'intervallo 0 a q – 1. Per impegnare che il mittente picchi un β uniformemente casuale dallo spazio di casualità ovvero Zq e calcola la funzione di impegno che denota come PedCom (α β) che non è altro che g α h β. Io dengo quell' impegno di questa notazione. Così C denota l'impegno e i suoi subscript α e β denota che si tratta di una stringa o di un elemento di gruppo che è un impegno di qualche valore sconosciuto α rispetto alla casualità β. Così nel sottoscrigno il primo componente denota un valore che viene commesso e un secondo componente denota quella casualità che viene utilizzata per calcolare quell' impegno. La fase di apertura è dritta in avanti. Quindi immaginare il ricevitore ha un impegno esistente a disposizione con esso che ha ottenuto in una fase di impegno e dire che il mittente ha commesso α rispetto alla casualità β. Ora fornisce le informazioni di apertura che io denotano da (α cori, β). Se mittente è onesto e α il tuo sarà uguale a α e β il tuo sarà uguale a β. Mentre se il mittente è corrotto e se vuole rivelare un messaggio diverso nell'impegno esistente potrebbe presentare (α cori, β) diverso da (α, β). Per verificare se le informazioni rivelatrici o le informazioni di apertura siano corrette o meno. Ricevitore fa il seguente: ricompone l'impegno rispetto al fornito (α cori, β) e cioè calcola g α corβ lo confronta e lo confronta con l'impegno esistente che ha. Se corrisponde, allora outmette α o outmette 1. In sostanza accetta α altrimenti rifiuta alph. Quindi ora quello che dimostreremo qui è che se l'assunzione di DLog è vera nel gruppo ciclico sottostante, allora la funzione PedCom che abbiamo definito qui soddisfa la proprietà vincolante. E questo deriva semplicemente dal fatto che se si vede da vicino che la funzione PedCom che abbiamo definito qui è esattamente la stessa della funzione di compressione HDL che abbiamo definito appena in precedenza. Questo significa spezzare la proprietà di collegamento di questa funzione di impegno Pederson equivale ad arrivare con una coppia di valori (α β) e (α cori, β) tale che la funzione di impegno PedCom quando si calcola su (α β) e quando valutato su calcolato su (α cori, β) ti dà lo stesso valore di C α β Questo significa sostanzialmente uno sa come scoprire una collisione per la funzione HDL e se uno sa come calcolare o trovare collisioni nella funzione HDL con notevole probabilità in quantità polinomiale di tempo, allora sappiamo come calcolare il Dloggh in quantità polinomiale di tempo con notevole probabilità. Ma questo va contro il presupposto che l'assunzione discreta di log sia vera nel gruppo sottostante. Quindi questo significa che se a tutta la proprietà vincolante è rotto allora sappiamo che il problema del log discreto è facilmente risolvibile anche nel gruppo che è contrario al presupposto che il problema del log discreto sia difficile nel mio gruppo. Così che ti dimostra proprietà vincolante. (Riferimento Slide Time: 25 :51) Così ora cerchiamo di provare la proprietà nascosta. Ricordate quindi che l'obiettivo del nascondere la proprietà è che se il mittente è onesto e se il destinatario è malintenzionato poi semplicemente esaminando l'impegno C α β non può capire se sta vedendo un impegno di m0 o se sta vedendo un impegno di m1. Ovvero, se vediamo l'esperimento nascosto giocato rispetto allo schema di impegno di Pedersen lo schema di impegno allora ecco come sembrerebbe il nascondino: l'avversario potrebbe presentare una coppia di messaggi dicono (α 0, α 1). Lo sfidante avrebbe scelto casualmente uno qualsiasi di quei due messaggi per aver commesso e per impegnarlo picchi una casualità uniforme β e compatte Pedersen e impegno del messaggio α β, α b. E l'obiettivo dell'avversario è scoprire se si sta vedendo un impegno di α 0 o se sta vedendo un impegno di α 1. Quindi quello che possiamo dimostrare ora è che questo schema di impegno di Pedersen soddisfa la proprietà nasale anche contro un avversario computazionalmente sconfinato. E questo deriva dal fatto che questa funzione di impegno di Pedersen è esattamente la stessa della funzione di compressione HDL e ciò che significa è che l'impegno che l'avversario sta vedendo ha esattamente q numero di rappresentazioni distinte relative ad g e h e ognuna di queste risentizioni sono ugualmente probabili. Questo significa per ogni candidato α b se si tratterebbe di α 0, α 1, α 2 o qualsiasi α dallo spazio dei messaggi, esiste una casualità unica che dice β b tale che gli impegni che l'avversario sta vedendo potrebbe essere l'impegno del messaggio α b sotto quella casualità β. Ma la casualità effettiva che viene utilizzata dal mittente o che viene effettivamente prelevata dallo sfidante nell'esperimento nascosto viene scelta casualmente dal set Zq che significa che la probabilità che α 0 sia impegnata in questo impegno C sub α b, β e la probabilità che l'impegno che l'avversario stia vedendo potrebbe essere l'impegno del messaggio α 1 è esattamente lo stesso con probabilità 1/q. L'impegno che l'avversario sta vedendo potrebbe essere l'impegno di α 0 e con la stessa probabilità potrebbe essere l'impegno di α 1. E questo vale anche se il mio avversario è computazionalmente sconfinato che dimostra la proprietà nascosta. (Riferimento Slide Time: 28:23) Quindi vorrei concludere questa lezione con un'altra interessante caratteristica di questo schema di impegno di Pedersen che chiamiamo come proprietà homomorphism. Quindi sto conservando la fase di impegno e di apertura della fase di impegno di impegno Pedersen. E questo schema di impegno di Pedersen è linearmente omomorfo. Cosa intendo esattamente per questo, immaginate di ricevere un impegno di qualche α sconosciuto rispetto a una casualità sconosciuta β 1. Quindi conosci solo l'impegno ma non sai qual è esattamente il valore che si impegna e qual è la corrispondente casualità? E allo stesso modo, immaginate di ricevere un impegno di un altro sconosciuto α 2 rispetto a una casualità sconosciuta β 2 e dite di conoscere la costante pubblica c1 e c2 appartenente al set Zq.Ora la funzione di impegno di Pedersen è definita, se prendiamo l'impegno di α 1 poi si scopre che fondamentalmente finisce per ottenere un valore che può essere trattato come l'impegno del valore c1 volte α 1 sotto la casualità c1 volte β 1. Allo stesso modo se si prende il secondo impegno cioè l'impegno dello sconosciuto α 2 e lo solleva al noto c2, in sostanza finiamo per ottenere il valore di impegno di Pedersen che può essere trattato come un impegno di Pederson del valore c2 volte α 2 rispetto alla casualità c2 volte β 2. Sottolineo qui che state semplicemente eseguendo operazioni sull'impegno. Eseguendo quelle operazioni sull'impegno, si sta ottenendo qualcosa che può essere trattato come impegno di qualche altro valore. E ora se prendo in pratica questi due impegni calcolati, finiamo per ottenere un valore che può essere trattato come un impegno Pedersen del valore c1 volte α 1 + c2 volte α 2 rispetto alla casualità c1 volte α 1 + c2 volte β 2. Cosa significa che qualsiasi funzione lineare dei valori commessi può essere computata localmente semplicemente eseguendo alcune operazioni sugli impegni. Il che significa anche se non si sa cosa sia esattamente α 1, cosa esattamente α 2. Se qualcuno ha commesso α 1 e ti ha dato il sigillato α 1 e un α 2 sigillato in forma di impegno, e se vuoi eseguire un impegno sigillato di qualche funzione lineare di α 1 e α 2 ovvero una funzione del formato c1 volte α 1 + c2 volte α 2where i combinatori lineari della funzione lineare ovvero c1 e c2 sono noti a te. Poi anche senza conoscere α 1 e α 2 e una casualità β 1, β 2 si potrebbero eseguire operazioni sull'impegno stesso che finirà per darvi l'impegno di Pedersen di una qualche funzione lineare dei valori sottostanti sconosciuti ed è ciò che intendiamo per la proprietà lineare omomorfica. Così, si scopre che questa proprietà lineare omofoba dello schema di impegno Pedersen può essere sfruttata in primitivi crittografici avanzati come il calcolo sicuro multi - party. Così questo mi porta alla fine di questa lezione. Tanto per riepilogare, in questa lezione abbiamo visto le applicazioni dell'assunzione discreta di log ovvero abbiamo visto una instantificazione della funzione di compressione a lunghezza fissa e abbiamo visto un instanziamento di regime di impegno nello schema di simpegno di Pedersen e una sicurezza di entrambi questi primitivi sono nel modello standard e nel loro