Secret sharing with additive access structures from correlated random variables

Resumen Técnico: Distribución de Secretos con Estructuras de Acceso Aditivas a partir de Variables Aleatorias Correlacionadas

Planteamiento del Problema
El artículo aborda el problema de la distribución de secretos en un entorno dinámico donde el conjunto de participantes autorizados (la estructura de acceso) evoluciona con el tiempo. Los modelos tradicionales de distribución de secretos suelen asumir una estructura de acceso fija; si la estructura cambia, los fragmentos (shares) deben redistribuirse, lo que genera ineficiencia. El modelo de "Estructura de Acceso Evolutiva" (EAS, por sus siglas en inglés) permite un crecimiento monotónico, pero asume que los participantes se incorporan secuencialmente y reciben sus fragmentos a través de canales privados.

Este trabajo introduce el modelo de Estructura de Acceso Aditiva (AAS), el cual difiere del EAS en dos aspectos fundamentales:

1. Inicialización Simultánea: Todos los participantes están presentes inicialmente.
2. Fuente de Aleatoriedad Correlacionada: Los fragmentos se generan simultáneamente a partir de una fuente de aleatoriedad correlacionada (por ejemplo, mediciones de ganancia de canal en redes inalámbricas) en lugar de distribuirse a través de canales privados.
3. Comunicación Pública: El distribuidor (dealer) se comunica con los participantes mediante un canal público, sin ruido y autenticado. El distribuidor se entera de los cambios en la estructura de acceso (nuevos grupos autorizados) solo en el instante de tiempo en que estos ocurren y debe adaptar la estrategia de distribución de secretos de forma iterativa.

El objetivo es determinar una estrategia de distribución de secretos que permita a los grupos autorizados recuperar un secreto con alta fiabilidad, asegurando al mismo tiempo que los grupos no autorizados obtengan una información insignificante, todo ello mientras se maximiza la tasa de secreto (el tamaño del secreto compartido normalizado por el número de observaciones de la fuente).

Metodología
Los autores proponen una estrategia de distribución de secretos basada en el agrupamiento aleatorio (random binning) adaptado para un entorno dinámico. El núcleo de la metodología consiste en:

• Agrupamiento Aleatorio Cuantizado: El distribuidor observa una secuencia $Y^n$ de una fuente correlacionada $(Y, X_L)$. Para cada instante de tiempo $t$, el distribuidor y los participantes utilizan funciones de agrupamiento aleatorio predeterminadas ($g_i$ y $h_j$) que mapean las secuencias de la fuente a índices.
• Codificación Iterativa: En cada instante de tiempo $t$, el distribuidor determina el número de índices de agrupación ($k_t$) a incluir en el mensaje público y el número de índices ($\sigma_t$) a designar como secreto. Estos conteos se eligen basándose en el conjunto autorizado actual $A_t$ y el conjunto no autorizado $U_t$.
• Especificación de Estrategia A Priori: Un aspecto novedoso de la prueba es la introducción de un número cuantizado de agrupamientos. Esto permite la construcción de una única estrategia de distribución de secretos que está totalmente especificada a priori. Crucialmente, esta estrategia no depende del conocimiento de cómo evolucionará la AAS en futuros instantes de tiempo; el distribuidor solo necesita conocer la estructura de acceso actual para determinar el mensaje y el secreto para ese paso específico.
• Decodificación: Los participantes autorizados utilizan sus observaciones locales ($X^n_A$), los mensajes públicos acumulados y las funciones de agrupación para identificar la secuencia de la fuente única que sea consistente con las restricciones de tipicidad y los índices de agrupación recibidos.

Contribuciones Clave y Resultados
El artículo establece los siguientes resultados teóricos:

1. Alcanzabilidad de Tasas de Estructura Fija: Los autores demuestran que existe una estrategia para el modelo AAS donde la tasa de secreto alcanzable en cualquier instante $t$ es independiente de las estructuras de acceso en todos los demás instantes de tiempo. Específicamente, la tasa alcanzable $R_t$ coincide con la mejor tasa conocida alcanzable para un modelo de estructura fija:
   $$R_t = \min_{U \in U_t} H(Y | X_U) - \max_{A \in A_t} H(Y | X_A)$$
   Este resultado implica que la naturaleza dinámica de la estructura de acceso no degrada inherentemente la tasa de secreto en comparación con un escenario estático.

2. Capacidad para Estructuras de Acceso de Umbral: El artículo demuestra que cuando la estructura de acceso en un determinado instante de tiempo forma una Estructura de Acceso de Umbral (donde cualquier grupo de tamaño $\ge f_1(t)$ es autorizado y cualquier grupo de tamaño $\le f_2(t)$ es no autorizado), la estrategia propuesta alcanza la capacidad. Para un caso específico donde el distribuidor comparte claves privadas independientes con los participantes, la capacidad se muestra como:
   $$R_t = H(X)(f_1(t) - f_2(t))$$

3. Omnisciencia vs. Causalidad: Un hallazgo significativo es que, para el caso de la AAS de umbral, un distribuidor omnisciente (que conoce toda la secuencia futura de estructuras de acceso) no obtiene ninguna ventaja sobre un distribuidor causal (que solo conoce la estructura actual) en términos de tasas de secreto alcanzables.

Significado y Reivindicaciones
El artículo afirma generalizar los modelos de distribución de secretos que dependen de la aleatoriedad correlacionada desde estructuras de acceso aditivas fijas a dinámicas. La principal significación radica en demostrar que la adaptabilidad dinámica no conlleva un costo en la eficiencia de la tasa de secreto. Los autores muestran que se puede alcanzar el rendimiento de las mejores estrategias estáticas sin requerir conocimiento previo de la evolución del sistema.

El trabajo destaca que el resultado "sorprendente" es la independencia de la tasa alcanzable en $t$ respecto al historial o futuro de la estructura de acceso. Si bien el artículo proporciona una prueba de existencia no constructiva para el caso general de la AAS (basándose en el método probabilístico para demostrar la existencia de funciones de agrupación adecuadas), señala explícitamente que proporcionar una prueba de alcanzabilidad constructiva para la AAS general sigue siendo un problema abierto, lo que la distingue de las pruebas constructivas existentes para estructuras fijas.

El artículo concluye que, para las estructuras dinámicas basadas en umbrales, la capacidad está plenamente caracterizada, y la falta de previsión respecto a los cambios futuros en la estructura de acceso no penaliza el rendimiento del sistema.