Informe sobre estructuras de acceso

2. Esquemas para compartir secretos

Los esquemas para compartir secretos son la pieza esencial de la criptografía distribuida, dado que éstos permiten definir políticas de acceso a recursos compartidos por un conjunto de usuarios.

En un esquema para compartir secretos se reparte el valor de un secreto en fragmentos entre los participantes de un conjunto 𝒫 = {P₁,…,P_n}, de forma que sólo ciertos subconjuntos, denominados autorizados, pueden reconstruir el secreto a partir de su información privada.

Los esquemas para compartir secretos se introdujeron de forma independiente por Blackley [4] y Shamir [17] en 1979.

La familia de subconjuntos de 𝒫 autorizados Γ se denomina estructura de acceso y es monótona, es decir, si un subconjunto A contiene un subconjunto B autorizado, entonces A también debe ser autorizado.

En un esquema para compartir secretos, con estructura de acceso Γ y conjunto de posibles secretos K, a partir de un valor secreto s ∈ K y de una cierta elección aleatoria, cada participante P_i recibe privadamente un fragmento s_i ∈ S_i, donde S_i denota el conjunto de posibles fragmentos de P_i. Normalmente, se exige que el esquema de compartir secretos sea perfecto, es decir,

1. Los subconjuntos autorizados, A ∈ Γ, pueden reconstruir el valor del secreto s a partir de sus fragmentos s_A = {s_i∣P_i ∈ A}. Es decir, para cualquier A ∈ Γ existe un único valor posible del secreto s compatible con los fragmentos s_A.
2. Los participantes de un subconjunto no autorizado no pueden obtener ninguna información sobre el secreto a partir del valor de sus fragmentos. Es decir, si A ⁄∈ Γ todos los valores posibles del secreto s permanecen equiprobables, aún conociendo los fragmentos s_A.

En algunas ocasiones, la segunda propiedad se relaja, permitiendo que algunos conjuntos no autorizados sean capaces de adquirir cierta información limitada sobre el secreto, pero en este documento solamente trataremos el caso perfecto.

Los primeros esquemas de compartir secretos que se introdujeron utilizaban la llamada estructura de acceso de umbral, en la que un conjunto A es autorizado si el número de participantes que contiene iguala o supera cierto umbral t, independientemente de la identidad de los mismos. A continuación describiremos el esquema de umbral de Shamir, que es quizás el esquema para compartir secretos más ampliamente utilizado.

2.1. El esquema de Shamir

Consideremos el conjunto de participantes 𝒫 = {P₁,P₂,...,P_n} y un entero t tal que 1 ≤ t ≤ n. La estructura de acceso Γ es la de umbral (t,n), en la que un conjunto A es autorizado si consiste en t o más participantes. El conjunto de posibles secretos es un cuerpo finito, que por simplicidad, vamos a suponer que es el cuerpo primo ℤ_p, siendo p un número primo. En todo caso, el tamaño del cuerpo, p, debe ser estrictamente mayor que el número de participantes, n.

En la fase inicial, a cada participante se le asigna un elemento x_i del cuerpo ℤ_p, de modo que los valores x_i son todos no nulos y diferentes entre si. Los valores x_i así como el tamaño del conjunto de secretos, p ,forman parte de la descripción pública del esquema.

Para distribuir un secreto s ∈ ℤ_p se toma al azar un polinomio de grado menor o igual que t − 1, r(x), tal que r(0) = s. Cada participante recibe como fragmento s_i = r(x_i). Debido a que el valor del secreto y los coeficientes del polinomio han de mantenerse secretos, esta fase la lleva a cabo una entidad especial de confianza D llamada distribuidor.

Veamos un ejemplo: En ℤ₁₇ diseñamos un esquema de umbral (3, 4), los participantes son P₁, P₂, P₃, P₄ y los elementos asignados son x₁ = 1, x₂ = 2, x₃ = 3, x₄ = 6, respectivamente. El valor secreto a repartir es s = 2 y el polinomio elegido por el distribuidor es r(x) = 2x² − 4x + 2. Entonces, los fragmentos de cada participante serán s₁ = 0, s₂ = 2, s₃ = 8, s₄ = 1, respectivamente. Ahora, los participantes P₁, P₂ y P₃ pueden colaborar entre ellos para construir el único polinomio de grado menor o igual que 3 que pasa por los puntos (1, 0), (2, 2) y (3, 8), que debe coincidir con r(x). El término independiente r(0) es exactamente el secreto compartido.

Por otra parte, si sólo colaborasen los participantes P₁ y P₂, para cualquier valor del secreto s existe un único polinomio de grado menor o igual que 3 que pasa por los puntos correspondientes, (1, 0) y (2, 2), y por el punto (0,s). Por tanto, aún conociendo esos dos fragmentos, el secreto sigue siendo completamente desconocido, ya que todos los valores posibles siguen siendo equiprobables.

