🔢 mathematics

Spinel: A Post-Quantum Signature Scheme Based on $\mathrm{SL}_n(\mathbb{F}_p)$ Hashing

Este artigo apresenta o Spinel, um novo esquema de assinatura digital pós-quântica que integra a estrutura do SPHINCS+ a uma nova família de funções de hash algébricas baseadas na dificuldade de navegar em grafos expansores sobre $\mathrm{SL}_n(\mathbb{F}_p)$ .

Autores originais: Asmaa Cherkaoui, Faraz Heravi, Delaram Kahrobaei, Siamak F. Shahandashti

Publicado 2026-02-12

📖 4 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Asmaa Cherkaoui, Faraz Heravi, Delaram Kahrobaei, Siamak F. Shahandashti

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

O Problema: O "Supercomputador" que pode quebrar cofres

Imagine que hoje, toda a segurança da internet (suas senhas, transações bancárias e mensagens privadas) funciona como se estivéssemos usando cadeados de alta tecnologia. Esses cadeados são baseados em problemas matemáticos tão difíceis que os computadores atuais levariam bilhões de anos para resolvê-los.

O problema é que está chegando um novo tipo de máquina: o Computador Quântico. Pense nele não como um computador comum, mas como um "super-mestre de chaves" que consegue testar todas as combinações de um cadeado quase instantaneamente. Se os computadores quânticos chegarem, os cadeados que usamos hoje vão "derreter" como se fossem feitos de chocolate no sol.

A Solução: O Projeto "Spinel"

Os cientistas estão tentando criar novos cadeados que nem mesmo esse "super-mestre de chaves" consiga abrir. O artigo apresenta o Spinel, um novo método de assinatura digital (que serve para provar que uma mensagem é autêntica e não foi alterada).

Para entender o Spinel, vamos usar duas analogias:

1. A Base: O Labirinto de SPHINCS+ (A Estrutura)

O Spinel não inventou a roda inteira; ele usa uma estrutura chamada SPHINCS+. Imagine que o SPHINCS+ é um labirinto gigantesco e infinito.
Para assinar um documento, você não entrega uma chave única; você entrega um "mapa" de como percorrer um caminho específico dentro desse labirinto. Como o labirinto é tão grande e complexo, é impossível para um invasor adivinhar o caminho certo para falsificar sua assinatura.

2. A Inovação: O "Caminho de Formigas" (A Função Hash)

A grande sacada deste artigo é o que eles colocaram dentro do labirinto.
Até agora, os labirintos usavam "tintas" comuns (funções matemáticas como SHA-256) para marcar os caminhos. Essas tintas são boas, mas são baseadas em regras que não sabemos ao certo se um computador quântico não conseguiria "ler" através delas.

Os autores do Spinel substituíram essa tinta por algo novo: Caminhadas em Grupos Matemáticos (SLn(Fp)).

A Analogia das Formigas:
Imagine que, em vez de usar tinta, para marcar o caminho no labirinto, nós soltamos um exército de formigas. Cada passo que a formiga dá é determinado por uma regra matemática muito rígida e complexa.

Se você der 10 passos, a formiga termina em um lugar.
Se você mudar apenas um milímetro no início do caminho, a formiga vai parar em um lugar completamente diferente, do outro lado do mundo.

Essa "caminhada das formigas" (que os matemáticos chamam de random walk) é baseada em estruturas de grupos que são tão complexas que nem mesmo o computador quântico consegue prever onde a formiga vai parar. É como tentar prever o movimento de um bilhão de formigas em um labirinto de espelhos: é matematicamente impossível.

O que os cientistas provaram?

Os autores não apenas criaram a ideia, eles fizeram o "teste de estresse":

Teste de Aleatoriedade: Eles verificaram se o caminho das "formigas" era realmente imprevisível (usando testes estatísticos rigorosos). O resultado? As formigas se comportam de forma totalmente caótica e imprevisível, o que é perfeito para a segurança.
Teste de Velocidade e Tamanho: Eles testaram o Spinel na prática. Descobriram que, embora ele seja um pouco mais "pesado" (as assinaturas são maiores e demoram um pouco mais para serem feitas) do que os métodos antigos, ele é perfeitamente viável para usos importantes, como certificados digitais de segurança máxima.

Resumo da Ópera

O Spinel é como se estivéssemos trocando os cadeados de metal da nossa casa por cadeados feitos de um material matemático desconhecido e ultra-complexo. Ele garante que, quando o "supercomputador quântico" chegar, nossas assinaturas digitais continuem sendo tão seguras quanto um segredo sussurrado em um labirinto infinito.

