Firmas Basadas en MPCitH a partir de Problemas de Decodificación Restringida

Información Básica

• ID del Artículo: 2510.11224
• Título: Firmas Basadas en MPCitH a partir de Problemas de Decodificación Restringida
• Autores: Michele Battagliola (Universidad Politécnica de Marche), Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger (Universidad Técnica de Múnich)
• Clasificación: cs.CR (Criptografía y Seguridad), cs.IT (Teoría de la Información), math.IT (Teoría de la Información)
• Fecha de Publicación: 13 de octubre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.11224

Resumen

Este artículo integra el Problema de Decodificación Síndrome Restringida (E-SDP) en los marcos Threshold-Computation-in-the-Head (TCitH) y VOLE-in-the-Head (VOLEitH), que representan los desarrollos más recientes del paradigma MPC-in-the-Head (MPCitH), mejorando significativamente el rendimiento de esquemas de firma digital. Los autores proponen un método de modelado estructuralmente simple que logra tamaños de firma competitivos. Al instanciar el problema de decodificación restringida utilizando los mismos supuestos de dificultad que CROSS, el tamaño de firma se reduce más del doble en comparación con la versión enviada a NIST. Además, los autores descubren que la decodificación ternaria de peso completo está estrechamente relacionada con el supuesto de dificultad subyacente de WAVE, logrando tamaños de firma comparables con los candidatos MPCitH más pequeños en la competencia NIST.

Antecedentes y Motivación de la Investigación

Contexto del Problema

1. Necesidad de Estandarización de Criptografía Poscuántica: Tras estandarizar CRYSTALS-Dilithium, FALCON y SPHINCS+, NIST lanzó en septiembre de 2022 una convocatoria para esquemas de firma digital adicionales, con el objetivo de diversificar la cartera de estándares de firma poscuántica.
2. Desarrollo del Paradigma MPCitH: Desde su introducción por Ishai et al. en 2007, la tecnología MPCitH ha transformado el panorama de las firmas digitales poscuánticas. TCitH y VOLEitH, como especializaciones más recientes de MPCitH, ofrecen mejoras de rendimiento significativas en comparación con construcciones anteriores.
3. Aplicación de Teoría de Códigos en Criptografía: Los problemas de dificultad basados en teoría de códigos (como problemas de decodificación en métrica de Hamming y métrica de rango) proporcionan una base teórica para construir firmas poscuánticas eficientes.

Motivación de la Investigación

1. Necesidad de Optimización de Rendimiento: Aunque el esquema de firma CROSS existente se basa en problemas de decodificación restringida, utiliza el protocolo CVE relativamente simple, dejando espacio para optimización en términos de tamaño de firma.
2. Unificación de Marcos: Integrar problemas de decodificación restringida en marcos avanzados TCitH/VOLEitH para aprovechar plenamente las ventajas de rendimiento de estos marcos.
3. Mejora de Competitividad: Reducir significativamente el tamaño de firma mientras se mantiene la seguridad, mejorando la competitividad en la competencia NIST.

Contribuciones Principales

1. Propuesta de Método de Modelado Polinomial para E-SDP: Se diseña una relación polinomial estructuralmente simple pero efectiva que integra el problema de decodificación síndrome restringida en los marcos TCitH y VOLEitH.
2. Reducción Significativa del Tamaño de Firmas de Tipo CROSS: Para el mismo problema de decodificación, el tamaño de firma se reduce en más del 50% en comparación con el esquema CROSS enviado a NIST (de 12.4 kB a 5.5 kB).
3. Descubrimiento del Potencial de Aplicación de Decodificación Ternaria de Peso Completo: Se demuestra que la decodificación ternaria de peso completo relacionada con WAVE es un problema de decodificación restringida, logrando un tamaño de firma comparable con los candidatos MPCitH más pequeños (3.1 kB).
4. Provisión de Esquema de Parametrización Completo: Se proporcionan selecciones de parámetros específicas y análisis de rendimiento para las categorías de seguridad NIST 1, 3 y 5.

Explicación Detallada del Método

Definición de la Tarea

