Asymptotically Ideal Hierarchical Secret Sharing Based on CRT for Integer Ring

Resumen Técnico: Esquema de Compartición de Secretos Jerárquico Asintóticamente Ideal basado en el Teorema Chino del Resto

1. Planteamiento del Problema

La Compartición de Secretos (Secret Sharing - SS) es un método fundamental en criptografía para distribuir un secreto entre un grupo de participantes, de modo que solo ciertos subconjuntos autorizados puedan reconstruirlo.

• Limitación de los esquemas tradicionales: En el esquema clásico de umbral $(t, n)$ de Shamir, todos los participantes tienen el mismo nivel de privilegio. Sin embargo, en escenarios prácticos (como corporaciones o gobiernos), es necesario asignar diferentes niveles de autoridad a distintos participantes.
• Esquemas Jerárquicos (HSS): Para abordar esto, se desarrollaron esquemas HSS que dividen a los participantes en subconjuntos jerárquicos ($P_1, P_2, \dots, P_m$) con umbrales distintos ($t_1 < t_2 < \dots < t_m$). Existen dos estructuras principales:
  • Disyuntiva (DHSS): Un grupo autorizado si cumple el umbral de cualquiera de los niveles jerárquicos acumulados.
  • Conjuntiva (CHSS): Un grupo autorizado solo si cumple los umbrales de todos los niveles jerárquicos acumulados.
• El problema actual: Las soluciones existentes basadas en el Teorema Chino del Resto (CRT) para anillos enteros presentan una dicotomía:
  1. O bien son inseguras (ej. esquemas de Harn et al., Ersoy et al., Tiplea et al. y Yang et al. han sido demostrados como vulnerables en trabajos previos de los mismos autores).
  2. O bien son seguras pero no ideales, con una tasa de información ($\rho$) estrictamente menor a $1/2$ o menor a 1, lo que implica un desperdicio de recursos al distribuir "shares" (comparticiones) más grandes que el secreto.
  3. Los esquemas ideales existentes (basados en interpolación de Birkhoff o politopos) requieren complejidad computacional exponencial para el distribuidor (dealer) o verificación de matrices complejas.

2. Metodología

Los autores proponen dos nuevos esquemas (uno disyuntivo y uno conjuntivo) que combinan tres herramientas matemáticas clave para lograr seguridad y eficiencia:

1. Teorema Chino del Resto (CRT) para Anillos Enteros: Se utiliza para la reconstrucción del secreto y para permitir tamaños de "shares" flexibles. Se basa en una secuencia de primos coprimos $L = \{m_0, m_1, \dots, m_n\}$.
2. Secuencias $k$-compactas de primos: Se introduce una estructura específica de primos donde $km_0 < m_i < km_0 + m_0^\theta$ (con $k \ge 1, \theta \in (0,1)$). Esta propiedad es crucial para garantizar que la restricción de Asmuth-Bloom se cumpla asintóticamente y para controlar la entropía condicional.
3. Funciones de Una Vía (One-way Functions): Se utilizan funciones hash $h_\ell(\cdot)$ públicas para enmascarar los valores intermedios ($y_\ell$) en las "shares" de los participantes de niveles inferiores. Esto previene que los participantes no autorizados puedan deducir información sobre el secreto o los valores de niveles superiores, resolviendo las vulnerabilidades de esquemas CRT anteriores.

Fases del Esquema Propuesto:

• Generación de Shares:
  • El distribuidor genera primos coprimos asignados a cada participante.
  • Para el secreto $s$, se generan valores aleatorios $y_\ell$ relacionados con $s$ y la jerarquía.
  • Se calculan "shares" parciales. Para participantes en niveles inferiores, el share es un valor aleatorio $c_i$. Para participantes en niveles superiores, el share es una función de $y_\ell$ y la función de una vía.
  • Se publican valores auxiliares $w_i^{(\ell)}$ que permiten a los participantes autorizados recuperar $y_\ell$ sin revelar $s$ a no autorizados.
