criptografía y teoría de juegos
DESCRIPTION
(7/12/2010) Criptografía y Teoría de Juegos. Muestra de un par de protocolos de Rational Secret Sharing. (12/07/2010) Cryptography and Game Theory. Showing a few protocols of Rational Secret Sharing.TRANSCRIPT
Introduccion
Criptografıa y Teorıa de JuegosRational Secret Sharing
Mauricio Quezada [email protected]
Departamento de Ciencias de la ComputacionUniversidad de Chile
7 de Diciembre de 2010
Criptografıa y Teorıa de Juegos
Introduccion
Agenda
1 Introduccion
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
Suponga que existe un dealer D que desea compartir s ∈ Z entrelos participantes P1, .., Pn, repartiendolo en trozos d1, .., dn de talforma que:
1 El conocimiento de t o mas trozos permita reconstruir s
2 El conocimiento de t− 1 o menos trozos no entregueinformacion sobre s
Vimos como el esquema de Comparticion de Secreto de AdiShamir nos permite satisfacer estas dos condiciones
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
Suponga que existe un dealer D que desea compartir s ∈ Z entrelos participantes P1, .., Pn, repartiendolo en trozos d1, .., dn de talforma que:
1 El conocimiento de t o mas trozos permita reconstruir s
2 El conocimiento de t− 1 o menos trozos no entregueinformacion sobre s
Vimos como el esquema de Comparticion de Secreto de AdiShamir nos permite satisfacer estas dos condiciones
Criptografıa y Teorıa de Juegos
Introduccion
Esquema de Adi Shamir
Sea p un numero primo y s en Zp el secreto. Para compartir elsecreto entre n participantes de forma que t ≤ n de ellos puedanreconstruirlo:
1 El dealer genera un polinomio al azar de grado t− 1
q(x) = a0 + a1x+ ...+ at−1xt−1
Tal que q(0) = a0 = s, y a1, .., an son escogidos al azar en Zp
2 Cada trozo es de la forma di = q(i) ∀i ∈ [1..n], y esentregado al participante i-esimo
Criptografıa y Teorıa de Juegos
Introduccion
Esquema de Adi Shamir
Para reconstruir el secreto, basta interpolar el polinomio q teniendot o mas valores de el.
Usando interpolacion de Lagrange, dados los trozosdi ∈ ∆ ⊂ [1..n], |∆| = t
• Definiendo los coeficientes de Lagrange, λi = Πj∈∆,j 6=ij
j−i• El secreto se calcula entonces como
s =∑i∈∆
siλi
Criptografıa y Teorıa de Juegos
Introduccion
Consideraciones
Usualmente en Criptografıa se asume que los participantes siguenun comportamiento determinado:
1 Son completamente honestos, es decir, siguen el protocoloal pie de la letra, o
2 son arbitrariamente maliciosos, donde su comportamientopuede ser totalmente indeterminado
3 (tambien pueden ser honestos, pero curiosos)
Criptografıa y Teorıa de Juegos
Introduccion
Ejemplo
¿Es eso realista?
Criptografıa y Teorıa de Juegos
Introduccion
Ejemplo
Bueno...
Criptografıa y Teorıa de Juegos
Introduccion
Adversarios Racionales
Uno puede considerar a los adversarios como racionales, donderacional se define como la tendencia a buscar el propio beneficio.Por ejemplo,
• Un participante de votacion electronica puede preferir que sucandidato gane, y atacar el sistema para lograrlo
• O preferir desencriptar textos cifrados sobre ciertos mensajespor sobre otros
Para generalizar, consideraremos que un partipante P posee unafuncion de utilidad u, y su objetivo sera maximizar su valor.
Criptografıa y Teorıa de Juegos
Introduccion
Adversarios Racionales
Uno puede considerar a los adversarios como racionales, donderacional se define como la tendencia a buscar el propio beneficio.Por ejemplo,
• Un participante de votacion electronica puede preferir que sucandidato gane, y atacar el sistema para lograrlo
• O preferir desencriptar textos cifrados sobre ciertos mensajespor sobre otros
Para generalizar, consideraremos que un partipante P posee unafuncion de utilidad u, y su objetivo sera maximizar su valor.
Criptografıa y Teorıa de Juegos
Introduccion
Adversarios Racionales
Uno puede considerar a los adversarios como racionales, donderacional se define como la tendencia a buscar el propio beneficio.Por ejemplo,
• Un participante de votacion electronica puede preferir que sucandidato gane, y atacar el sistema para lograrlo
• O preferir desencriptar textos cifrados sobre ciertos mensajespor sobre otros
Para generalizar, consideraremos que un partipante P posee unafuncion de utilidad u, y su objetivo sera maximizar su valor.
Criptografıa y Teorıa de Juegos
Introduccion
Adversarios Racionales
Uno puede considerar a los adversarios como racionales, donderacional se define como la tendencia a buscar el propio beneficio.Por ejemplo,
• Un participante de votacion electronica puede preferir que sucandidato gane, y atacar el sistema para lograrlo
• O preferir desencriptar textos cifrados sobre ciertos mensajespor sobre otros
Para generalizar, consideraremos que un partipante P posee unafuncion de utilidad u, y su objetivo sera maximizar su valor.
Criptografıa y Teorıa de Juegos
Introduccion
Teorıa de Juegos
Definicion
La Teorıa de Juegos es un area de la matematica que utilizamodelos para estudiar interacciones en estructuras formalizadas deincentivos y llevar a cabo procesos de decision.
En nuestro caso, un protocolo puede ser visto como un juego en elcual los participantes tratan de maximizar su beneficio (actuandosegun sus incentivos).
Pero no tan ası, pues el objetivo del protocolo puede ser distintodel de los participantes!
Criptografıa y Teorıa de Juegos
Introduccion
Teorıa de Juegos
Definicion
La Teorıa de Juegos es un area de la matematica que utilizamodelos para estudiar interacciones en estructuras formalizadas deincentivos y llevar a cabo procesos de decision.
En nuestro caso, un protocolo puede ser visto como un juego en elcual los participantes tratan de maximizar su beneficio (actuandosegun sus incentivos).
Pero no tan ası, pues el objetivo del protocolo puede ser distintodel de los participantes!
Criptografıa y Teorıa de Juegos
Introduccion
Teorıa de Juegos
Definicion
La Teorıa de Juegos es un area de la matematica que utilizamodelos para estudiar interacciones en estructuras formalizadas deincentivos y llevar a cabo procesos de decision.
En nuestro caso, un protocolo puede ser visto como un juego en elcual los participantes tratan de maximizar su beneficio (actuandosegun sus incentivos).
Pero no tan ası, pues el objetivo del protocolo puede ser distintodel de los participantes!
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
Ejemplo: La herencia
Un anciano millonario entrega a cada uno de sus hijos una piezadel secreto en donde se encuentran todas sus riquezas. Solo almomento de su muerte los herederos podran reconstruir el secretoy ası conocer la ubicacion de las riquezas.
Sin embargo, los hijos son ambiciosos y cada uno quiere conocer laubicacion de la herencia sin que se enteren los demas.
¿Como puede el anciano asegurarse de que todos ellosconozcan la ubicacion?
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
Ejemplo: La herencia
Un anciano millonario entrega a cada uno de sus hijos una piezadel secreto en donde se encuentran todas sus riquezas. Solo almomento de su muerte los herederos podran reconstruir el secretoy ası conocer la ubicacion de las riquezas.
Sin embargo, los hijos son ambiciosos y cada uno quiere conocer laubicacion de la herencia sin que se enteren los demas.
¿Como puede el anciano asegurarse de que todos ellosconozcan la ubicacion?
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
¡Podemos usar Comparticion de Secreto!
Notemos que
• Cada uno de los participantes desea conocer el secreto s de laubicacion del “tesoro”
• Pero ademas prefieren que la menor cantidad de otrosparticipantes lo conozcan
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
Usemos un esquema de comparticion de secreto, por ejemplo el deShamir.
Sin embargo, el esquema NO funciona. Considere que sonnecesarios t participantes para reconstruir el secreto, y considere laaccion del participante P1:
• Si menos de t− 1 trozos fueron revelados, entonces la accionde P1 no tiene ningun efecto y nadie reconstruye el secreto
• Si mas de t− 1 trozos fueron revelados, entonces todosconocen el secreto y la accion de P1 nuevamente no tieneefecto
• Si exactamente t− 1 trozos han sido revelados, entonces P1
puede conocer el secreto (usando su trozo), y a la vez, al norevelar el suyo, evita que todos los demas conozcan el secreto!
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
Usemos un esquema de comparticion de secreto, por ejemplo el deShamir.
Sin embargo, el esquema NO funciona. Considere que sonnecesarios t participantes para reconstruir el secreto, y considere laaccion del participante P1:
• Si menos de t− 1 trozos fueron revelados, entonces la accionde P1 no tiene ningun efecto y nadie reconstruye el secreto
• Si mas de t− 1 trozos fueron revelados, entonces todosconocen el secreto y la accion de P1 nuevamente no tieneefecto
• Si exactamente t− 1 trozos han sido revelados, entonces P1
puede conocer el secreto (usando su trozo), y a la vez, al norevelar el suyo, evita que todos los demas conozcan el secreto!
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
Usemos un esquema de comparticion de secreto, por ejemplo el deShamir.
Sin embargo, el esquema NO funciona. Considere que sonnecesarios t participantes para reconstruir el secreto, y considere laaccion del participante P1:
• Si menos de t− 1 trozos fueron revelados, entonces la accionde P1 no tiene ningun efecto y nadie reconstruye el secreto
• Si mas de t− 1 trozos fueron revelados, entonces todosconocen el secreto y la accion de P1 nuevamente no tieneefecto
• Si exactamente t− 1 trozos han sido revelados, entonces P1
puede conocer el secreto (usando su trozo), y a la vez, al norevelar el suyo, evita que todos los demas conozcan el secreto!
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
Usemos un esquema de comparticion de secreto, por ejemplo el deShamir.
Sin embargo, el esquema NO funciona. Considere que sonnecesarios t participantes para reconstruir el secreto, y considere laaccion del participante P1:
• Si menos de t− 1 trozos fueron revelados, entonces la accionde P1 no tiene ningun efecto y nadie reconstruye el secreto
• Si mas de t− 1 trozos fueron revelados, entonces todosconocen el secreto y la accion de P1 nuevamente no tieneefecto
• Si exactamente t− 1 trozos han sido revelados, entonces P1
puede conocer el secreto (usando su trozo), y a la vez, al norevelar el suyo, evita que todos los demas conozcan el secreto!
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
Usemos un esquema de comparticion de secreto, por ejemplo el deShamir.
Sin embargo, el esquema NO funciona. Considere que sonnecesarios t participantes para reconstruir el secreto, y considere laaccion del participante P1:
• Si menos de t− 1 trozos fueron revelados, entonces la accionde P1 no tiene ningun efecto y nadie reconstruye el secreto
• Si mas de t− 1 trozos fueron revelados, entonces todosconocen el secreto y la accion de P1 nuevamente no tieneefecto
• Si exactamente t− 1 trozos han sido revelados, entonces P1
puede conocer el secreto (usando su trozo), y a la vez, al norevelar el suyo, evita que todos los demas conozcan el secreto!
Criptografıa y Teorıa de Juegos
Introduccion
Juegos en forma normal
Definicion (Juego en forma normal)
Un juego de n jugadores es de la forma Γ = ({Ai}ni=1, {ui}ni=1),donde cada jugador Pi tiene un conjunto de posibles acciones Ai yuna funcion de utilidad ui : A1 ×A2 × . . .×An 7→ R.
• Todos los jugadores se mueven simultaneamente, donde Pi
escoge una accion ai ∈ Ai.
• El pago de Pi es ui(a1, ..., an)
• El algoritmo (posiblemente probabilıstico) σi que diceque accion tomar por Pi es llamado una estrategia.
Criptografıa y Teorıa de Juegos
Introduccion
Equilibrio de Nash
Sea a = (a1, ..., an) y a−i = (a1, ..., ai−1, ai+1, ..., an)
Definicion (Equilibrio de Nash)
Sea Γ = ({Ai}ni=1, {ui}ni=1) un juego en forma normal, y seaA = Ai × . . .×An. Una tupla a = (a1, . . . , an) ∈ A es unEquilibrio de Nash (estrategico, o “pure-strategy”) si para todo i ypara cualquier a′i ∈ A se tiene que ui(a
′i,a−i) ≤ ui(a).
En otras palabras, para cada participante Pi, seguir las acciones aes la mejor respuesta ante las acciones a−i de los otrosparticpantes.
Teorema de Nash
El resultado mas famoso de John Nash en la Teorıa de Juegosestablece que todo juego estrategico finito tiene al menos unEquilibrio de Nash
Criptografıa y Teorıa de Juegos
Introduccion
Comparticion de Secreto
Luego, asumiendo que al momento de reconstruir hay t∗ ≥ tparticipantes
1 Para cualesquiera t, n, t∗, es un NE el NO revelar el trozo delsecreto
2 Si t∗ > t es un NE para todos los t∗ participantes revelar suparte. Sin embargo, tambien es preferible el NO hacerlo (yaque la utilidad no cambia). Luego es mas probable el NOrevelar.
3 Si t∗ = t, entonces tampoco es un NE revelar, ya que cadauno de los t∗ participantes puede desviarse y no revelar suparte.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolos para Rational Secret Sharing
Veremos 2 protocolos que sı satisfacen las restricciones impuestasaun bajo adversarios racionales
Protocolo (n = 3, t = 3) de Halpern y Teague
1 Al principio de cada iteracion, el dealer ejecuta un esquema deShamir y reparte los trozos a cada participante
2 Durante la iteracion, cada participante Pi lanza una monedacargada ci, tal que Pr[ci = 1] = α
3 Los participantes/jugadores calculan c∗ =⊕ci
4 Si c∗ = ci = 1, entonces Pi revela su parte.
5 Si c∗ = 1 y no han sido revelados los trozos, o exactamente 2trozos fueron revelados, el protocolo aborta.
6 En otro caso, continua a la siguiente iteracion
Criptografıa y Teorıa de Juegos
Introduccion
Protocolos para Rational Secret Sharing
Veremos 2 protocolos que sı satisfacen las restricciones impuestasaun bajo adversarios racionales
Protocolo (n = 3, t = 3) de Halpern y Teague
1 Al principio de cada iteracion, el dealer ejecuta un esquema deShamir y reparte los trozos a cada participante
2 Durante la iteracion, cada participante Pi lanza una monedacargada ci, tal que Pr[ci = 1] = α
3 Los participantes/jugadores calculan c∗ =⊕ci
4 Si c∗ = ci = 1, entonces Pi revela su parte.
5 Si c∗ = 1 y no han sido revelados los trozos, o exactamente 2trozos fueron revelados, el protocolo aborta.
6 En otro caso, continua a la siguiente iteracion
Criptografıa y Teorıa de Juegos
Introduccion
Protocolos para Rational Secret Sharing
Veremos 2 protocolos que sı satisfacen las restricciones impuestasaun bajo adversarios racionales
Protocolo (n = 3, t = 3) de Halpern y Teague
1 Al principio de cada iteracion, el dealer ejecuta un esquema deShamir y reparte los trozos a cada participante
2 Durante la iteracion, cada participante Pi lanza una monedacargada ci, tal que Pr[ci = 1] = α
3 Los participantes/jugadores calculan c∗ =⊕ci
4 Si c∗ = ci = 1, entonces Pi revela su parte.
5 Si c∗ = 1 y no han sido revelados los trozos, o exactamente 2trozos fueron revelados, el protocolo aborta.
6 En otro caso, continua a la siguiente iteracion
Criptografıa y Teorıa de Juegos
Introduccion
Protocolos para Rational Secret Sharing
Veremos 2 protocolos que sı satisfacen las restricciones impuestasaun bajo adversarios racionales
Protocolo (n = 3, t = 3) de Halpern y Teague
1 Al principio de cada iteracion, el dealer ejecuta un esquema deShamir y reparte los trozos a cada participante
2 Durante la iteracion, cada participante Pi lanza una monedacargada ci, tal que Pr[ci = 1] = α
3 Los participantes/jugadores calculan c∗ =⊕ci
4 Si c∗ = ci = 1, entonces Pi revela su parte.
5 Si c∗ = 1 y no han sido revelados los trozos, o exactamente 2trozos fueron revelados, el protocolo aborta.
6 En otro caso, continua a la siguiente iteracion
Criptografıa y Teorıa de Juegos
Introduccion
Protocolos para Rational Secret Sharing
Veremos 2 protocolos que sı satisfacen las restricciones impuestasaun bajo adversarios racionales
Protocolo (n = 3, t = 3) de Halpern y Teague
1 Al principio de cada iteracion, el dealer ejecuta un esquema deShamir y reparte los trozos a cada participante
2 Durante la iteracion, cada participante Pi lanza una monedacargada ci, tal que Pr[ci = 1] = α
3 Los participantes/jugadores calculan c∗ =⊕ci
4 Si c∗ = ci = 1, entonces Pi revela su parte.
5 Si c∗ = 1 y no han sido revelados los trozos, o exactamente 2trozos fueron revelados, el protocolo aborta.
6 En otro caso, continua a la siguiente iteracion
Criptografıa y Teorıa de Juegos
Introduccion
Protocolos para Rational Secret Sharing
Veremos 2 protocolos que sı satisfacen las restricciones impuestasaun bajo adversarios racionales
Protocolo (n = 3, t = 3) de Halpern y Teague
1 Al principio de cada iteracion, el dealer ejecuta un esquema deShamir y reparte los trozos a cada participante
2 Durante la iteracion, cada participante Pi lanza una monedacargada ci, tal que Pr[ci = 1] = α
3 Los participantes/jugadores calculan c∗ =⊕ci
4 Si c∗ = ci = 1, entonces Pi revela su parte.
5 Si c∗ = 1 y no han sido revelados los trozos, o exactamente 2trozos fueron revelados, el protocolo aborta.
6 En otro caso, continua a la siguiente iteracion
Criptografıa y Teorıa de Juegos
Introduccion
Protocolos para Rational Secret Sharing
Veremos 2 protocolos que sı satisfacen las restricciones impuestasaun bajo adversarios racionales
Protocolo (n = 3, t = 3) de Halpern y Teague
1 Al principio de cada iteracion, el dealer ejecuta un esquema deShamir y reparte los trozos a cada participante
2 Durante la iteracion, cada participante Pi lanza una monedacargada ci, tal que Pr[ci = 1] = α
3 Los participantes/jugadores calculan c∗ =⊕ci
4 Si c∗ = ci = 1, entonces Pi revela su parte.
5 Si c∗ = 1 y no han sido revelados los trozos, o exactamente 2trozos fueron revelados, el protocolo aborta.
6 En otro caso, continua a la siguiente iteracion
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n = 3, t = 3) de Halpern y Teague
Para ver que el protocolo funciona, asuma que P1, P2 siguen elprotocolo y considere si P3 deberıa desviarse o no.
• Primero, no hay incentivo para P3 de “cargar” la moneda c3
para que sea 0 con alta probabilidad, ya que si c3 = 0,entonces P1 o P2 no revelara su parte.
• Tampoco lo es que cargue c3 hacia 1, ya que, aunque logreque el secreto sea reconstruido antes, no tendra efecto en lautilidad de P3.
• Si c∗ = 0 o c3 = 0, no hay incentivo para desviarse.
• Si c∗ = c3 = 1, P3 no sabe si c1 = c2 = 1 o 0, por lo que siP3 no revela su parte se arriesga a no conocer el secreto.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n = 3, t = 3) de Halpern y Teague
Para ver que el protocolo funciona, asuma que P1, P2 siguen elprotocolo y considere si P3 deberıa desviarse o no.
• Primero, no hay incentivo para P3 de “cargar” la moneda c3
para que sea 0 con alta probabilidad, ya que si c3 = 0,entonces P1 o P2 no revelara su parte.
• Tampoco lo es que cargue c3 hacia 1, ya que, aunque logreque el secreto sea reconstruido antes, no tendra efecto en lautilidad de P3.
• Si c∗ = 0 o c3 = 0, no hay incentivo para desviarse.
• Si c∗ = c3 = 1, P3 no sabe si c1 = c2 = 1 o 0, por lo que siP3 no revela su parte se arriesga a no conocer el secreto.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n = 3, t = 3) de Halpern y Teague
Para ver que el protocolo funciona, asuma que P1, P2 siguen elprotocolo y considere si P3 deberıa desviarse o no.
• Primero, no hay incentivo para P3 de “cargar” la moneda c3
para que sea 0 con alta probabilidad, ya que si c3 = 0,entonces P1 o P2 no revelara su parte.
• Tampoco lo es que cargue c3 hacia 1, ya que, aunque logreque el secreto sea reconstruido antes, no tendra efecto en lautilidad de P3.
• Si c∗ = 0 o c3 = 0, no hay incentivo para desviarse.
• Si c∗ = c3 = 1, P3 no sabe si c1 = c2 = 1 o 0, por lo que siP3 no revela su parte se arriesga a no conocer el secreto.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n = 3, t = 3) de Halpern y Teague
Para ver que el protocolo funciona, asuma que P1, P2 siguen elprotocolo y considere si P3 deberıa desviarse o no.
• Primero, no hay incentivo para P3 de “cargar” la moneda c3
para que sea 0 con alta probabilidad, ya que si c3 = 0,entonces P1 o P2 no revelara su parte.
• Tampoco lo es que cargue c3 hacia 1, ya que, aunque logreque el secreto sea reconstruido antes, no tendra efecto en lautilidad de P3.
• Si c∗ = 0 o c3 = 0, no hay incentivo para desviarse.
• Si c∗ = c3 = 1, P3 no sabe si c1 = c2 = 1 o 0, por lo que siP3 no revela su parte se arriesga a no conocer el secreto.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n = 3, t = 3) de Halpern y Teague
Para ver que el protocolo funciona, asuma que P1, P2 siguen elprotocolo y considere si P3 deberıa desviarse o no.
• Primero, no hay incentivo para P3 de “cargar” la moneda c3
para que sea 0 con alta probabilidad, ya que si c3 = 0,entonces P1 o P2 no revelara su parte.
• Tampoco lo es que cargue c3 hacia 1, ya que, aunque logreque el secreto sea reconstruido antes, no tendra efecto en lautilidad de P3.
• Si c∗ = 0 o c3 = 0, no hay incentivo para desviarse.
• Si c∗ = c3 = 1, P3 no sabe si c1 = c2 = 1 o 0, por lo que siP3 no revela su parte se arriesga a no conocer el secreto.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n = 3, t = 3) de Halpern y Teague
• El protocolo puede extenderse para n ≥ 3 y t ≥ 2
• Sin embargo, establecen que es imposible para n = 2
• Asumen demasiadas restricciones sobre el modelo
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n ≥ 2, t ≥ 2) de Gordon y Katz
Suponga que el dealer tiene un secreto s que pertence a unconjunto S ⊂ F , y que los participantes conocen S.
Protocolo de Gordon y Katz
1 Al comienzo de cada iteracion, el dealer invoca el esquema deShamir sobre s con probabilidad β
2 Y, con probabilidad 1− β, invoca Shamir sobre s ∈ F \ S3 Luego los trozos son distribuidos a los participantes
4 Los participantes comunican sus trozos entre sı,reconstruyendo un secreto s′ (si alguno se niega, se aborta elprotocolo)
5 Si s′ ∈ S, entonces es el verdadero secreto y fue reconstruido,sino (es el falso), continuan a la siguiente iteracion.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n ≥ 2, t ≥ 2) de Gordon y Katz
Suponga que el dealer tiene un secreto s que pertence a unconjunto S ⊂ F , y que los participantes conocen S.
Protocolo de Gordon y Katz
1 Al comienzo de cada iteracion, el dealer invoca el esquema deShamir sobre s con probabilidad β
2 Y, con probabilidad 1− β, invoca Shamir sobre s ∈ F \ S3 Luego los trozos son distribuidos a los participantes
4 Los participantes comunican sus trozos entre sı,reconstruyendo un secreto s′ (si alguno se niega, se aborta elprotocolo)
5 Si s′ ∈ S, entonces es el verdadero secreto y fue reconstruido,sino (es el falso), continuan a la siguiente iteracion.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n ≥ 2, t ≥ 2) de Gordon y Katz
Suponga que el dealer tiene un secreto s que pertence a unconjunto S ⊂ F , y que los participantes conocen S.
Protocolo de Gordon y Katz
1 Al comienzo de cada iteracion, el dealer invoca el esquema deShamir sobre s con probabilidad β
2 Y, con probabilidad 1− β, invoca Shamir sobre s ∈ F \ S
3 Luego los trozos son distribuidos a los participantes
4 Los participantes comunican sus trozos entre sı,reconstruyendo un secreto s′ (si alguno se niega, se aborta elprotocolo)
5 Si s′ ∈ S, entonces es el verdadero secreto y fue reconstruido,sino (es el falso), continuan a la siguiente iteracion.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n ≥ 2, t ≥ 2) de Gordon y Katz
Suponga que el dealer tiene un secreto s que pertence a unconjunto S ⊂ F , y que los participantes conocen S.
Protocolo de Gordon y Katz
1 Al comienzo de cada iteracion, el dealer invoca el esquema deShamir sobre s con probabilidad β
2 Y, con probabilidad 1− β, invoca Shamir sobre s ∈ F \ S3 Luego los trozos son distribuidos a los participantes
4 Los participantes comunican sus trozos entre sı,reconstruyendo un secreto s′ (si alguno se niega, se aborta elprotocolo)
5 Si s′ ∈ S, entonces es el verdadero secreto y fue reconstruido,sino (es el falso), continuan a la siguiente iteracion.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n ≥ 2, t ≥ 2) de Gordon y Katz
Suponga que el dealer tiene un secreto s que pertence a unconjunto S ⊂ F , y que los participantes conocen S.
Protocolo de Gordon y Katz
1 Al comienzo de cada iteracion, el dealer invoca el esquema deShamir sobre s con probabilidad β
2 Y, con probabilidad 1− β, invoca Shamir sobre s ∈ F \ S3 Luego los trozos son distribuidos a los participantes
4 Los participantes comunican sus trozos entre sı,reconstruyendo un secreto s′ (si alguno se niega, se aborta elprotocolo)
5 Si s′ ∈ S, entonces es el verdadero secreto y fue reconstruido,sino (es el falso), continuan a la siguiente iteracion.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n ≥ 2, t ≥ 2) de Gordon y Katz
Suponga que el dealer tiene un secreto s que pertence a unconjunto S ⊂ F , y que los participantes conocen S.
Protocolo de Gordon y Katz
1 Al comienzo de cada iteracion, el dealer invoca el esquema deShamir sobre s con probabilidad β
2 Y, con probabilidad 1− β, invoca Shamir sobre s ∈ F \ S3 Luego los trozos son distribuidos a los participantes
4 Los participantes comunican sus trozos entre sı,reconstruyendo un secreto s′ (si alguno se niega, se aborta elprotocolo)
5 Si s′ ∈ S, entonces es el verdadero secreto y fue reconstruido,sino (es el falso), continuan a la siguiente iteracion.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n ≥ 2, t ≥ 2) de Gordon y Katz
Veremos que funciona para t = n = 2
Sin perdida de generalidad, asuma que P2 sigue el protocolo yveamos si P1 puede desviarse en la primera iteracion:
• La unica posibilidad de desviarse de P1 es no revelar su parte,en este caso, este conoce el secreto (mientras que P2 no) conprobabilidad β, pero con probabilidad 1− β nunca lo hara.
Criptografıa y Teorıa de Juegos
Introduccion
Protocolo (n ≥ 2, t ≥ 2) de Gordon y Katz
Sea U+ la utilidad de P1 si descubre el secreto pero P2 no. U siambos lo descubren, y U− si ninguno lo hace. Tenemos queU+ > U > U−.
Tenemos que, si P1 sigue el protocolo, su utilidad esperada es U .Si P1 se desvıa, su utilidad esperada es β·U+ + (1− β)·U−,ası que mientras
U > β·U+ + (1− β)·U−
entonces P1 siempre seguira el protocolo, para un β apropiado.
Criptografıa y Teorıa de Juegos
Introduccion
Conclusiones
• Aun existen muchas variantes sobre supuestos en Criptografıa,donde cada una tiene una aplicacion especıfica o una formaparticular de abordarla
• Vimos como la Teorıa de Juegos se complementa muy biencon algunos protocolos, haciendo posible nuevos supuestos
• Los esquemas de comparticion de secreto son la base paraconstrucciones mas complejas, como la Evaluacion “Justa” deFunciones Seguras (Computacion Multipartita Racional)
• Y finalmente el millonario se podra morir tranquilo.
Criptografıa y Teorıa de Juegos
Introduccion
Conclusiones
• Aun existen muchas variantes sobre supuestos en Criptografıa,donde cada una tiene una aplicacion especıfica o una formaparticular de abordarla
• Vimos como la Teorıa de Juegos se complementa muy biencon algunos protocolos, haciendo posible nuevos supuestos
• Los esquemas de comparticion de secreto son la base paraconstrucciones mas complejas, como la Evaluacion “Justa” deFunciones Seguras (Computacion Multipartita Racional)
• Y finalmente el millonario se podra morir tranquilo.
Criptografıa y Teorıa de Juegos
Introduccion
Conclusiones
• Aun existen muchas variantes sobre supuestos en Criptografıa,donde cada una tiene una aplicacion especıfica o una formaparticular de abordarla
• Vimos como la Teorıa de Juegos se complementa muy biencon algunos protocolos, haciendo posible nuevos supuestos
• Los esquemas de comparticion de secreto son la base paraconstrucciones mas complejas, como la Evaluacion “Justa” deFunciones Seguras (Computacion Multipartita Racional)
• Y finalmente el millonario se podra morir tranquilo.
Criptografıa y Teorıa de Juegos
Introduccion
Conclusiones
• Aun existen muchas variantes sobre supuestos en Criptografıa,donde cada una tiene una aplicacion especıfica o una formaparticular de abordarla
• Vimos como la Teorıa de Juegos se complementa muy biencon algunos protocolos, haciendo posible nuevos supuestos
• Los esquemas de comparticion de secreto son la base paraconstrucciones mas complejas, como la Evaluacion “Justa” deFunciones Seguras (Computacion Multipartita Racional)
• Y finalmente el millonario se podra morir tranquilo.
Criptografıa y Teorıa de Juegos
Introduccion
Referencias
A. Shamir. How to Share a Secret. Comm. ACM, 1979.
J. Katz. Bridging Game Theory and Cryptography: RecentResults and Future Directions.
J. Halpern y V. Teague. Rational Secret Sharing andMultiparty Computation. 36th Annual ACM Symposium onTheory of Computing. 2004.
S. Dov Gordon y J. Katz. Rational Secret Sharing, Revisited.2006.
Y. Dodis y T. Rabin. Cryptography and Game Theory.
Criptografıa y Teorıa de Juegos