Loading
Apuntes
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

    +

Fundamentos de la criptografía Prof. Ashish Choudhury Departamento de Informática Instituto Internacional de Tecnología de la Información-Conferencia de Bangalore-49 CCA Secure Public Key Ciphers Based on Diffie-Hellman Problems (Referir Slide Time: 00:33) Hola a todos. Bienvenidos a esta conferencia. El plan para esta conferencia es el siguiente: Así que en esta conferencia, veremos la inseguridad de CCA de El Gamal clave pública criptosystem, que habíamos demostrado antes de ser CPA segura. A continuación, veremos una instanciación del mecanismo de encapsulación de clave segura de CCA basado en suposiciones de gap-CDH. Así que introduciremos formalmente lo que es exactamente la brecha gap-CDH. Y en base a eso, veremos una instanciación segura de CCA de mecanismo de encapsulación clave y ya que en la última conferencia, habíamos visto que, si se le da un CCA seguro KEM, luego combinándolo con cualquier cifrado de clave simétrica segura de CCA, podemos obtener un esquema de cifrado de clave pública híbrida segura de CCA. Así que al hacer eso, obtendremos una versión segura de CCA de instanciación de criptosistema de clave pública híbrida basada en problemas de Diffie-Hellman y las dos variantes de tal instanciación, es decir, DHIES y ECIES, vamos a discutirlas. (Consulte la hora de la diapositiva: 01:26) Así que comencemos con la maleabilidad de El Gamal Cipher. Así que sólo para recordar, esta es una descripción del proceso de cifrado de El Gamal. El algoritmo de generación de claves da salida a una clave pública y una clave secreta, donde la clave pública es alguna g α, donde α se elige aleatoriamente de Zq y una clave secreta. Para cifrar un texto sin formato, el remitente primero calcula g β, donde β se elige aleatoriamente de Zq. Y luego el mensaje se multiplica por la clave pública (pk) β y (pk) β no es más que una clave Diffie-Hellman g α β. Así que por simplicidad, estoy asumiendo que mi grupo subyacente es un grupo multiplicativo y por eso mi c2 es el producto de m y el componente (pk) β. Para desencriptar, el receptor primero calcula una clave común de Diffie-Hellman al elevar la parte c1 del texto de cifrado a la clave secreta y tomar su inverso multiplicativo y multiplicar eso con el componente c2 del texto de cifrado. De modo que el efecto de g α β se cancela. Y nosotros habíamos probado que si la suposición de DDH se sostiene, entonces esto es seguro de CPA. Así que recordemos que, también discutimos en una de nuestras conferencias anteriores la propiedad homomórfica de los cifrados de El Gamal. Así que El Gamal ciphers, así que lo que exactamente queremos decir es que, supongamos que se le da el cifrado cm de algún mensaje desconocido m, entonces según la sintaxis de El Gamal cipher cm constará de dos elementos de grupo. El primer elemento de grupo será algunos g β (uknonwn β) y el segundo componente será el texto sin formato desconocido m multiplicado por g α β. Ahora si tomamos el texto de cifrado y tomamos el segundo componente del texto de cifrado y lo multiplicamos por cualquier valor c del grupo. Entonces lo que obtenemos es básicamente un nuevo texto de cifrado que consta de dos elementos de grupo, que puede ser considerado como el cifrado de El Gamal válido del mensaje c veces m. Esto significa que mi proceso de encriptación de El Gamal es maleable, porque sólo tomando un texto de cifrado de un mensaje desconocido m, puedo producir un texto de cifrado de un mensaje relacionado, a saber, c veces m donde c es conocido por mí, pero el m no es conocido por mí, simplemente realizando algunas operaciones locales y resulta que, si mi proceso de encriptación es maleable, entonces nunca podemos esperar que pueda ser CCA seguro y voy a demostrar eso con un ejemplo aquí. (Consultar tiempo de la diapositiva: 04:05) Así que imagínate, hay un adversario arbitrario, que participa en una instancia del juego CCA contra el cifrado de El Gamal. Así que según las reglas del juego, el retador lanzará la llave pública al adversario, donde la clave pública u es g &alfa;, donde &alfa; no se conoce. Lo que hace el adversario es que toma un par arbitrario de texto plano del grupo. El reto lo prepara el retador seleccionando m0 o m1 para el cifrado. Y envía un texto de cifrado de reto c * al adversario y lo que hace ahora el adversario es, sabe que el texto de cifrado de reto, que consta de dos elementos de grupo, tiene esta estructura: 1 ← y 2 ←. , donde β no es conocido por él, el mb real no se le conoce y g α β no se le conoce, pero lo que el adversario puede hacer es, puede escoger alguna x arbitraria del grupo y puede explotar la propiedad de maleabilidad del texto de cifrado de El Gamal. Y ahora puede producir algún texto de cifrado modificado denotado como c, que ahora es un cifrado del mensaje x veces el mensaje desconocido mb y lo que hace ahora el adversario es, pide el servicio de oráculo de descifrado para este texto de cifrado modificado c, que está permitido según las reglas del juego CCA. Ahora el retador tiene que descifrar este texto de cifrado modificado c y al descifrarlo, devolverá x * mb al adversario. Ahora ya que el adversario sabe el valor de x y x pertenece al grupo, puede computar el inverso multiplicativo del valor x y al multiplicarlo con m, puede identificar completamente lo que mb y por lo tanto, puede enviar el derecho b y como se puede ver que la probabilidad de que esta estrategia adversarial gana el juego, CCA juego es exactamente 1. Eso significa, mi cifrado de El Gamal no es CCA seguro. Sólo es seguro de CPA. Tan pronto como encriptamos algún mensaje usando el cifrado de El Gamal y si estamos en el modelo de adversaria maliciosa usando la ayuda del servicio de oráculo de descifrado, el adversario puede descubrir completamente lo que está encriptado exactamente. (Consultar tiempo de la diapositiva: 06:20) Así que eso significa, ahora tenemos que pensar que cómo podemos diseñar una instanciación segura de CCA del cifrado de El Gamal, así que lo que vamos a hacer es en lugar de ver una versión segura de CCA de El Gamal cifrado, vamos a ver una variante segura de CCA de cifrado El Gamal híbrido y para eso lo que vamos a hacer es, vamos a crear una instancia de un CCA seguro KEM basado en los problemas de Diffie-Hellman. Así que recordemos el mecanismo de encapsulación de la clave segura CPA basado en la suposición de CDH en el modelo de oráculo aleatorio, que habíamos discutido en una de las conferencias anteriores. Así que imagina que Sita quiere configurar la clave para su mecanismo de encapsulación clave. Así que lo que hace es que hace su parte del protocolo de intercambio de claves Diffie-Hellman de una vez por todas al escoger un &alfa; aleatorio, que se establece como su clave secreta y hace g α como su clave pública. Esto puede ser considerado, este mensaje g α puede ser considerado como un mensaje una vez para todos para cada emisor potencial que quiere comunicarse a ella y ahora si hay un Ram que quiere encapsular la clave, entonces el algoritmo de encapsulación para Ram será el siguiente. Ram hará su parte del protocolo de intercambio de claves Diffie-Hellman escogiendo una β aleatoria y calculando g β, es decir, la encapsulación. Y la clave, que Ram obtiene o que se considera encapsulado en esta encapsulación c es básicamente la salida de (pk) β evaluada bajo la función de derivación de claves, que está disponible públicamente, donde el elemento de derivación de la función de derivación de claves subyacente del grupo cíclico g, al espacio clave de algún esquema de cifrado de clave simétrica subyacente. Para descabezar c, lo que Sita tiene que hacer es, tiene que hacer su parte del protocolo de intercambio de claves Diffie-Hellman para obtener la clave común g α β y obtener la salida de la función de derivación de claves en ese g α β y luego puede obtener la misma clave k. Hemos demostrado que en el modelo de oráculo aleatorio, si asumimos que el problema de CDH es difícil de resolver en el grupo subyacente, entonces el mecanismo de encapsulación de la clave anterior es el CPA asegurado. Pero resulta que el mismo mecanismo de encapsulación de claves no es CCA seguro, incluso si estamos en el modelo de oráculo aleatorio. Esto se debe a que si asumimos que hay un adversario politiempo, que participa en una instancia de CCA juego contra el mecanismo de encapsulación de la clave anterior, entonces el juego se verá algo como sigue. El retador generará la clave secreta y una clave pública y utilizando la clave pública, realizará un encapsulado para obtener el encapsulado c y clave encapsulada k. Y preparará el desafío lanzando, lanzando una moneda justa y el desafío para el adversario será u, c, y el objetivo del adversario es identificar si se genera según el método b igual a 0 o según el método b igual a 1. Pero como estamos en el mundo del CCA, ahora se permite al adversario tener acceso al servicio de oráculo de la decapitación. A saber, puede presentar cualquier encapsulación c ’, que es diferente de c y c la decapitación de la c ’ resultante. Así que lo que el adversario puede hacer ahora es, puede elegir arbitrariamente algún elemento c ’ del grupo y decir que es algo g β ’ y junto con eso, escoge algún elemento aleatorio z ’ del grupo y no sólo eso, también computa la salida de la función de derivación de claves en ese elemento elegido al azar z ’ para obtener la clave k ’. Ahora que el adversario tiene permitido tener el servicio de oráculo de la decapitación, puede pedir la decapitación de c ’. Puesto que c ’ se elige al azar del grupo, muy probablemente c ’ va a ser diferente de c. Incluso si no es diferente de c, lo que el adversario puede hacer es, puede seguir recogiendo al azar c ’ y muy probable c ’ será diferente de c en cuanto obtenga la c ’ diferente de c, pide la decapitación de c. Y en respuesta el retador dará salida a esta k, y si ve la sintaxis del algoritmo de descapitalización, este valor k no es más que la salida de la función de derivación de claves en la entrada g α β ’, porque si c ’ es g β ’, entonces para descabezar c ’, el retador va a calcular primero g α β ’ y luego correlacionará ese elemento g α β ’ con un elemento del espacio de claves ejecutando, calculando la salida de la función de derivación de claves. Ahora lo que el adversario puede hacer ahora es, puede pedir el servicio de oráculo de la decapitación para muchos de tal c ’, es decir, puede realizar el mismo cálculo que ha hecho aquí, el número de tiempo polinomio, recogiendo un poco de c ’ al azar, el azar z ’, la computación de la k ’ correspondiente a la z ’ y pedir el servicio de la decapitación del componente c ’ y ahora una vez que se entrena polinomialmente, puede enviar su respuesta, si se genera según el método b igual a 0 o según el método b igual a 1. Ahora usted podría estar pensando que lo que la ventaja adicional que el adversario aquí está recibiendo al ver la respuesta del servicio de oráculo de la decapitación. Si usted ve de cerca aquí, al ver la respuesta del servicio de oráculo de la decapitación, el adversario viene a aprender si el triplete (u, c ’, z ’) es un triplete DDH o no. Más específicamente, si la respuesta del servicio de decapitación para c ’ devuelve la clave k, que es diferente de la k ’, que el adversario ha calculado, entonces el adversario sabe que definitivamente (u, c ’, z ’) no constituye un triplete DDH. Porque contrapositivamente, si de hecho (u, c ’, z ’) es un triplete DDH, entonces básicamente k habría sido igual a k ’. Por otro lado, el adversario también sabe que si k ’ es igual a k, es decir, la respuesta que sale como la respuesta del servicio de oráculo de la decapitación correspondiente a la consulta del adversario es igual que la k ’, que ella ha calculado, entonces con muy alta probabilidad, el triplete (u, c ’, z ’) constituye un triplete DDH. Esto se debe a que (u, c ’, z ’) no es un triplete DDH, es decir, esta z ’ es diferente de g α β ’, entonces es muy poco probable que la función de derivación de claves en dos entradas diferentes sea g α β ’ y alguna g γ, donde γ es diferente de α veces β ’ le da la misma salida y esto se mantiene, porque estamos en el modelo oracle aleatorio, donde la función de derivación de claves se está comportando como una función realmente aleatoria. Así que eso significa, lo que ahora podemos ver aquí es que la forma en que el adversario está recogiendo su servicio de oráculo de decapitación y haciendo algún cálculo local entonces comparando la respuesta del servicio de oráculo de la decapitación, básicamente el adversario tiene un acceso al solver DDH, que le dice si un triplete presentado constituye un triplete DDH o no. Eso significa, sólo basado en la suposición de CDH y la suposición de modelo de oráculo aleatorio, no podemos demostrar que esta construcción de mecanismo de encapsulación clave es CCA seguro. Porque a través del servicio de oráculo de la decapitación, el adversario ahora está consiguiendo acceso al solver DDH y eso nos motiva a definir ahora un nuevo supuesto. (Consultar Tiempo de Slide: 14 :47) O un nuevo problema duro, que llamamos como la brecha computacional Diffie-Hellmen problema o brecha computacional Diffie-Hellman suposición y la intuición subyacente detrás de esta suposición es que requerimos que el problema de CDH debe ser difícil de resolver en mi grupo subyacente, incluso si un adversario tiene acceso oracle a un solver DDH. Hago hincapié aquí en que él tiene sólo un acceso de oráculo al solver DDH; no tiene un politiempo; no sabía los pasos exactos de ese solver DDH. Así que la forma en que la modemos aquí es la siguiente: llamamos a este experimento como gap-CDH y básicamente el retador prepara una instancia de problema de CDH escogiendo un g α y g β, donde α y β elegidos al azar del conjunto 0 a q – 1 y el desafío para el adversario es calcular la función Diffie-Hellman de este au, v par, es decir tiene que calcular g α β. Pero ahora para modelar el hecho de que el adversario tiene acceso oráculo a un solver DDH, permitimos que el adversario someta el número polinomio de consultas de la forma (v, w) y en respuesta las salidas del retador 1, si y sólo si el retador encuentra que este wcomponent es de hecho este v &alfa;, es decir, este par (v, w) constituye un triplete DDH con respecto a la u, que el adversario ha lanzado como un desafío. Y ahora se permite al adversario hacer el número polinomio de tales consultas aquí y una vez que ha hecho polinomio número de consultas, el objetivo del adversario es calcular la función CDH del desafío u, v, que se lanza al adversario, es decir, produce un elemento de grupo y la definición del experimento es decir que el adversario ha ganado el experimento, que denotamos diciendo que la salida del experimento es 1, si y sólo si el adversario es capaz de resolver correctamente el problema de CDH, es decir, es de hecho igual a g &alfa; β. Decimos que la brecha de asunción de CDH en mi grupo subyacente g con respecto a la cual se juega este juego es para cada adversario de politiempo que participa en este experimento, la probabilidad de que gane el experimento es superior limitada por alguna función insignificante. Es posible que te estés preguntando qué significa exactamente aquí la diferencia de prefijo. Bueno, la brecha significa aquí que queremos que un problema de CDH sea difícil incluso si el problema de DDH es computacionalmente fácil de resolver en ese grupo. Eso significa que queremos capturar la esencia de que existe una brecha entre la dificultad del problema del CDH y el problema de la DDH aquí y resulta que hay varios grupos de candidatos, donde creemos que el déficit de la brecha de CDH, a saber, el problema del déficit de CDH, de hecho, es difícil de resolver. Por ejemplo, el grupo basado en los puntos en curvas elípticas modulo prime es uno de esos grupos candidatos. También puede tomar el subgrupo de primer orden del grupo multiplicativo Zp *. En ambos grupos de candidatos, creemos que la suposición de brecha-CDH se mantiene para valores suficientemente grandes del parámetro de seguridad. (Consultar tiempo de la diapositiva: 18 :04) Así que ahora, veamos cómo podemos crear una instancia de mecanismo de encapsulación clave bajo el supuesto de brecha-CDH y resulta que la construcción no es una nueva construcción. La construcción es exactamente la misma construcción, que habíamos visto, cuando discutimos una instanciación segura de CPA de mecanismo de encapsulación clave bajo el supuesto de CDH y suposición DDH. La única diferencia ahora es que ahora estamos tratando de modelar un adversario activo, cada vez que el receptor recibe la encapsulación c antes de ir a descabezarla, sólo tiene que comprobar si la encapsulación c es el elemento de grupo o no. Porque idealmente, si de hecho la encapsulación c viene de una parte honesta o un remitente honesto, entonces según los pasos del algoritmo de encapsulación, el componente c de la encapsulación debe ser un elemento de grupo. Por otro lado, si c en realidad viene como una consulta de oráculo de decapitación, entonces lo que un adversario podría tratar de hacer es, puede pedir la decapitación de un elemento, que no es un elemento del grupo y si el receptor no realiza la comprobación de la cordura y proceder ciegamente para decapitarlo y enviar de vuelta la salida, entonces podría conducir a una violación de la seguridad aquí. Así que es el único cheque adicional que estamos haciendo aquí. El resto de los pasos para el algoritmo de generación de claves, el algoritmo de encapsulación y el algoritmo de descapitalización son exactamente los mismos, como había antes. Ahora lo que podemos probar aquí, si la brecha de CDH de gap se mantiene en mi grupo subyacente, entonces esta instanciación del mecanismo de encapsulación clave es CCA seguro en el modelo de oráculo aleatorio. Y veamos una visión general de muy alto nivel de la prueba. No entraríamos en los detalles formales. Si usted está interesado, puede ver el libro de Katz & Lindell para los detalles formales. Así que si pensamos en cualquier adversario, un adversario politiempo que participa en el juego de CCA contra este mecanismo de encapsulación, entonces mi afirmación es que la decapitación, las consultas de descapitalización de oráculo, básicamente da al adversario acceso al solver DDH y esto lo habíamos visto antes, justo. Pero si mi brecha-CDH asume en el grupo subyacente, derecho, entonces significa que incluso si el adversario consigue acceso al solver DDH implícito, el problema de CDH todavía sigue siendo difícil para el adversario a resolver. Eso significa, el oráculo de la decapitación, las consultas de decapitación no sirven para nada al adversario. No le ayudaría a resolver el problema de CDH y ahora lo que básicamente estamos haciendo aquí es básicamente ya que las consultas de descapitalización no son de ayuda para el adversario, entonces sabemos ya que en ausencia de consultas de descapitalización una instancia de juego de CCA contra el mecanismo de encapsulación clave es exactamente lo mismo que una instancia del juego de CPA contra el mismo mecanismo de encapsulación clave, que ya habíamos demostrado ser CPA seguros bajo el supuesto de CDH en el modelo de oráculo aleatorio. Esto significa que no tenemos que añadir ningún paso sofisticado en este mecanismo de encapsulación de claves existente para que CCA sea seguro. Lo que sólo tenemos que asegurar es que, instanciamos los pasos del algoritmo de encapsulación y descapitalización en un grupo en el que la suposición de la brecha de CDH se mantiene y en la suposición de la brecha se mantiene, estamos a salvo porque el servicio de oráculo de la decapitación es completamente inútil para el adversario y no obtiene ninguna ventaja adicional en comparación con un adversario de CPA. (Consulte el tiempo de la diapositiva: 21:54) Así que eso significa que ahora tenemos una instanciación del mecanismo de encapsulación de claves seguras de CCA, así que lo que vamos a hacer es, vamos a utilizarlo para llegar a las versiones híbridas seguras de CCA de los cifrados de clave pública basados en los problemas de Diffie-Hellman y hay dos instanciaciones bien conocidas de este marco, una se llama DHIES y ECIES y la idea aquí es básicamente utilizar el marco genérico que habíamos discutido en la última conferencia. Donde hemos visto que si se nos da un mecanismo de encapsulación de llave segura de CCA y si se nos da un proceso de cifrado de claves simétricas seguras de CCA, entonces el proceso de cifrado híbrido resultante es CCA seguro. Lo que tenemos que hacer básicamente ahora es que tenemos que crear una instanciación segura de CCA del mecanismo de encapsulación clave. Así que lo que podemos hacer es utilizar el mecanismo de encapsulación clave, que es CCA seguro basado en la brecha gap-CDH, que acabamos de ver ahora. Y para instanciar el cifrado de claves simétricas seguras de CCA, lo que podemos hacer es, podemos utilizar cualquier esquema de cifrado autenticado, que habíamos visto durante nuestra discusión sobre el proceso de cifrado de claves simétricas, a saber, podemos utilizar la construcción genérica basada en el cifrado then authenticate approach, que siempre nos da la garantía de que el esquema resultante es un esquema de cifrado autenticado. Así que recuerde en el método de cifrado y luego autenticar, tomamos un proceso de cifrado seguro de CPA, proceso de cifrado de claves simétricas y un código de autenticación de mensaje seguro y los combinamos utilizando este enfoque de cifrado y luego autenticar, donde primero ciframos el mensaje utilizando el cifrado de clave simétrica segura de CPA y el texto de cifrado de cifrado resultante se autentica según el código de autenticación de mensajes para obtener la etiqueta. Y (texto de cifrado, etiqueta) se considera como el texto de cifrado general y hemos probado rigurosamente que este enfoque genérico siempre nos da un proceso de cifrado de clave simétrica de cifrado autenticado y sabemos que en el mundo de claves simétricas, el cifrado autenticado implica la seguridad de CCA, porque una de las condiciones para que se cumpla el esquema de cifrado autenticado es que, debería tener la noción de seguridad de CCA. Así que para crear una instancia de este cifrado de claves simétricas seguras de CCA, podemos utilizar cualquier esquema de cifrado autenticado. Así que ahora, tenemos la instanciación de ambos los gadgets que necesitamos en nuestro esquema de cifrado híbrido. Si utilizamos estas dos instanciaciones, obtenemos lo que llamamos esquema de cifrado integrado Diffie-Hellman o DHIES en resumen y cuando instanciamos esta DHIES donde el grupo subyacente se basa en los puntos en curva elíptica, entonces la instanciación DHIES resultante se llama ECIES, es decir, esquema de cifrado integrado de curva elíptica. Se trata de dos estándares bien conocidos, que se utilizan en la práctica para crear una instancia, cifrados de claves públicas híbridas basadas en problemas de Diffie-Hellman. Así que eso me lleva al final de esta conferencia. Sólo para resumir, en esta conferencia, hemos visto instanciaciones del mecanismo de encapsulación de claves seguras de CCA. Para eso, hemos introducido una noción de brecha-CDH y brecha-la asunción de CDH y hemos visto que si combinamos un KEM seguro de CCA basado en la asunción de gap-CDH junto con cualquier esquema de cifrado autenticado en el mundo de clave simétrica, que es clave simétrica, entonces la construcción resultante nos da CCA seguro de proceso de cifrado de clave pública, que llamamos como