⚛️ quantum physics

CRT-Decomposed $Σ$ -Protocols for CSIDH

Este artículo presenta un protocolo $\Sigma$ descompuesto mediante CRT para CSIDH que logra completitud perfecta, conocimiento cero y extracción directa eficiente en el QROM sin suposiciones heurísticas, al tiempo que verifica rigurosamente su corrección algebraica y demuestra que su seguridad depende actualmente de parámetros futuros con factores primos grandes debido a una reducción significativa en el costo de ataque clásico cuando se publican las curvas de salto CRT.

Autores originales: I. Dey, I. Cherkaoui

Publicado 2026-09-23

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: I. Dey, I. Cherkaoui

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el mundo digital, la privacidad a menudo depende de un delicado equilibrio: un usuario quiere demostrar que tiene el derecho de gastar dinero o acceder a un servicio sin revelar su identidad o los detalles específicos de la transacción. Este es el ámbito de las firmas ciegas, una herramienta criptográfica que permite a un banco certificar una moneda sin ver jamás dónde se gastará. Durante décadas, la seguridad de estos sistemas ha descansado en acertijos matemáticos que involucran números grandes, pero el auge de las potentes computadoras cuánticas amenaza con resolver esos acertijos, dejando obsoletas las protecciones de privacidad actuales. Para contrarrestar esto, los científicos están recurriendo a un tipo diferente de matemáticas basadas en la geometría de las curvas elípticas, específicamente un método llamado criptografía basada en isogenias. Este enfoque utiliza un tipo único de movimiento entre curvas que es fácil de realizar en una dirección pero increíblemente difícil de revertir, creando una base para la seguridad que las máquinas cuánticas no pueden romper fácilmente. Sin embargo, construir sistemas prácticos sobre esta base ha sido difícil porque los métodos estándar para probar el conocimiento de una clave secreta a menudo dependen de un proceso que falla cuando se enfrenta a adversarios cuánticos.

Un equipo de investigadores de la Universidad Tecnológica del Sudeste de Irlanda ha desarrollado una nueva forma de construir estas pruebas que evita las debilidades fatales de los métodos anteriores. Su trabajo se centra en un sistema específico conocido como CSIDH, que utiliza una estructura matemática llamada grupo de clases para moverse entre curvas elípticas. Los investigadores descubrieron que cuando la estructura interna de este grupo se conoce por completo, como es el caso de una versión específica llamada CSIDH-512, puede descomponerse en piezas más pequeñas e independientes utilizando un principio matemático clásico conocido como el Teorema del Resto de la China. En lugar de tratar la clave secreta como un bloque único y monolítico, diseñaron un protocolo que demuestra el conocimiento de cada pequeña pieza por separado. Este cambio estructural permite al sistema extraer la clave secreiosa directamente de la prueba mediante aritmética simple, en lugar de depender de un juego de adivinanzas complejo y repetitivo que las computadoras cuánticas pueden interrumpir.

El núcleo de su logro es un nuevo tipo de prueba interactiva que es tanto perfectamente completa como perfectamente segura contra la interceptación. En este sistema, un probador y un verificador intercambian mensajes para confirmar que el probador conoce una clave secreta sin revelar la clave en sí. Los investigadores demostraron que si un probador puede responder con éxito a dos desafíos diferentes para el mismo paso, el secreto puede recuperarse instantáneamente restando las respuestas y realizando una sola división. Este proceso, que llaman extracción algebraica, ocurre en línea recta sin la necesidad de rebobinar o reiniciar la interacción. Esta es una distinción crítica porque las pruebas de seguridad anteriores para sistemas similares dependían de rebobinar al atacante a un estado previo para forzar un error, una técnica que es imposible de justificar contra una computadora cuántica que no puede ser pausada o copiada. Al eliminar este paso, el nuevo protocolo ofrece un camino hacia la seguridad que se mantiene firme incluso en un futuro donde las computadoras cuánticas sean comunes.

Para asegurar que su diseño no fuera solo una idea teórica, el equipo implementó todo el sistema en una computadora utilizando los parámetros exactos del grupo CSIDH-512. Verificaron la lógica matemática del protocolo a lo largo de diez mil instancias aleatorias, confirmando que los pasos algebraicos funcionaban exactamente como se predijo en cada ocasión. También realizaron simulaciones para medir cómo se comportaría el sistema bajo un ataque. Estas pruebas confirmaron que la seguridad del sistema sigue las leyes matemáticas esperadas, con la dificultad de romperlo creciendo de manera predecible a medida que aumenta el número de rondas. Sin embargo, los investigadores también fueron cuidadosos al identificar los límites de su enfoque. Demostraron que, si bien dividir el problema en piezas más pequeñas hace posible la extracción del secreto, también expone al sistema a un tipo específico de ataque que reduce la dificultad de romper la clave. Para los parámetros actuales de CSIDH-512, esta reducción disminuye la seguridad de un nivel que requiere aproximadamente 2^128.6 evaluaciones de acción de grupo a unas 2^67.3 evaluaciones, una caída significativa que hace que los parámetros actuales sean insuficientes para una seguridad clásica de 128 bits.

