🔢 mathematics

Cycles of supersingular elliptic curves for pairing-based proof systems

Este artigo introduz novas construções de ciclos de curvas elípticas supersingulares para sistemas de prova baseados em emparelhamento recursivos ilimitados, oferecendo uma vantagem prática sobre os ciclos MNT anteriores ao permitir a construção eficiente de famílias infinitas de curvas e facilitar conexões com campos finitos menores e mais eficientes através de configurações "lollipop".

Autores originais: Craig Costello, Gaurish Korpal

Publicado 2026-08-18

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Craig Costello, Gaurish Korpal

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

No mundo digital, provar que você conhece um segredo sem revelar o segredo em si é uma ferramenta poderosa. Este é o coração da criptografia moderna, onde os "sistemas de prova" permitem que um computador convença um usuário de que um cálculo foi feito corretamente, sem a necessidade de reexecutar todo o cálculo. Para que essas provas sejam úteis no mundo real, elas devem ser curtas e rápidas de verificar. Um tipo específico de prova, conhecido como argumento não interativo sucinto, tornou-se uma pedra angular desta tecnologia. Para tornar essas provas ainda mais poderosas, pesquisadores desenvolveram uma maneira de empilhá-las, permitindo que uma prova verifique outra, criando uma cadeia de confiança que pode crescer indefinidamente. Este processo, chamado recursão, é o motor por trás de algumas das tecnologias de privacidade e escalabilidade mais avançadas em uso hoje. No entanto, construir essas cadeias requer um tipo muito específico de fundação matemática: pares de curvas elípticas que se encaixam perfeitamente como peças de um quebra-cabeça. Durante anos, as únicas peças conhecidas que se encaixavam nesta descrição eram raras, difíceis de encontrar e limitadas em número, criando um gargalo para a tecnologia.

Uma equipe de pesquisadores descobriu agora uma nova maneira de gerar esses pares de curvas essenciais, desbloqueando um vasto suprimento anteriormente inacessível. Eles descobriram que, ao usar uma classe diferente de objetos matemáticos chamados curvas supersingulares, podem construir uma família infinita desses pares de peças de quebra-cabeça. Ao contrário do método anterior, que dependia de um conjunto estreito de condições que tornava a busca por novos pares uma questão de sorte e de um esforço computacional imenso, esta nova abordagem funciona de forma confiável para quase qualquer número escolhido. Os pesquisadores demonstraram que poderiam construir esses novos ciclos e conectá-los a outras curvas eficientes para formar o que chamam de "lollipops" (pirulitos). Essas estruturas permitem que o trabalho pesado inicial de uma prova ocorra em um campo pequeno e rápido, enquanto o empilhamento recursivo acontece no ciclo maior e seguro. Em uma busca prática, eles construíram com sucesso dezoito exemplos distintos dessas novas estruturas, oferecendo um recurso flexível e abundante para a próxima geração de sistemas digitais seguros.

A jornada para esta descoberta começou com uma limitação na tecnologia existente. O padrão atual para estes sistemas de prova recursiva baseia-se em um arranjo específico de duas curvas elípticas, frequentemente referido como um ciclo. Neste arranjo, o número de pontos na primeira curva corresponde ao tamanho do campo que define a segunda, e vice-versa. Este equilíbrio delicado permite que a prova passe de uma curva para a outra perfeitamente. Por mais de uma década, a única maneira conhecida de construir tais ciclos utilizou curvas "ordinárias", um método desenvolvido por Miyaji, Nakabayashi e Takano. Embora este método funcione na teoria, na prática ele é incrivelmente esparso. Encontrar um novo par requer resolver equações matemáticas complexas onde os números devem ser exatos. À medida que os requisitos de segurança crescem, a probabilidade de tropeçar em um par válido cai para quase zero. É como tentar encontrar um grão de areia específico em uma praia que atenda a um conjunto preciso de critérios; a praia é infinita, mas os grãos certos são de uma raridade extrema. Esta escassez forçou os desenvolvedores a usar parâmetros mais antigos e menos seguros ou a abandonar o ideal de recursão ilimitada para cadeias mais curtas e limitadas.

