Lattice-based extended withdrawability

Resumen Técnico: Firma de Retirabilidad Extendida basada en Redes (Lattice-based Extended Withdrawability)

Planteamiento del Problema
Las firmas digitales tradicionalmente proporcionan permanencia: una vez firmada, un mensaje permanece verificable bajo la clave pública del firmante indefinidamente. Sin embargo, muchas aplicaciones descentralizadas (por ejemplo, acceso por tiempo limitado, acuerdos revocables, custodia descentralizada) requieren la capacidad de retirar una firma sin revelar la clave secreta o invalidar otras firmas. Liu, Susilo y Baek introdujeron las firmas de retirabilidad extendida (EWS, por sus siglas en inglés) para abordar esto, permitiendo que una firma sea ambigua entre un conjunto de posibles firmantes hasta que el verdadero firmante la "confirma". Su construcción se basa en primitivas de logaritmo discreto (firmas de Schnorr y firmas de 1-de-N).

Este artículo aborda la "brecha post-cuántica": el algoritmo de Shor rompe la base de logaritmo discreto de los esquemas EWS existentes. Si bien existen firmas basadas en redes (como Dilithium), una "transcripción literal" de la construcción de Liu-Susilo-Baek (LSB) a las redes falla debido a obstrucciones estructurales. Específicamente, el esquema LSB se basa en la publicación de desplazamientos multiplicativos de las claves públicas para re-aleatorizar la contribución del firmante. En el entorno de redes (Fiat-Shamir con abortos), tales desplazamientos toman la forma $As_1 s_j$, que comparten un factor común $As_1$ con la clave pública del firmante $t_i = As_1 + s_2$. Publicar estos desplazamientos filtra la identidad del firmante, rompiendo la ambigüedad requerida.

Metodología
Los autores proponen una nueva construcción para EWS basada en redes que difiere del enfoque LSB al tratar el esquema como una firma de anillo reclamable (Park y Sealfon). En lugar de intentar re-aleatorizar las claves públicas en claro, la construcción separa las dos funciones principales de EWS:

1. Ambigüedad: Proporcionada por una firma de anillo anónima de 1-de-N, utilizada como una caja negra.
2. Confirmación: Proporcionada por la reclamación del firmante, que consiste en una firma vinculante sobre el objeto retirable y la apertura de un compromiso oculto hacia el índice del firmante.

La construcción opera sobre el paradigma de Fiat-Shamir con abortos y se basa en tres ingredientes modulares:

• Un esquema de firma base (por ejemplo, un esquema tipo Dilithium de no-pista, full-$t$).
• Una firma anónima de 1-de-N (instanciada mediante una prueba de 1-de-muchos en redes).
• Un esquema de compromiso de ocultación y vinculación (tipo Ajtai).

La firma retirable $\sigma$ consiste en una firma de anillo $\sigma_r$ sobre el mensaje y un compromiso $C$ al índice del firmante, junto con el conjunto de claves públicas. Para confirmar, el firmante revela la apertura $(i, \rho)$ de $C$ y firma todo el objeto retirable $\langle \mu, \pi, \sigma \rangle$ con su clave secreta base.

Contribuciones Clave

1. Refinamiento del Modelo de Seguridad: Los autores refinan el modelo de seguridad de LSB.

   • Reemplazan la definición de "completitud" de la retirabilidad extendida de LSB con un juego de indistinguibilidad de anonimato-hasta-la-reclamación (Definición 14), capturando explícitamente la garantía de ocultación.
   • Introducen la solidez de la reclamabilidad (Definición 16), asegurando que una firma confirmada se vincule a un índice de firmante único, evitando que un adversario atribuya la misma firma a diferentes miembros del anillo.
   • Formalizan la inautenticidad bajo corrupción de insider con un índice objetivo fijo, evitando la pérdida de reducción por $q_H$ (consulta de hash) presente en la prueba de LSB.

2. Construcción Genérica: Se presenta una construcción genérica de EWS sobre el paradigma de Fiat-Shamir con abortos. Crucialmente, no publica ningún valor derivado del firmante en claro. La ambigüedad se deriva únicamente de las propiedades de conocimiento cero de la firma de anillo, y la trazabilidad se deriva de la propiedad de vinculación del compromiso.

3. Resultado de Imposibilidad: El artículo demuestra (Proposición 2) que una transcripción literal a redes de la firma 1-de-N de LSB (usando división de desafíos aditiva) es insegura. En el entorno de redes con desafíos dispersos, la probabilidad de que un firmante honesto produzca una división de desafío válida es negligible ($2^{-\Omega(n)}$), e incluso si la completitud fuera parcheada, la anonimidad fallaría porque el registro simulado no sería indistinguible de uno real.

4. Pruebas de Seguridad Completas: Los autores proporcionan reducciones explícitas basadas en juegos en el Modelo de Oráculo Cuántico Aleatorio (QROM) para:

   • Correctitud: Reduciendo a la correctitud de las primitivas subyacentes.
   • Retirabilidad Extendida: Reduciendo a la ocultación del compromiso (MLWE decisional) y al anonimato de la firma 1-de-N.
   • Inautenticidad: Reduciendo a la seguridad EUF-CMA de la firma base (sin reintento y sin pérdida $q_H$).
   • Solidez de la Reclamabilidad: Reduciendo a la vinculación del compromiso (MSIS).

5. Instanciación: El esquema se instancia utilizando una firma base tipo Dilithium de no-pista, full-$t$ y una prueba de 1-de-muchos en redes establecida. El artículo discute la elección de parámetros y señala que HAETAE podría servir como una alternativa base.

Resultados
El artículo establece que la construcción propuesta es:

• Correcta: Las firmas honestas se verifican con una probabilidad abrumadora.
• Retirable Extendida: Un adversario que posee todas las claves secretas no puede distinguir qué miembro de un anillo produjo una firma retirable hasta que el firmante la confirma.
• Inautenticable: Incluso con acceso a oráculos de firma y las claves secretas de todos los miembros del anillo excepto el objetivo, un adversario no puede falsificar una firma confirmada para un mensaje nuevo.
• Sólida: Una firma confirmada no puede ser atribuida a dos firmantes diferentes.

La seguridad se basa en supuestos estándar de redes modulares: MLWE decisional, MSIS y SelfTargetMSIS, junto con la propiedad de conocimiento cero de la prueba 1-de-muchos.

Significancia
El artículo reclama significancia al proporcionar la primera realización post-cuántica segura de firmas de retirabilidad extendida. Demuestra que la construcción de logaritmo discreto de LSB no puede trasladarse directamente a las redes debido a la falta de "re-aleatorización libre" de los valores compartidos. Al reformular el problema como una firma de anillo reclamable y utilizar un mecanismo de confirmación basado en compromisos, los autores logran un esquema que es:

• Seguro Post-Cuántico: Resistente a adversarios cuánticos mediante supuestos de redes.
• Verificable Públicamente: A diferencia de las variantes de verificador designado, cualquier parte puede verificar la firma retirable.
• Modular: Las pruebas de seguridad se basan solo en las interfaces de las primitivas subyacentes, lo que permite la sustitución de diferentes componentes de redes (por ejemplo, diferentes firmas base o pruebas de anillo) sin tener que volver a probar todo el sistema.
• Fiel a los Objetivos Originales: El diseño preserva los objetivos funcionales e la intuición del esquema LSB original mientras corrige sus fallos estructurales en el entorno de redes.