Esquema de Shamir

Es una forma de compartición de secretos donde un secreto se divide en partes y se da a cada participante una sola: todas o parte de ellas son necesarias para reconstruir el secreto.

El algoritmo basa su funcionamiento en una propiedad de los polinomios interpoladores[1]​ y fue desarrollado por el criptógrafo israelí Adi Shamir, que lo presentó en 1979.

[2]​ Formalmente, nuestro objetivo es dividir un conjunto de datos

de manera que: Esta combinación se denomina combinación o esquema de umbral

se requiere la concurrencia de todos los participantes para reconstruir el secreto.

La idea esencial de la combinación de umbral de Shamir es que dos puntos son suficientes para definir una línea recta, tres puntos lo son para definir una parábola, cuatro para definir una curva cúbica y así sucesivamente.

Es decir, son necesarios

puntos para definir un polinomio de grado

Supongamos que queremos trabajar con un umbral de

para compartir un secreto

(cualquier número, sin pérdida de generalidad) siendo

determina la fortaleza del sistema.

Eligiendo al azar

, se construye el polinomio

puntos a partir del mismo, por ejemplo determinamos que

de lo que se deriva

A todo participante en el secreto se le da un punto (un par de valores, el de entrada y el de salida para el polinomio) Dado cualquier subconjunto de

entre estos pares, podemos calcular los coeficientes del polinomio mediante interpolación y luego despejar

Supongamos que el secreto es el número de una tarjeta de crédito: 1234

Queremos dividir el secreto en seis partes

, de forma que cualquier subconjunto

sea suficiente para reconstruir el secreto.

Al azar obtenemos

números: por ejemplo, 166 y 94.

El polinomio con el que operaremos será por lo tanto:

Calculamos seis puntos a partir del polinomio:

Damos a cada partícipe un único punto, que comprende el valor

Para reconstruir el secreto bastará con tres puntos.

Usamos la interpolación polinómica de Lagrange:

Teniendo en cuenta que el secreto es el coeficiente de