Resumo Técnico: Spinel – Um Esquema de Assinatura Pós-Quântica Baseado em Hashing em $SL_n(\mathbb{F}_p)$

1. O Problema (Contexto e Motivação)

Com a iminente chegada da computação quântica em larga escala, os algoritmos de assinatura digital atuais (baseados em fatoração ou logaritmos discretos) tornam-se vulneráveis. A comunidade criptográfica tem focado em esquemas baseados em funções de hash, como o SPHINCS+ (padronizado pelo NIST como SLH-DSA), devido à sua robustez.

No entanto, o SPHINCS+ utiliza funções de hash tradicionais (como SHA-256 ou SHAKE-256) cuja segurança é baseada em premissas heurísticas (não há uma prova matemática de que são difíceis de quebrar, apenas que ninguém conseguiu até agora). O problema central que este artigo aborda é: é possível fortalecer a base teórica de assinaturas baseadas em hash substituindo essas funções heurísticas por funções de hash algébricas, cuja segurança é fundamentada em problemas matemáticos comprovadamente difíceis?

2. Metodologia

Os autores propõem o Spinel, um novo esquema de assinatura que integra uma família de funções de hash algébricas ao framework do SPHINCS+.

A Função de Hash Algébrica: Baseia-se no paradigma de Tillich–Zémor, utilizando caminhadas aleatórias não-retroativas (non-backtracking random walks) em grafos de Cayley do grupo linear especial $SL_n(\mathbb{F}_p)$ .
Parâmetros de Implementação: Para evitar ataques conhecidos contra grupos de baixa dimensão (como o $SL_2$ ), os autores fixam a dimensão da matriz em $n=4$ e utilizam um corpo primo $\mathbb{F}_p$ com $p = 2^{31}-1$ . O digest (resumo) resultante tem 512 bits, garantindo resistência de 256 bits contra ataques de colisão (pelo limite de birthday).
Integração com SPHINCS+: O Spinel mantém toda a estrutura modular do SPHINCS+, incluindo:
- WOTS+: Assinaturas de uso único (one-time signatures).
- FORS: Assinaturas de poucos usos (few-time signatures).
- Hypertree: Uma estrutura de árvores de Merkle em camadas que permite o uso "sem estado" (stateless), possibilitando um número massivo de assinaturas.
Abordagem de Segurança: O esquema utiliza tweakable hashing (hashing ajustável) para garantir a separação de domínios através de endereços (ADRS), prevenindo ataques de múltiplos alvos.

3. Principais Contribuições

Introdução do Spinel: O primeiro esquema de assinatura que combina a estrutura provável do SPHINCS+ com a segurança algébrica de grupos lineares.
Validação Empírica do Hash: Os autores realizaram testes estatísticos rigorosos (NIST Statistical Test Suite) na nova função de hash, provando que ela produz saídas com propriedades de aleatoriedade robustas, complementando as análises teóricas prévias.
Análise de Degradação de Segurança: O trabalho modela matematicamente como a segurança do esquema diminui à medida que mais assinaturas são emitidas sob a mesma chave pública (devido à exposição parcial de segredos no componente FORS).
Implementação e Benchmarking: Forneceram uma implementação prática em C e avaliaram o desempenho computacional e o tamanho das assinaturas.

4. Resultados

Testes Estatísticos: A função de hash passou em todas as 15 categorias do teste NIST, confirmando sua viabilidade como um substituto para funções tradicionais.
Desempenho Computacional:
- O processo de verificação é significativamente mais rápido que o de assinatura (em torno de três ordens de magnitude de diferença).
- O custo de assinatura varia entre $10^{11}$ e $10^{12}$ ciclos de clock, dependendo dos parâmetros.
Trade-offs (Compromissos): Os resultados mostram um equilíbrio claro entre o tamanho da assinatura e a velocidade. Parâmetros otimizados para "menor tamanho de assinatura" tendem a degradar a segurança mais rapidamente sob uso intensivo do que parâmetros otimizados para "maior velocidade de assinatura".
Comparação com SPHINCS+: O Spinel apresenta assinaturas maiores e verificação ligeiramente mais lenta que o SPHINCS+ com SHAKE-256, o que é o preço a pagar pela utilização de premissas de segurança algébrica mais fortes.

5. Significância

O Spinel é significativo porque expande o "kit de ferramentas" da criptografia pós-quântica. Ao mover a segurança de funções de hash heurísticas para problemas de teoria de grupos (navegação em grafos expansores sobre $SL_n(\mathbb{F}_p)$ ), os autores oferecem um caminho para assinaturas digitais com fundamentos matemáticos muito mais sólidos. O esquema é considerado prático para aplicações onde a assinatura é feita com menos frequência do que a verificação, como em certificados de chaves públicas.