On the Spectral theory of Isogeny Graphs and Quantum Sampling of Secure Supersingular Elliptic curves

Resumen Técnico: Teoría Espectral de Grafos de Isogenía y Muestreo Cuántico de Curvas Elípticas Supersingulares Seguras

1. Planteamiento del Problema

La criptografía basada en isogenías es una de las principales candidatas para la criptografía post-cuántica. Su seguridad se basa en la dificultad de encontrar un camino de isogenías entre dos curvas elípticas supersingulares (problema del camino de isogenía) o, equivalentemente, calcular el anillo de endomorfismos de una curva dada (Problema EndRing).

Un requisito fundamental para la implementación segura de primitivas como la función hash CGL, esquemas de compromiso o funciones de derivación de claves (VDFs), es la capacidad de generar una curva supersingular "segura". Una curva se considera segura si su anillo de endomorfismos es desconocido para el generador y para cualquier adversario.

• El desafío actual: No existen algoritmos clásicos o cuánticos eficientes y probados para muestrear tales curvas sin un "setup confiado" (trusted setup). Los métodos existentes requieren recursos exponenciales o dependen de suposiciones heurísticas.
• Limitaciones de los métodos actuales: Los protocolos de configuración distribuida (trusted setup) son costosos y a menudo solo generan curvas sobre $\mathbb{F}_{p^2}$, mientras que muchas aplicaciones requieren curvas sobre $\mathbb{F}_p$ con una orientación específica (estructura de nivel).

2. Metodología y Enfoque

Los autores proponen algoritmos cuánticos de tiempo polinomial que explotan las propiedades espectrales de los grafos de isogenía supersingular y las acciones de grupos asociadas a curvas orientadas. El enfoque se basa en dos pilares teóricos principales:

1. Deslocalización de Autovalores (Spectral Delocalization):

   • Los grafos de isogenía $\ell$-supersingulares son grafos Ramanujan $(\ell+1)$-regulares.
   • Los autores demuestran que los autovectores de los operadores de adyacencia (matrices de Brandt) están deslocalizados. Esto significa que la "masa" del autovector no se concentra en un subconjunto pequeño de curvas, sino que se distribuye uniformemente sobre el grafo.
   • Se prueba una cota superior para la norma sup de los autovectores: $\|\phi\|_\infty \ll p^{-1/4+\epsilon}$, y se proporciona evidencia numérica para la deslocalización completa ($\|\phi\|_\infty \ll \log p / \sqrt{p}$).

2. Separación $\epsilon$ de Autovalores:

   • Para que el algoritmo de muestreo funcione, diferentes autovectores deben tener etiquetas espectrales (conjuntos de autovalores) distinguibles.
   • Bajo la Hipótesis de Riemann Generalizada (GRH), los autores prueban una propiedad de separación $\epsilon$ más fuerte que las asumidas heurísticamente en trabajos anteriores. Demuestran que la distancia entre los vectores de autovalores de dos formas propias distintas de Hecke es acotada inferiormente por una constante positiva, eliminando la necesidad de suposiciones heurísticas sobre la separación.

3. Contribuciones Clave y Algoritmos

El artículo presenta dos algoritmos cuánticos principales:

A. Algoritmo de Muestreo del Grafo Completo (Algoritmo 1)

• Objetivo: Generar una curva supersingular aleatoria sobre $\mathbb{F}_{p^2}$ con anillo de endomorfismos desconocido.
• Mecanismo:
  1. Prepara un estado cuántico superpuesto sobre los vértices del grafo de isogenía.
  2. Utiliza Estimación de Fase Cuántica (QPE) sobre una serie de operadores de adyacencia $A_{\ell}$ (correspondientes a diferentes primos $\ell$) para diagonalizarlos simultáneamente.
  3. La medición de las etiquetas espectrales (autovalores) colapsa el estado a un autovector específico.
  4. La medición final en la base de curvas produce una curva aleatoria.
• Complejidad:
  • Heurístico: $\tilde{O}(\log^4 p)$.
  • Condicional (bajo GRH): $\tilde{O}(\log^{13} p)$.
• Seguridad: La seguridad se demuestra bajo la dificultad promedio del problema EndRing. Gracias a la deslocalización probada, la probabilidad de que un adversario pueda calcular el anillo de endomorfismos de la curva de salida es despreciable, incluso si tiene acceso a las etiquetas espectrales medidas.

B. Algoritmo de Muestreo de Curvas Orientadas (Algoritmo 3)

• Objetivo: Generar curvas supersingulares orientadas por un orden cuadrático imaginario $\mathcal{O}$ sobre $\mathbb{F}_p$ (o $\mathbb{F}_{p^2}$).
• Mecanismo:
  • Aprovecha la acción regular del grupo de clases $\text{Cl}(\mathcal{O})$ sobre el conjunto de curvas orientadas.
  • Utiliza la Transformada de Fourier Cuántica (QFT) sobre el grupo de clases para muestrear uniformemente en la base de Fourier, y luego invierte el proceso para obtener una curva aleatoria en la base estándar.
• Seguridad: Se basa en la dureza del problema de Vectorización para la acción del grupo de clases (el problema de encontrar el ideal que conecta dos curvas orientadas). Este problema es la base de seguridad de esquemas como CSIDH.
• Ventaja: No requiere simulación de Hamiltonianos complejos ni QPE, siendo potencialmente más eficiente en la práctica que el Algoritmo 1.

4. Resultados Principales

1. Primeros Algoritmos Probados: Se presentan los primeros algoritmos cuánticos de tiempo polinomial con garantías de seguridad probada (bajo suposiciones estándar de teoría de números) para muestrear curvas seguras sin setup confiado.
2. Eliminación de Heurísticas: Se reemplazan las suposiciones heurísticas sobre la separación de autovalores (presentes en trabajos de Kane, Sharif, Silverberg y otros) por demostraciones rigurosas bajo GRH.
3. Prueba de Deslocalización: Se establece un nuevo resultado de deslocalización espectral para grafos de isogenía, probando la conjetura de Ergodicidad Cuántica Única (QUE) en este contexto y proporcionando evidencia numérica de deslocalización completa.
4. Análisis de Complejidad: Se proporciona un análisis detallado de la complejidad de puertas cuánticas, mostrando que el muestreo es factible en tiempo polinomial.

5. Significado e Impacto

• Resolución de un Problema Abierto: Este trabajo aborda uno de los problemas fundamentales abiertos en criptografía basada en isogenías: cómo generar parámetros seguros (curvas) de manera eficiente y sin confianza.
• Viabilidad de Primitivas Criptográficas: Permite la implementación segura y verificable de la función hash CGL y otras primitivas (VDFs, funciones pseudoaleatorias) sin depender de una autoridad central de configuración, lo cual es crucial para la descentralización y la seguridad a largo plazo.
• Robustez ante Adversarios: A diferencia de los métodos clásicos donde un adversario podría observar el camino de isogenía recorrido, los algoritmos cuánticos propuestos generan la curva mediante simulación de Hamiltonianos o acciones de grupo, sin generar un camino explícito que pueda ser registrado o explotado.
• Fundamentos Teóricos: Los resultados sobre la teoría espectral de grafos de isogenía y la conexión con formas automorfas cuaterniónicas tienen implicaciones más allá de la criptografía, contribuyendo a la teoría de números analítica y a la teoría de grafos aleatorios.

En conclusión, el artículo proporciona una solución teórica sólida y práctica para la generación de parámetros seguros en criptografía post-cuántica basada en isogenías, utilizando herramientas avanzadas de mecánica cuántica y teoría de números.