FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG

Este trabajo presenta el primer esquema umbral de ML-DSA compatible con FIPS 204 que garantiza la privacidad de las partes del nonce mediante un DKG de Shamir y máscaras PRF, permitiendo firmas estándar verificables sin modificaciones y eliminando la necesidad de que todos los participantes sean honestos en ciertos perfiles.

Lo esencial

¡Hola! Imagina que tienes un cofre del tesoro digital (tu clave privada) que contiene todo tu dinero o identidad en internet. En el mundo de la criptografía actual, este cofre es vulnerable a las computadoras cuánticas del futuro, que podrían romper los candados tradicionales. Por eso, el gobierno de EE. UU. (NIST) ha creado un nuevo candado ultra-resistente llamado ML-DSA (FIPS 204).

Pero hay un problema: ¿Qué pasa si quieres que ese cofre solo se abra si varias personas están presentes y de acuerdo? Por ejemplo, si eres una empresa y quieres que para mover grandes sumas de dinero se necesiten 3 de 5 directores, o si quieres proteger tu identidad digital con tus amigos.

Aquí es donde entra este paper. Es como un manual de instrucciones para construir un "candado mágico" que cumple tres cosas difíciles a la vez:

1. Es resistente a las computadoras cuánticas.
2. Permite que un grupo de personas firme cosas juntas (umbral).
3. Es tan pequeño y compatible que las máquinas actuales no se dan cuenta de que es nuevo.

Vamos a desglosarlo con analogías sencillas:

1. El Problema: El "Rompecabezas" de la Firma

Imagina que para firmar un documento, necesitas mezclar dos ingredientes secretos:

• Tu Clave Secreta (como una receta familiar).
• Un "Nonce" (Un número aleatorio) (como un trozo de papel con un número escrito que solo usas una vez).

En la firma normal, tú tienes ambos. En una firma de grupo, el problema es que si repartes la receta y el papel entre varios amigos, al juntar las piezas para hacer la firma, a veces las piezas no encajan bien o se hacen demasiado grandes, haciendo que la firma sea inválida o demasiado pesada.

Anteriormente, los expertos tenían que elegir entre:

• Opción A: Firmas muy grandes (como enviar un camión entero para llevar un sobre).
• Opción B: Solo funcionar con grupos muy pequeños (como un dúo).
• Opción C: Necesitar que casi todos los miembros del grupo estén presentes y honestos (lo cual es difícil en la vida real).

2. La Solución: "Shamir Nonce DKG" (El Truco del Pastel)

El autor, Leo Kao, propone una técnica brillante llamada Shamir Nonce DKG.

La Analogía del Pastel:
Imagina que el "Nonce" (el número aleatorio) no es un solo número, sino un pastel gigante que se corta en rebanadas.

• En lugar de que cada persona tenga una parte fija, cada persona tiene una rebanada de un pastel matemático (un polinomio).
• Lo genial es que el "pastel" se construye de tal manera que, aunque tú solo tengas una rebanada, nadie puede adivinar cómo es el pastel completo ni el centro del mismo, a menos que tengas suficientes rebanadas (digamos, 3 de 5).
• El Truco: El papel (el nonce) se genera antes de saber qué se va a firmar. Es como si cada amigo escribiera un número secreto en un papel, lo doblara y lo guardara en una caja. Solo cuando todos ponen sus papeles en la caja y se mezclan, sale el número final.

¿Por qué es genial?

• Privacidad Total: Incluso si un espía roba las rebanadas de 2 amigos, no puede saber nada sobre el número secreto del tercer amigo. Es como si el tercer amigo tuviera un "manto de invisibilidad" matemático.
• Sin suposiciones de computación: No se basa en "esperar que el hacker sea lento". Se basa en que matemáticamente es imposible adivinar el número con tan pocas piezas.

3. Los "Máscaras" que se Anulan (Pairwise-Canceling Masks)

Hay otro problema: cuando mezclas las piezas, a veces se filtran datos. Para evitarlo, usan Máscaras.

La Analogía de los Gemelos:
Imagina que dos amigos (A y B) tienen un secreto. Para ocultarlo, A le da a B un sobre con un número positivo, y B le da a A un sobre con el mismo número pero negativo.

• Cuando A y B suman sus sobres, los números se anulan (positivo + negativo = 0).
• Pero individualmente, cada sobre parece un número aleatorio gigante.
• Al final, cuando todos suman sus sobres, las "máscaras" desaparecen y solo queda el mensaje real limpio.

Esto permite que el grupo firme sin que nadie sepa la parte secreta de los demás, y sin que la firma final sea enorme.

4. Los Tres Perfiles de Despliegue (Cómo usarlo en la vida real)

El paper ofrece tres formas de usar este sistema, dependiendo de cuánto confíes en la tecnología o en las personas:

• Perfil P1 (El Guardián de Confianza): Usas una caja fuerte digital (un TEE o HSM) que actúa como el "árbitro". Es el más rápido (como un suspiro, 5.8 ms). Es ideal para bancos o empresas que ya tienen cajas fuertes seguras.
• Perfil P2 (El Equipo Desconfiado): No confías en nadie, ni siquiera en el árbitro. Todos hacen los cálculos juntos usando criptografía avanzada (MPC). Es un poco más lento (21 ms), pero es el más seguro porque no necesitas confiar en un solo dispositivo.
• Perfil P3+ (El Equipo Semi-Asíncrono): ¡Este es el más innovador! Imagina que firmas un documento mientras estás en el tren. Preparas tu parte "offline" (en tu teléfono) y cuando el grupo te pide la firma, respondes en una ventana de tiempo (ej. 5 minutos). No necesitas que todos estén conectados al mismo tiempo. Es perfecto para humanos que no pueden estar pegados a la pantalla todo el día.

5. ¿Por qué es importante esto?

• Tamaño: Las firmas son del mismo tamaño que las normales (3.3 KB). No tienes que cambiar nada en los servidores que verifican las firmas.
• Seguridad: Funciona con cualquier número de personas (desde 2 hasta 45 o más).
• Velocidad: Es lo suficientemente rápido para usarse en transacciones diarias, criptomonedas o certificados digitales.

En Resumen

Este paper es como el manual de construcción para un candado cuántico que se abre con varias llaves. Resuelve el problema de cómo dividir un secreto sin que nadie lo pierda, sin hacer la firma gigante y sin necesitar que todos estén presentes al mismo tiempo.

Es un paso gigante para que, en el futuro de la computación cuántica, podamos seguir confiando en que nuestros activos digitales están seguros, incluso si necesitamos la aprobación de un grupo de personas para moverlos. ¡Es como tener un cofre del tesoro que solo se abre si tus amigos te dan la mano, pero sin que ninguno de ellos sepa la combinación completa!

Resumen técnico

Resumen Técnico: Umbral ML-DSA Compatible con FIPS 204 mediante DKG de Nonces de Shamir

1. Problema y Motivación

Con la inminente llegada de la computación cuántica, el NIST ha estandarizado ML-DSA (Module-Lattice-Based Digital Signature Algorithm) como el estándar FIPS 204 para firmas post-cuánticas. Sin embargo, existe una brecha crítica en la implementación de firmas umbral (donde un grupo de $N$ partes requiere un subconjunto de $T$ para firmar) para este algoritmo:

• Incompatibilidad de Formato: Las soluciones existentes para umbral en ML-DSA o bien producen firmas demasiado grandes (rompiendo la compatibilidad con FIPS 204, que requiere ~3.3 KB) o están limitadas a umbrales muy bajos ($T \le 6$) debido a la explosión de los coeficientes de Lagrange en la reconstrucción de secretos.
• Privacidad del Nonce: En esquemas de firma basados en el paradigma Fiat-Shamir con Abortos, la privacidad del nonce (el valor aleatorio $y$) es crucial. Las soluciones anteriores a menudo requieren suposiciones computacionales o asumen que hay al menos $T+1$ partes honestas (el requisito de "dos honestos"), lo cual es restrictivo.
• Escalabilidad: No existía un esquema que soportara umbrales arbitrarios ($T \in [9, 32]$), mantuviera el tamaño de firma estándar, ofreciera seguridad demostrable y fuera compatible con los verificadores FIPS 204 existentes.

2. Metodología y Técnicas Clave

El autor propone un esquema unificado basado en dos técnicas principales que resuelven los desafíos algebraicos y de privacidad de las firmas basadas en retículos:

A. DKG de Nonces de Shamir (Técnica Primaria)

En lugar de generar el nonce $y$ de forma uniforme y luego compartirlo, el protocolo genera el nonce mediante un Protocolo de Generación Distribuida de Claves (DKG) que utiliza el mismo esquema de compartición de Shamir que la clave secreta a largo plazo ($s_1$).

• Estructura: Cada parte genera un polinomio de grado $(T-1)$. El nonce global $y$ es la suma de las contribuciones constantes de estos polinomios.
• Privacidad Estadística: Dado que un adversario solo observa $T-1$ evaluaciones de los polinomios de las partes honestas, queda un grado de libertad que actúa como una "una sola vez" (one-time pad) aproximada. Esto garantiza una entropía condicional mínima en la parte del nonce de una parte honesta que supera 5 veces la entropía de la clave secreta (para $|S| \le 17$), sin necesidad de suposiciones computacionales.
• Eliminación del Requisito de "Dos Honestos": En perfiles con coordinador (P1 y P3+), esto permite que el conjunto de firmantes sea exactamente de tamaño $T$ ($|S|=T$), eliminando la necesidad de tener $T+1$ partes.

B. Máscaras de Cancelación Pareada (Técnica Secundaria)

Adaptadas de esquemas ECDSA, estas máscaras se utilizan para ocultar los compromisos de los nonces ($W_i$) y las participaciones de la verificación $r_0$ ($V_i$) durante la comunicación.

