🔢 mathematics

Cycles of supersingular elliptic curves for pairing-based proof systems

Este artículo introduce nuevas construcciones de ciclos de curvas elípticas supersingulares para sistemas de pruebas basados en emparejamientos recursivos no acotados, ofreciendo una ventaja práctica sobre los ciclos MNT previos al permitir la construcción eficiente de familias infinitas de curvas y facilitar conexiones con campos finitos más pequeños y eficientes a través de configuraciones de tipo "lollipop".

Autores originales: Craig Costello, Gaurish Korpal

Publicado 2026-08-18

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Craig Costello, Gaurish Korpal

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, demostrar que conoces un secreto sin revelar el secreto mismo es una herramienta poderosa. Este es el corazón de la criptografía moderna, donde los "sistemas de prueba" permiten que una computadora convenza a un usuario de que un cálculo se realizó correctamente, sin necesidad de volver a ejecutar todo el cálculo. Para que estas pruebas sean útiles en el mundo real, deben ser cortas y rápidas de verificar. Un tipo específico de prueba, conocido como argumento no interactivo sucinto, se ha convertido en una piedra angular de esta tecnología. Para hacer que estas pruebas sean aún más poderosas, los investigadores han desarrollado una forma de apilarlas, permitiendo que una prueba verifique a otra, creando una cadena de confianza que puede crecer indefinidamente. Este proceso, llamado recursión, es el motor detrás de algunas de las tecnologías de privacidad y escalabilidad más avanzadas en uso hoy en día. Sin embargo, construir estas cadenas requiere un tipo muy específico de fundamento matemático: pares de curvas elípticas que encajen perfectamente como piezas de un rompecabezas. Durante años, las únicas piezas conocidas que encajaban con esta descripción eran raras, difíciles de encontrar y limitadas en número, lo que creaba un cuello de botella para la tecnología.

Un equipo de investigadores ha descubierto ahora una nueva forma de generar estos pares de curvas esenciales, desbloqueando un suministro vasto y previamente inaccesible. Descubrieron que, al utilizar una clase diferente de objetos matemáticos llamados curvas supersingulares, pueden construir una familia infinita de estos pares de piezas de rompecabezas. A diferencia del método anterior, que dependía de un conjunto estrecho de condiciones que hacía que encontrar nuevos pares fuera una cuestión de suerte y un esfuerzo computacional inmenso, este nuevo enfoque funciona de manera confiable para casi cualquier número elegido. Los investigadores demostraron que podían construir estos nuevos ciclos y conectarlos con otras curvas eficientes para formar lo que llaman "lollipops" (piruletas). Estas estructuras permiten que el trabajo pesado inicial de una prueba ocurra en un campo pequeño y rápido, mientras que la acumulación recursiva ocurre en el ciclo más grande y seguro. En una búsqueda práctica, construyeron con éxito dieciocho ejemplos distintos de estas nuevas estructuras, ofreciendo un recurso flexible y abundante para la próxima generación de sistemas digitales seguros.

El viaje hacia este descubrimiento comenzó con una limitación en la tecnología existente. El estándar actual para estos sistemas de prueba recursivos depende de una disposición específica de dos curvas elípticas, a menudo denominadas un ciclo. En esta disposición, el número de puntos en la primera curva coincide con el tamaño del campo que define a la segunda, y viceversa. Este delicado equilibrio permite que la prueba pase de una curva a la otra sin problemas. Durante más de una década, la única forma conocida de construir tales ciclos fue utilizando curvas "ordinarias", un método desarrollado por Miyaji, Nakabayashi y Takano. Aunque este método funciona en teoría, en la práctica es increíblemente escaso. Encontrar un nuevo par requiere resolver ecuaciones matemáticas complejas donde los números deben ser precisos. A medida que los requisitos de seguridad crecen, la probabilidad de tropezar con un par válido cae a casi cero. Es como intentar encontrar un grano de arena específico en una playa que cumple con un conjunto de criterios precisos; la playa es infinita, pero los granos adecuados son de una escasez extrema. Esta escasez ha obligado a los desarrolladores a usar parámetros más antiguos y menos seguros, o a abandonar el ideal de la recursión ilimitada en favor de cadenas más cortas y limitadas.