A diferencia de otros protocolos criptográficos, la seguridad del esquema de Shamir es incondicional, dado que un adversario con capacidad computacional ilimitada no puede extraer información alguna sobre el secreto s aunque conociese t − 1 fragmentos del mismo.

2.1.1. Valores extremos del umbral

Los valores extremos del umbral, es decir los esquemas de umbral (n,n) y los de umbral (1,n), merecen atención especial. En el esquema (n,n) la reconstrucción del secreto requiere la colaboración de todos los participantes, lo que admite una construcción sumamente sencilla: Cada participante P_i recibe un fragmento aleatorio s_i ∈ ℤ_p, y el secreto compartido es la suma (módulo p) de todos ellos, s = s₁ + … + s_n.

El otro caso extremo es trivial, ya que la estructura de umbral (1,n) justamente indica que cada participante puede individualmente recuperar el secreto. Por ello, el esquema consiste en entregar directamente dicho secreto a cada participante, es decir, s_i = s.

Debemos observar que en las dos construcciones anteriores desaparece la limitación sobre el tamaño del cuerpo, p, ya que puede ser ahora arbitrariamente pequeño (incluso p = 2) e independiente del número de participantes.

Los dos casos extremos de estructuras de umbral resultan especialmente útiles como piezas auxiliares en la definición de estructuras de acceso más complejas y versátiles, como veremos en secciones posteriores.

2.1.2. Propiedades homomórficas

Un aspecto a tener en cuenta en algunos esquemas de compartición de secretos es la posibilidad de efectuar operaciones básicas sobre distintos secretos sin tener que reconstruirlos previamente, es decir, operando únicamente sobre los fragmentos. Concretamente, un esquema para compartir secretos es aditivamente homomórfico sobre ℤ_p si cada participante P_i puede combinar los fragmentos s_i^(a) y s _i^(b) recibidos en la compartición de dos secretos s^(a) y s^(b), respectivamente, para obtener un nuevo fragmento del secreto suma s^(a) + s^(b).

El esquema de Shamir disfruta de esa propiedad, dado que la suma de los fragmentos de dos secretos repartidos con el mismo umbral t equivale a la compartición de la suma de los dos secretos, también con el mismo umbral. En efecto, cada secreto se reparte por medio de un polinomio aleatorio, de modo que la suma de polinomios corresponderá tanto a la suma de los secretos como a la suma de los fragmentos de cada participante.

El esquema también puede dotarse de propiedades homomórficas multiplicativas, pero ello requiere añadir comunicaciones adicionales entre los participantes.

2.2. Eficiencia de los esquemas para compartir secretos

Existen varias medidas sobre la eficiencia de un esquema para compartir secretos. Enumeramos a continuación los aspectos más relevantes a tener en cuenta desde el punto de vista de las aplicaciones de los mismos:

• El tamaño de los fragmentos recibidos por los participantes, que es la medida de la cantidad de información secreta que éstos deben custodiar. Puede cuantificarse de varias maneras, que comúnmente son el máximo de los tamaños, o el valor promedio entre los distintos participantes.
• La complejidad del algoritmo de generación de los parámetros públicos del esquema y de los fragmentos. Para algunas estructuras de acceso diferentes de las de umbral solamente se conocen esquemas de compartición de secretos que o bien son imprácticos por su complejidad, o bien éstos requieren la costosa construcción de ciertos objetos combinatorios especiales en el proceso de inicialización.
• La complejidad del algoritmo de reconstrucción del secreto. En una aplicación práctica de los esquemas para compartir secretos, una excesiva complejidad de cálculo en el algoritmo de reconstrucción del secreto puede degradar sustancialmente las prestaciones de un protocolo criptográfico. Por ejemplo, la reconstrucción del secreto, o un procedimiento relacionado con la misma, es requerida durante la generación de una firma digital conjunta entre varios participantes.
• El tamaño mínimo requerido para el conjunto de secretos. Por ejemplo, el esquema de Shamir descrito anteriormente impone una seria restricción en el tamaño mínimo del conjunto de secretos en función del número de participantes. Esto puede tener un impacto sustancial en protocolos criptográficos con un elevado número de participantes en los que se comparten números aleatorios secretos pequeños, o incluso bits.

Se demuestra que en un esquema para compartir secretos perfecto, el tamaño de los fragmentos no puede ser inferior al del secreto. Si se da la igualdad, el esquema se denomina ideal.

No todas las estructuras de acceso admiten esquemas ideales, por lo que la eficiencia del esquema estará limitada en particular por la estructura de acceso que pretenda implementar. Como se desprende de la propia existencia del esquema de Shamir, las estructuras de umbral admiten esquemas ideales.