Loading
Apuntes
Study Reminders
Support
Text Version

Encryption El Gamal

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

    +

Fundamentos de la Criptografía Dr. Ashish Choudhury Departamento de Informática Instituto Indio de Ciencia-Conferencia de Bangalore-44 El Gamal Public Key Encryption Scheme (Referir Slide Time: 00:33) Hola a todos. Bienvenidos a esta conferencia. Sólo para recapitular, en la última conferencia, hemos visto la sintaxis del esquema de cifrado de clave pública. Así que la hoja de ruta para esta conferencia es la siguiente. En esta conferencia, veremos un esquema de cifrado de clave pública candidato, a saber, el sistema criptográfico de clave pública de El Gamal y demostraremos formalmente su seguridad de CPA y terminaremos la conferencia con algunos de los problemas de implementación, que enfrentamos mientras se implementa el esquema de encriptación de El Gamal en la práctica. (Consultar tiempo de la diapositiva: 00 :56) Así que intentemos entender la intuición del esquema de encriptación de El Gamal. Así que para eso, recordemos el protocolo de intercambio de claves Diffie – Hellman. Y por simplicidad, asumir que estamos considerando un grupo cíclico multiplicativo. Por lo tanto, los parámetros públicos son la descripción de un grupo cíclico, un generador y el tamaño del grupo, que es. Y en el protocolo de intercambio de claves Diffie – Hellman, dicen Sita y Ram, quieren acordar una clave, cada uno de ellos recoge su propia contribución para la clave general. Así que Sita escoge su contribución, y ella envía a Ram. Y de forma independiente, Ram escoge su contribución y envía. Y la clave general que se acuerda entre el remitente y el receptor es. Y hemos probado formalmente la seguridad del protocolo de intercambio de claves Diffie – Hellman. Así que ahora, considere el siguiente proceso de cifrado. Por lo tanto, el remitente y el receptor primero ejecutan una instancia del protocolo de intercambio de claves Diffie – Hellman para obtener una clave compartida, indicada por, que es un elemento de grupo. Y sabemos que si la suposición DDH se mantiene en el grupo subyacente, eso significa que si el problema DDH es difícil de resolver en el grupo subyacente, entonces la clave acordada es indistinguible de cualquier elemento aleatorio del grupo. Ahora imagínate, Ram tiene un mensaje, dice texto plano, que es un elemento de grupo, que quiere cifrar y enviarlo a Sita. Así que lo que Ram puede hacer es, desde el punto de vista de Ram, Ram sabe que al ejecutar el protocolo de intercambio de claves Diffie – Hellman, Sita también va a tener la misma clave Y Ram también sabe que si hay un eavesdropper, que ha escuchas la comunicación entre Sita y Ram, entonces desde el punto de vista de ese adversario, la clave, que está disponible con Ram, es una especie de indistinguible de cualquier elemento aleatorio del grupo. Así que lo que Ram puede hacer es, para cifrar el texto plano, puede utilizar la clave para enmascarar su tarea llana y ya que estamos realizando operaciones en el grupo, para enmascarar el texto plano, lo que Ram puede hacer es, puede realizar la operación de grupo en el mensaje y la clave y el resultado es denotado por, que también se envía con el mensaje, que Ram habría enviado como parte del protocolo de intercambio de claves Diffie – Hellman. Ahora que Sita recibe los mensajes de Ram, ahora está recibiendo dos elementos del grupo. El primer elemento es la contribución de Ram ’ s como parte del protocolo de intercambio de claves Diffie – Hellman, que Sita utiliza para generar la clave según los pasos del protocolo de intercambio de claves Diffie – Hellman. Como una vez que ha recibido la clave, para descifrar el texto de cifrado, lo que Sita tiene que hacer es, ella tiene que simplemente cancelar el efecto de la clave o ella tiene que desenmascarar la clave. Y para desenmascarar la clave, lo que puede hacer es simplemente realizar la operación de grupo en el texto de cifrado y el inverso multiplicativo del elemento. Así que como el elemento es conocido por Sita y ella conoce la descripción del grupo, ella puede calcular la inversa multiplicativa en el tiempo polinómico, que denotan por − 1. Y si realiza la operación de grupo en el texto de cifrado y − 1, el efecto de la cancelación. Y Sita termina consiguiendo el texto plano. Ahora, reclamo aquí que el texto de cifrado, que es el resultado de la operación de grupo en el texto plano y la clave, va a ser independiente del texto plano subyacente. Lo demostraré muy pronto, pero por el momento asumo que esta afirmación es cierta. Si de hecho esta afirmación es cierta, entonces todo este protocolo, todo este proceso de cifrado y descifrado de hecho parece un esquema de cifrado de candidatos. Porque si la distribución del texto de cifrado es independiente de la clave, entonces incluso después de ver el texto de cifrado, el adversario será incapaz de averiguar qué es exactamente encriptado, si es un cifrado de 0, 1, 2, no se puede averiguar. Así que esa es la intuición general del esquema de encriptación de El Gamal. (Consulte la hora de la diapositiva: 05 :09) Así que he escrito el esquema del esquema de cifrado que había discutido en la última diapositiva. Ahora la pregunta es ¿cómo podemos visualizar todo el proceso que hemos discutido ahora como una instanciación del esquema de cifrado de claves públicas? Debido a que recuerda como por la sintaxis del esquema de cifrado de clave pública, necesitamos tener un algoritmo de generación de claves, que daría salida a un par de clave pública, secreto-clave, deberíamos tener un algoritmo de cifrado y deberíamos tener un algoritmo de descifrado. Tan pictorialmente, sabemos que ahora tenemos un plan de un proceso de cifrado, pero ahora tenemos que poner todo en la sintaxis del proceso de cifrado de clave pública. Y este proceso de visualización del proceso de cifrado anterior como una instancia de esquema de cifrado de clave pública fue identificado por Taher El Gamal. Y por eso este proceso de encriptación que vamos a discutir ahora se llama esquema de encriptación de El Gamal. Así que usted podría preguntarse que ¿cómo exactamente es diferente de este protocolo de intercambio de llaves de Diffie – Hellman? Bueno, no estamos haciendo nada aparte del protocolo de intercambio de claves Diffie – Hellman. Así que esta parte de la comunicación, que he destacado es exactamente Diffie – Hellman clave de intercambio protocolo. Pero encima de eso, estamos haciendo alguna comunicación adicional desde el lado del remitente, que permite al receptor descifrar el texto de cifrado y recuperar el texto plano. Así que lo que vamos a hacer es, todo el proceso de cifrado que hemos discutido hasta ahora visualmente, podemos imaginarlo como una instancia de esquema de cifrado de clave pública de la siguiente manera. Así que podemos imaginar que el mensaje del receptor, es decir, el mensaje de Sita ’ s como parte del protocolo de intercambio de claves Diffie – Hellman es su clave pública.Y podemos visualizar eso como si, esa es su contribución para el protocolo de intercambio de claves Diffie – Hellman con todo emisor potencial, una vez para todos. Eso significa que el algoritmo de generayión clave que Sita puede correr aquí es el siguiente. Como parte de la clave secreta, puede elegir al azar un índice en el rango de 0 a y ella puede hacer que su clave pública sea. Y se garantizará que sea una copia autenticada. Eso significa, de hecho, esto es generado por el llamado Sita. Cómo se asegura exactamente, vamos a ver o resolver ese problema más adelante. Pero por el momento asumir que Sita ha generado una clave secreta como esa y ha computado clave pública para estar y hacerlo disponible en el dominio público. Entonces, podemos imaginar como si esta fuera su contribución o su parte del mensaje para el protocolo de intercambio de claves Diffie – Hellman con cada posible Ram, a quien le gustaría hacer una comunicación segura con Sita. Ahora, supongamos que tenemos un llamado Ram o un remitente que quiere cifrar un texto sin formato, digamos, usando la clave pública. Así que lo que Ram va a hacer es, Ram va a escoger un aleatorio en el rango de 0 a y ahora va a computar ahora dos elementos de grupo. El primer elemento de grupo es 1, que no es otra cosa que. Y un segundo elemento de grupo 2 es básicamente la operación de grupo que se realiza en el texto plano y la clave, donde está la clave, que se obtiene al elevar la clave pública al índice. Así que los dos mensajes o los dos elementos que Ram está enviando, se pueden visualizar de la siguiente manera. El primer mensaje, puede interpretar como si fuera la contribución de Ram ’ s o la contribución del remitente para el protocolo de intercambio de claves Diffie – Hellman, porque si realmente Ram hubiera participado en una instancia del protocolo de intercambio de claves Diffie – Hellman, entonces 1 es el mensaje, que Ram habría enviado a Sita en respuesta al mensaje, que Sita ya ha enviado y se ha puesto fuera de línea. El segundo mensaje 2 o el segundo elemento de grupo 2, se puede imaginar como si fuera el enmascaramiento del texto plano con la clave resultante Diffie – Hellman, que Sita y Ram habrían acordado utilizando y como transcripción del protocolo. Así que ahora si imaginamos este proceso de cifrado analizando los mensajes de Sita y Ram como este, entonces automáticamente encaja en el marco de nuestro proceso de cifrado de clave pública. Para hacer el descifrado, lo que Sita tiene que hacer es, desde el primer elemento de grupo, que Ram ha enviado, utilizando eso y la clave pública que Sita ha enviado ya a la llamada Ram, Sita puede realizar sus pasos del protocolo de intercambio de claves Diffie – Hellman y ponerse de acuerdo o retener la misma clave, que Ram ha utilizado para enmascarar el mensaje. Y una vez que recupera la clave, para descifrar el texto de cifrado, toma el segundo componente del texto de cifrado, a saber, 2 y realiza la operación de grupo en 2 y el inverso multiplicativo de − 1 para recuperar el texto sin formato. Mi afirmación aquí es que en todo este proceso, la distribución del segundo componente del texto de cifrado general, a saber, 2 es independiente del texto plano subyacente. Así que pronto probaremos este hecho, pero ahora si nos imaginamos todo esto, como la forma en que he dicho, ahora se puede ver que ahora tenemos una instancia de un esquema de cifrado de clave pública. (Consultar Tiempo de Slide: 10:31) Así que ahora vamos a poner los detalles formales exactos del proceso de encriptación de El Gamal. Así que el espacio de texto plano y el espacio de clave pública van a ser ambos el grupo. Y el espacio secreto-clave va a ser Z, es decir, va a ser el conjunto {0, …,. Y el texto de cifrado general constará de dos elementos de grupo. Así que va a ser un par de elementos del grupo subyacente. El algoritmo de generación de claves genera una clave pública y una clave secreta como se indica a continuación. La clave secreta es un aleatorio en el rango 0 a y una clave pública. Para que puedas imaginar como si Sita estuviera haciendo su parte del protocolo de intercambio de claves Diffie – Hellman con cada receptor potencial una vez para todos. El algoritmo de cifrado, que Ram o cualquier remitente va a seguir para cifrar un texto sin formato es el siguiente. El remitente va a elegir un aleatorio en el rango de 0 a 1. Y calcular, que va a ser el primer componente del texto de cifrado. Y el cifrado real del mensaje es la operación de grupo realizada en el texto plano y la clave pública elevada a la potencia. Tan pictorialmente, se puede imaginar que el primer componente del texto de cifrado no es más que la contribución del remitente para la clave Diffie – Hellman, que el remitente y el receptor van a acordar. Y el segundo componente del texto de cifrado es el enmascaramiento del texto plano con la clave Diffie – Hellman. Ahora la operación de descifrado es, se recibe un texto de cifrado que consta de dos elementos de grupo. Así que primero computa una clave común Diffie – Hellman, que se va a establecer entre el emisor y el receptor, al elevar el elemento de grupo 1 a la clave secreta, para que también se obtenga, encontrar un inverso multiplicativo de la misma. A continuación, realice la operación de grupo con el segundo componente del texto de cifrado, de modo que se desvanezca el efecto y se termine con el texto sin formato. Así que esa es la sintaxis formal del esquema de encriptación de El Gamal. Ahora queremos demostrar formalmente que este esquema de cifrado de El Gamal es de hecho COA seguro. Como hemos discutido en la última conferencia, en el mundo de la clave pública, la seguridad de COA, la seguridad de CPA de un solo mensaje y la seguridad de la CPA de múltiples mensajes son equivalentes. Por lo tanto, basta con probar la seguridad COA de este proceso de cifrado. Así que como estoy reclamando sobre las últimas diapositivas, la distribución del componente de texto de cifrado 2, a saber, la operación de grupo con la clave Diffie – Hellman, va a ser independiente del texto plano subyacente. Eso significa, desde el punto de vista de un adversario computacionalmente acotado, si ve 2, entonces desde su punto de vista, 2 podría ser el resultado de aplicar la operación de grupo en cualquiera y en cualquiera. Y si ese es el caso, eso significa, si esta afirmación es realmente cierta, entonces automáticamente implica la seguridad de COA. Intuitivamente esto se debe a que por cada instancia del algoritmo de cifrado en este esquema de cifrado de El Gamal, el remitente va a escoger un aleatoriamente. No es el caso de que va a escoger el mismo cada vez. Y se selecciona ifis independientemente para cada instancia del cifrado, entonces automáticamente significa que la clave Diffie – Hellman, que se utiliza para enmascarar el mensaje también va a ser independiente para cada instancia. Porque la clave general de Diffie – Hellman es. Así que incluso si el valor en la clave resultante Diffie – Hellman, que el remitente y el receptor están utilizando para hacer el cifrado y descifrado es el mismo, es el que está provocando la aleatoriedad aquí y desde que se selecciona de forma independiente aquí, para cada instancia del cifrado, la clave general de Diffie – Hellman, que se utiliza en cada instancia es independiente. Y ahora suponiendo que esta afirmación es verdadera, que significa que la distribución de 2 es independiente del texto plano subyacente, obtenemos la seguridad COA. (Consultar Tiempo de Slide: 14:34) Así que ahora formalizemos esta intuición por una prueba rigurosa. Y antes de entrar en la prueba, hagamos un calentamiento aquí y consideremos una variación del esquema de encriptación de El Gamal. Principalmente vamos a considerar una variante perfectamente segura del esquema de cifrado de El Gamal. Hago hincapié aquí en que no es la forma en que vamos a implementar el esquema de cifrado de El Gamal y no es la forma en que realmente usamos el esquema de encriptación de El Gamal. Esta variación del esquema de cifrado de El Gamal en el ámbito de la clave privada es sólo para hacer la prueba más sencilla. Así que el esquema de cifrado de El Gamal modificado en el valor de la clave privada, estoy denotando como Π. Tiene su propio algoritmo de generación de claves, algoritmo de cifrado y algoritmo de descifrado. Los parámetros públicos son el grupo cíclico, la descripción de grupo y un elemento de grupo uniformemente aleatorio, donde no se conoce. Así que podemos imaginarnos como si fuera algún tipo de set up, que ha sido hecho por un tercero de confianza y no se le conoce a nadie. Ahora que se trata de un proceso de cifrado de claves simétricas, el algoritmo de generación de claves va a generar una clave aleatoria uniforme y la clave es un elemento del grupo. Para cifrar un mensaje en esta variante del proceso de cifrado de El Gamal, se computan dos elementos de grupo, a saber, 1 y 2. Donde 1 es algunos, donde se elige al azar del conjunto Z. Y el componente de texto de cifrado 2 es básicamente el enmascaramiento del mensaje con la clave. Puesto que es un esquema de cifrado de claves simétricas, vamos a utilizar la misma clave para el descifrado también. Y para recuperar el texto plano, básicamente tomamos el segundo componente del texto de cifrado y realizamos la operación de grupo con respecto a la inversa multiplicativa de la clave. Observe que en esta variación del proceso de cifrado de El Gamal, el primer componente del texto de cifrado, a saber, 1 y el conocido públicamente, no se utilizan en absoluto para el proceso de cifrado y para el proceso de descifrado. Pero sólo estoy reteniéndolos, para asegurar que la sintaxis general del texto de cifrado que estamos obteniendo aquí parezca lo mismo que vamos a obtener en la instanciación real del esquema de encriptación de El Gamal. Ahora reclamo aquí que la variante privada clave del proceso de encriptación de El Gamal es perfectamente segura si mi texto plano subyacente es el grupo. Y esto se debe a que esta variante de clave privada del esquema de cifrado de El Gamal es exactamente similar al esquema de almohadilla única sobre el grupo. La única diferencia es que en el esquema de almohadilla única, realizamos la XOR de la clave con el texto plano. Pero puesto que estamos en el entorno del grupo, vamos a sustituir la operación XOR por la operación de grupo. Más formalmente, asumir que tenemos un texto de cifrado arbitrario, digamos (1, 2) y decir que consideramos un par de texto plano arbitrario, a saber 0 y 1, que son elementos de grupo, porque aquí mi espacio de texto plano es el grupo subyacente. Voy a demostrar que de hecho este proceso de cifrado satisface la definición de secreto perfecto. A saber, considerar la probabilidad de que este texto de cifrado arbitrario (1, 2) sea un cifrado del texto sin formato 0. Y de la misma manera, considere la probabilidad de que este texto de cifrado arbitrario (1, 2) sea un cifrado de 1. Resulta que este texto de cifrado arbitrario (1, 2) es un cifrado de 0, sólo si el algoritmo de generación de claves hubiera producido una clave, que es el resultado de la operación de grupo realizada en 2 y el inverso multiplicativo de 0. Pero dado que el algoritmo de generación de claves da salida uniformemente a elementos aleatorios del grupo como la clave, resulta que el algoritmo de generación de claves efectivamente da salida a una clave, que es la misma que la operación de 2 grupos 0 − 1 es 1 sobre el tamaño de grupo. Ahora, al ejecutar exactamente el mismo argumento, podemos afirmar que la probabilidad de que el texto plano 1 esté cifrado en el texto de cifrado (1, 2) es exactamente el mismo, que mi algoritmo de generación de claves da salida a una clave, que es la misma que la operación de grupo realizada en 2 y 1 − 1.Y la probabilidad de que mi clave sea esta, es 1 sobre el tamaño del grupo. Eso significa, para cualquier adversario, aunque sea computacionalmente ilimitado, si participa en un experimento de indistinguishabilidad perfectamente seguro en el ajuste de clave simétrica o en el experimento COA, entonces la probabilidad de que pueda distinguir aparte si está viendo un cifrado del elemento de grupo 0 o si está viendo un cifrado del elemento de grupo 1, es exactamente la mitad. Eso significa, no se puede distinguir aparte; con igual probabilidad es un cifrado de 0, así como el cifrado de 1. Y por eso esta variante modificada o clave simétrica del proceso de cifrado de El Gamal es perfectamente segura. (Vea el tiempo de la diapositiva: 19:38) Ahora vamos a la seguridad del COA del esquema de cifrado real de El Gamal que hemos diseñado en el entorno de la clave pública. Así que antes de ir más lejos, recordemos de nuevo lo que hemos demostrado justo ahora. Así que hemos considerado una variante del esquema de cifrado de El Gamal en el ajuste de clave simétrica y aquí está el algoritmo de cifrado. El algoritmo de cifrado produce dos elementos de grupo (1, 2), donde 1 es algo aleatorio y 2 es el enmascaramiento del mensaje. Y aparte de eso, el adversario también tiene una información pública, a saber, donde no se conoce al adversario. Así que si considero la visión del adversario, la visión del adversario consiste básicamente en tres distribuciones de probabilidad, a saber, él tiene un elemento, donde se elige al azar de Z.Sabe el valor de, donde se elige al azar de Z. Y conoce el enmascaramiento del mensaje con el texto plano, donde la clave se elige al azar del grupo subyacente. Y hemos demostrado que este proceso de cifrado es perfectamente seguro. Por otro lado, el esquema de cifrado de clave pública real de El Gamal, que hemos diseñado, también el texto de cifrado consta de dos elementos de grupo. Y el segundo componente del texto de cifrado es el enmascaramiento del mensaje con la clave Diffie – Hellman, a saber. Por lo tanto, si considero la vista del adversario en esta instancia real o la instanciación real del esquema de cifrado de El Gamal en el valor de clave pública, su vista es la siguiente. Sabe el valor de, donde se desconoce y uniformemente al azar del conjunto Z. Sabe el valor de, donde es uniformemente aleatorio del conjunto Z. Y sabe el enmascaramiento del mensaje con la clave Diffie – Hellman, donde la clave Diffie – Hellman no es más que, y pertenece al grupo subyacente. Ahora, si usted ve aquí de cerca, ¿qué es exactamente diferente aquí, si considero las opiniones de los dos adversarios aquí? La distribución de tanto en los mundos como en los adversarios es perfectamente la misma. Son exactamente indistinguibles. Aquí también alfa es al azar, aquí también alfa es aleatorio, no conocido por el adversario y el adversario conoce el valor de. De la misma manera, la distribución de ambos mundos es exactamente idéntica. Lo que es diferente aquí, es la naturaleza de 2 que el adversario ve en la variante clave simétrica del esquema de El Gamal y la distribución de 2, que el adversario ve en el esquema de cifrado real de El Gamal. En el mundo de claves simétricas, el enmascaramiento es con un elemento de grupo uniformemente aleatorio, mientras que en la clave pública El Gamal, el enmascaramiento del texto plano es con la clave pseudo-aleatoria, que es una clave Diffie – Hellman. Y si asumo que el supuesto DDH se sostiene en mi grupo subyacente, entonces sabemos que según la suposición Diffie – Hellman, triplete de Diffie – Hellman y un triplete no Diffie – Hellman, son computacionalmente indistinguibles desde el punto de vista de cualquier adversario computacionalmente acotado. Eso significa, si mi es uniformemente aleatorio, eso significa que si estoy en este caso, entonces en ese caso es algo, donde es totalmente aleatorio, no relacionado con y. Mientras que si considero el texto de cifrado 2 según la clave pública Diffie – Hellman pulic-key El esquema de cifrado de El Gamal, entonces mi clave no es más que. Así que si mi adversario no puede distinguir entre un triplete de DH y un triplete no DH, entonces puedo decir que la distribución del componente de texto de cifrado 2, que el adversario ve en ambos los mundos también son computacionalmente indistinguibles y que automáticamente demostrará que nuestro proceso de encriptación El Gamal es COA seguro. (Consultar Tiempo de Slide: 23:45) Así es la declaración formal que vamos a probar ahora. Vamos a demostrar que si el supuesto DDH se mantiene en mi grupo subyacente, entonces el proceso de cifrado de El Gamal es de hecho COA asegurado. Y formalmente establecemos este hecho dando una reducción. Así que asuma, usted tiene un adversario de tiempo de poli que puede atacar su esquema de cifrado de la clave pública de El Gamal. Usando ese ataque, vamos a diseñar un solver DDH, un solver DDH de tiempo de poli que puede distinguir aparte un triplete de Diffie – Hellman de un triplete no Diffie – Hellman. Así que participa en una instancia del experimento DDH. El experimento DDH prepara un desafío para el solver DDH dándole (, donde y son elementos de grupo al azar. Y el tercer componente del triplete es, o es un elemento uniformemente aleatorio, dependiendo de si el retador tiene o. Y la tarea del solver DDH es encontrar si se trata de un triplete de DH o un triplete no DH. Para resolver eso, el solver DDH invoca a nuestro atacante, quien puede atacar el esquema de encriptación de El Gamal y participa en una instancia del juego del COA y configura la clave pública para ser. Ahora según las reglas del juego de COA, el atacante de COA presentará un par de textos sin formato de desafío del grupo subyacente y este solver DDH va a elegir al azar uno de esos dos mensajes y prepara el texto de cifrado de desafío de la siguiente manera. El segundo componente del triplete, que se da como el desafío a este solver DDH, se establece como el primer componente del texto de cifrado y el cifrado real del mensaje se establece como, enmascarado con el tercer componente del triplete, que se lanza como un desafío al solver DDH. Así que ahora, antes de seguir adelante, intentemos entender lo que está sucediendo en esta reducción general. Si ves aquí que si este triplete es un triplete no DDH, eso significa en este caso en algunos, donde no está relacionado con y, entonces la distribución del texto de cifrado (1, 2), que se le da a este atacante contra el esquema de El Gamal, tiene exactamente la misma distribución si este atacante hubiera participado en el juego de COA contra la variante simétrica-clave del esquema de cifrado de El Gamal. Porque así se vería este texto de cifrado de reto para el atacante en ese experimento. Mientras que, si el triplete que se da a este solver DDH es un triplete de DH, entonces la distribución de (1, 2) que este adversario está viendo es exactamente la misma distribución que si este adversario hubiera visto participando en una instancia de juego de COA contra el proceso de encriptación de El Gamal. Así que volveremos a ese hecho de nuevo. Así que ahora este adversario tiene que identificar si ha visto un cifrado de 0 o 1. Por lo tanto, envía su salida. Y la respuesta del solver DDH es que, dice que está viendo un triplete de DH, si y sólo si el adversario EG ha identificado correctamente si es 0 o si es 1, que está cifrado en el texto de cifrado de desafío (1, 2). Así que ahora vamos a analizar la ventaja, a saber, con cuánta probabilidad este DDH solver va a resolver una instancia aleatoria del problema DDH. Así que reclamo que si, eso significa que este triplete es un triplete no DDH. Entonces la probabilidad de que mis salidas de solver DDH de forma incorrecta, a saber, outputs ′ = 1, es exactamente la misma con la que este atacante de COA habría ganado el juego de COA contra la variante simétrica-clave del esquema de cifrado de El Gamal. Y ya hemos probado que es 1 ⁄ 2. Esto se debe a que si estamos en el escenario donde, entonces como ya he probado que el texto de cifrado, que nuestro adversario EG está viendo, tiene exactamente la misma distribución que habría visto participando en una instancia de juego de COA contra el modificado esquema de cifrado de El Gamal. Por otro lado, reclamo que si mi caso es, entonces la probabilidad de que mi DDH solver outputs ′ = 1 es exactamente la misma que mi adversario EG gana el juego de COA contra el esquema de encriptación de El Gamal. Y esto se desprende del hecho de que si estamos en el caso en que, entonces eso significa que el triplete que se da es un triplete DDH o triplete de Diffie – Hellman, lo que significa que la distribución del texto de cifrado, cualquiera que sea el adversario visto es exactamente lo mismo que la distribución del texto de cifrado que este adversario habría visto al participar en una instancia de juego de COA contra el esquema de cifrado de El Gamal. Así que en resumen, lo que estamos concluyendo ahora es que, si ves la ventaja distintiva de nuestro solver DDH, entonces es exactamente 1 ⁄ 2 menos la probabilidad con la que nuestro adversario podría haber ganado el juego de COA contra el esquema de cifrado de El Gamal. Pero como estoy asumiendo que la suposición de DDH se mantiene en el grupo subyacente, entonces sé que la ventaja distintiva de cualquier solver DDH está limitada por alguna probabilidad insignificante. Así que no conozco el texto plano, pero conozco la clave pública y tengo un cifrado de El Gamal de ese texto plano desconocido, que consta de dos elementos de grupo, que estoy denotando por y. Y según la sintaxis del proceso de cifrado de El Gamal, tendrá esta propiedad, por lo que 1 es la aleatoriedad subyacente utilizada por el remitente. Y de la misma manera, imagina que tengo un cifrado de El Gamal o texto de cifrado de un mensaje desconocido, que consta de nuevo de dos elementos de grupo. Ahora supongamos que multiplico el primer componente de ambos textos de cifrado. Y, independientemente, multiplique el segundo componente de ambos textos de cifrado. Y esto producirá dos elementos de grupo, que matemáticamente tendrán la siguiente propiedad. El primer elemento de grupo no será más que la aleatoriedad de alimentación utilizada en el primer texto de cifrado más la aleatoriedad utilizada en el segundo texto de cifrado. Y el segundo componente será el producto de los dos textos planos, multiplicado por el poder público veces la suma de las dos aleatoriedad. Y si se mira de cerca, esto no es más que se puede imaginar como si se tratara de un texto de cifrado de El Gamal para el texto plano, bajo la aleatoriedad 1 + 2. Y por eso digo que mi proceso de encriptación El Gamal es homomórfico multiplicativo. La razón por la que es homomórfico multiplicativo es que si multiplico dos textos de cifrado de El Gamal, entonces incluso sin conocer los textos planos subyacentes (subrayo que no conozco los textos planos subyacentes y la aleatoriedad subyacente 1 y 2, que se utilizan individualmente), termino obteniendo un texto de cifrado de El Gamal de un texto plano relacionado, a saber, bajo alguna aleatoriedad desconocida, a saber, 1 + 2. Así que este es un tipo de propiedad muy interesante del proceso de cifrado de El Gamal. Y más adelante