Partial Derandomization for Leakage-Resilient Shamir's Secret Sharing over Composite Order Fields

Resumen Técnico: Derandomización Parcial para la Distribución de Secretos de Shamir con Resiliencia a la Filtración sobre Campos de Orden Compuesto

1. Planteamiento del Problema

El artículo aborda la construcción de lugares de evaluación explícitos para esquemas de Distribución de Secretos de Shamir (SSS) que sean resilientes contra la filtración de bits físicos sobre campos de orden compuesto ($\mathbb{F}_{p^d}$ donde $d \ge 2$).

En el SSS estándar, un secreto se distribuye entre $n$ partes de tal manera que cualquier $k$ puede reconstruirlo. Las construcciones aleatorizadas (elegir los lugares de evaluación uniformemente al azar) son conocidas por ser estadísticamente seguras contra la filtración local, pero requieren una fuente de aleatoriedad pública confiable. En la práctica, los adversarios pueden influir en la semilla aleatoria, dirigiendo el esquema hacia lugares de evaluación vulnerables.

Trabajos previos establecieron que:

• Sobre campos primos ($\mathbb{F}_p$), los lugares de evaluación aleatorios producen resiliencia a la filtración con alta probabilidad.
• Sobre campos compuestos ($\mathbb{F}_{p^d}$), Nguyen (EUROCRYPT 2025) estableció una dicotomía perfecta: cualquier esquema de distribución de secretos basado en códigos lineales es o bien perfectamente seguro (distancia estadística 0) o completamente inseguro contra la filtración de bits físicos.
• Sin embargo, para campos compuestos, no se conocía una familia explícita y determinista de lugares de evaluación para $k > 2$ o regímenes generales de bloques de filtración. Las construcciones explícitas existentes para campos primos dependían de propiedades de extracción de bits no lineales que no se aplican a los mapas de coordenadas lineales de los campos compuestos.

El desafío central es derandomizar la elección de los lugares de evaluación (reduciendo la entropía necesaria para especificarlos) manteniendo al mismo tiempo la seguridad perfecta contra la filtración de bits físicos en el entorno de campos compuestos.

2. Metodología y Construcción

El autor propone una estrategia de derandomización parcial. En lugar de seleccionar $n$ puntos de evaluación independientes de forma aleatoria, construye los lugares de evaluación como las iteraciones de una función racional $\Phi$ aplicada a un punto base elegido aleatoriamente $x_0$.

La Construcción:

• Configuración del Campo: Sea $\mathbb{F} = \mathbb{F}_{p^d}$ con un elemento primitivo $\alpha$.
• Operador de Paso: Definir la transformación de Möbius $\Phi(x) = \frac{\alpha x}{x + 1}$.
• Lugares de Evaluación: Los $n$ lugares de evaluación se definen como $x_j = \Phi^j(x_0)$ para $j = 0, \dots, n-1$, donde $x_0 \in \mathbb{F}^*$ es un punto base elegido aleatoriamente.
• Reducción de Entropía: Especificar el esquema requiere solo $d \log p$ bits (para elegir $x_0$), una reducción significativa de los $nd \log p$ bits requeridos para $n$ puntos aleatorios independientes.

Perspicacia Estructural Clave:
El análisis de seguridad se basa en los polos distintos de las iteraciones de $\Phi$.

• $\Phi^0(x) = x$ tiene un polo en $\infty$.
• Para $j \ge 1$, $\Phi^j(x)$ tiene un polo en un punto finito distinto en $\mathbb{F}^*$.
• Esta "distinción de polos" es crucial. El autor contrasta esto con el candidato $\Psi(x) = \alpha x$ (dilatación pura), donde todas las iteraciones comparten el mismo polo en $\infty$, lo que provoca que el argumento de seguridad colapse.

3. Enfoque Técnico

La prueba procede en tres fases, aprovechando la dicotomía perfecta establecida por Nguyen (2025):

1. La Dicotomía Perfecta (Fase 1):
   El artículo utiliza el hecho de que la extracción de coordenadas en $\mathbb{F}_{p^d}$ es $\mathbb{F}_p$-lineal. En consecuencia, el mapa de filtración es lineal. Esto implica que la distancia estadística entre las distribuciones de filtración para diferentes secretos es o bien 0 o bien 1. La seguridad perfecta se logra si y solo si el mapa de filtración es sobreyectivo. Esta condición es equivalente a que una matriz de prueba $\Theta_{\vec{i}}$ (derivada de los lugares de evaluación y el patrón de filtración) tenga rango de columna completo sobre $\mathbb{F}_p$.