Los investigadores se dieron cuenta de que el cuello de botella no era el concepto del ciclo en sí, sino el tipo específico de curva que se estaba utilizando. Dirigieron su atención a las curvas "supersingulares". Estas son una variedad matemática diferente que, aunque menos común en la criptografía estándar, posee propiedades únicas que las hacen ideales para esta tarea específica. La desventaja es que estas curvas deben definirse sobre campos matemáticos ligeramente más grandes, lo que hace que algunos cálculos sean un poco más pesados. Sin embargo, el beneficio es abrumador: la nueva construcción funciona para casi cualquier número elegido, siempre que cumpla con una prueba de primalidad básica. No hay necesidad de buscar números raros y afortunados. Los investigadores demostraron que, para cualquier número válido, podían generar inmediatamente un par de curvas supersingulares funcional. Esto transforma el problema de una búsqueda del tesoro en un proceso de fabricación. En lugar de encontrar unos pocos ejemplos dispersos, ahora pueden producir un número infinito de estos ciclos bajo demanda.

Para demostrar que este concepto funciona en el mundo real, el equipo no solo se basó en la teoría; construyeron un motor de búsqueda para encontrar ejemplos concretos. Se propusieron construir lo que llaman "lollipops". Imagine un bastón de caramete donde el palo es una cadena de curvas eficientes y la parte redonda en la parte superior es el ciclo recursivo. El palo permite que la prueba comience en un campo pequeño y rápido, haciendo que los pasos iniciales del cálculo sean muy rápidos. La parte redonda, el ciclo, permite que la prueba sea apilada y verificada recursivamente sin límite. Los investigadores desarrollaron un algoritmo para encontrar estas estructuras resolviendo un tipo específico de acertijo numérico conocido como la ecuación de Pell. Ejecutaron este algoritmo en computadoras potentes, buscando entre millones de posibilidades. La búsqueda fue exitosa. Encontraron dieciocho ejemplos distintos de estos lollipops, que varían en tamaño para soportar niveles de seguridad desde 80 bits hasta 128 bits y más allá. Uno de sus ejemplos, una instancia grande con un campo de 956 bits, incluso superó los límites del interés práctico, mostrando que estas estructuras pueden escalar para satisfacer las necesidades de seguridad futuras.

La importancia de estos hallazgos reside en la flexibilidad que ofrecen a los diseñadores de sistemas. Con el método antiguo, los diseñadores se veían obligados a usar un conjunto de parámetros específico y a menudo ineficiente porque no existían otras opciones. Si querían mayor seguridad, tenían que aceptar un rendimiento más lento o límites de recursión más cortos. Con los nuevos ciclos supersingulares, los diseñadores pueden elegir parámetros que estén optimizados para la velocidad, como campos donde las matemáticas son particularmente rápidas de computar, o campos que tengan propiedades específicas útiles para la aceleración por hardware. También pueden elegir conectar estos ciclos con otros tipos de curvas que no son aptas para emparejamientos (pairing-friendly) pero que son extremadamente eficientes para los pasos iniciales de una prueba. Esta capacidad de mezclar y combinar componentes, creando un "lollipop" personalizado para una aplicación específica, era imposible con la tecnología anterior. Los investigadores señalaron que, si bien las nuevas curvas son ligeramente más grandes en algunas partes, la capacidad de optimizar el resto del sistema y la enorme abundancia de ciclos disponibles hacen que la compensación valga la pena.

El artículo concluye enfatizando que esto es un avance constructivo. Los investigadores no solo han demostrado que estos ciclos existen, sino que han proporcionado las herramientas para construirlos y un catálogo de dieciocho ejemplos funcionales. Reconocen que el siguiente paso es implementar estos nuevos ciclos en software real para medir las ganancias exactas de rendimiento, ya que las ventajas teóricas deben sopesarse frente a los costos prácticos de los campos más grandes. Sin embargo, la puerta ahora está abierta. La escasez que una vez limitó el crecimiento de los sistemas de prueba recursivos ha sido eliminada. Al pasar de las curvas ordinarias a las supersingulares, los investigadores han proporcionado un suministro infinito de los bloques de construcción matemáticos necesarios para asegurar el futuro digital, permitiendo sistemas de prueba que no solo son más seguros, sino también más adaptables a las diversas necesidades del mundo real.

