Withdrawability in Fiat-Shamir with aborts constructions

Resumen Técnico: Retractabilidad en Construcciones de Fiat–Shamir con Abortos

Planteamiento del Problema
Las firmas digitales tradicionalmente proporcionan permanencia; una vez generada, una firma no puede ser revocada sin comprometer la clave privada del firmante o invalidar otras firmas. Esta limitación plantea desafíos en entornos dinámicos como contratos inteligentes de blockchain, votación electrónica descentralizada y servicios de custodia (escrow), donde los participantes pueden necesitar revocar compromisos basados en condiciones cambiantes. Liu, Baek y Susilo [LBS23] introdujeron las "firmas retractables" (withdrawable signatures), una primitiva que permite a un firmante generar una firma verificable solo por un verificador designado, la cual puede transformarse posteriormente en una firma públicamente verificable. Sin embargo, su construcción depende de supuestos clásicos (Logaritmo Discreto, Diffie-Hellman) vulnerables a ataques cuánticos.

El desafío abordado en este artículo es extender el concepto de firmas retractables al entorno post-cuántico, específicamente dentro del paradigma de Fiat–Shamir con abortos. Este paradigma es la base de esquemas de firma post-cuánticos líderes como Dilithium (ML-DSA) y HAETAE. Existe un obstáculo estructural específico: la construcción original de Liu–Baek–Susilo depende de un secreto compartido Diffie-Hellman "gratuito" para lograr la ambigüedad entre firmante/verificador y la designación simultáneamente. La criptografía basada en retículos carece de un análogo eficiente y económico para este secreto compartido, lo que requiere un nuevo enfoque arquitectónico.

Metodología
El artículo propone una construcción abstracta general para firmas retractables basada en el paradigma de Fiat–Shamir con abortos, seguida de una instanciación concreta.

1. Construcción Abstracta:
   Los autores definen un marco que comprende cinco algoritmos: KeyGen, WSign (firma retractante), WSVerify (verificación retractante), Confirm y CVerify.

   • Mecanismo Central: El esquema utiliza una prueba OR de Fiat–Shamir con abortos de dos partes. La firma retractante consiste en dos ramas: una generada por el firmante (usando su clave secreta) y otra simulada por el firmante para imitar la rama del verificador.
   • Ambigüedad: Debido a que tanto el firmante como el verificador designado pueden generar una rama válida (el firmante mediante la simulación del verificador, y el verificador mediante la simulación del firmante), el origen de la firma es indistinguible para terceros.
   • Confirmación: Para hacer que la firma sea públicamente verificable, el firmante ejecuta el algoritmo Confirm, el cual genera una firma estándar y ordinaria sobre el mensaje, el conjunto de claves públicas y la propia firma retractante. Esto vincula la firma retractante a la identidad del firmante sin requerir la rederivación de la aleatoriedad compartida (lo cual es inviable en el esquema de FS-con-abortos basado en retículos debido al muestreo de rechazo).

2. Variante de Verificador Designado Fuerte (SDVS):
   Para asegurar que la firma retractante no sea públicamente verificable (coincidiendo con el modelo de Liu–Baek–Susilo), los autores cifran el núcleo público de la firma utilizando un esquema de Cifrado de Clave Pública (PKE) (específicamente, el módulo-LWE CPA-seguro que subyace a ML-KEM/Kyber).

   • La firma se cifra tanto para la clave pública del verificador designado como para la clave pública del firmante. Esto permite al verificador descifrar y verificar, y permite al firmante descifrar y realizar la operación Confirm de forma sin estado (stateless).
   • Este enfoque reemplaza el secreto compartido Diffie-Hellman con cifrado explícito, reconociendo que el intercambio de claves no interactivo (NIKE) basado en retículos es actualmente demasiado ineficiente para este propósito.

3. Instanciación Concreta:
   El marco abstracto se instancia utilizando una construcción de tipo Dilithium de no-pistas (no-hint) y full-$t$.

   • Los autores utilizan una variante de Dilithium que no utiliza "pistas" (la división $t_1$/$t_0$), asegurando que el simulador para la prueba de conocimiento cero sea perfecto ($\varepsilon_{zk} = 0$).
   • Esta elección simplifica las pruebas de seguridad, particularmente para la propiedad de retractabilidad, al evitar los pequeños errores estadísticos asociados con los esquemas basados en pistas.

Contribuciones Clave

• Marco General: El artículo introduce la primera construcción abstracta para firmas retractables basada en el paradigma de Fiat–Shamir con abortos, cerrando la brecha entre el modelo de Liu–Baek–Susilo y la criptografía de retículos post-cuántica.
• Pruebas de Seguridad:
  • Inautenticidad (Unforgeability): Se demuestra que el esquema es inauténtico bajo corrupción de insider (donde el adversario posee la clave secreta del verificador) en el Modelo de Oráculo Aleatorio Cuántico (QROM). La prueba se reduce a la seguridad EUF-CMA del esquema de firma de retículos subyacente (supuestos SelfTargetMSIS/MSIS).
  • Retractabilidad: Se demuestra que el esquema es retractante, lo que significa que un adversario no puede distinguir si una firma fue generada por el firmante o por el verificador designado. Para la instanciación de no-pistas, esta propiedad es estadística (informacional) con $\varepsilon_{zk} = 0$, apoyándose en el conocimiento cero de verificador honesto no-abortante (naHVZK) perfecto del esquema de identificación subyacente y la min-entropía de los compromisos.
• Adaptación a las Restricciones Post-Cuánticas: El artículo aborda explícitamente la falta de un secreto compartido Diffie-Hellman basado en retículos. Demuestra que la designación puede lograrse mediante Cifrado de Clave Pública (PKE) en lugar de NIKE, y que la ambigüedad del firmante puede lograrse mediante pruebas OR en lugar de simetría algebraica.

Resultados

• Seguridad Concreta: Para la instanciación de Dilithium de no-pistas, el artículo proporciona límites de seguridad concretos. La ventaja de inautenticidad está acotada por la seguridad del esquema subyacente más un término negligible relacionado con la programación del oráculo aleatorio ($2^{-1024}$). La ventaja de retractabilidad está acotada por $1/2$ más un término estadístico negligible, logrando efectivamente una ambigüedad perfecta para el verificador designado en el caso de no-pistas.
• Comparación: Los autores proporcionan una comparación detallada con el esquema de Liu–Baek–Susilo (Tabla 2). Si bien la construcción de retículos requiere material de clave adicional (claves de cifrado) y resulta en firmas más grandes (debido a la sobrecarga de cifrado), gana dos propiedades significativas: la firma retractante es pseudialeatoria (ocultando su existencia a terceros) y la no-transferibilidad contra el verificador designado es perfecta (estadística) en lugar de computacional.

Significancia
El artículo afirma que es una adaptación necesaria de la primitiva de firma retractante a la era post-cuántica. Establece que la retractabilidad es alcanzable en la criptografía basada en retículos sin depender de los ineficientes o inexistentes análogos de Diffie-Hellman en retículos. Al separar los mecanismos de designación (cifrado) y ambigüedad (pruebas OR), los autores proporcionan una construcción robusta y demostrablemente segura que mantiene las propiedades de seguridad de los esquemas subyacentes como Dilithium, añadiendo la flexibilidad crítica de la revocación de firmas. El trabajo sugiere que estas construcciones podrían mejorar la resistencia cuántica en sistemas de blockchain donde la revocación de transacciones es deseable pero tradicionalmente difícil de implementar.