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

Each language version is independently generated for its own context, not a direct translation.

Imagine que você está tentando criar um sistema de segurança digital (uma assinatura eletrônica) que seja impossível de quebrar, mesmo por computadores quânticos do futuro. Os criptógrafos estão correndo contra o tempo para encontrar essa solução.

Este artigo apresenta uma nova ferramenta chamada SQInstructor. Para entender o que ela faz, vamos usar uma analogia com mapas de tesouros e labirintos.

1. O Cenário: Labirintos Mágicos (Curvas Elípticas)

Na criptografia moderna, usamos objetos matemáticos chamados "curvas elípticas". Imagine que cada curva é um labirinto mágico gigante.

O Segredo: Para navegar por esses labirintos, você precisa de um "mapa mestre" (chamado de endomorfismo).
O Problema: Se eu te der apenas o ponto de entrada e o ponto de saída do labirinto, é extremamente difícil descobrir qual caminho eu fiz para chegar lá. É como tentar adivinhar o trajeto de um carro apenas vendo onde ele começou e onde parou, sem ver o GPS.
A Solução Atual (SQIsign): O método atual (SQIsign) é muito eficiente e compacto, mas é como se o "carteiro" (quem assina) tivesse que resolver um quebra-cabeça matemático muito difícil e lento para criar a assinatura. Além disso, provar que é seguro é complicado.

2. A Nova Ideia: O "Nível de Estrutura" (Level Structures)

Os autores do artigo dizem: "E se, em vez de apenas pedir para ir do ponto A ao ponto B, nós adicionássemos uma regra extra ao labirinto?"

Essa regra é o Nível de Estrutura (Level Structure).

A Analogia: Imagine que dentro do labirinto, existem marcas de tinta em certos pontos (chamados de "pontos de torção").
A Regra: Ao criar sua assinatura, você não pode apenas ir de A para B. Você precisa garantir que, ao passar pelo labirinto, você pinte as marcas de tinta do ponto A exatamente sobre as marcas de tinta do ponto B.
Por que isso ajuda? Isso transforma o problema. Em vez de apenas encontrar qualquer caminho, você precisa encontrar um caminho que obedeça a essa "regra de pintura". Isso parece mais difícil, mas na verdade, para quem tem o segredo (o "carteiro"), é como ter um atalho mágico. Para quem tenta hackear, é como tentar adivinhar um caminho que pinte cores específicas em um labirinto escuro.

3. O Que é o SQInstructor?

O SQInstructor é um "manual de instruções" (um framework) que permite criar sistemas de assinatura usando essa ideia de "pintar as marcas".

O papel funciona assim:

O Carteiro (Proponente): Tem um segredo (um ideal matemático). Ele gera uma curva pública (o labirinto inicial).
O Desafio: O Verificador diz: "Ok, agora vá para este outro labirinto, mas lembre-se: você precisa garantir que as marcas de tinta do seu ponto de partida se alinhem perfeitamente com as marcas deste novo destino".
A Resposta: O carteiro usa seu segredo para encontrar o caminho (isogenia) que faz essa "pintura" funcionar.
A Verificação: O verificador olha o caminho. Se as marcas de tinta estiverem alinhadas corretamente, a assinatura é válida.

4. As Duas Maneiras de Fazer (1D e 2D)

O artigo mostra como usar essa ideia de duas formas diferentes, como se fossem dois tipos de veículos para atravessar o labirinto:

Versão 1D (O Caminhão Lento): Usa caminhos tradicionais (isogenias de 1 dimensão). É como dirigir um caminhão por uma estrada estreita. É mais lento e o caminho é longo, mas é a única maneira de fazer certas coisas complexas, como "assinaturas em anel" (onde um grupo assina, mas ninguém sabe quem foi).
Versão 2D (O Helicóptero Rápido): Usa caminhos multidimensionais (isogenias de 2 dimensões). É como usar um helicóptero para voar direto sobre o labirinto. É muito mais rápido e eficiente. O artigo mostra que essa versão é tão rápida quanto a melhor tecnologia atual (SQIsign), mas com a vantagem de ser mais fácil de provar matematicamente que é segura.

5. Por que isso é importante?

