The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures

Este artículo presenta un marco general para generalizar el esquema de firma SQIsign mediante el uso de estructuras de nivel, proporcionando una nueva correspondencia explícita de Deuring para curvas elípticas supersingulares con dichas estructuras y resolviendo nuevas ecuaciones de norma restringidas.

Lo esencial

¡Hola! Imagina que el mundo de la criptografía (la ciencia de los secretos) es como un laberinto gigante construido con formas geométricas extrañas llamadas "curvas elípticas". Para proteger tus datos en el futuro, cuando las computadoras cuánticas sean reales y puedan romper los candados actuales, necesitamos nuevos candados más fuertes.

Este paper, escrito por un equipo de investigadores de IBM y varias universidades, presenta una nueva versión de un candado muy prometedor llamado SQIsign. A este nuevo y mejorado le han puesto un nombre divertido: SQInstructor.

Aquí te explico de qué trata, usando analogías sencillas:

1. El Problema: El Laberinto de las Curvas

Imagina que tienes dos puntos en un mapa (dos curvas matemáticas). El reto de la criptografía es encontrar un camino secreto (una "isogenia") que conecte esos dos puntos.

• Para los hackers: Encontrar ese camino es como buscar una aguja en un pajar cósmico. Es extremadamente difícil.
• Para el dueño del candado: Él tiene un "mapa de trampa" (una estructura matemática oculta) que le permite encontrar el camino fácilmente.

El sistema original, SQIsign, ya era muy bueno porque sus "llaves" (firmas digitales) eran muy pequeñas, como un mensaje de texto en lugar de un libro entero. Pero tenía un problema: el proceso para crear la firma era lento y complicado.

2. La Nueva Idea: El "Instructor" y las Estructuras de Nivel

Aquí es donde entra SQInstructor. Los autores se dieron cuenta de que el sistema original estaba usando solo una parte de la información disponible.

Imagina que las curvas elípticas son como edificios.

• En el sistema antiguo, el desafío era simplemente decir: "Conecta el edificio A con el edificio B".
• En el nuevo sistema (SQInstructor), el desafío es más específico: "Conecta el edificio A con el edificio B, pero asegúrate de que la puerta principal del edificio A coincida exactamente con la puerta del edificio B".

A estas "puertas" o características especiales las llaman Estructuras de Nivel.

• La analogía: Imagina que tienes que emparejar dos cajas de herramientas. No basta con que sean del mismo tamaño; el "Instructor" exige que el destornillador rojo de la caja A encaje exactamente en el hueco rojo de la caja B.
• Esto añade una capa extra de control y flexibilidad. El "Instructor" puede elegir qué tipo de "puertas" (estructuras) quiere usar para crear el candado.

3. ¿Cómo funciona la magia? (La Correspondencia Deuring)

Para que esto funcione, los autores usaron una herramienta matemática llamada Correspondencia Deuring.

• La analogía: Imagina que tienes dos idiomas muy difíciles de entender: el "Idioma de las Curvas" y el "Idioma de los Cuaterniones" (un tipo de números extraños).
• Tradicionalmente, era muy difícil traducir problemas del Idioma de las Curvas al Idioma de los Cuaterniones.
• Los autores de este paper han creado un diccionario nuevo y mejorado. Ahora pueden traducir problemas que involucran esas "puertas" (estructuras de nivel) de un idioma al otro con mucha más precisión. Esto les permite resolver los rompecabezas matemáticos necesarios para crear las firmas de manera más eficiente.

4. Dos Maneras de Hacerlo (1D y 2D)

El paper explora dos formas de construir estas firmas, dependiendo de qué tan rápido o seguro quieras ir:

• Opción 1 (Isogenias 1D): Es como caminar por un pasillo estrecho. Es un poco más lento y las firmas son un poco más grandes, pero es la única forma conocida de hacer ciertas cosas avanzadas, como firmas de grupo (donde un grupo de personas puede firmar algo sin revelar quién fue).
• Opción 2 (Isogenias 2D): Es como volar en un helicóptero. Es mucho más rápido y eficiente. Los autores muestran que, usando esta técnica, SQInstructor es casi tan rápido como el SQIsign original, pero con la ventaja de ser más flexible y tener una seguridad teórica más sólida.

5. ¿Por qué es importante?