El objetivo de investigación es representar el Problema de Decodificación Síndrome Restringida (E-SDP) como una relación polinomial, permitiendo su construcción de esquemas de firma digital en los marcos TCitH y VOLEitH.

Definición de E-SDP: Dado un conjunto de restricción E ⊂ F, una matriz de paridad H ∈ F^(r×n) y un síndrome s ∈ F^r, encontrar e ∈ E^n tal que eH^T = s.

Método de Modelado Principal

1. Construcción de Restricciones Polinomiales

Para una matriz de paridad en forma sistemática H = (A, I_r), donde A ∈ F^(r×k), I_r es la matriz identidad:

• Vector de Testigo: w ∈ F^k (vector de error parcial)
• Vector de Error Extendido: e = (w, s - wA^T)
• Polinomio de Restricción: f_E(x) = ∏_{e∈E}(x - e)

Sistema de Relaciones Polinomiales:

F(x) = (f_1, ..., f_n) ∈ F[x_1, ..., x_k]^n

donde:

• f_i(x) = f_E(x_i) para i ∈ k
• f_{k+i}(x) = f_E(s_i - ⟨a_i, x⟩) para i ∈ r

2. Análisis de Grado

Proposición 1: Esta relación polinomial proporciona un modelado de E-SDP con grado z = |E|. Si w ∈ F^k satisface F(w) = 0, entonces el vector de error e = (w, s - wA^T) resuelve la instancia E-SDP (H, s).

Instanciaciones Concretas

CROSS-SDP

• Conjunto de Restricción: E = {2^i | i ∈ 7} ⊆ F_{127}
• Parámetros: |E| = 7, p = 127
• Seguridad: Basada en análisis detallado de 7,15

Ternary-SDP

• Conjunto de Restricción: E = {1, 2} ⊆ F_3
• Parámetros: |E| = 2, p = 3
• Complejidad: O(2^{0.247·n}) operaciones (dentro de factores polinomiales)

Configuración Experimental

Estrategia de Selección de Parámetros

Según los requisitos de seguridad y objetivos de optimización de rendimiento, se seleccionan los siguientes parámetros clave:

1. Parámetros del Marco TCitH:
   • τ: número de repeticiones paralelas
   • N: tamaño del dominio de evaluación
   • μ: grado de extensión de campo K : F
   • η: parámetro de procesamiento por lotes
2. Parámetros del Marco VOLEitH:
   • ρ: parámetro de extensión de campo
   • B: parámetro de verificación de consistencia
   • T_open: parámetro del esquema VC

Restricciones de Seguridad

Se satisfacen los siguientes requisitos de seguridad:

• TCitH: N ≤ p^μ, p^{μ·η} ≥ 2^λ, (N/d)^τ ≥ 2^{λ-w}
• VOLEitH: N^τ/d ≥ 2^{λ-w}, p^ρ ≥ 2^λ

Métricas de Evaluación

La evaluación principal se centra en el tamaño de firma, que comprende tres componentes:

• |σ_sym|: relacionado con esquema VC
• |σ_w|: relacionado con testigo
• |σ_F|: relacionado con OWF

Resultados Experimentales

Resultados Principales

Rendimiento del Marco TCitH

| Nivel de Seguridad | Tipo E-SDP | |F| | |E| | n | k | τ | N | μ | η | Tamaño de Firma (B) | |---------|-----------|-----|-----|---|---|---|---|---|---|-----------| | NIST 1 | CROSS-SDP | 127 | 7 |127| 76| 15|2048| 2| 10| 5,533 | | NIST 1 | Ternary-SDP| 3 | 2 |579|213| 12|2048| 7| 12| 3,095 | | NIST 3 | CROSS-SDP | 127 | 7 |187|111| 23|2048| 2| 14| 12,354 | | NIST 3 | Ternary-SDP| 3 | 2 |839|309| 18|2048| 7| 18| 6,860 |

Rendimiento del Marco VOLEitH

Comparación con Candidatos NIST

Hallazgos Clave

1. Reducción Significativa de Tamaño: CROSS-SDP reduce el tamaño de firma en un 64.5% en comparación con CROSS original
2. Impacto de la Selección del Marco: Para problemas de alto grado, VOLEitH es más ventajoso que TCitH
3. Competitividad: Ternary-SDP logra un rendimiento comparable con los mejores candidatos MPCitH