2. No Degeneración de Fracciones Parciales (Fase 2):
   Para probar que la matriz de prueba tiene rango completo, el autor debe demostrar que ninguna combinación lineal no trivial de las potencias de los lugares de evaluación se anula. Definen una función racional $G_\ell(x) = \sum c_j \eta(i_j) (\Phi^j(x))^\ell$.
   Utilizando la descomposición en fracciones parciales, explotan los polos distintos de $\Phi^j$. Debido a que los polos son distintos, el residuo de $G_\ell$ en cualquier polo específico está determinado por un único término de la suma. Si $G_\ell$ fuera identicamente cero, todos los coeficientes tendrían que anularse. Este argumento de "no degeneración" acota el número de puntos base "malos" $x_0$ que causan que la condición de rango falle.

3. Extensión a Multi-bloques (Fase 3):
   El argumento se extiende a la filtración de múltiples bloques (donde se filtran múltiples coordenadas por cada participación). El autor gestiona los coeficientes de campo que surgen de las combinaciones lineales dentro de las participaciones, demostrando que el argumento de las fracciones parciales sigue siendo válido siempre que el patrón de filtración sea "admisible" (posiciones de bloque distintas por participación).

4. Resultados Clave

Teorema 1.1 (Seguridad Perfecta contra Filtración de Bloque Único):
Para parámetros $n = O(d / \log_p d)$ y cualquier umbral $k \ge 2$, existe un conjunto de "puntos base malos" $Bad \subset \mathbb{F}^*$ con tamaño $|Bad| \le n + n(dp)^n$. Para cualquier $x_0 \notin Bad$, el esquema que utiliza los lugares de evaluación $x_j = \Phi^j(x_0)$ es perfectamente seguro (distancia estadística exactamente 0) contra cualquier patrón de filtración de bloque único.

• Esto implica seguridad perfecta contra la filtración de un solo bit físico por participación para cualquier primo $p$.
• Se garantiza la existencia de un buen $x_0$ cuando $d > n(1 + \log_p d) + \log_p(2n)$.

Teorema 1.2 (Filtración de Multi-bloque):
Para un patrón de filtración de bloque único admisible con $M$ bloques totales filtrados, el tamaño del conjunto malo está acotado por $n + n \cdot p^M$. Un buen $x_0$ existe si $M < d - \log_p(2n)$.

• Para la seguridad universal contra todos los patrones con $\le M$ bloques, el límite es $|Bad| \le n + n(dpe)^M$, con existencia garantizada cuando $d > M(\frac{5}{2} + \log_p d) + \log_p(2n)$.

Clasificador:
El artículo proporciona un clasificador explícito (Algoritmo 1) que, dado un $x_0$ candidato, verifica la condición de rango completo para todos los patrones de filtración. Esto sirve como una prueba sólida para certificar la seguridad de la construcción estructurada.

5. Significado y Comparación

El artículo reclama las siguientes contribuciones y distinciones:

• Seguridad Perfecta vs. Seguridad Estadística: A diferencia de las construcciones aleatorizadas previas sobre campos compuestos que ofrecían seguridad estadística ($\epsilon = 2^{-\Omega(d)}$), esta construcción logra la seguridad perfecta (distancia estadística 0) para un régimen restringido de parámetros.
• Derandomización: Reduce la aleatoriedad requerida para especificar el esquema de $nd \log p$ bits a $d \log p$ bits al restringir los lugares de evaluación a una familia de un solo parámetro (la órbita de $\Phi$).
• Construcción Explícita: Proporciona la primera familia explícita de lugares de evaluación para $k > 2$ sobre campos compuestos que resiste la filtración de bits físicos, yendo más allá del paradigma de los "lugares aleatorios".
• Limitaciones y Compromisos:
  • El número de participantes $n$ está limitado a $O(d / \log_p d)$, mientras que las construcciones aleatorizadas soportan $O(dk / \log_p d)$. El autor conjetura que esta pérdida de un factor-$k$ es inherente a las construcciones de un solo parámetro.
  • La universalidad de multi-bloque está actualmente limitada por un cuello de botella en la enumeración de patrones, lo que resulta en límites de conjuntos malos exponenciales en $M$.
  • La construcción depende de la estructura algebraica específica de la transformación de Möbius $\Phi(x) = \alpha x / (x+1)$; la alternativa de dilatación $\alpha x$ falla en proporcionar seguridad.

El trabajo no pretende resolver el problema de la derandomización para todos los regímenes de parámetros, identificando la limitación de la universalidad de multi-bloque como un problema abierto. La contribución principal es una derandomización parcial rigurosa que logra la seguridad perfecta en un régimen específico y prácticamente relevante, explotando los polos distintos de las iteraciones racionales.