Segurança: O SQInstructor mantém a segurança contra computadores quânticos, mas com uma base matemática mais sólida e mais fácil de verificar.
Flexibilidade: Ele permite escolher entre ser super rápido (helicóptero) ou super versátil (caminhão), dependendo do que você precisa.
Inovação: Eles criaram uma "ponte" (correspondência Deuring) que traduz o problema do labirinto (curvas) para um problema de álgebra (quaterniões), onde é mais fácil resolver, e depois traduzem a resposta de volta.

Resumo em uma frase

O SQInstructor é um novo sistema de assinatura digital que adiciona uma "regra de alinhamento de cores" aos labirintos matemáticos, permitindo criar assinaturas que são rápidas, seguras contra computadores quânticos e matematicamente mais fáceis de provar que são invioláveis.

É como se os autores tivessem descoberto que, ao invés de apenas pedir para alguém atravessar um labirinto, se pedirmos para eles deixarem um rastro de tinta específico, o caminho se torna mais fácil para quem tem o mapa secreto, mas impossível para quem está tentando adivinhar.

Each language version is independently generated for its own context, not a direct translation.

Aqui está um resumo técnico detalhado do artigo "The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures", em português.

1. O Problema

A criptografia baseada em isogenias é uma candidata promissora para a criptografia pós-quântica. O esquema de assinatura SQIsign é atualmente o mais compacto em processo de padronização pelo NIST. No entanto, o SQIsign original enfrenta desafios:

Complexidade de Assinatura: O processo de assinatura é lento e complexo, dependendo de resolver equações de norma em álgebras de quatérnios (algoritmo KLPT).
Prova de Segurança: A prova de segurança (EUF-CMA) é difícil devido às limitações do algoritmo KLPT e à dificuldade de provar que a distribuição das assinaturas é indistinguível de aleatória (Zero-Knowledge).
Rigidez: O protocolo original exige que a resposta do provador "aniquile" uma estrutura de nível específica (um subgrupo cíclico), o que limita a generalização para primitivas avançadas como assinaturas em anel ou hashes camaleão.

O artigo propõe uma generalização deste paradigma, introduzindo o conceito de SQInstructor, que utiliza estruturas de nível (level structures) de forma mais flexível para definir o desafio e a resposta no protocolo de identificação.

2. Metodologia

Os autores desenvolvem um framework teórico e algorítmico baseado em três pilares principais:

A. Generalização da Correspondência de Deuring

A correspondência de Deuring estabelece uma equivalência entre curvas elípticas supersingulares e ordens máximas em álgebras de quatérnios.

Os autores estendem essa correspondência para curvas elípticas equipadas com estruturas de nível (bases de subgrupos de torção, definidas por subgrupos $\Gamma$ de $GL_2(\mathbb{Z}/N\mathbb{Z})$ ).
Eles definem anéis de endomorfismos $O(E, S)$ para curvas com estrutura de nível e provam que ideais locais principais nessas ordens correspondem a isogenias que preservam (ou mapeiam) essas estruturas.
Isso permite tratar o problema de encontrar uma isogenia entre duas curvas com estruturas de nível específicas como um problema de encontrar um ideal conectado em uma ordem sub-estruturada.

B. O Protocolo SQInstructor

O protocolo é um esquema de identificação de três etapas (Sigma-protocolo):

Compromisso: O provador envia uma curva $E_{com}$ derivada de uma chave secreta.
Desafio: O verificador envia uma estrutura de nível $S_{com}$ na curva $E_{com}$ .
Resposta: O provador deve produzir uma isogenia $\phi_{rsp}$ $ϕ_{r s p}$ que mapeie a estrutura de nível da chave pública ( $S_{pk}$ $S_{p k}$ ) para a estrutura de desafio ( $S_{com}$ $S_{co m}$ ).
- Diferente do SQIsign clássico (onde a resposta aniquila um ponto), aqui a resposta deve transportar uma estrutura para outra.
- O framework permite escolher o tipo de estrutura de nível (Borel, Cartan, Escalar) e o método de representação da isogenia (1-dimensional ou de alta dimensão).

C. Algoritmos e Implementação

Os autores abordam duas instâncias principais do framework:

Isogenias 1-Dimensionais (Baseadas em KLPT):
- Adaptam o algoritmo KLPT para resolver equações de norma com restrições de nível.
- Introduzem o algoritmo ScalarSigningKLPT e BorelSigningKLPT, que encontram ideais equivalentes com norma suave (smooth norm) respeitando a estrutura de nível.
- Demonstram como mapear esses ideais para cadeias de isogenias 1D.
Isogenias de Alta Dimensão (2D):
- Utilizam técnicas modernas (como as do SQIsign v2) para representar a resposta como uma isogenia de dimensão superior.
- Isso permite assinaturas mais rápidas e com tamanhos competitivos, evitando a necessidade de resolver equações de norma complexas para a resposta final, focando apenas na randomização do ideal.

3. Principais Contribuições

Correspondência de Deuring Explicíta com Estruturas de Nível: Fornecem uma correspondência explícita e algorítmica para curvas supersingulares com estruturas de nível, mesmo para níveis não suaves e grandes.
Framework SQInstructor: Um protocolo genérico que generaliza o SQIsign, permitindo flexibilidade na escolha da estrutura de nível e do método de isogenia.
Novos Algoritmos de Equação de Norma: Desenvolvimento de variantes do KLPT (como ScalarSigningKLPT) que resolvem equações de norma com restrições de nível, essenciais para a versão 1D do protocolo.
Análise de Segurança Rigorosa:
- Prova de 2-special soundness (sombras de segurança) baseada no problema do anel de endomorfismos.
- Análise de Zero-Knowledge utilizando oráculos de isogenia (Γ-UTO e FIDIO) e o modelo de oráculo aleatório, provando a segurança EUF-CMA.
Implementação e Benchmarks:
- Implementação de prova de conceito para a versão 1D.
- Implementação completa da versão 2D (alta dimensão), comparável ao SQIsign de referência.

4. Resultados

Desempenho: A implementação da versão 2D do SQInstructor apresenta desempenho muito similar ao SQIsign atual (NIST candidate).
- Tempo de Assinatura: Aumento marginal (ex: ~78.9 Mcycles vs 76.8 Mcycles para NIST I).
- Tamanho da Assinatura: Levemente maior devido à necessidade de codificar a matriz de desafio e a estrutura de nível, mas ainda compacto (ex: 174 bytes vs 148 bytes para NIST I).
- Verificação: Tempo de verificação ligeiramente aumentado, mas ainda muito rápido.
Versão 1D: Embora menos eficiente em termos de velocidade de assinatura, a versão 1D é crucial para primitivas avançadas (como assinaturas em anel e hashes camaleão) que dependem da simulabilidade das assinaturas, algo difícil de garantir com isogenias de alta dimensão.
Segurança: O esquema mantém a segurança baseada nas mesmas fundações do SQIsign (dificuldade de calcular o anel de endomorfismos), mas com uma estrutura de desafio mais rica que facilita provas de segurança em cenários complexos.

5. Significado

O trabalho do SQInstructor é significativo por várias razões:

Unificação Teórica: Ele unifica a compreensão de vários protocolos de isogenias (SIKE, FESTA, SQIsign) sob a ótica de estruturas de nível, mostrando que o SQIsign é um caso particular de um problema mais geral de mapeamento de estruturas.
Flexibilidade para Criptografia Avançada: Ao permitir a construção de protocolos onde a resposta "transporta" estruturas em vez de apenas aniquilá-las, o framework abre caminho para a construção de primitivas criptográficas mais complexas (como assinaturas em anel e esquemas de threshold) que eram difíceis de implementar com o SQIsign original.
Viabilidade Prática: A demonstração de que é possível implementar uma variante de alta dimensão com desempenho comparável ao SQIsign atual valida a abordagem como uma evolução natural e viável para a padronização pós-quântica.
Resolução de Limitações do KLPT: Ao fornecer algoritmos específicos para resolver equações de norma com restrições de nível, o trabalho supera barreiras algorítmicas que limitavam a generalização do SQIsign.

Em resumo, o SQInstructor não apenas melhora e generaliza o estado da arte em assinaturas baseadas em isogenias, mas também fornece a base teórica e prática necessária para expandir o uso dessas primitivas para cenários de criptografia mais avançados e complexos.