Os pesquisadores perceberam que o gargalo não era o conceito do ciclo em si, mas o tipo específico de curva sendo utilizada. Eles voltaram sua atenção para curvas "supersingulares". Estas são uma variedade matemática diferente que, embora menos comum na criptografia padrão, possui propriedades únicas que as tornam ideais para esta tarefa específica. A compensação é que estas curvas devem ser definidas sobre campos matemáticos ligeiramente maiores, o que torna alguns cálculos um pouco mais pesados. No entanto, o benefício é esmagador: a nova construção funciona para quase qualquer número escolhido, desde que este cumpra um teste básico de primalidade. Não há necessidade de caçar números raros e sortudos. Os pesquisadores mostraram que, para qualquer número válido, eles poderiam gerar imediatamente um par funcional de curvas supersingulares. Isso transforma o problema de uma caça ao tesouro em um processo de fabricação. Em vez de encontrar alguns exemplos dispersos, eles agora podem produzir um número infinito desses ciclos sob demanda.

Para provar que este conceito funciona no mundo real, a equipe não se baseou apenas na teoria; eles construíram um mecanismo de busca para encontrar exemplos concretos. Eles se propuseram a construir o que chamam de "lollipops". Imagine um pirulito onde o bastão é uma cadeia de curvas eficientes e a parte redonda no topo é o ciclo recursivo. O bastão permite que a prova comece em um campo pequeno e rápido, tornando as etapas iniciais do cálculo muito rápidas. A parte redonda, o ciclo, permite que a prova seja empilhada e verificada recursivamente sem limites. Os pesquisadores desenvolveram um algoritmo para encontrar essas estruturas resolvendo um tipo específico de enigma numérico conhecido como equação de Pell. Eles executaram este algoritmo em computadores poderosos, buscando através de milhões de possibilidades. A busca foi bem-sucedida. Eles encontraram dezoito exemplos distintos destes lollipops, variando em tamanho para suportar níveis de segurança de 80 bits até 128 bits e além. Um de seus exemplos, uma instância grande com um campo de 956 bits, até mesmo expandiu os limites do interesse prático, mostrando que estas estruturas podem escalar para atender às necessidades de segurança futuras.

A significância destas descobertas reside na flexibilidade que oferecem aos designers de sistemas. Com o método antigo, os designers eram forçados a usar um conjunto específico, muitas vezes ineficiente, de parâmetros porque não existiam outras opções. Se quisessem maior segurança, teriam que aceitar um desempenho mais lento ou limites de recursão menores. Com os novos ciclos supersingulares, os designers podem escolher parâmetros que sejam otimizados para velocidade, como campos onde a matemática é particularmente rápida de computar, ou campos que possuam propriedades específicas úteis para aceleração de hardware. Eles também podem escolher conectar estes ciclos a outros tipos de curvas que não são amigáveis ao emparelhamento (pairing-friendly), mas que são extremamente eficientes para as etapas iniciais de uma prova. Esta capacidade de misturar e combinar componentes, criando um "lollipop" personalizado para uma aplicação específica, era impossível com a tecnologia anterior. Os pesquisadores observaram que, embora as novas curvas sejam ligeiramente maiores em algumas partes, a capacidade de otimizar o restante do sistema e a abundância disponível de ciclos tornam a compensação vantajosa.

O artigo conclui enfatizando que este é um avanço construtivo. Os pesquisadores não apenas provaram que estes ciclos existem, mas também forneceram as ferramentas para construí-los e um catálogo de dezoito exemplos funcionais. Eles reconhecem que o próximo passo é implementar estes novos ciclos em software real para medir os ganhos exatos de desempenho, pois as vantagens teóricas precisam ser pesadas contra os custos práticos dos campos maiores. No entanto, a porta agora está aberta. A escassez que outrora limitou o crescimento dos sistemas de prova recursiva foi removida. Ao mudar de curvas ordinárias para curvas supersingulares, os pesquisadores forneceram um novo e infinito suprimento dos blocos de construção matemáticos necessários para assegurar o futuro digital, permitindo sistemas de prova que são não apenas mais seguros, mas também mais adaptáveis às diversas necessidades do mundo real.

