Cómo compartir un secreto

Mauricio Quezada

21/01/11

Criptografía

Queremos distribuir un secreto S entre n participantes

Dividiéndolo en n trozos

De tal forma que

• t - 1 o menos trozos no permiten reconstruir el secreto

• El conocimiento de t o más trozos permite reconstruir el secreto S

Adi Shamir’s Secret Sharing

• Ideado en 1979

• Shamir es la S de RSA

Cómo se hace

• Genere un polinomio p de grado t-1 con coeficientes aleatorios

• De tal forma que

2 1

0 1 2 1( ) ... t

tx a xp x a a xa

0 (0)a p S

• Los trozos son de la forma

• Y entregados a cada participante

( , ( ))iD i p i 1..i n

¿Cómo se reconstruye S?

• Con t o más trozos, es posible interpolar el polinomio

• Recuperando la fórmula original

• Y por lo tanto, recuperando 0a S

¿Y por qué funciona?

¿Y por qué funciona?

¿Es seguro?

¿¡ Y para qué \u001A sirve !?

• Asegurar una llave privada

¿¡ Y para qué \u001A sirve !?

• Asegurar una llave privada

• Tener una jerarquía para hacer firmas digitales

¿¡ Y para qué \u001A sirve !?

• Asegurar una llave privada

• Tener una jerarquía para hacer firmas digitales

• Distribuir la fórmula de la Coca-Cola

¿Y funciona en la práctica?

¿Y funciona en la práctica?

NO

Exageré, sí funciona

• Bajo ciertos supuestos…

– Los participantes son honestos y desean que todos conozcan el secreto

• Existen muchos protocolos para distintas suposiciones

SSSS

• http://point-at-infinity.org/ssss/

• t = 3

• n = 10

t=3, n=10

t=3, n=10

t=3, n=10

Referencias

• Shamir, Adi (1979). "How to share a secret". Communications of the ACM 22 (11)

• Simpsons, The (1996). “The Curse of the FlyingHellfish”. Fox Broadcasting Company.

• SSSS - http://point-at-infinity.org/ssss/

BONUS TRACK