• Seguridad: Mantiene la promesa de ser resistente a las computadoras cuánticas.
• Velocidad: Al usar técnicas de "dimensiones superiores" (volar en helicóptero en lugar de caminar), el proceso de firmar es muy rápido.
• Flexibilidad: Al ser un "Instructor", el sistema puede adaptarse a diferentes tipos de desafíos matemáticos, lo que abre la puerta a nuevas aplicaciones en el futuro.

En resumen

SQInstructor es como una nueva versión de un candado digital ultra-compacto. En lugar de solo pedir que conectes dos puntos, el "Instructor" exige que conectes puntos específicos con características especiales (las estructuras de nivel). Los autores han creado un nuevo "diccionario" matemático para hacer esto posible y han demostrado que, aunque suena complicado, funciona tan rápido como los mejores candados actuales, pero con un diseño más inteligente y adaptable para el futuro de la seguridad digital.

¡Es un paso más hacia un internet que nadie podrá hackear, ni siquiera con una computadora del año 3000!

Resumen técnico

Resumen Técnico: SQInstructor y la Correspondencia de Deuring con Estructuras de Nivel

1. El Problema

La criptografía basada en isogenias es una de las candidatas más prometedoras para la criptografía post-cuántica. SQIsign, el esquema de firma más compacto en el proceso de estandarización del NIST, se basa en la Correspondencia de Deuring, que establece una equivalencia entre curvas elípticas supersingulares y órdenes de un álgebra de cuaterniones.

Sin embargo, SQIsign presenta desafíos significativos:

• Procedimiento de firma lento: La generación de firmas requiere resolver ecuaciones de norma complejas en el álgebra de cuaterniones (algoritmo KLPT), lo que hace que el proceso de firma sea computacionalmente costoso.
• Dificultad en la seguridad: Probar la seguridad EUF-CMA (Existential Unforgeability under Chosen Message Attack) es intrínsecamente difícil debido a las limitaciones del algoritmo KLPT y la falta de una comprensión completa de la distribución de las salidas.
• Limitaciones de las isogenias 1D: Las versiones anteriores dependían de isogenias unidimensionales, lo que limitaba la eficiencia y la aplicabilidad a primitivas avanzadas como firmas anulares.

El objetivo de este trabajo es generalizar el marco de SQIsign introduciendo estructuras de nivel (bases de subgrupos de torsión de curvas elípticas) para crear un protocolo más flexible, eficiente y con fundamentos de seguridad más sólidos.

2. Metodología

Los autores proponen SQInstructor, un marco general que modifica el protocolo de identificación de SQIsign. En lugar de simplemente encontrar una isogenia que anule un punto de torsión (como en SQIsign clásico), el nuevo protocolo exige que la respuesta (la isogenia) mapee una estructura de nivel específica a otra.

Componentes clave de la metodología:

• Generalización de la Correspondencia de Deuring:

  • Extienden la correspondencia clásica para incluir curvas elípticas supersingulares equipadas con estructuras de nivel ($\Gamma$-estructuras).
  • Demuestran que los homomorfismos entre curvas con estructuras de nivel corresponden a ideales localmente principales en órdenes subyacentes (órdenes de Eichler o subórdenes) del álgebra de cuaterniones $B_{p,\infty}$.
  • Proporcionan una correspondencia explícita incluso para niveles no suaves y grandes, resolviendo ecuaciones de norma con restricciones adicionales.

• El Protocolo SQInstructor:

  • Clave pública: Una curva $E_{pk}$ junto con una estructura de nivel $S_{pk}$.
  • Desafío: El verificador envía una nueva estructura de nivel $S_{com}$ sobre la curva de compromiso.
  • Respuesta: El firmante debe producir una isogenia $\phi_{rsp}$ tal que $\phi_{rsp}(S_{pk}) = S_{com}$.
  • Esto permite elegir entre diferentes tipos de estructuras de nivel (Borel, Cartan dividida, Escalar) y diferentes representaciones de isogenias (1D o multidimensional).