Resumo Técnico: Ciclos de Curvas Elípticas Supersingulares para Sistemas de Prova Baseados em Emparelhamento

Declaração do Problema
O artigo aborda as limitações dos atuais ciclos de 2-ciclos de curvas elípticas amigáveis a emparelhamento (pairing-friendly), especificamente o ciclo ordinário MNT (Miyaji-Nakabayashi-Takano), que serve como base para sistemas de prova recursiva baseados em emparelhamento (SNARKs). O ciclo MNT sofre de dois problemas primários:

Escassez de Instâncias Construíveis: Construir curvas MNT requer resolver equações de Pell para encontrar parâmetros onde o discriminante CM $D$ seja suficientemente pequeno (tipicamente $D < 10^{17}$ ) para tornar a computação dos polinômios de classe de Hilbert viável. À medida que o nível de segurança aumenta, a probabilidade de encontrar tais parâmetros torna-se exponencialmente pequena, tornando a construção de ciclos MNT de alta segurança praticamente inviável.
Pequenos Graus de Incorporação (Embedding Degrees): O ciclo MNT força os corpos finitos subjacentes a serem significativamente maiores do que o necessário para equilibrar o Problema do Logaritmo Discreto de Curva Elíptica (ECDLP) e o Problema do Logaritmo Discreto de Corpo Finito (DLP). Essa ineficiência impede a implantação generalizada de sistemas de prova baseados em emparelhamento.

Embora ciclos "híbridos" ou "não amigáveis ao emparelhamento" sejam mais fáceis de construir, eles carecem das vantagens de tamanho de prova constante dos sistemas baseados em emparelhamento (ex: Groth16). Além disso, as cadeias existentes de curvas amigáveis ao emparelhamento permitem apenas um número limitado de composições recursivas, falhando em suportar a recursão "ilimitada" necessária para sistemas de prova escaláveis.

Metodologia
Os autores propõem uma nova construção de 2-ciclos utilizando curvas elípticas supersingulares em vez de curvas ordinárias. A metodologia baseia-se nos seguintes componentes:

Parametrização: A construção utiliza primos $p = x^2 - x + 1$ e $q = x^2 + 1$ para inteiros $x$ , semelhante à configuração MNT. No entanto, ao contrário do MNT, a construção não depende de o discriminante CM ser pequeno.
Construção Supersingular via Algoritmo de Bröker: Em vez de usar o método CM, os autores empregam o algoritmo de Bröker para construir curvas supersingulares sobre corpos de extensão ( $\mathbb{F}_{p^u}$ e $\mathbb{F}_{q^v}$ ). Os graus de extensão $u$ e $v$ dependem de $x \pmod{12}$ , resultando em quatro casos possíveis (ex: $u, v \in \{2, 3, 4\}$ ).
Definição de Ciclo: Um 2-ciclo amigável ao emparelhamento é definido onde $p$ divide a ordem da curva sobre $\mathbb{F}_{q^v}$ e $q$ divide a ordem da curva sobre $\mathbb{F}_{p^u}$ . Os grupos alvo para os emparelhamentos são $\mathbb{F}_{p^4}^\times$ e $\mathbb{F}_{q^6}^\times$ , mantendo a equivalência de segurança ao ciclo MNT em relação ao DLP.
Construção Lollipop: Para abordar os problemas de eficiência dos pequenos graus de incorporação, os autores constroem "lollipops" (pirulitos). Um lollipop consiste em uma cadeia de curvas amigáveis ao emparelhamento (o "haste" ou stick) conectada a um ciclo amigável ao emparelhamento (o "laço" ou loop).
- Os autores derivam equações de Pell generalizadas ( $U^2 - 3DV^2 = -8$ ) para encontrar parâmetros onde uma curva $E$ definida sobre $\mathbb{F}_p$ (ou $\mathbb{F}_q$ ) tenha uma ordem relacionada a $N_q = x^2 - 2x + 2$ (ou $N_p = x^2 + x + 1$ ).
- Isso permite que a curva da "haste" seja definida sobre um corpo menor (com um primo $r$ menor) enquanto se conecta ao ciclo supersingular, permitindo aritmética inicial eficiente enquanto mantém a recursão ilimitada.

