From Orientations to $\ell$-adic Period Vectors

A continuación presento un resumen técnico detallado del artículo "From Orientations to ℓ-adic Period Vectors" de Leonardo Colò, estructurado según los puntos solicitados.

1. El Problema y el Contexto

El artículo aborda la necesidad de establecer un puente riguroso entre dos áreas de la matemática y la criptografía post-cuántica:

1. Criptografía basada en isogenias: Específicamente, el uso de curvas elípticas supersingulares orientadas (oriented supersingular elliptic curves) y la acción de grupos de clases de ideales sobre ellas (como en CSIDH y OSIDH).
2. Geometría aritmética y formas modulares: El uso de símbolos modulares, homología relativa de curvas modulares $X_0(N)$ e integración $\ell$-ádica (Coleman) para estudiar formas modulares.

El problema central es la falta de una representación explícita y computable que traduzca la estructura combinatoria de las curvas supersingulares orientadas en datos analíticos discretos ($\ell$-ádicos) que puedan utilizarse para definir nuevos problemas computacionales duros, distintos pero relacionados con el problema de encontrar caminos en grafos de isogenias.

2. Metodología

El autor propone un "pipeline" algebraico-analítico que transforma una curva elíptica supersingular orientada en un vector de periodos $\ell$-ádicos truncados. El proceso se divide en tres etapas principales:

A. De Curvas Orientadas a Clases de Homología

Se parte de una curva supersingular $E$ sobre $\mathbb{F}_p$ con una orientación $\iota: \mathcal{O} \hookrightarrow \text{End}(E)$, donde $\mathcal{O}$ es un orden en un cuerpo cuadrático imaginario.

• Se utiliza la acción del grupo de clases de ideales $\text{Pic}(\mathcal{O})$ sobre las curvas orientadas.
• Mediante correspondencias de Hecke y la correspondencia de Jacquet-Langlands, esta acción se transfiere a la homología relativa de la curva modular $X_0(N)$, específicamente al grupo $H_1(X_0(N), \mathcal{C}; \mathbb{Z})$, donde $\mathcal{C}$ es el conjunto de cúspides.
• A cada clase de ideal $[a] \in \text{Pic}(\mathcal{O})$ se le asocia una clase de homología $\gamma([a])$. El autor demuestra la equivalencia de tres construcciones para esta asignación:
  1. Módulos de Brandt (álgebra de cuaterniones).
  2. Puntos de Heegner y ciclos geodésicos en la curva analítica.
  3. Cociclos armónicos en el árbol de Bruhat-Tits (geometría $\ell$-ádica).

B. Integración de Coleman y Vectores de Periodos

Una vez obtenida la clase de homología $\gamma$, se evalúa contra un conjunto de formas cúbicas de peso 2 ($f_1, \dots, f_d$) mediante integración de Coleman.

• La integración de Coleman permite calcular integrales de diferenciales holomorfos sobre caminos en curvas sobre cuerpos $\ell$-ádicos sin necesidad de modelos algebraicos explícitos de la curva modular.
• Se define el vector de periodos $\ell$-ádico truncado $\Pi_m(\gamma)$ como el vector de integrales módulo $\ell^m$:
  $$\Pi_m(\gamma) = (\langle f_1, \gamma \rangle_\ell \pmod{\ell^m}, \dots, \langle f_d, \gamma \rangle_\ell \pmod{\ell^m}) \in (\mathbb{Z}/\ell^m\mathbb{Z})^d$$

C. El Problema de Inversión (MSI)

Se formula el Problema de Inversión de Símbolos Modulares (Modular Symbol Inversion - MSI):

• Entrada: Un vector $y \in (\mathbb{Z}/\ell^m\mathbb{Z})^d$ que se sabe es la imagen de algún "corto" representante de homología $\gamma_\star$ (con complejidad de camino acotada).
• Salida: Encontrar cualquier clase de homología $\gamma$ de complejidad comparable tal que $\Pi_m(\gamma) = y$.