• Algoritmos de Resolución de Normas (KLPT con restricciones):

  • Para la implementación 1D, adaptan el algoritmo KLPT (Kohel-Lauter-Petit-Tignol) para encontrar ideales de norma suave que respeten las restricciones de la estructura de nivel.
  • Desarrollan variantes como ScalarSigningKLPT y BorelSigningKLPT que resuelven ecuaciones de norma en subórdenes específicos ($Z + N\mathcal{O}$).
  • Incluyen pasos de realeatorización para asegurar que la distribución de las firmas sea indistinguible de la uniforme (bajo suposiciones computacionales).

• Implementación de Alta Dimensión (2D):

  • Para la implementación moderna, utilizan isogenias de 2 dimensiones (técnicas de alto rendimiento introducidas tras los ataques a SIKE).
  • Esto elimina la necesidad de KLPT para la firma, acelerando drásticamente el proceso y mejorando la seguridad demostrable.

3. Contribuciones Clave

1. Marco Teórico Unificado: Generalización explícita de la Correspondencia de Deuring para curvas con estructuras de nivel, proporcionando algoritmos para mapear ideales a isogenias que respetan estas estructuras.
2. Nuevo Protocolo (SQInstructor): Definición de un esquema de identificación y firma genérico que permite la elección flexible de estructuras de nivel y representaciones de isogenias.
3. Algoritmos de Firma 1D: Resolución práctica de ecuaciones de norma con restricciones de nivel en el álgebra de cuaterniones, con una implementación de prueba de concepto para estructuras de tipo Borel y Escalar.
4. Implementación 2D Optimizada: Una instancia de SQInstructor utilizando isogenias de 2 dimensiones que alcanza un rendimiento comparable al de SQIsign actual (NIST), pero con una estructura de seguridad más clara.
5. Análisis de Seguridad Riguroso:
   • Prueba de 2-especial solidez para la relación de conocimiento de un endomorfismo no escalar.
   • Análisis de Cero Conocimiento (Zero-Knowledge) utilizando oráculos de isogenias (modelo Γ-UTO y FIDIO) y demostración de seguridad EUF-CMA.
   • Demostración de que la seguridad se reduce a la dificultad del problema del anillo de endomorfismos (Problema 3).

4. Resultados

• Rendimiento: La implementación de SQInstructor con isogenias de 2 dimensiones muestra un rendimiento muy similar al de SQIsign v2 (el candidato actual del NIST).
  • Tiempos: Las diferencias en generación de claves, firma y verificación son marginales (dentro del 5-10% en algunas métricas).
  • Tamaños: Hay un ligero aumento en el tamaño de la firma (debido a la cadena de isogenias (2,2) y la matriz de desafío), pero sigue siendo extremadamente compacto (ej. ~272 bytes para seguridad NIST III).
• Flexibilidad: El marco permite instanciar protocolos avanzados como firmas anulares y hashes camaleónicos utilizando la variante 1D, algo que es difícil o imposible con las técnicas puramente multidimensionales actuales.
• Corrección de Parámetros: Se establecen guías para la selección de parámetros (primes $p$, nivel $N$) para garantizar que el espacio de desafíos sea suficientemente grande ($\approx 2^\lambda$) y que la probabilidad de reinicio en la firma sea despreciable.

5. Significancia

Este trabajo es fundamental por varias razones:

• Unificación Conceptual: Muestra que SQIsign y sus variantes pueden entenderse y generalizarse a través de la lente de las estructuras de nivel, ofreciendo una visión más profunda de la criptografía de isogenias.
• Seguridad Mejorada: Al proporcionar una reducción de seguridad más directa y un análisis de cero conocimiento más robusto (especialmente en la variante 2D), fortalece la confianza en los esquemas basados en Deuring.
• Puente hacia Primitivas Avanzadas: La capacidad de usar estructuras de nivel en la variante 1D abre la puerta a la construcción de esquemas de firma anular y otros protocolos criptográficos complejos que requieren propiedades de simulación específicas, llenando un vacío dejado por las técnicas puramente multidimensionales.
• Viabilidad Práctica: Demuestra que estas generalizaciones teóricas no solo son matemáticamente elegantes, sino que son implementables con eficiencia comparable a los estándares actuales, asegurando su relevancia para la estandarización post-cuántica.

En resumen, SQInstructor no solo mejora la comprensión teórica de la correspondencia de Deuring, sino que ofrece un marco práctico y flexible para la próxima generación de firmas digitales post-cuánticas, equilibrando eficiencia, tamaño y seguridad demostrable.