• Reconstrucción:
  • Los participantes autorizados utilizan sus shares y los valores públicos para reconstruir los valores $y_\ell$ mediante CRT.
  • Finalmente, recuperan $s = y_\ell \pmod{m_0}$ (en DHSS) o combinan residuos para obtener $s$ (en CHSS).

3. Contribuciones Clave

El artículo presenta las siguientes contribuciones originales:

1. Construcción de Esquemas HSS Asintóticamente Ideales: Se proponen por primera vez esquemas DHSS y CHSS basados en CRT para anillos enteros que son seguros y asintóticamente ideales.
2. Tasa de Información Asintótica a 1: A diferencia de los esquemas CRT anteriores que tenían $\rho < 1/2$, los esquemas propuestos logran que la tasa de información $\rho$ tienda a 1 a medida que el tamaño del secreto ($m_0$) aumenta. Esto significa que el tamaño de la "share" es casi igual al tamaño del secreto.
3. Seguridad Comprobada: Se demuestra que los esquemas son asintóticamente perfectos. Esto significa que cualquier subconjunto no autorizado obtiene información nula (o despreciable) sobre el secreto cuando el tamaño del secreto es suficientemente grande.
4. Flexibilidad y Eficiencia:
   • Permiten tamaños de shares flexibles (los participantes de niveles superiores pueden tener shares más grandes si es necesario, aunque el esquema optimiza esto).
   • La complejidad computacional del distribuidor y de los participantes es polinómica, evitando la complejidad exponencial de los esquemas ideales anteriores basados en politopos.
5. Corrección de Vulnerabilidades: Se supera la inseguridad de esquemas previos (como los de Ersoy, Tiplea, etc.) mediante la integración correcta de funciones de una vía y la estructura de secuencias $k$-compactas.

4. Resultados

• Análisis de Seguridad: Se demuestra teóricamente (Teoremas 2 y 4) que la entropía condicional del secreto dado el conocimiento de un grupo no autorizado tiende a la entropía del secreto mismo ($\Delta \to 0$) a medida que $m_0 \to \infty$.
• Tasa de Información: Se demuestra (Teorema 3 y 5) que para secuencias 1-compactas, la tasa de información $\rho = \frac{\log_2 m_0}{\log_2 m_n}$ tiende a 1, ya que $m_n \approx m_0 + m_0^\theta$ y $\theta < 1$.
• Comparación: Las tablas del artículo (Tabla 1 y 2) muestran que el esquema propuesto es el único que cumple simultáneamente con:
  • Seguridad (Sí).
  • Soporte para tamaños de shares flexibles (Sí).
  • Perfectitud asintótica (Sí).
  • Tasa de información que tiende a 1 (Sí).
  • Complejidad polinómica (Sí).

5. Significado e Impacto

Este trabajo es significativo porque cierra una brecha importante en la criptografía de compartición de secretos:

• Resuelve el dilema Seguridad vs. Eficiencia: Antes, los investigadores debían elegir entre esquemas CRT rápidos pero inseguros/ineficientes, o esquemas ideales seguros pero computacionalmente costosos. Este trabajo ofrece lo mejor de ambos mundos.
• Aplicabilidad Práctica: Al ser asintóticamente ideales y tener complejidad polinómica, estos esquemas son viables para implementaciones reales en sistemas donde los participantes tienen diferentes niveles de autoridad (ej. bancos, gobiernos, gestión de claves corporativas) sin incurrir en sobrecarga de almacenamiento o procesamiento.
• Avance Teórico: Proporciona una nueva metodología para construir esquemas jerárquicos ideales utilizando el Teorema Chino del Resto, estableciendo un nuevo estándar para futuras investigaciones en este dominio.

En conclusión, Ding et al. han desarrollado una solución robusta que combina la flexibilidad del CRT con la seguridad de las funciones de una vía, logrando por primera vez esquemas jerárquicos ideales, seguros y eficientes para anillos enteros.