Consecuentemente, los investigadores concluyen que, si bien su construcción es matemáticamente correcta y estructuralmente completa, aún no es segura para su despliegue inmediato en los parámetros actuales de CSIDH-512. El sistema funciona perfectamente, pero la misma característica que lo hace eficiente —la exposición de los pasos intermedios— también lo hace vulnerable a un método de ataque conocido. La solución, argumentan, reside en futuros conjuntos de parámetros donde los componentes matemáticos sean mucho más grandes. Si el grupo se construye a partir de factores primos que son individualmente muy grandes, la pérdida de seguridad por exponer los pasos intermedios se vuelve insignificante, y el sistema seguiría siendo seguro. El artículo también comparó su método con esquemas existentes, señalando que, aunque sus firmas son actualmente más grandes, la compensación es un modelo de seguridad que no se degrada al enfrentarse a amenazas cuánticas. El trabajo constituye una demostración rigurosa de que la estructura algebraica puede reemplazar las pruebas de seguridad complejas y propensas a errores, siempre que los números subyacentes se elijan con la suficiente precaución para resistir las nuevas vulnerabilidades que la estructura introduce.

Resumen Técnico: Protocolos $\Sigma$ -Descompuestos por CRT para Acciones de Grupos de Clases de CSIDH

Planteamiento del Problema
El artículo aborda una debilidad crítica en las pruebas de seguridad de las firmas ciegas y los protocolos de identificación isogenia-basados, específicamente aquellos construidos sobre la acción de grupo CSIDH (Commutative Supersingular Isogeny Diffie-Hellman). Los esquemas de vanguardia actuales (por ejemplo, CSI-Otter, Tanuki) dependen de protocolos de identificación interactivos cuya reducción de seguridad depende del lema de bifurcación (forking lemma). Este lema requiere "rebobinar" (rewinding) a un adversario cuántico para extraer una clave secreta, un proceso que incurre en una pérdida cuadrática de seguridad y es teóricamente inválido contra adversarios cuánticos cuyas condiciones internas no pueden ser clonadas. En consecuencia, estas pruebas obligan al uso de parámetros más grandes y lentos para compensar dicha pérdida. El artículo busca eliminar este paso de rebobinado aprovechando la estructura algebraica del grupo de clases de CSIDH para permitir una extracción de línea recta (straight-line extraction).

Metodología
Los autores construyen una prueba de conocimiento de tipo cero-conocimiento ( $\Sigma$ -protocolo) que explota la estructura del Teorema del Resto Chino (CRT) del grupo de clases ideales de CSIDH. Este enfoque es aplicable únicamente cuando la estructura del grupo es exactamente conocida, una condición que actualmente solo se cumple para CSIDH-512.

Descomposición por CRT: El grupo de clases $C\ell(\mathcal{O})$ de orden $N$ se descompone en componentes cíclicos independientes correspondientes a los factores de potencia de primos de $N$ . La clave secreta $s$ se divide en componentes $s_i$ módulo cada factor primo $q_i$ .
Curvas de Salto (Hop Curves): El protocolo publica una cadena de "curvas de salto" ( $F_0, \dots, F_k$ ) que representan los estados intermedios de la acción de grupo. Cada salto $i$ corresponde a un problema de vectorización dentro de un subgrupo $\langle h_i \rangle$ de orden $q_i$ .
Estructura del Protocolo: El protocolo consta de $k$ saltos, cada uno ejecutado en $t$ rondas paralelas. En cada ronda, el probador se compromete a un desplazamiento aleatorio, el verificador emite un desafío binario ( $c \in \{0,1\}$ ) y el probador responde con un valor $z$ .
Extracción Algebraica: A diferencia de las pruebas estándar que requieren rebobinar para encontrar dos transcripciones aceptables con desafíos diferentes, este protocolo permite recuperar el secreto mediante una fórmula algebraica de forma cerrada. Dados dos registros aceptables para el mismo compromiso, el componente secreto es simplemente la diferencia de las respuestas ( $z_0 - z_1$ ), seguido de la inversión modular y la recombinación por CRT.
Compilación QROM: Debido a que cada ronda admite exactamente dos respuestas, el protocolo es compatible con la transformada de Unruh. Esto permite la conversión del protocolo interactivo en una prueba de conocimiento no interactiva en el Modelo de Oráculo Aleatorio Cuántico (QROM) con extracción de línea recta, evitando completamente el lema de bifurcación.

Contribuciones Clave
El artículo realiza cinco contribuciones principales:

Definición Formal: Formaliza la extracción débil para acciones de grupos criptográficos, definiendo una noción de seguridad donde un extractor puede recuperar el secreto utilizando solo operaciones de anillo (sin reducción de retículos ni heurísticas) a partir de las transcripciones aceptables.
Construcción del Protocolo ( $\Pi_{CRT}$ ): Construye un protocolo que demuestra cuatro propiedades:
- Completitud Perfecta: Los probadores honestos siempre tienen éxito.
- HVZK Especial Perfecta: Las transcripciones no revelan información sobre el secreto, incluso para observadores ilimitados.
- Solidez 2-Especial (2-Special Soundness): El secreto es algebraicamente recuperable a partir de dos transcripciones mediante una simple resta e inversión modular.
- Error de Conocimiento: La probabilidad de que un probador tenga éxito sin la clave es $2^{-t}$ .
Verificación por Máquina: Los autores implementaron la capa algebraica sobre el módulo exacto de 258 bits de CSIDH-512. Verificaron 10,000 instancias aleatorias, confirmando que la extracción algebraica funciona perfectamente y que la lógica del protocolo se mantiene sin computar isogenias reales.
Resultados Delimitados (Resultados Negativos):
- Límite del Espacio de Desafíos: La descomposición por CRT no amplía el espacio de desafíos por ronda; los desafíos binarios siguen siendo necesarios a menos que se publiquen múltiples curvas, lo que aumenta el tamaño de la clave.
- Costo de Seguridad: Publicar las curvas de salto intermedias reduce la seguridad clásica de la recuperación de la clave de $\approx 2^{128.6}$ a $\approx 2^{67.3}$ evaluaciones de acción de grupo. Esto se debe a que el problema se descompone en instancias de vectorización independientes en subgrupos, resolubles mediante ataques de encuentro en el medio (meet-in-the-middle) en el componente más grande.
Seguridad QROM: El artículo demuestra que el protocolo, cuando se compila mediante la transformada de Unruh, produce una prueba de conocimiento no interactiva con extracción en línea (online extraction) en el QROM, eliminando la pérdida multiplicativa del lema de bifurcación.

Resultos y Análisis Cuantitativo

Instanciación: El esquema se instancia en CSIDH-512. El grupo de clases tiene 5 factores primos (longitudes de bits: 2, 6, 21, 96, 135).
Límites de Seguridad:
- Clásica: La seguridad está limitada por el factor primo más grande ( $q_{max} \approx 2^{135}$ ). El costo del ataque de encuentro en el medio es $O(\sqrt{q_{max}}) \approx 2^{67.3}$ . El artículo señala que CSIDH-512 no alcanza la seguridad clásica de 128 bits bajo esta construcción debido a las curvas de salto publicadas.
- Cuántica: La seguridad está limitada por cribas de tipo Kuperberg, de forma similar a otros esquemas CSIDH.
Rendimiento:
- Tamaño de la Firma: Para $t=128$ rondas y $k=5$ componentes, el tamaño de la firma es aproximadamente 24.1 KiB (comparado con 263 B para CSI-FiSh y 8 KiB para CSI-Otter).
- Computación: La extracción algebraica y la simulación son de sub-microsegundos. El costo dominante sigue siendo la evaluación de la isogenia (proyectada en 40 ms por acción), lo que hace que el tiempo total de firma sea de aproximadamente 25.6 segundos para el protocolo completo.
Simulación: Las simulaciones de Monte Carlo confirmaron que el error de solidez coincide con el límite teórico de $2^{-t}$ dentro de intervalos de confianza del 95%.

Significancia y Reivindicaciones
El artículo afirma que la construcción es estructuralmente completa y correcta para grupos de clases de estructura conocida como CSIDH-512. Su principal significancia radica en proporcionar una reducción de seguridad segura para computadoras cuánticas para las pruebas de conocimiento basadas en isogenias al eliminar el paso de rebobinado, que es una vulnerabilidad conocida en las pruebas de seguridad post-cuánticas.

Sin embargo, los autores son explícitos sobre las compensaciones (trade-offs):

Modestia sobre la Seguridad: El esquema no es cuantitativamente seguro al nivel de 128 bits para CSIDH-512 debido a la degradación de seguridad causada por la publicación de las curvas de salto. Los autores afirman que la construcción es "cuantitativamente segura solo en futuros conjuntos de parámetros cuyo número de clase tenga factores primos grandes" (por ejemplo, donde cada factor sea $\ge 256$ bits).
No es una Solución Mágica: La descomposición por CRT no reduce el número de rondas requeridas para la solidez; simplemente cambia el mecanismo de extracción.
Trabajo Futuro: El artículo deja la construcción de una firma ciega basada en esta prueba de conocimiento y la reducción ajustada de su no falsabilidad al problema del anillo de endomorfismos como trabajo futuro.

En resumen, el artículo presenta un protocolo matemáticamente riguroso y verificado por máquina que resuelve el "problema del rebobinado" para las pruebas de conocimiento de CSIDH, ofreciendo un camino hacia firmas ciegas seguras en el QROM, pero a costa de tamaños de firma más grandes y una reducción de la seguridad clásica para los conjuntos de parámetros actuales.

Más como este