• Funcionamiento: Cada parte calcula máscaras basadas en semillas compartidas por pares (PRF) que se cancelan mutuamente al sumar todas las contribuciones ($\sum m_i = 0$).
• Desafío Específico: A diferencia de ECDSA, en ML-DSA la verificación $r_0$ implica $cs_2$. Si se revela $cs_2$ y el desafío $c$ es invertible (lo cual es casi seguro), se puede recuperar la clave secreta $s_2$. El protocolo utiliza MPC (Cálculo Multipartito Seguro) o TEEs para asegurar que $cs_2$ nunca se reconstruya en texto plano fuera del entorno seguro.

C. Distribución Irwin-Hall y Seguridad

La suma de nonces compartidos sigue una distribución Irwin-Hall (suma de variables uniformes) en lugar de una distribución uniforme pura.

• Análisis de Seguridad: El artículo realiza un análisis de invarianza de desplazamiento directo (Direct Shift-Invariance) utilizando divergencia de Rényi.
• Resultado: Se demuestra que la pérdida de seguridad por sesión es insignificante (< 0.013 bits para $|S| \le 33$), eliminando la brecha de escalabilidad que hacían inviables las pruebas de seguridad en trabajos anteriores para grandes umbrales.

3. Perfiles de Despliegue

El protocolo se implementa en tres perfiles con diferentes supuestos de confianza y complejidad:

1. Perfil P1 (Asistido por TEE/HSM):
   • Utiliza un coordinador en un Entorno de Ejecución Confiable (TEE).
   • El coordinador realiza la verificación $r_0$ y la generación de la pista (hint) dentro del enclave seguro.
   • Ventaja: 3 rondas en línea, latencia muy baja (~5.8 ms para 3 de 5), privacidad estadística con $|S|=T$.
2. Perfil P2 (Totalmente Distribuido / MPC):
   • Sin confianza en hardware. Utiliza MPC (SPDZ y edaBits) para calcular la verificación $r_0$.
   • Ventaja: Seguridad contra mayoría deshonesta (tolera $N-1$ corruptos), 5 rondas en línea.
   • Requisito: Necesita $|S \setminus C| \ge 2$ para la privacidad de las máscaras en modo broadcast.
3. Perfil P3+ (2PC Semi-Asíncrono):
   • Diseñado para autorización humana en bucle. Dos Partes de Cálculo (CP) ejecutan un 2PC (Two-Party Computation) para la verificación.
   • Innovación: Los firmantes precalculan nonces de forma offline y responden dentro de una ventana de tiempo (ej. 5 minutos), sin necesidad de sincronización estricta en múltiples rondas.
   • Ventaja: 2 rondas lógicas, latencia baja (~22 ms), ideal para flujos de trabajo con intervención humana.

4. Resultados y Rendimiento

La implementación en Rust demuestra la viabilidad práctica del esquema:

• Compatibilidad: Las firmas generadas son byte-identicas a las de un solo firmante ML-DSA (3.3 KB) y son verificables por cualquier implementación FIPS 204 sin modificaciones.
• Latencia:
  • P1 (TEE): ~5.8 ms (3 de 5).
  • P2 (MPC): ~21.5 ms (3 de 5).
  • P3+ (2PC): ~22.1 ms (3 de 5).
  • Escala hasta umbrales de 32 de 45 manteniendo latencias sub-100ms en P1 y P3+.
• Tasa de Éxito: Debido a la distribución Irwin-Hall (que concentra más probabilidad cerca de cero), la tasa de éxito por intento es del 21% al 45%, comparable o incluso superior a la línea base de un solo firmante (~20-25%), evitando el colapso de rendimiento típico de los esquemas umbral.
• Seguridad: Pruebas de seguridad UC (Universal Composability) completas para todos los perfiles. La pérdida de seguridad por la distribución de nonces es negligible (< 0.013 bits por sesión), manteniendo la seguridad demostrable por encima de los 85 bits incluso con miles de sesiones.

5. Significado y Contribuciones

Este trabajo es un avance fundamental en la criptografía post-cuántica por las siguientes razones:

1. Cierre de la Brecha Umbral: Es la primera solución que logra simultáneamente: umbrales arbitrarios, tamaño de firma estándar FIPS 204, seguridad UC y privacidad de nonces estadística (sin suposiciones computacionales).
2. Superación de Límites Teóricos: Resuelve el problema de la explosión de coeficientes de Lagrange y la pérdida de privacidad en la reconstrucción de nonces mediante la alineación estructural del DKG de nonces con la clave secreta.
3. Análisis de Seguridad Riguroso: Proporciona un análisis de seguridad directo y ajustado para la distribución Irwin-Hall, demostrando que la seguridad no se degrada significativamente con el aumento del número de firmantes, a diferencia de los límites conservadores anteriores que hacían las pruebas vacías para $T$ grandes.
4. Viabilidad Práctica: Demuestra que las firmas umbral post-cuánticas no son solo teóricas, sino que pueden implementarse con latencias aceptables para aplicaciones del mundo real como custodia de criptomonedas, autoridades de certificación distribuidas y gestión de claves empresariales.

En resumen, el artículo presenta un marco robusto y eficiente para la adopción de ML-DSA en entornos distribuidos, resolviendo los principales obstáculos de privacidad, tamaño y rendimiento que impedían su uso en infraestructuras críticas.