3. Contribuciones Clave

1. Nuevo Mapeo Algebraico-Analítico: Se establece una conexión explícita entre la acción de grupos de clases en curvas supersingulares orientadas y la homología de curvas modulares, utilizando símbolos modulares como interfaz.
2. Definición del Problema MSI: Se introduce formalmente el problema MSI como una nueva suposición de dureza criptográfica. Este problema combina la dificultad de la búsqueda de caminos en grafos exponenciales (similar a las isogenias) con la estructura lineal de sistemas de congruencias (similar a SIS/LWE en retículos), pero con restricciones de esparsidad estructurada.
3. Algoritmos Computables: Se describe un flujo de trabajo práctico utilizando el algoritmo de Chen-Kedlaya-Lau para calcular integrales de Coleman directamente a partir de datos de formas modulares (expansiones $q$), evitando la construcción de modelos algebraicos costosos de $X_0(N)$.
4. Primitivas Criptográficas: Se esbozan dos construcciones basadas en MSI:
   • Un protocolo de identificación (tipo Sigma) con seguridad basada en la dificultad de invertir el mapeo de periodos.
   • Una función pseudoaleatoria (PRF) donde la clave secreta es una clase de homología corta.

4. Resultados y Análisis de Dureza

• Complejidad Combinatoria: La dureza del problema MSI se fundamenta en el crecimiento exponencial del número de caminos válidos de longitud $L$ en el grafo subyacente (árbol de Bruhat-Tits o grafo de símbolos modulares). El número de candidatos es aproximadamente $B^L$ (donde $B$ es el factor de ramificación).
• Resistencia a Ataques:
  • Ataques Clásicos: Se requiere un tiempo exponencial $O(B^L)$ para una búsqueda por fuerza bruta o $O(B^{L/2})$ para ataques de "meet-in-the-middle".
  • Ataques Cuánticos: Se espera una aceleración cuadrática genérica (algoritmo de Grover), resultando en complejidad $O(B^{L/2})$, lo que aún es exponencial en $L$.
  • Relación con otros problemas: El autor argumenta que MSI no es reducible polinomialmente a problemas de retículos estándar (SIS/LWE) debido a la restricción de que la solución debe ser un camino válido (esparsidad estructurada), ni a problemas de caminos de isogenias estándar, aunque comparten la naturaleza de búsqueda en grafos.
• Parámetros: Se sugiere que para lograr seguridad de $\lambda$ bits, se debe elegir $L$ tal que $B^L \approx 2^\lambda$ y el espacio de salida $\ell^{md}$ sea suficientemente grande ($\ell^{md} \gg (\#W_L)^2$) para evitar colisiones.

5. Significado e Impacto

• Nueva Familia de Primitivas Post-Cuánticas: El trabajo abre una nueva vía para la criptografía post-cuántica que no depende exclusivamente de la estructura de grafos de isogenias supersingulares ni de retículos euclidianos estándar, sino de la interacción entre topología algebraica (homología modular) y análisis $\ell$-ádico.
• Herramientas Computacionales: La aplicación de la integración de Coleman a la criptografía de isogenias ofrece métodos eficientes para calcular invariantes sin modelos algebraicos explícitos, lo cual es crucial para niveles altos de modularidad.
• Fundamentos Teóricos: Proporciona una comprensión más profunda de cómo la acción de grupos de clases en curvas supersingulares se refleja en la homología de curvas modulares, uniendo la teoría de números, la geometría algebraica y la teoría de grafos.

En resumen, el artículo propone un marco teórico y computacional novedoso donde la "inversión" de datos analíticos $\ell$-ádicos (periodos) para recuperar estructuras combinatorias (caminos de homología) constituye un problema computacionalmente difícil, ofreciendo una base prometedora para futuros esquemas criptográficos seguros contra ataques cuánticos.