Resumen Técnico: Ciclos de Curvas Elípticas Supersingulares para Sistemas de Pruebas Basados en Emparejamientos

Planteamiento del Problema
El artículo aborda las limitaciones de los ciclos existentes de curvas elípticas compatibles con emparejamientos (pairing-friendly), específicamente el ciclo ordinario de Miyaji-Nakabayashi-Takano (MNT), que sirve como base para los sistemas de pruebas (SNARKs) basados en emparejamientos recursivos. El ciclo MNT sufre dos desventajas principales:

Escasez de Instancias Construibles: La construcción de curvas MNT requiere resolver ecuaciones de Pell para encontrar parámetros donde el discriminante de la Multiplicación Compleja (CM) $D$ sea suficientemente pequeño (típicamente $D < 10^{17}$ ) para que el cálculo de los polinomios de clase de Hilbert sea factible. A medida que el nivel de seguridad aumenta, la probabilidad de encontrar tales parámetros se vuelve exponencialmente pequeña, lo que hace que la construcción de ciclos MNT de alta seguridad sea prácticamente inviable.
Grados de Inmersión Pequeños: El ciclo MNT obliga a que los campos finitos subyacentes sean significativamente más grandes de lo necesario para equilibrar el Problema del Logaritmo Discreto de la Curva Elíptica (ECDLP) y el Problema del Logaritmo Discreto del Campo Finito (DLP). Esta ineficiencia obstaculiza el despliegue generalizado de los sistemas de pruebas basados en emparejamientos.

Si bien los ciclos "híbridos" o "no compatibles con emparejamientos" son más fáciles de construir, carecen de las ventajas de tamaño de prueba constante de los sistemas basados en emparejamientos (por ejemplo, Groth16). Además, las cadenas existentes de curvas compatibles con emparejamientos solo permiten un número limitado de composiciones recursivas, fallando en el soporte de la recursión "ilimitada" requerida para sistemas de pruebas escalables.

Metodología
Los autores proponen una nueva construcción de ciclos de 2 utilizando curvas elípticas supersingulares en lugar de curvas ordinarias. La metodología se basa en los siguientes componentes:

Parametrización: La construcción utiliza primos $p = x^2 - x + 1$ y $q = x^2 + 1$ para enteros $x$ , de forma similar a la configuración MNT. Sin embargo, a diferencia de MNT, la construcción no depende de que el discriminante CM sea pequeño.
Construcción Supersingular mediante el Algoritmo de Bröker: En lugar de utilizar el método CM, los autores emplean el algoritmo de Bröker para construir curvas supersingulares sobre campos de extensión ( $\mathbb{F}_{p^u}$ y $\mathbb{F}_{q^v}$ ). Los grados de extensión $u$ y $v$ dependen de $x \pmod{12}$ , lo que resulta en cuatro casos posibles (por ejemplo, $u, v \in \{2, 3, 4\}$ ).
Definición del Ciclo: Se define un ciclo de 2 compatible con emparejamientos donde $p$ divide el orden de la curva sobre $\mathbb{F}_{q^v}$ y $q$ divide el orden de la curva sobre $\mathbb{F}_{p^u}$ , manteniendo la equivalencia de seguridad con el ciclo MNT respecto al DLP. Los grupos objetivo para los emparejamientos son $\mathbb{F}_{p^4}^\times$ y $\mathbb{F}_{q^6}^\times$ .
Construcción de "Lollipop" (Pirulí): Para abordar los problemas de eficiencia de los grados de inmersión pequeños, los autores construyen "lollipops". Un lollipop consiste en una cadena de curvas compatibles con emparejamientos (el "palito") conectada a un ciclo compatible con emparejamientos (el "bucle").
- Los autores derivan ecuaciones de Pell generalizadas ( $U^2 - 3DV^2 = -8$ ) para encontrar parámetros donde una curva $E$ definida sobre $\mathbb{F}_p$ (o $\mathbb{F}_q$ ) tiene un orden relacionado con $N_q = x^2 - 2x + 2$ (o $N_p = x^2 + x + 1$ ).
- Esto permite que la curva del "palito" se defina sobre un campo más pequeño (con un primo $r$ más pequeño) mientras se conecta al ciclo supersingular, permitiendo una aritmética inicial eficiente mientras se retiene la capacidad de recursión ilimitada.

