Loading
Study Reminders
Support
Text Version

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 Lezione - 44 El Gamal Public Key Encryption Schema (Riferimento Slide Time: 00.33) Ciao a tutti. Benvenuti a questa lezione. Giusto per ricapitolarsi, nell'ultima lezione abbiamo visto la sintassi dello schema di crittografia a chiave pubblica. Così la roadmap per questa lezione è la seguente. In questa lezione vedremo un candidato schema di crittografia a chiave pubblica, ovvero il sistema di crittografia - chiave di El Gamal - key e dimostreremo formalmente la sua sicurezza CPA e termineremo la lezione con alcune delle problematiche di implementazione, che affrontiamo mentre implementiamo in pratica lo schema di crittografia El Gamal. (Riferimento Slide Time: 00 :56) Quindi cerchiamo di capire l'intuizione dello schema di crittografia di El Gamal. Quindi per questo, richiamate il protocollo di scambio chiave Diffie – Hellman. E per semplicità, supponiamo di considerare un gruppo ciclico moltiplicativo. Quindi i parametri pubblici sono la descrizione di un gruppo ciclico, un generatore e le dimensioni del gruppo, ovvero. E nel protocollo di scambio chiave Diffie – Hellman, diciamo Sita e Ram, vogliono accordarsi su una chiave, ognuno di loro raccolga il proprio contributo per la chiave complessiva. Così Sita picchia il suo contributo, e manda a Ram. E indipendentemente, Ram picchia il suo contributo e manda. E la chiave complessiva concordata tra mittente e destinatario è. E avevamo formalmente dimostrato la sicurezza del protocollo di scambio delle chiavi di Diffie – Hellman. Quindi ora, consideriamo il seguente processo di codifica. Così mittente e destinatario esegue per la prima volta un'istanza del protocollo di scambio chiave Diffie – Hellman per ottenere un tasto condiviso, denotato da, che è un elemento di gruppo. E sappiamo che se l'assunzione di DDH detiene nel gruppo sottostante, questo significa che se il problema del DDH è difficile da risolvere nel gruppo sottostante, allora la chiave concordata è indistinguibile da qualsiasi elemento casuale del gruppo. Ora immaginate, Ram ha un messaggio, diciamo testo semplice, che è un elemento di gruppo, che vuole criptare e mandarlo a Sita. Quindi quello che Ram può fare è, dal punto di vista di Ram, Ram sa che percorrendo il protocollo di scambio Diffie – Hellman ha anche la stessa chiave E Ram sa anche che se c'è un eavesdropper, che ha eavesato la comunicazione tra Sita e Ram, allora dal punto di vista di quell' avversario, la chiave, disponibile con Ram, è una sorta di indistinguibile da qualsiasi elemento casuale del gruppo. Quindi ciò che Ram può fare è, per criptare il testo della pianura, può usare la chiave per mascherare il suo compito di pianura e dato che stiamo eseguendo operazioni nel gruppo, per mascherare il testo di pianura, ciò che Ram può fare è, può eseguire l'operazione di gruppo sul messaggio e la chiave e il risultato è denotato da, che viene inviato anche con il messaggio, che Ram avrebbe inviato come parte del protocollo di scambio Diffie – Hellman. Ora una volta Sita riceve i messaggi di Ram, ora sta ricevendo due elementi dal gruppo. Il primo elemento è il contributo di Ram pu s come parte del protocollo di scambio di chiavi Diffie – Hellman, che Sita utilizza per generare la chiave come per i passi del protocollo di scambio delle chiavi Diffie – Hellman. Come una volta che ha ricevuto la chiave, per decodificare il testo di cifratura, quello che Sita deve fare è, deve solo annullare l'effetto della chiave o deve smaschettare la chiave. E per smaschere la chiave, quello che può fare è, può solo eseguire l'operazione di gruppo sul testo di cifratura e l'inverso moltiplicativo dell'elemento. Così, dato che l'elemento è noto a Sita e conosce la descrizione del gruppo, può calcolare l'inno moltiplicativo in tempo polinomiale, che io dengo di − 1. E se esegue l'operazione di gruppo sul testo di cifratura e − 1, l'effetto dei cancelli. E Sita finisce per ottenere il testo della pianura. Ora, affermo qui che il testo di cifratura, che è il risultato dell'operazione di gruppo sul testo di pianura e la chiave, sarà indipendente dal sottostante testo di pianura. Lo dimostrerò molto presto, ma per il momento ipotizza che questa affermazione sia vera. Se effettivamente questa affermazione è vera, allora questo intero protocollo, questo intero processo di crittografia e di decodifica sembra effettivamente uno schema di crittografia dei candidati. Perché se la distribuzione del testo di cifratura è indipendente dalla chiave, poi anche dopo aver visto il testo di cifratura, l'avversario non sarà in grado di capire cosa esattamente è crittografato, sia che si tratti di una crittografia di 0, 1, 2, non può capirlo. Ecco quindi l'intuizione complessiva dello schema di crittografia El Gamal. (Riferimento Slide Time: 05 :09) Così ho scritto il blueprint dello schema di crittografia che avevo discusso nell'ultima slide. Ora la domanda è che come possiamo visualizzare l'intero processo che abbiamo discusso appena ora come un'istanziazione dello schema di crittografia a chiave pubblica? Poiché ricordati come per la sintassi dello schema di crittografia a chiave pubblica, dobbiamo avere un algoritmo di generazione chiave, che avrebbe prodotto una coppia di chiavi pubbliche, segrete, dovremmo avere un algoritmo di crittografia e dovremmo avere un algoritmo di decodifica. Quindi pittoricamente sappiamo che ora abbiamo un blueprint di un processo di crittografia, ma ora dobbiamo mettere tutto nella sintassi del processo di crittografia a chiave pubblica. E questo processo di visualizzazione del suddetto processo di codifica come istanza di schema di crittografia a chiave pubblica è stato identificato da Taher El Gamal. Ed è per questo che questo processo di crittografia che andiamo a discutere ora è chiamato come schema di crittografia El Gamal. Quindi vi potreste chiedere come esattamente sia diverso da questo protocollo di scambio chiavi Diffie – Hellman? Ebbene, non stiamo facendo nulla al di là di Diffie – Hellman key exchange protocol. Così questa parte della comunicazione, che ho evidenziato è esattamente Diffie – Hellman key exchange protocol. Ma in cima a questo stiamo facendo qualche ulteriore comunicazione dal lato del mittente del mittente, che permette al destinatario di decodificare il testo di cifratura e recuperare il testo di pianura. Quindi quello che faremo è, l'intero processo di codifica che abbiamo discusso fino ad ora visivamente, possiamo immaginarlo come un'istanza di schema di crittografia a chiave pubblica come segue. Possiamo quindi immaginare che il messaggio del destinatario sia arrivato qui, ovvero il messaggio di Sita Sita come parte del protocollo di scambio Diffie – Hellman è la sua chiave pubblica.E possiamo visualizzarlo come se, questo è il suo contributo per il protocollo chiave Diffie – Hellman con ogni potenziale mittente, una volta per tutti. Questo significa che l'algoritmo chiave - generayion che Sita può correre qui è il seguente. Come parte di chiave segreta, può scegliere casualmente un indice nella gamma 0 a e può rendere la sua chiave pubblica. E sarà garantito che si tratti di una copia autenticata. Questo significa, anzi questo è generato da così chiamato Sita. Come esattamente è garantito, vedremo o risolveremo quel problema più avanti. Ma per il momento ipotizza che Sita abbia generato una chiave segreta come quella e ha calcolato la chiave pubblica per essere e renderla disponibile in ambito pubblico. Poi, possiamo immaginare come se questo fosse il suo contributo o la sua parte del messaggio per il protocollo chiave Diffie – Hellman con ogni possibile Ram, che vorrebbe fare una comunicazione sicura con Sita. Ora, supponiamo di avere un così chiamato Ram o un mittente che vuole criptare un testo semplice, diciamo, usando la chiave pubblica. Quindi quello che Ram sta per fare è, Ram andrà a scegliere un casuale nella gamma 0 a e ora sta per calcolare due elementi di gruppo. Il primo elemento di gruppo è 1, che non è altro che. E un secondo elemento di gruppo 2 è sostanzialmente l'operazione di gruppo eseguita sul testo di pianura e la chiave, dove si trova la chiave, che si ottiene sollevando la chiave pubblica dell'indice. Così i due messaggi o i due elementi che Ram sta inviando, possono essere visiti come segue. Il primo messaggio, si può interpretare come se si tratti di Ram dei contributi o del mittente del mittente del contributo per il protocollo di scambio Diffie – Hellman, perché se effettivamente Ram avrebbe partecipato ad un'istanza del protocollo di scambio Diffie – Hellman, allora 1 è il messaggio, che Ram avrebbe inviato a Sita in risposta al messaggio, che Sita ha già inviato ed è andato offline. Il secondo messaggio 2 o il secondo elemento di gruppo 2, potete immaginare come se stesse mascherando il testo di pianura con la chiave Resultant Diffie – Hellman, che Sita e Ram avrebbero accettato di utilizzare e come la trascrizione del protocollo. Quindi ora se immaginate questo processo di crittografia analizzando i messaggi di Sita e Ram come questo, allora si inserisce automaticamente nel quadro del nostro processo di crittografia a chiave pubblica. Per fare la decodifica, quello che Sita deve fare è, dal primo elemento di gruppo, che Ram ha inviato, utilizzando quello e la chiave pubblica che Sita ha inviato già al così chiamato Ram, Sita può eseguire i suoi passi del protocollo di scambio Diffie – Hellman e concordare o conservare la stessa chiave, che Ram ha usato per mascherare il messaggio. E una volta recupera la chiave, per decodificare il testo di cifratura, ci vuole la seconda componente del testo di cifratura, ovvero 2 e esegue l'operazione di gruppo su 2 e l'inverso moltiplicativo di − 1 per recuperare il testo di pianura. La mia affermazione qui è che in questo intero processo, la distribuzione della seconda componente del testo integrale del cifrario, ovvero il 2 è indipendente dal testo di pianura sottostante. Così dimostreremo presto questo fatto, ma ora se immaginate tutta questa cosa, come il modo in cui ho detto, ora potete vedere che abbiamo ora un'istanza di uno schema di crittografia a chiave pubblica. (Riferimento Slide Time: 10.31) Così ora mettiamo i dettagli formali esatti del processo di crittografia El Gamal. Così lo spazio in chiaro e lo spazio pubblico - chiave saranno entrambi il gruppo. E lo spazio segreto - chiave sta per essere Z, ovvero sarà il set {0, …. E il testo di cifratura complessivo consisterà in due elementi di gruppo. Così sarà un paio di elementi del gruppo sottostante. L'algoritmo di generazione di chiavi mette in funzione una chiave pubblica e una chiave segreta come segue. La chiave segreta è casuale nella gamma 0 a e una chiave pubblica. Così che si possa immaginare come se Sita stia facendo la sua parte del protocollo di scambio Diffie – Hellman con ogni potenziale ricevitore una volta per tutti. L'algoritmo di crittografia, che Ram o qualsiasi mittente segua per criptare un testo di pianura è il seguente. Il mittente sceglierà un casuale nella gamma da 0 a 1. E compatto, che sarà la prima componente del testo di cifratura. E la crittografia effettiva del messaggio è l'operazione di gruppo eseguita sul testo di pianura e la chiave pubblica sollevata al potere. Quindi pittoricamente si può immaginare che il primo componente del testo di cifratura non sia altro che il contributo di mittente del mittente per la chiave Diffie – Hellman, che sender e ricevente saranno d'accordo. E la seconda componente del testo di cifratura è la mascheratura del testo di pianura con la chiave Diffie – Hellman. Ora l'operazione di decodifica è, si riceve un testo di cifratura composto da due elementi di gruppo. Così si calcola per la prima volta un tasto comune Diffie – Hellman, che va stabilito tra il mittente e il destinatario, innalzando l'elemento di gruppo 1 alla chiave secreta, in modo da ottenere anche, trovare un inno moltiplicativo. E poi eseguire l'operazione di gruppo con il secondo componente del testo di cifratura, quindi quell' effetto di vaniglia e si finisce con il testo di pianura. Ecco quindi la sintassi formale dello schema di crittografia El Gamal. Ora vogliamo dimostrare formalmente che questo schema di crittografia El Gamal è effettivamente COA sicuro. Come abbiamo discusso nell'ultima lezione, nel mondo delle chiavi pubbliche, la sicurezza COA, la sicurezza del singolo messaggio CPA e la sicurezza multi messaggio CPA sono tutte equivalenti. Quindi basti provare la sicurezza COA di questo processo di codifica. Così come io premia le ultime slide, la distribuzione del componente di testo di cifratura 2, ovvero l'operazione di gruppo su con il tasto Diffie – Hellman, sarà indipendente dal sottostante testo di pianura. Il che significa, dal punto di vista di un avversario computazionalmente limitato, se vede 2, quindi dal suo punto di vista, il 2 potrebbe essere il risultato dell'applicazione dell'operazione di gruppo su qualsiasi e qualsiasi. E se questo è il caso, questo significa, se questa affermazione è effettivamente vera, allora implica automaticamente la sicurezza COA. Intuitivamente questo è perché per ogni istanza dell'algoritmo di crittografia in questo schema di crittografia El Gamal, il mittente sceglierà una casualità. Non è il caso che sceglierà lo stesso ogni volta. E ifis viene scelto in modo indipendente per ogni istanza della crittografia, poi significa automaticamente che il tasto Diffie – Hellman, utilizzato per mascherare il messaggio, sarà anche indipendente per ogni istanza. Perché la chiave generale Diffie – Hellman è. Quindi anche se il thecomponent nella chiave Resultant Diffie – Hellman, che mittente e destinatario stanno usando per fare la crittografia e la decodifica è lo stesso, è il che sta scatenando la casualità qui e da allora viene scelto in modo indipendente, per ogni istanza della crittografia, la chiave generale Diffie – Hellman, utilizzata in ogni istanza è indipendente. E ora ipotizziamo che questa affermazione sia vera, questo significa che la distribuzione di 2 è indipendente dal testo di pianura sottostante, otteniamo la sicurezza COA. (Riferimento Slide Time: 14.34) Così ora formalizziamo questa intuizione da una prova rigorosa. E prima di entrare nella prova, facciamo un caldo qui e consideriamo una variazione dello schema di crittografia di El Gamal. Principalmente andremo a considerare una variante perfettamente sicura dello schema di crittografia El Gamal. Sottolineo qui che non è il modo di implementare lo schema di crittografia El Gamal e non è il modo in cui utilizziamo realmente lo schema di crittografia El Gamal. Questa variazione dello schema di crittografia El Gamal nell'impostazione delle chiavi private è solo per rendere la prova più semplice. Quindi lo schema di crittografia El Gamal modificato nell'impostazione delle chiavi private, sto denotando come  . Ha il suo algoritmo di generazione chiavi, algoritmo di crittografia e algoritmo di decodifica. I parametri pubblici sono il gruppo ciclico, la descrizione di gruppo e un elemento di gruppo uniformemente casuale, dove non è noto. Quindi possiamo immaginare come se si tratti di qualche tipo di set up, che è stato fatto da un terzo partito attendibile e non è noto a nessuno. Ora visto che si tratta di un processo di codifica della chiave simmetrica, l'algoritmo di generazione chiavi in uscita sta andando a produrre una chiave uniformemente casuale e la chiave è un elemento del gruppo. Per criptare un messaggio in questa variante di processo di crittografia El Gamal, compendiamo due elementi di gruppo, ovvero 1 e 2. Dove 1 sono alcuni, dove viene scelto casualmente dal set Z. E la componente di testo di cifratura 2 è sostanzialmente la mascheratura del messaggio con la chiave. Dal momento che si tratta di uno schema di codifica a chiave simmetrica, utilizzeremo la stessa chiave anche per la decodifica. E per recuperare il testo pianeggiante, praticamente prendiamo il secondo componente del testo di cifratura ed eseguiamo l'operazione di gruppo rispetto all'inverso moltiplicativo della chiave. Notate che in questa variazione del processo di crittografia El Gamal, la prima componente del testo di cifratura, ovvero il 1 e il noto pubblicamente, non sono affatto utilizzate per il processo di codifica e per il processo di decodifica. Ma li sto solo conservando, per fare in modo che la sintassi complessiva del testo di cifratura che stiamo ottenendo qui assomiglia allo stesso che otterremo nella vera e propria istanziazione dello schema di crittografia El Gamal. Ora affermo qui che la variante chiave privata del processo di crittografia El Gamal è perfettamente sicura se il mio testo di pianura sottostante è il gruppo. E questo perché questa variante chiave privata dello schema di crittografia El Gamal è esattamente simile allo schema di pad one-time over the group. L'unica differenza è che nello schema di pad one-time, eseguiamo lo XOR della chiave con il testo della pianura. Ma visto che siamo nell'impostazione di gruppo, stiamo semplicemente sostituendo quella operazione XOR da parte dell'operazione di gruppo. Più formalmente, ipotizziamo di avere un testo di cifratura arbitrario, diciamo (1, 2) e diciamo che consideriamo un paio di testo arbitrario arbitrario, ovvero 0 e 1, che sono elementi di gruppo, perché qui il mio spazio di testo pianeggiante è il gruppo sottostante. Dimostrerò che effettivamente questo processo di codifica soddisfa la definizione di perfetta segretezza. Ovvero considerare la probabilità che questo testo arbitrario di cifratura (1, 2) sia una crittografia del testo di pianura 0. E allo stesso modo, considerare la probabilità che questo testo arbitrario di cifratura (1, 2) sia una crittografia di 1. Si scopre che questo testo arbitrario di cifratura (1, 2) è una crittografia del 0, solo se l'algoritmo di generazione chiave avrebbe prodotto una chiave, che è il risultato dell'operazione di gruppo eseguita su 2 e l'inverso moltiplicativo del 0. Ma dato che l'algoritmo di generazione chiavi in mano mette in funzione elementi uniformemente casuali dal gruppo come chiave, si scopre che l'algoritmo di generazione chiavi in realtà supera una chiave, che è uguale a 2 operazione di gruppo 0 − 1 è il 1 rispetto alla dimensione del gruppo. Ora percorrendo esattamente lo stesso argomento, possiamo affermare che la probabilità che il testo di pianura 1 sia criptato nel testo di cifratura (1, 2) è esattamente lo stesso, che il mio algoritmo di generazione chiave outmette una chiave, uguale all'operazione di gruppo eseguita su 2 e 1 − 1.And la probabilità che la mia chiave sia questa, è il 1 sulle dimensioni del gruppo. Il che significa, per qualsiasi avversario, anche se computazionalmente sconfinato, se partecipa a sperimentazioni indistinguibili perfettamente sicure nell'impostazione della chiave simmetrica o nell'esperimento COA, allora la probabilità che possa distinguere se sta vedendo una crittografia dell'elemento di gruppo 0 o se sta vedendo una codifica dell'elemento di gruppo 1, è esattamente la metà. Il che significa, non si può distinguere a parte; con pari probabilità si tratta di una crittografia di 0 oltre che di crittografia di 1. Ed è per questo che questa variante modificata o simmetrica del processo di codifica El Gamal è perfettamente sicura. (Riferimento Slide Time: 19.38) Ora passiamo alla sicurezza COA dell'effettivo schema di crittografia El Gamal che abbiamo progettato nell'impostazione della chiave pubblica. Quindi prima di andare oltre, ricordiamo ancora una volta quello che abbiamo dimostrato poco fa. Abbiamo quindi considerato una variante dello schema di crittografia El Gamal nell'impostazione della chiave simmetrica ed ecco l'algoritmo di crittografia. L'algoritmo di crittografia produce due elementi di gruppo (1, 2), dove 1 è qualche casuale e 2 è la mascheratura del messaggio. E a parte questo, l'avversario ha anche un'informazione pubblica, ovvero, dove non si conosce l'avversario. Quindi se considero la vista dell'avversario, la vista degli avversari è sostanzialmente costituita da tre distribuzioni di probabilità, ovvero ha un elemento, dove viene scelto casualmente da Z.It conosce il valore di, dove viene scelto casualmente da Z. E conosce la mascheratura del messaggio con il testo della pianura, dove la chiave viene scelta casualmente dal gruppo sottostante. E abbiamo dimostrato che questo processo di codifica è perfettamente sicuro. D'altra parte, l'effettivo schema di crittografia a chiave pubblica El Gamal, che abbiamo progettato, presente anche il testo di cifratura è costituito da due elementi di gruppo. E secondo componente del testo di cifratura è la mascheratura del messaggio con la chiave Diffie – Hellman, ovvero. Quindi se considero la vista degli avversari in questa vera e propria istanziazione o l'effettiva istanziazione dello schema di crittografia El Gamal nell'impostazione della chiave pubblica, allora la sua vista è la seguente. Conosce il valore di, dove è sconosciuto e uniformemente casuale dal set Z. Conosce il valore di, dove è uniformemente casuale dal set Z. E conosce la mascheratura del messaggio con la chiave Diffie – Hellman, dove il tasto Diffie – Hellman non è altro che, e appartiene al gruppo sottostante. Ora se vedete qui da vicino, cosa è esattamente diverso qui, se considero qui le opinioni dei due avversari? La distribuzione di in entrambi i mondi o per gli avversari sono perfettamente uguali. Sono esattamente indistinguibili. Qui anche alpha è casuale, qui anche alpha è casuale, non noto all'avversario e l'avversario conosce il valore. Allo stesso modo, la distribuzione di in entrambi i mondi è esattamente identica. Ciò che qui è diverso, è la natura del 2 che l'avversario vede nella variante chiave simmetrica dello schema El Gamal e la distribuzione del 2, che avversario vede nell'effettivo schema di crittografia El Gamal. Nel mondo chiave simmetrico, la mascheratura è con un elemento di gruppo uniformemente casuale, mentre nella chiave pubblica El Gamal, il mascheramento del testo di pianura è con la chiave pseudo - casuale, che è un tasto Diffie – Hellman. E se presumo che l'assunzione di DDH sia titolare nel mio gruppo sottostante, allora sappiamo che come per l'assunzione di Diffie – Hellman, Diffie – Hellman triplet e una tripletta non Diffie – Hellman, sono computazionalmente indistinguibili dal punto di vista di qualsiasi avversario delimitato computazionalmente. Questo significa, se il mio è uniformemente casuale, questo significa se sono in questo caso, allora in quel caso sono alcuni, dove è totalmente casuale, non legato e. Mentre se considero il testo di cifratura 2 come per la chiave pubblica Diffie – Hellman pulic - key El Gamal encryption schema, allora la mia chiave non è altro che mai. Quindi se il mio avversario non può distinguere tra una tripletta DH e una tripletta non DH, allora posso dire che la distribuzione del componente di testo di cifratura 2, che gli avversari vede in entrambi i mondi sono anche computazionalmente indistinguibili e che dimostreranno automaticamente che il nostro processo di crittografia El Gamal è COA sicuro. (Rinvio Slide Time: 23.45) Così è la dichiarazione formale che dimostreremo ora. Proveremo che se l'assunzione di DDH detiene nel mio gruppo sottostante, allora il processo di crittografia El Gamal è effettivamente COA garantito. E stabiliamo formalmente questo fatto dando una riduzione. Quindi supponiamo che tu abbia un avversario in prima persona che può attaccare il tuo schema di crittografia a chiave pubblica El Gamal. Usando quell' attacco, stiamo per progettare un solutore DDH, un solutore DDH a tempo di polpa che sa distinguere un tripletto Diffie – Hellman da una tripletta non Diffie – Hellman. Così partecipa ad una ricorrenza dell'esperimento DDH. L'esperimento DDH prepara una sfida per il solutore DDH dandogli (, dove e sono elementi di gruppo casuali. E terzo componente della tripletta è, oppure è un elemento uniformemente casuale, a seconda che lo sfidante abbia o. E il compito del solutore DDH è quello di scoprire se si tratta di una tripletta DH o di una tripletta non DH. Per risolvere questo, il solutore DDH richiama il nostro aggressore, che può attaccare lo schema di crittografia El Gamal e partecipa ad un'istanza del gioco COA e imposta la chiave pubblica. Ora come per le regole del gioco COA, l'aggressore COA presenterà un paio di testi di pianura di sfida dal gruppo sottostante e questo solutore DDH sceglierà casualmente uno di quei due messaggi e prepara il testo della sfida cifrata come segue. Il secondo componente della tripletta, che viene dato come la sfida a questo solutore DDH, è impostato per essere il primo componente del testo di cifratura e la crittografia effettiva del messaggio è impostata come, mascherata con il terzo componente della tripletta, che viene lanciata come una sfida al solutore DDH. Quindi ora prima di procedere oltre, cerchiamo di capire cosa sta accadendo in questa riduzione complessiva. Se vedete qui che se questa tripletta è una tripletta non DDH, questo significa in questo caso in alcuni, dove non è legato e, poi la distribuzione del testo di cifratura (1, 2), che viene dato a questo aggressore contro lo schema El Gamal, ha esattamente la stessa distribuzione se questo aggressore avrebbe partecipato al gioco COA contro la variante simmetrica dello schema di crittografia El Gamal. Perché è così che questo testo di sfida si direbbe per l'aggressore in quell' esperimento. Mentre, se la tripletta che viene data a questo solutore DDH è una tripletta DH, allora la distribuzione di (1, 2) che questo avversario sta vedendo è esattamente la stessa distribuzione di se questo avversario avrebbe visto partecipando ad un'istanza di gioco COA contro il processo di crittografia El Gamal. Così torneremo a quel fatto di nuovo. Così ora questo avversario deve individuare se ha visto una crittografia di 0 o 1. Quindi sottopone la sua produzione. E la risposta del solutore DDH è quella, dice che si sta vedendo una tripletta DH, se e solo se l'avversario EG ha individuato correttamente se si tratta di 0 o se si tratta di 1, cifrato nel testo della sfida cifrata (1, 2). Quindi ora analizziamo il vantaggio, e cioè con quanta probabilità questo DDH solver risolve un'istanza casuale del problema del DDH. Quindi affermo che se, questo significa che questa tripletta è una tripletta non DDH. Poi la probabilità che il mio DDH solutti outmetta in modo incorretto, cioè di outputs ′ = 1, è esattamente lo stesso con cui questo aggressore COA avrebbe vinto il gioco COA contro la variante simmetrica dello schema di crittografia El Gamal. E abbiamo già dimostrato che si tratta di 1 ⁄ 2. Questo perché se siamo nell'ambientazione dove, allora come ho già dimostrato che il testo di cifratura, che il nostro avversario EG sta vedendo, ha esattamente la stessa distribuzione che avrebbe visto partecipando ad un'istanza di gioco COA contro lo schema di crittografia El Gamal modificato. D'altra parte, affermo che se il mio caso è, allora la probabilità che il mio DDH risolve ′ = 1 è esattamente lo stesso che il mio avversario EG vince il gioco COA contro lo schema di crittografia El Gamal. E questo deriva dal fatto che se siamo nel caso in cui, allora, questo significa che la tripletta che viene data è una tripletta DDH o Diffie – Hellman triplet, il che significa che la distribuzione del testo di cifratura, qualunque sia l'avversario visto è esattamente la stessa distribuzione del testo di cifratura che questo avversario avrebbe visto partecipando ad un'istanza di gioco COA contro lo schema di crittografia El Gamal. Così in sintesi, quello che stiamo concluendo ora è che, se si vede il vantaggio distintivo del nostro solutore DDH, allora è esattamente 1 ⁄ 2 meno la probabilità con cui il nostro avversario avrebbe potuto vincere il gioco COA contro lo schema di crittografia El Gamal. Ma dato che presumo che l'assunzione di DDH sia titolare nel gruppo sottostante, allora so che il vantaggio distintivo di qualsiasi solutore DDH è delimitato da qualche probabilità trascurabile. Quindi non conosco il testo di pianura, ma conosco la chiave pubblica e ho una crittografia El Gamal di quel testo di pianura sconosciuto, che consiste in due elementi di gruppo, che sto denotando da e. E come per la sintassi del processo di crittografia El Gamal, avrà questa proprietà, quindi 1 è la casualità sottostante utilizzata dal mittente. E allo stesso modo, immaginate di avere una crittografia El Gamal o un testo di cifratura di un messaggio sconosciuto, di nuovo composto da due elementi di gruppo. Ora supponga di moltiplicare il primo componente di entrambi i testi di cifratura. E in modo indipendente moltiplico la seconda componente di entrambi i testi di cifratura. E questo produrrà due elementi di gruppo, che avranno matematicamente la seguente proprietà. Il primo elemento di gruppo non sarà altro che la casualità usata nel primo testo di cifratura più la casualità utilizzata nel secondo testo di cifratura. E il secondo componente sarà il prodotto dei due testi di pianura, moltiplicato per il power public-key times la sommità delle due casualità. E se si guarda da vicino, questo non è altro che si può immaginare come se si tratti di un testo di cifratura El Gamal per il testo della pianura, sotto la casualità 1 + 2. Ed è per questo che dico che il mio processo di crittografia El Gamal è multiplicativo omomorfo. Il motivo è molteplice omomorfo è che se moltiplicato due testi di cifratura El Gamal, poi anche senza conoscere i testi di pianura sottostante (sottolineo di non conoscere i testi di pianura sottostante e la casualità sottostante 1 e 2, che vengono utilizzati singolarmente), finendo per ottenere un testo di cifratura El Gamal di un testo di pianura correlato, ovvero sotto qualche casualità sconosciuta, ovvero 1 + 2. Si tratta quindi di una proprietà molto interessante del processo di crittografia di El Gamal. E più avanti