Trabajo Relacionado

Desarrollo del Paradigma MPCitH

1. MPCitH Original 23: Propuesto en 2007, combinando computación segura multiparte con transformación Fiat-Shamir
2. Marco TCitH 21: Instanciación utilizando compartición de secretos de umbral ℓ-de-n
3. Marco VOLEitH 13: Compilación de protocolos de conocimiento cero basados en VOLE a protocolos públicamente verificables

Aplicación de Teoría de Códigos

1. Decodificación en Métrica de Hamming: Base de esquemas como SDitH
2. Decodificación en Métrica de Rango: Esquemas RYDE, Mirath, etc.
3. Problema del Núcleo de Permutación: Supuesto de dificultad del esquema PERK

Problemas de Decodificación Restringida

1. Esquema CROSS 6: Decodificación restringida utilizando protocolo CVE simple
2. Esquema WAVE 10,19: Basado en decodificación de síndrome ternario de alto peso
3. Análisis Teórico 8,9: Completitud NP y dificultad concreta de E-SDP

Conclusiones y Discusión

Conclusiones Principales

1. Integración Exitosa del Marco: Se demuestra que los problemas de decodificación restringida pueden integrarse efectivamente en marcos MPCitH avanzados
2. Mejora Significativa de Rendimiento: Mediante la sustitución del protocolo CVE simple por construcciones TCitH/VOLEitH, se reduce significativamente el tamaño de firma
3. Aplicabilidad Amplia: El método es aplicable a diferentes tipos de problemas de decodificación restringida

Limitaciones

1. Aumento de Complejidad: En comparación con el protocolo CVE simple del CROSS original, las construcciones TCitH/VOLEitH son significativamente más complejas
2. Sobrecarga Computacional: Aunque el tamaño de firma se reduce, puede aumentar la complejidad computacional de generación y verificación de firmas
3. Dependencia de Parámetros: El rendimiento depende altamente de la selección específica de parámetros y estrategias de optimización

Direcciones Futuras

1. Optimización Adicional: Exploración de métodos de modelado polinomial más eficientes
2. Otros Problemas Restringidos: Extensión del método a otros tipos de problemas de decodificación restringida
3. Optimización de Implementación: Desarrollo de implementaciones eficientes para reducir la sobrecarga computacional

Evaluación Profunda

Fortalezas

1. Innovación Técnica: Propuesta de un método de modelado polinomial conciso y efectivo para problemas de decodificación restringida
2. Mejora Significativa: Reducción sustancial del tamaño de firma manteniendo la misma seguridad
3. Contribución Teórica: Establecimiento de un puente entre problemas de decodificación restringida y marcos MPCitH avanzados
4. Valor Práctico: Provisión de nuevas ideas de diseño para esquemas de firma poscuántica

Deficiencias

1. Compensación de Complejidad: Reducción del tamaño de firma a costa de mayor complejidad de construcción
2. Novedad Limitada: Principalmente combinación ingeniosa de técnicas existentes, con innovación teórica relativamente limitada
3. Ausencia de Detalles de Implementación: Falta de análisis detallado de rendimiento y comparaciones de implementación práctica

Impacto

1. Valor Académico: Proporciona nuevo caso de estudio para aplicación del marco MPCitH
2. Significado Práctico: Puede influir en la selección de esquemas en futuros procesos de estandarización NIST
3. Contribución Metodológica: Proporciona referencia para modelado similar de otros problemas de dificultad

Escenarios de Aplicación

1. Entornos con Recursos Limitados: Escenarios de aplicación sensibles al tamaño de firma
2. Despliegue de Criptografía Poscuántica: Sistemas que requieren diversidad de supuestos de seguridad
3. Prototipos de Investigación: Base para optimización y mejora adicional

Referencias

El artículo cita 24 referencias importantes que abarcan el desarrollo del marco MPCitH, aplicaciones de teoría de códigos y esquemas candidatos NIST relacionados, proporcionando una base teórica sólida para la investigación.