Contribuciones Clave

Familia Infinita de Ciclos Construibles: El artículo presenta una construcción que produce una familia infinita de ciclos compatibles con emparejamientos en la práctica. A diferencia del ciclo MNT, que es teóricamente infinito pero prácticamente finito debido a las restricciones del discriminante CM, la construcción supersingular funciona para cualquier $x$ que resulte en primos $p$ y $q$ , independientemente del tamaño del discriminante.
Primeros Lollipops Compatibles con Emparejamientos: Los autores proporcionan la primera construcción explícita de lollipops compatibles con emparejamientos. Encontraron con éxito 18 ejemplos de lollipops $(2, 2)$ (una cadena de 2 conectada a un ciclo de 2) que ofrecen niveles de seguridad entre 80 y 128 bits.
Análisis de Optimización: El artículo demuestra que los grados de extensión utilizados en su construcción ( $u \in \{2, 4\}, v \in \{2, 3\}$ ) son óptimos para la parametrización dada, mostrando que ningún ciclo supersingular permite grupos objetivo más grandes que mejorarían significativamente el equilibrio entre seguridad y tamaño.

Resultos

Implementación: Los autores implementaron un algoritmo de búsqueda utilizando PARI/GP y Magma. Resolvieron ecuaciones de Pell generalizadas para discriminantes $D' < 10^{17}$ e identificaron 18 instancias válidas de lollipops.
Seguridad: Los lollipops encontrados proporcionan entre 80 y 128 bits de seguridad. La seguridad del ECDLP de la curva del "palito" coincide estrechamente con la seguridad del DLP de los campos objetivo, asegurando una seguridad equilibrada.
Comparación: El artículo compara una instancia estándar de MNT298 (80 bits de seguridad) con su instancia "lollipop-305-158". Mientras que MNT298 requiere primos de 298 bits, el lollipop permite que la capa inicial de la prueba opere sobre un campo de un primo de 158 bits (usando curvas no compatibles con emparejamientos como curvas de Weierstrass corta o de Edwards torcido), mejorando significativamente la eficiencia para la primera capa de recursión mientras mantiene la capacidad de recursión ilimitada del ciclo supersingular.
Compromisos (Trade-offs): Los autores reconocen que los ciclos supersingulares se definen sobre campos de extensión cuadrática (o superior) ( $\mathbb{F}_{p^2}, \mathbb{F}_{q^2}$ ), lo que hace que los elementos en el grupo $G_1$ sean el doble de grandes y las computaciones menos eficientes en comparación con el campo base del ciclo MNT. Sin embargo, señalan que la flexibilidad para elegir campos con alta 2-adicidad y la capacidad de usar twists de grado superior para $G_2$ pueden compensar estos costos.

Significancia
El artículo afirma que su principal significancia radica en superar la "escasez" del ciclo MNT, desbloqueando así la realización práctica de familias infinitas de ciclos compatibles con emparejamientos. Esta flexibilidad permite la construcción de lollipops, que fue un problema motivador planteado por el desafío Coda+Dekrypt SNARK en 2019 pero que permaneció sin resolver hasta este trabajo.

Al conectar curvas eficientes de campos pequeños no compatibles con emparejamientos a un ciclo supersingular, los autores permiten sistemas de pruebas que pueden comenzar con una aritmética altamente eficiente (tamaños de campo óptimos) y transicionar hacia una composición recursiva ilimitada. Los autores enfatizan que, si bien no proporcionan comparativas de rendimiento concretas en este trabajo, la construcción ofrece un camino teórico y práctico hacia sistemas de pruebas basados en emparejamientos escalables que anteriormente estaban bloqueados por las limitaciones del método CM en curvas ordinarias. También señalan que los emparejamientos supersingulares son el único entorno conocido donde se puede lograr el mínimo teórico de dos elementos de grupo por prueba (Groth16).

Más como este