Resumen Técnico: La aritmética centrada no es neutral ante la fuga de información

Planteamiento del problema

En las implementaciones de software de criptografía basada en retículos (p. ej., ML-KEM, ML-DSA), los valores sensibles se protegen mediante el enmascaramiento aritmético, donde un secreto se divide en partes aleatorias cuyas sumas dan el secreto módulo $q$. Aunque la operación matemática es modular, el almacenamiento físico de estas partes requiere una elección de representación dentro de la palabra de la máquina. Típicamente, las partes se almacenan ya sea como residuos sin signo en $[0, q)$ o como enteros con signo centrados en la forma de complemento a dos $[-\lfloor q/2 \rfloor, \lceil q/2 \rceil - 1]$.

Aunque ambas codificaciones implementan aritmética modular idéntica, difieren significativamente en su representación binaria. Específicamente, los enteros negativos en complemento a dos exhiben extensión de signo (unos líderes), mientras que sus contrapartes sin signo no lo hacen. Trabajos previos han explotado este efecto de "extensión de signo" para ataques de canal lateral (p. ej., predictores de valor absoluto). Sin embargo, faltaba un marco teórico exhaustivo que caracterizara cómo esta elección de representación afecta a la fuga de información en todos los órdenes de enmascaramiento, bajo ruido finito y para módulos arbitrarios. Este artículo aborda la pregunta fundamental: ¿Es la aritmética centrada neutral ante la fuga de información en comparación con el almacenamiento sin signo?

Metodología

El artículo emplea un enfoque matemático riguroso que combina la teoría de la probabilidad, el análisis de Fourier y la teoría de números combinatoria para modelar el canal de fuga de información de canal lateral.

1. Modelado del canal de ruido finito: El autor modela la fuga de las partes enmascaradas como canales de ruido aditivo independientes. Deriva la verosimilitud exacta de la suma enmascarada tratando el problema como una convolución cíclica de las distribuciones de fuga de las partes individuales.
2. Análisis de Fourier: El análisis utiliza la Transformada Discreta de Fourier (DFT) para convertir la convolución en un producto en el dominio de la frecuencia. Esto permite la derivación de ataques óptimos y la descomposición espectral de la fuga.
3. Minimax de representación: El estudio evalúa diferentes "secciones" (representaciones) de $\mathbb{Z}_q$ minimizando la energía del espectro de fuga. Esto implica comparar secciones contiguas (sin signo frente a centradas) y libros de códigos binarios inyectivos arbitrarios.
4. Descomposición espectral: Una innovación metodológica clave es la descomposición del espectro de fuga de complemento a dos centrado en términos de extensión de signo y términos de acarreo (carry), permitiendo un análisis asintótico preciso.
5. Validación algorítmica: Los límites teóricos se verifican mediante computaciones exactas, experimentos sintéticos con parámetros de tamaño completo de ML-KEM y ML-DSA, y el análisis de trazas físicas públicas.

Contribuciones clave

1. Inferencia óptima de ruido finito

El artículo establece que la verosimilitud completa de una suma enmascarada puede computarse en tiempo cuasi lineal $O(dq \log q)$ utilizando una convolución circular evaluada mediante la Transformada Rápida de Fourier (FFT).

• Resultado: Esto proporciona una estrategia de ataque óptima que evalúa todas las $q$ hipótesis simultáneamente.
• Condición de suficiencia: El autor deriva una condición exacta bajo la cual la estadística de producto (multiplicar partes centradas) comúnmente utilizada conserva toda la información de verosimilitud. Demuestra que para cualquier módulo $q \ge 2$ y orden $d \ge 2$ bajo ruido finito, la estadística de producto es estrictamente insuficiente. La observación completa contiene estrictamente más información (mayor divergencia KL, divergencia de Rényi, etc.) que la estadística de producto.

2. Leyes minimax de representación global

El artículo optimiza la elección de la representación para minimizar la fuga:

• Fuga de primer orden: Entre todas las secciones contiguas, el almacenamiento sin signo ($[0, q)$) es el minimizador único de la fuga de primer orden, a menos que el módulo $q$ ocupe la palabra de máquina completa ($q=2^m$), en cuyo caso todas las secciones son equivalentes.
• Fuga de orden superior: La optimalidad del almacenamiento sin signo no es permanente. El artículo identifica un "cambio de fase" exacto donde, para parámetros específicos (p. ej., $q=14, \beta=4$), el almacenamiento centrado se convierte en el minimizador único para órdenes $d \ge 4$, mientras que el sin signo es óptimo para órdenes menores.
• Ley lexicográfica: Para cualquier familia finita de representaciones, el minimizador eventual a medida que el orden de enmascaramiento $d \to \infty$ está determinado por el espectro de coeficientes de fuga ordenado lexicográficamente más pequeño.
• Libros de códigos de peso constante: Para codificaciones binarias arbitrarias, la fuga desaparece exactamente si y solo si el libro de códigos tiene un peso de Hamming constante. El artículo proporciona un límite de capacidad agudo para la existencia de tales libros de códigos ($q \le \binom{\beta}{\lfloor \beta/2 \rfloor}$) y calcula el ancho de palabra mínimo requerido para los módulos estándar de NIST (p. ej., $\beta=14$ para $q=3329$).