Principais Contribuições

Família Infinita de Ciclos Construíveis: O artigo apresenta uma construção que produz uma família infinita de ciclos amigáveis ao emparelhamento na prática. Ao contrário do ciclo MNT, que é teoricamente infinito mas praticamente finito devido às restrições do discriminante CM, a construção supersingular funciona para qualquer $x$ que resulte em primos $p$ e $q$ , independentemente do tamanho do discriminante.
Primeiros Lollipops Amigáveis ao Emparelhamento: Os autores fornecem a primeira construção explícita de lollipops amigáveis ao emparelhamento. Eles encontraram com sucesso 18 exemplos de lollipops $(2, 2)$ (uma cadeia de 2 conectada a um 2-ciclo) oferecendo níveis de segurança entre 80 e 128 bits.
Análise de Otimalidade: O artigo prova que os graus de extensão usados em sua construção ( $u \in \{2, 4\}, v \in \{2, 3\}$ ) são ótimos para a parametrização dada, mostrando que nenhum ciclo supersingular permite grupos alvo maiores que melhorariam significativamente o equilíbrio segurança/tamanho.

Resultos

Implementação: Os autores implementaram um algoritmo de busca usando PARI/GP e Magma. Eles resolveram equações de Pell generalizadas para discriminantes $D' < 10^{17}$ e identificaram 18 instâncias válidas de lollipops.
Segurança: Os lollipops encontrados fornecem 80 a 128 bits de segurança. A segurança do ECDLP da curva da "haste" aproxima-se da segurança do DLP dos corpos alvo, garantindo segurança equilibrada.
Comparação: O artigo compara uma instância padrão MNT298 (80 bits de segurança) com sua instância "lollipop-305-158". Enquanto o MNT298 requer primos de 298 bits, o lollipop permite que a camada inicial de prova opere sobre um corpo de primo de 158 bits (usando curvas não amigáveis ao emparelhamento como Weierstrass torcida ou curvas de Edwards torcidas), melhorando significativamente a eficiência para a primeira camada de recursão enquanto mantém a capacidade de recursão ilimitada do ciclo supersingular.
Compromissos (Trade-offs): Os autores reconhecem que os ciclos supersingulares são definidos sobre corpos de extensão quadrática (ou superior) ( $\mathbb{F}_{p^2}, \mathbb{F}_{q^2}$ ), tornando os elementos no grupo $G_1$ duas vezes maiores e as computações menos eficientes em comparação com o corpo base do ciclo MNT. No entanto, eles observam que a flexibilidade em escolher corpos com alta 2-adicidade e a capacidade de usar torções (twists) de grau superior para $G_2$ podem compensar esses custos.

Significância
O artigo afirma que sua principal significância reside em superar a "escassez" do ciclo MNT, desbloqueando assim a realização prática de famílias infinitas de ciclos amigáveis ao emparelhamento. Essa flexibilidade permite a construção de lollipops, que foi um problema motivador proposto pelo desafio Coda+Dekrypt SNARK em 2019, mas permaneceu sem solução até este trabalho.

Ao conectar curvas eficientes de campos pequenos não amigáveis ao emparelhamento a um ciclo supersingular, os autores permitem sistemas de prova que podem começar com aritmética altamente eficiente (tamanhos de campo otimizados) e transitar para uma composição recursiva ilimitada. Os autores enfatizam que, embora não forneçam benchmarks de desempenho concretos neste trabalho, a construção oferece um caminho teórico e prático para sistemas de prova baseados em emparelhamento escaláveis que antes estavam bloqueados pelas limitações do método CM em curvas ordinárias. Eles também observam que os emparelhamentos supersingulares são o único cenário conhecido onde o mínimo teórico de dois elementos de grupo por prova (Groth16) pode ser alcançado.

Mais como este