Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

Resumo Técnico: Criptanálise da Função Pseudoaleatória de Legendre sobre Campos de Extensão

Autores: Daksh Pandey (IIT Roorkee)
Contexto: O artigo investiga a segurança da Função Pseudoaleatória (PRF) baseada no Símbolo de Legendre quando implementada em campos de extensão ($\mathbb{F}_{p^r}$), em vez dos campos primos tradicionais ($\mathbb{F}_p$). Embora a PRF de Legendre seja altamente eficiente para Computação Multi-Parte (MPC) e Provas de Conhecimento Zero (ZKP) devido à sua baixa complexidade multiplicativa, sua segurança em campos de extensão não havia sido totalmente analisada até este trabalho.

---

1. O Problema

A PRF de Legendre original opera sobre um campo primo $\mathbb{F}_p$, onde a entrada é um deslocamento linear simples $(x + K)$. Para otimizar o desempenho em protocolos criptográficos específicos, há uma tendência de migrar essas operações para campos de extensão $\mathbb{F}_{p^r}$.

• A Hipótese de Segurança: Acredita-se que a representação polinomial das entradas em $\mathbb{F}_{p^r}$ introduz uma "fratura" no padrão de adição sequencial (devido à ausência de "carregamento" ou carry entre coeficientes polinomiais), o que deveria neutralizar ataques clássicos de colisão por janela deslizante (sliding-window).
• A Questão: A estrutura algébrica dos campos de extensão realmente protege a chave secreta contra ataques passivos e ativos, ou existem vulnerabilidades estruturais exploráveis?

---

2. Metodologia

O autor emprega uma abordagem analítica rigorosa dividida em dois modelos de ameaça:

A. Modelo de Ameaça Passiva (Consultas Aditivas Sequenciais)

• Análise da Codificação: O estudo formaliza como inteiros sequenciais são mapeados para polinômios em $\mathbb{F}_{p^r}$. Demonstra-se que a adição de inteiros ($n \to n+1$) não resulta em uma diferença constante no domínio polinomial, mas sim em uma sequência de diferenças determinística e periódica (a "fratura sem carregamento").
• Técnica de "Assinatura Diferencial": O autor propõe uma nova técnica de agrupamento (bucketing) baseada na forma estrutural das sequências de diferenças. Em vez de tentar encontrar colisões diretas em janelas contíguas (que falham devido à fratura), o atacante agrupa janelas de saída que compartilham a mesma "assinatura" de diferença polinomial.
• Recuperação Passiva: Ao agrupar as janelas por assinatura, o atacante reduz o espaço de busca e recupera a chave através de uma tabela de colisão, explorando a periodicidade determinística das diferenças.

B. Modelo de Ameaça Ativa (Consultas Escolhidas)

• Exploração de Homomorfismo Multiplicativo: O autor demonstra que um atacante ativo pode contornar completamente as limitações aditivas do grupo polinomial.
• Sequência Geométrica: Em vez de consultar entradas aditivas, o atacante solicita a avaliação da PRF em uma sequência geométrica gerada por um polinômio primitivo $g(x)$ (ou seja, $g^1, g^2, g^3, \dots$).
• Fatoração Algébrica: Devido à propriedade multiplicativa do Símbolo de Legendre generalizado, a avaliação $L(g^i + K)$ pode ser fatorada algebricamente em uma constante dependente da chave e uma sequência de referência universal deslocada por um logaritmo discreto. Isso transforma o problema de quebra de chave em um problema de deslocamento de índice.

---

3. Contribuições Principais

1. Primeira Criptanálise Abrangente: Este é o primeiro trabalho a analisar sistematicamente a PRF de Legendre de grau único ($d=1$) sobre campos de extensão $\mathbb{F}_{p^r}$.
2. Refutação da Defesa "Sem Carregamento": O paper prova que a ausência de carry em adições polinomiais, longe de ser uma defesa, cria uma periodicidade determinística que pode ser explorada passivamente.
3. Novo Ataque Passivo (Shape-Bucketing): Introdução de uma técnica que agrupa janelas de saída por sua "assinatura diferencial", permitindo a recuperação passiva da chave com complexidade $O(U \cdot p^r / M)$.
4. Ataque Ativo Otimizado: Demonstração de que, sob um modelo de consulta escolhida, a segurança pode ser quebrada em $O(p^r / M)$ operações, generalizando o ataque de colisão de tabela para o grupo multiplicativo do campo de extensão.
5. Definição de Limites de Segurança: Estabelecimento formal de que variantes de grau único são inseguras e que variantes de grau superior ($d \ge 2$) são necessárias para segurança exponencial.

---

4. Resultados

• Quebra da PRF de Grau Único ($d=1$): A PRF de Legendre sobre $\mathbb{F}_{p^r}$ com chave de grau único é totalmente quebrada tanto em cenários passivos quanto ativos.
  • Passivo: A chave é recuperada explorando a periodicidade das diferenças polinomiais.
  • Ativo: A chave é recuperada explorando o homomorfismo multiplicativo em sequências geométricas, reduzindo o problema a um deslocamento de logaritmo discreto.
• Complexidade Computacional: Os ataques reduzem a complexidade de segurança para o limite teórico inferior, tornando a PRF de grau único impraticável para uso seguro em campos de extensão.
• Validação de Variantes de Grau Superior: A análise mostra que variantes onde a chave é um polinômio de grau $d \ge 2$ (ex: $x^2 + K_1x + K_0$) impedem a fatoração algébrica necessária para os ataques acima, neutralizando a eficiência do ataque de colisão. No entanto, ataques de "Meet-in-the-Middle" ainda podem reduzir a complexidade, sugerindo que graus $d \ge 3$ ou $4$ são necessários para uma margem de segurança robusta.

---

5. Significado e Impacto

• Revisão de Protocolos MPC e ZKP: Este trabalho alerta a comunidade criptográfica de que a migração da PRF de Legendre para campos de extensão para ganhos de eficiência não é segura se mantiver a estrutura de grau único. Protocolos que dependem dessa construção devem ser revisados.
• Diretrizes de Implementação: O artigo estabelece que, para garantir segurança em campos de extensão, é obrigatório o uso de variantes de chave de grau superior ($d \ge 2$). O uso de $d=1$ em $\mathbb{F}_{p^r}$ deve ser considerado uma falha de segurança crítica.
• Avanço Teórico: A descoberta de que a "fratura sem carregamento" é determinística e explorável adiciona uma nova camada de entendimento sobre a interação entre aritmética polinomial e propriedades de símbolos de caracteres em campos finitos.

Em suma, o artigo conclui que a segurança da PRF de Legendre em campos de extensão depende inteiramente da complexidade algébrica da chave (grau do polinômio), e que a simplicidade do deslocamento linear ($d=1$) é fatalmente vulnerável a ataques estruturais tanto passivos quanto ativos.