3. La ley de la fuga de reducción centrada

El resultado teórico central del artículo es una descomposición espectral exacta de la fuga de complemento a dos centrado:

• Descomposición: El espectro de fuga se divide en un término macroscópico de extensión de signo y un defecto binario de acarreo (carry).
• Umbral de dominancia: El artículo demuestra un umbral uniforme agudo: se requieren tres bits de exceso ($s = \beta - \lceil \log_2 q \rceil \ge 3$) para que el almacenamiento centrado exhiba una magnitud de fuga estrictamente mayor que el almacenamiento sin signo en el primer modo de Fourier. Específicamente, la condición $D(q, \beta) > 2U(q)$ se cumple si y solo si $s \ge 3$.
• Asintótica: Para un exceso de ancho fijo, la relación de los coeficientes de fuga de la representación centrada frente a la sin signo converge a $s+1$. Para el caso específico de $q=2^m-1$, la relación de fuga converge a una constante relacionada con la suma de tangentes ($\kappa \approx 1.81$).
• Neutralidad: La aritmética centrada no es neutral ante la fuga. Solo es neutral (equivalente en fuga al almacenamiento sin signo) en el caso exacto donde $q=2^m$ y $\beta=m$. En todos los demás casos, el almacenamiento centrado resulta en una fuga estrictamente mayor en el primer modo de Fourier (y típicamente para órdenes de enmascaramiento bajos), aunque puede convertirse en la representación óptima en órdenes muy altos para conjuntos de parámetros específicos.

4. Robustez y complejidad de muestra

• Radios de robustez: El artículo define radios de robustez exactos para modelos de peso de Hamming ponderado, mostrando que la separación estricta entre el almacenamiento centrado y el sin signo se mantiene incluso con variaciones en la sensibilidad de los bits, siempre que el exceso de bits sea al menos 3.
• Complejidad de muestra: Se propone una prueba armónica de confianza exponencial. El artículo demuestra que la relación de complejidad de muestra entre ataques con representación centrada y sin signo escala como la potencia $2d$ de la relación de sus coeficientes espectrales. Esto implica que para órdenes de enmascaramiento superiores, la penalización por usar almacenamiento centrado (que tiene una mayor fuga en el primer modo) crece exponencialmente, a menos que el conjunto de parámetros específico sitúe al sistema en un régimen donde el almacenamiento centrado es el minimizador global.

Resultados y validación

• Experimentos sintéticos: Implementaciones de tamaño completo para ML-KEM ($q=3329$) y ML-DSA ($q=8380417$) confirman los factores de complejidad de muestra teóricos. Para $d=3, 4, 6$, la representación centrada requiere significativamente más trazas que el almacenamiento sin signo para alcanzar el mismo nivel de éxito, alineándose con los límites asintóticos derivados.
• Trazas físicas: El análisis fue validado mediante trazas físicas públicas de una implementación enmascarada de ML-DSA. El predicado de signo alcanzó un Welch $|t|$ de 155.73 y una precisión de equilibrio del 90.80%, confirmando la presencia del canal de fuga de extensión de signo predicho por la teoría.
• Eficiencia algorítmica: El ataque óptimo propuesto (utilizando convolución basada en FFT) puntuó con éxito todas las hipótesis para $q=8,380,417$ en menos de 35 segundos, demostando su viabilidad práctica.

Significado

Este artículo cambia fundamentalmente la comprensión del enmascaramiento aritmético en software. Demuestra que la elección de la representación de la máquina (centrada frente a sin signo) no es simplemente un detalle de implementación, sino un componente crítico del canal de fuga de información de canal lateral.

• Refutación de la neutralidad: El autor demuestra concluyentemente que "La aritmética centrada no es neutral ante la fuga". La extensión de signo inherente a la representación de complemento a dos introduce un espectro de fuga distinto que no es mitigado únicamente por el enmascaramiento.
• Guías de diseño: El trabajo proporciona directrices exactas y accionables para los implementadores:
  • Utilizar almacenamiento sin signo para seguridad de primer orden y cuando el exceso de bits es bajo ($s < 3$), ya que minimiza de forma única la fuga de primer orden.
  • Ser consciente de que el almacenamiento centrado generalmente incurre en una penalización severa en la complejidad de muestra debido a la mayor magnitud de la fuga en el primer modo, convirtiéndose en óptimo solo en órdenes muy altos para conjuntos de parámetros específicos (demostrando un cambio de fase en la optimalidad).
  • Los libros de códigos de peso constante ofrecen un camino teórico hacia la fuga cero, pero requieren anchos de palabra específicos que pueden no alinearse con las restricciones de hardware estándar.
• Fundamento teórico: Al proporcionar leyes espectrales exactas y condiciones de optimalidad de ruido finito, el artículo cierra la brecha entre la seguridad teórica del enmascaramiento y las realidades de la implementación práctica, ofreciendo una base rigurosa para evaluar y diseñar sistemas criptográficos de retículos resistentes a ataques de canal lateral.