Loading
Apuntes
Study Reminders
Support
Text Version

Intercambio secreto

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

    +

Foundations of Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bengaluru Lecture-56 Secret Sharing (Consulte el tiempo de la diapositiva: 00:29) Hola a todos. Bienvenidos a esta conferencia. Así que en esta conferencia vamos a discutir sobre protocolos interactivos. Es decir, nuestro enfoque hasta ahora era resolver el problema de la comunicación segura donde teníamos dos entidades un remitente y un receptor y discutimos extensamente cómo diseñar algoritmos para resolver el problema de la comunicación segura. Pero ahora lo que vamos a discutir es un escenario, un problema bien conocido, donde tenemos múltiples entidades. Y nuestro objetivo es diseñar un protocolo criptográfico que requiera interacción entre las entidades. Por lo tanto, específicamente la hoja de ruta para esta conferencia es la siguiente. Introduciremos el problema del intercambio secreto. Veremos el uso compartido secreto aditivo, el intercambio secreto replicado y luego veremos la construcción clásica del esquema de intercambio secreto debido a Adi Shamir. (Consulte el tiempo de la diapositiva: 01:17)Así que veamos la motivación del intercambio secreto. Así que imaginemos que tenemos una aplicación bancaria, digamos donde el casillero en el banco es accesible sólo por los gerentes de la siguiente manera. La contraseña para el casillero se comparte entre los tres gestores y se comparte de tal manera que si solo dos de los directivos van juntos y entran en sus respectivas contraseñas, se puede acceder al casillero. Pero si solo un único gestor intenta introducir la contraseña y acceder al casillero, el acceso no es posible. Por lo tanto, por ejemplo si el segundo gerente va y trata de abrir el casillero, no debería ser capaz de hacer eso. De la misma manera, si el tercer gestor va solo, debería fallar. Pero si tomamos algún conjunto de dos o más número de gestores y ellos van y entran en sus respectivas contraseñas, deberían poder acceder al casillero. Así que eso es lo que requerimos aquí. (Consulte la hora de la diapositiva: 02:14)De la misma manera, tenga en cuenta otro escenario del mundo real. Este es un escenario del mundo real, que realmente sucedió durante los años 90. Así que esto se refiere a cómo las armas nucleares de Rusia eran accesibles por los principales líderes de los países. Por lo que se cree que la contraseña para lanzar el arma nuclear de Rusia, fue compartida entre las tres principales entidades del país, a saber, el presidente, el primer ministro y el ministro de Defensa de tal manera que el arma podría ser accedida o lanzada sólo si al menos 2 de las 3 entidades se reúnen y entran en sus contraseñas, mientras que si sólo una sola entidad intenta lanzar o acceder al arma, el acceso será negado. (Consulte la hora de la diapositiva: 02:55) Para que ambas aplicaciones puedan abstraerse por el siguiente problema, al que llamamos (Sharing Sharing). Y este problema fue formulado independientemente por Shamir en 1979 y Blakley en 1979. Así que lo que se nos da aquí es, se nos da el siguiente ajuste. Tenemos un conjunto de partes 1, y están conectados por un canal privado y auténtico. Lo que significa es, si alguna información quiere enviarlo a, suponemos que tiene un canal dedicado con el que está conectado. Y cualquier cosa envía a través de ese canal a, será recibido correctamente y de forma segura por. Si usted se está preguntando cómo exactamente que tales canales están disponibles en el mundo real, bien, podemos usar cualquiera de los conocidos protocolos de comunicación seguros que hemos discutido ampliamente hasta ahora, para asegurar que tales canales estén disponibles entre cada par de partes. Ahora, aparte de estos partidos, tenemos un partido designado entre esos partidos y todos conocerán la identidad de ese partido y se les llama como dealer. Y el distribuidor tiene algo de entrada privada, un secreto de un espacio más grande, que es un conjunto de todos los secretos posibles. Ahora el objetivo de este distribuidor es distribuir su secreto entre las partes al subir o calcular una acción para cada una de estas partes y distribuir las acciones. Así que el primer accionista obtiene una parte 1, la segunda parte debe obtener la segunda parte y la parte debe obtener la parte. Y estas acciones se distribuyen por el canal en par con el cual el distribuidor está conectado a los accionistas individuales. Ahora requerimos las siguientes propiedades de estas distribuciones de acciones. Requerimos que sea imposible que cualquier conjunto de accionistas o menos de accionistas intercambien sus acciones y reconstruyan el secreto. Y dependiendo de si el conjunto de accionistas que están tratando de reconstruir el secreto, ya sea que sean computacionalmente acotados o que sean computacionalmente desacotados, logramos el secreto perfecto o el secreto computacional. Así que ese es el primer requisito de esta distribución de acciones. Por otro lado, si algún conjunto de o más accionistas junta sus acciones entonces debería ser posible reconstruir el secreto. Así que el parámetro aquí está actuando como un umbral para usted. Eso significa que requerimos un mecanismo de reparto de tal manera que si algún conjunto de accionistas o menos de accionistas se unen, no deben acceder o no deben reconstruir el secreto. Las acciones deben ser completamente independientes del secreto subyacente. Por otro lado, si algún conjunto de o más accionistas se reúnen, el secreto debería ser reconstruido, debería ser posible reconstruir el secreto. (Consulte la hora de la diapositiva: 05:39) Así que vamos a ver una construcción muy sencilla de (el esquema de compartición de secreto aditivo. Así que básicamente aquí mi umbral. Eso significa que yo exigiré un mecanismo de reparto en el que todos los accionistas se unan para reconstruir el secreto. Pero si falta algún accionista, entonces no debería ser posible reconstruir el secreto. Y por qué se le llama intercambio secreto aditivo, sería claro para ti muy pronto. Así que aquí mi espacio secreto l. El algoritmo de compartimiento es el siguiente. Así que imagina que el distribuidor tiene un secreto. Para compartirlo, escoge acciones al azar del conjunto. Esto significa que la primera parte 1 es una cadena de bits aleatoria, la segunda parte es una cadena de bits aleatoria y de la misma manera la parte es también una cadena de bits aleatoria. Ahora una vez que las primeras acciones son arregladas por el distribuidor, la última acción es establecida como = 1. Y una vez que las acciones son computadas, los distribuidores envían las acciones respectivas a los accionistas respectivos. A saber, la parte se entrega a la parte sobre el canal dedicado seguro y auténtico entre el distribuidor y el partido. Así que la propiedad de corrección aquí es trivial para este compartimiento secreto, es decir, si todos los accionistas se reúnen y intercambian sus acciones entre sí, entonces de hecho pueden realizar el xor de todas las acciones y ellos de manera única recuperar el secreto subyacente que fue compartido por el distribuidor. W siguiente prueba formalmente la propiedad de la privacidad aquí. Así que por privacidad nuestro objetivo es mostrar que si entre estos accionistas, cualquier accionista se junta y tire de sus acciones, no debe aprender nada sobre secreto subyacente. Así que dividimos la prueba en dos casos. Considere el caso cuando el conjunto de accionistas que están corruptos y que están tratando de reconstruir el secreto son los primeros accionistas. Resulta que si los primeros accionistas son corruptos, entonces de sus acciones no aprenden absolutamente nada sobre secreto subyacente. Porque si ves el algoritmo de compartir, las primeras acciones que son escogidas independientemente del secreto real del distribuidor. Así que eso significa que si el adversario controla a los primeros accionistas y accede a sus acciones, el adversario no aprende absolutamente nada sobre el secreto de los concesionarios. Ese es el caso. Por otra parte, considere el caso cuando el conjunto de accionistas incluya definitivamente al accionista nth, donde la parte es una función de un secreto y un resto de acciones. Así que el segundo caso es cuando la coalición de accionistas excluye a algún partido, donde definitivamente es diferente del partido. Así que por simplicidad se puede imaginar que mi = 1, eso significa que el adversario está corrompiendo a los últimos accionistas aquí. Resulta que la parte faltante que falta el conjunto de accionistas, que en este ejemplo es la parte 1, que es independiente del secreto. Porque eso fue escogido al azar por el dealer y eso asegura que a pesar de que el adversario aprende, es la parte también es independiente del secreto. Porque, por ejemplo, si estamos considerando el caso en el que falta 1 en la coalición, entonces desde la parte de la vista del atacante, el atacante sabe que el valor = 1 es decir, el de la empresa, donde y no se conoce al adversario. Y donde 1 es independiente y elegido al azar por el distribuidor. Así que puedes imaginar que esto no es más que una encriptación de una almohadilla de tiempo del mensaje con una llave, donde la clave no es otra cosa que el xor de las acciones 2, las que son conocidas por el adversario y el valor aleatorio 1, que no es conocido por el atacante. Eso significa que aunque el adversario está viendo, no puede averiguar si en realidad es una acción que corresponde al secreto o corresponde a un secreto. Porque no sabe el valor de la parte que falta 1, que se escogió al azar y se escogió independientemente del secreto real del distribuidor. Eso asegura que incluso si el adversario controla el último accionista no aprenderá absolutamente nada sobre el secreto subyacente. Y es por eso que el intercambio secreto satisface los requisitos de un (esquema de intercambio secreto. (Consulte la hora de la diapositiva: 11:01) Por lo tanto, resulta que el uso compartido secreto de aditivo que hemos discutido, sólo funciona si mi umbral es. Pero en general podría estar interesado en diseñar un compartimiento secreto donde mi umbral puede no ser, mi umbral podría ser estrictamente menor que. Así que ahora veamos una solución, una solución ingenua de llegar a un esquema de reparto secreto para cualquier umbral. Así que la idea aquí es que tomamos todos los subconjuntos apropiados del conjunto de las partes, digamos, donde el tamaño de es y ejecutar una instancia independiente dedicada de uso compartido secreto aditivo entre las partes en como los accionistas, con el umbral de ser. Y la idea aquí es que si hacemos esto por cada subconjunto de tamaño, entonces cuando se trata de la coalición real de accionistas que podrían tratar de aprender sobre el secreto, esa coalición de accionistas se perderá al menos una parte para reconstruir el secreto compartido real. Así que lo que estoy tratando de decir se demuestra mejor con este ejemplo. Así que imagina mi y quiero diseñar un esquema donde mi umbral. Eso significa que cualquier subconjunto de tres accionistas debería ser capaz de reconstruir el secreto, pero cualquier conjunto de dos accionistas, si intentan retirar sus acciones, no deberían reconstruir el secreto. Así que la idea aquí es que el distribuidor divide este conjunto de cuatro partes en diferentes subconjuntos 1,2, 3, 4 de tamaño tres partes. Ahora, en el primer subconjunto 1 = {1, 2, 3}, el distribuidor ejecuta una instancia de esquema de compartición secreta de aditivo con el umbral de ser t = 2. El distribuidor de nombres elige las acciones aleatorias 11, 12, 13, de tal manera que 11 de 12 de 12 de 12 de 13, y luego las acciones se entregan al accionista respectivo 1,2,3. De manera similar, el distribuidor ejecuta una instancia independiente de (3, 3) compartimiento de aditivo para los subconjuntos 2, 3 y 4. Ahora la cuota global para 1 será todas las acciones que recibe en varias instancias de la (3, 3) distribución de aditivos, dependiendo de los diversos subconjuntos en los que está presente. Es decir, su participación será de 11, 21 y 31. Ahora es fácil ver que independientemente de qué dos partes se corrompen, porque mi umbral en todas las instancias de uso compartido de aditivos, esos dos accionistas no aprenden absolutamente ninguna información sobre los secretos. Así que por ejemplo si 1 y 2 se corrompen, si están bajo el control del adversario entonces basados en sus acciones que aprenden, debido a su presencia en el subconjunto 1, los partidos 1,2 no logran aprender el secreto, porque faltarán la participación 13. De la misma manera con respecto al subconjunto 2, a estos dos partidos les faltará la acción 23 y es por eso que el secreto no será conocido por ellos y así sucesivamente. Por lo tanto, no importa qué subconjunto de partes se corrompe, basándose en sus acciones no logran aprender el secreto real. Así que ahora se podría estar preguntando que ahora tenemos un esquema de intercambio secreto para cualquier umbral con respecto al valor de. Pero resulta que este esquema es ineficiente porque el número de subconjuntos de tamaño es (1), que se convierte en una cantidad exponencial si es aproximadamente. Eso significa que los distribuidores básicamente tienen que lidiar con el número exponencial de valores aquí y el mismo es el caso para cada accionista. Así que esta es una solución ineficiente. (Consulte la hora de la diapositiva: 15:53)Y háganos saber discutir una solución muy inteligente para (Secret-Sharing debido a Adi Shamir. Y esta es una de las construcciones criptográficas más sencillas de las que se puede pensar. Este es mi favorito personal. Y esto se basa en la aritmética simple que usted podría haber aprendido durante su escuela secundaria. Así que la idea aquí es, si quieres compartir un secreto, entonces para compartirlo escoges un polinomio aleatorio de grado, de tal manera que el término constante del polinomio es el secreto que quieres compartir. Y que las acciones sean los puntos o valores distintos que mienten en ese polinomio. Para demostrar mi punto, imagine mi umbral y tengo un secreto y yo soy el distribuidor. Lo que puedo hacer es compartir el secreto, desde mi umbral, escojo una línea recta al azar, podría ser cualquier línea recta en el avión con la única restricción de que su término constante debe ser el secreto que quiero compartir. Y lo que ahora hago es, computo el valor de la línea recta en unos valores distintos fijos públicamente conocidos, digamos en 1, en 2 y en 3. Y estas son las acciones para la primera parte, segunda parte y tercera parte respectivamente. Será públicamente conocido por todos que la primera parte está obteniendo el valor de línea recta que el distribuidor ha escogido a 1 y así sucesivamente. Así que estos valores, son públicamente conocidos y todos sabrán que está asociado con el partido. Ahora tratemos de probar que por qué intuitivamente satisface los requisitos de (compartir secretos. Así que es fácil ver que si los accionistas se reúnen entonces pueden reconstruir de forma exclusiva el polinomio de grado que el distribuidor ha escogido. Debido a que los valores distintos en un grado desconocido polinomio son suficientes para reconstruir de nuevo de forma exclusiva ese polinomio. Así, por ejemplo, si y dicen que los dos primeros accionistas tienen sus acciones 1 y 2, entonces pueden encontrar la línea recta que pasa a través de los puntos (1, 1) y (2, 2) ajustando una ecuación de línea recta. Una vez que obtienen la línea recta, pueden tomar el término constante de la línea recta para ser el secreto recuperado. Por otro lado, el segundo hecho que podemos usar para polinomios de grado es que, si usted toma a cualquier accionista que son los malos y están tratando de reconstruir el secreto del dealer ’ s, no van a hacer eso. Debido a que los valores distintos no son suficientes para recuperar de forma exclusiva el polinomio de grado desconocido que fue elegido por el distribuidor. Más concretamente, en este ejemplo desde entonces, decir que el primer accionista es corrupto. Entonces desde su punto de vista podría haber un número infinito de líneas rectas posibles en el plano que pasa a través del punto (1, 1) y por lo tanto un número infinito de posibles secretos. Eso significa sólo basado en las acciones, el adversario fallará completamente para reconstruir de forma exclusiva el polinomio original del crupier y, por lo tanto, el secreto original del crupier. Esa es la idea intuitiva. Resulta que tenemos que realizar todos los cálculos anteriores sobre algún campo finito para lograr seguridad y para evitar trabajar sobre un dominio infinito. (Consulte la hora de la diapositiva: 20:01) Así que intentemos comprender primero algunos hechos básicos sobre polinomios sobre un campo finito. Así que imagine que me dan un campo finito (. Un polinomio de grado encima es de la forma 0 + 1 n, donde 0, …, ∈. Un valor se llama una raíz de (), if () = 0I stress aquí que todas las operaciones aquí son las operaciones + y n sobre el campo. Ahora otro hecho bien conocido de álgebra abstracta que podemos utilizar aquí es el siguiente. Si se le da un polinomio de grado sobre un campo, entonces puede tener en lo más t raíces. Por ejemplo, si, entonces una recta sobre un campo se encuentra con el eje y en un punto más de un punto. Y esto es cierto para cualquier polinomio t grado sobre un campo. Y en base a este resultado, podemos afirmar que dos polinomios de grado distintos (), () sobre pueden tener en la mayoría de los valores comunes. Así, por ejemplo, si usted tiene 2 líneas rectas distintas que pueden intersecarse en el punto más de un punto. No pueden cruzarse en 2 puntos porque si se cruzan en dos puntos comunes entonces las 2 líneas rectas son básicamente la misma línea recta y en general, esto generaliza para cualquier valor de. Una vez más no estoy demostrando este teorema. Estos son algunos resultados bien conocidos de álgebra abstracta. Y el resultado final que voy a utilizar para dar la descripción de Shamir ’ s sharing es la fórmula de interpolación de Lagrange. Así que lo que este teorema básicamente dice es si se le dan t + 1 pares de valores (1, 1), …, (,) desde el campo, donde 1, …, son distintos. Entonces existe un polinomio de grado único sobre, tal que) =, para 1 ≤ Para ver cómo podemos calcular exactamente este polinomio, déjenme definir una secuencia de polinomios, donde el polinomio ((− 1) (− − 1) (− − 1) (− + 1) (− + 1) (− 1) (− − 1) (− − 1) (− 1), que tiene grado. Y la forma en que he definido este polinomio (sigue que () = 1, mientras que (1) = (2) = () = () = () = () = 0. Eso significa que estos (polinomios son tales que sobreviven a =, mientras que se desvanecen en todos los demás valores. Ahora mi polinomio desconocido pasando a través de los pares t + 1 dados de (xi, yi) valores. Y puedo representar ese polinomio 1 desconocido (1 + + + (. (Consultar Tiempo de Slide: 24:43)Y es fácil ver que de hecho 1) = 1, porque para 1, mi 1 (polinomio sobrevivirá y dará el valor 1 y 1 multiplicado por 1 será 1, mientras que todos los demás (polinomios se desvanecerán. De la misma manera para 2, todos mis polinomios delta se desvanecerán excepto el 2 (polinomio, que dará el valor 1 y 1 multiplicado por 2 me dará 2, que satisface mi condición. Así que es el polinomio de grado único, que usted puede descubrir pasando a través de los puntos dados (1, 1), …, (,), donde 1, …, son distintos. Ahora usted podría preguntarse que ¿por qué 1, …, son distintos tienen que ser distintos? Tienen que ser distintos para asegurar que cada uno de los (polinomios tienen un denominador que no es cero. Y si el denominador es no-cero entonces básicamente este numerador dividido por el denominador debe ser interpretado como si este numerador se multiplica por el inverso multiplicador de mi denominador, porque estoy haciendo la división aquí. Y esta división debe interpretarse como multiplicando el numerador con el inverso multiplicativo del denominador. Y el inverso multiplicativo del denominador existirá sólo si mi denominador es distinto de cero. (Consulte la hora de la diapositiva: 26:08)Así que ahora vamos a la descripción de Shamir ’ s Secret Sharing. Como parte de la configuración pública, se nos dará algún campo finito donde el tamaño del campo será al menos, el número de accionistas. Y asociados con los accionistas se conocerán públicamente valores distintos de cero, a saber, 1, …, que son los valores del campo finito. El algoritmo de intercambio de Shamir secreto compartido es el siguiente. Si el distribuidor tiene un valor secreto, que quiere compartir entonces escoge un polinomio aleatorio sobre el campo eligiendo elementos aleatorios como los coeficientes del campo, de tal manera que el término constante del polinomio es el secreto que el distribuidor quiere compartir. Y ahora el accionista, a saber, el partido, obtiene la parte, donde no es más que el valor de este polinomio recogido por el distribuidor en. La corrección de este intercambio secreto es trivial. Eso significa, imagínate de estos accionistas, cualquier subconjunto de accionistas se unen mediante el intercambio de sus acciones, entonces pueden interpolar de nuevo de nuevo el polinomio de grado utilizando la fórmula de interpolación de Lagrange ’ s que hemos discutido antes. Y para probar la privacidad vamos a demostrar que si tomamos algún conjunto de accionistas entre estos accionistas, entonces sus acciones son independientes del secreto de las acciones subyacentes, porque intuitivamente esto viene del hecho de que los coeficientes de polinomio que son recogidos por el distribuidor para compartir el secreto, son elegidos uniformemente al azar del campo subyacente. (Consulte la hora de la diapositiva: 27:55)Así que lo hagamos más riguroso. Así que déjenme definir un conjunto Fto denotar el conjunto de todos los polinomios de grado seleccionados del campo finito cuyo término constante es el secreto. Así que resulta que el número de tal polinomio de grado cuyo término constante es el secreto no es nada, sino |. Esto se debe a que en cada polinomio, aparte del término constante que es, hay otros coeficientes 1, de la mano, recogidos del campo y para cada uno de estos coeficientes, hay |candidatos. Por lo tanto | F | = |. Por simplicidad y sin pérdida de genialidad, asumir que los primeros accionistas son corruptos, eso significa que han visto las acciones 1, …,. Y saben que estas acciones no son más que el valor de algún polinomio de grado desconocido, evaluado en 1, …,. Demostraremos que la distribución de probabilidad de estas acciones es independiente del secreto elegido por el distribuidor. Para esto, primero notamos que dado cualquier acción arbitraria 1, …,, existe un único polinomio F, con =), para. Esto se deriva del hecho de que los puntos distintos (0,), (1, 1), …, (,) puede estar sólo en un polinomio de un solo grado. Ahora basándonos en todas estas cosas, reclamo que las acciones 1, …, son independientes del secreto real compartido por el distribuidor. Y para probar esta afirmación, consideremos un par de secretos arbitrarios (′) de, tal que. Vamos a mostrar que desde el punto de vista del adversario, 1, …, podrían ser las acciones de, así como con igual probabilidad. Let (ser polinomio único del conjunto Fque habría producido las acciones 1, …, para el secreto. Y de forma similar, deje que ′ (sean los polinomios exclusivos del conjunto F ′,, que habrían producido las acciones 1, …, para el secreto. Ahora la probabilidad de que el adversario haya visto las acciones 1, …, el secreto de los distribuidores es lo mismo que el distribuidor ha utilizado el polinomio (para compartir. Y este evento ocurre con la probabilidad 1/ |, ya que el polinomio del crupier es seleccionado al azar, donde todos los coeficientes excepto el término constante son seleccionados al azar de. Usando exactamente el mismo argumento, concluimos que la probabilidad de que el adversario haya visto las acciones 1, …, el secreto de los distribuidores es lo mismo que el distribuidor ha utilizado el polinomio ′ (para compartir. Y este evento se produce con probabilidad 1/ |. Eso prueba que la distribución de probabilidad de 1, …, es independiente del secreto subyacente y, por lo tanto, al ver estas acciones, el adversario será despistado si el distribuidor ha compartido el secreto o secreto. Así que eso me lleva al final de esta conferencia. Sólo para resumir. En esta conferencia presentamos el problema de (compartir secretos y vimos tres construcciones. Vimos la construcción de un intercambio secreto de aditivos donde está el umbral. Y luego utilizando esta (compartición secreta