An alternative approach towards attacks against fully-split PLWE instances

Resumo Técnico: Uma Abordagem Alternativa contra Ataques a Instâncias PLWE Totalmente Partidas (Fully-Split)

Enunciado do Problema
O problema do Aprendizado com Erros Polinomial (PLWE) é um pilar da criptografia pós-quântica, frequentemente favorecido por sua eficiência em relação ao Ring-LWE devido às suas propriedades algébricas estruturadas. No entanto, essa estrutura introduz vulnerabilidades potenciais. Trabalhos anteriores, notadamente [5, 6] e generalizados em [2], introduziram "ataques baseados em raízes" que exploram a existência de fatores polinomiais específicos (conhecidos como fatores ideais-$n$, $x^n - a$) sobre corpos finitos. Esses ataques utilizam homomorfismos de avaliação e operadores de traço para distinguir amostras PLWE de distribuições uniformes.

Embora o [2] tenha generalizado esses ataques para polinômios que fatoram sobre extensões de corpo, uma questão aberta crítica permanecia: Poderia um atacante contornar a falta de fatores vulneráveis em uma instância PLWE "segura" mapeando-a via um isomorfismo de anel para uma instância "vulnerável" (uma que possua fatores ideais-$n$ adequados), realizando o ataque lá, e inferindo a segurança da instância original? Este artigo investiga se tal estratégia de migração via isomorfismos oferece uma vantagem significativa contra instâncias PLware PLWE totalmente partidas (fully-split).

Metodologia
Os autores empregam uma abordagem algébrica rigorosa para analisar a viabilidade de transferir amostras PLWE entre diferentes anéis polinomiais. A metodologia procede em duas fases principais:

1. Generalização de Fatoração Arbitrária: O artigo explora primeiro a extensão de ataques baseados em raízes para polinômios sem fatores ideais-$n$. Utilizando o Lema 1, os autores demonstram que operadores de traço podem ser definidos sobre fatores irredutíveis arbitrários. No entanto, eles mostram que a probabilidade de sucesso de tais ataques depende fortemente do número de coeficientes com valor zero no fator, o que é tipicamente baixo para polinômios arbitrários, tornando o ataque impraticável no caso geral.

2. Análise de Isomorfismo em Configurações Totalmente Partidas (Fully-Split): O núcleo do trabalho foca no "método de isomorfismo". Os autores consideram dois polinômios, $f(x)$ e $g(x)$, ambos de grau $N$ e irredutíveis sobre $\mathbb{Z}[x]$, que compartilham a mesma "estrutura de fatoração" sobre $\mathbb{F}_q$ (ou seja, decompõem-se em fatores irredutíveis de mesmos graus).

   • Construção: Usando o Teorema Chinês dos Restos, eles constroem um isomorfismo explícito $\psi$ entre os anéis $R_q = \mathbb{F}_q[x]/(f(x))$ e $R'_q = \mathbb{F}_q[x]/(g(x))$. No caso totalmente partido (onde ambos os polinômios fatoram completamente em termos lineares), este isomorfismo é representado pelo produto de matrizes de Vandermonde: $\psi = V_g^{-1} \cdot V_f$.
   • Análise de Distorção: Os autores analisam o efeito de aplicar este isomorfismo às amostras PLWE seguido de uma avaliação em uma raiz $\beta$ de $g(x)$. Eles provam que a avaliação resultante é matematicamente equivalente a avaliar a amostra original em uma raiz correspondente $\alpha$ de $f(x)$.
   • Prova de Unicidade: Uma parte significativa da metodologia envolve provar que qualquer isomorfismo de anel entre tais anéis polinomiais totalmente partidos deve assumir esta forma específica (composição de homomorfismos de avaliação e o isomorfismo construído). Isso é estabelecido através dos Lemas 2, 3 e 4, e do Teorema 1.

Principais Contribuições

• Prova Formal de Invariância de Isomorfismo: O artigo fornece uma prova formal de que, para instâncias PLWE totalmente partidas, qualquer tentativa de migrar amostras para um cenário vulnerável via isomorfismo de anel não gera novas vulnerabilidades. O ruído (erro) introduzido pelo isomorfismo distorce as amostras de tal forma que as condições de distinguibilidade são idênticas às da instância original.
• Caracterização de Isomorfismos de Anel: Os autores caracterizam o conjunto completo de isomorfismos entre anéis polinomiais totalmente partidos, mostrando que eles são unicamente determinados pelo mapeamento das raízes. Isso prova que nenhum isomorfismo "oculto" existe que possa contornar a distorção do ruído.
• Extensão para Fatoração Arbitrária: O trabalho esclarece que, embora ataques baseados em raízes possam ser teoricamente aplicados a polinômios sem fatores ideais-$n$, a falta de restrições estruturais (especificamente o número de coeficientes zero) limita severamente sua probabilidade de sucesso, efetivamente fechando a porta para essa generalização como uma ameaça prática.

Resultados

• Distorção de Ruído: A aplicação de um isomorfismo $\psi$ seguido de uma avaliação em uma raiz $\beta$ de $g(x)$ resulta na expressão $b(\beta) = \sum a_j \alpha^j$, onde $\alpha$ é a raiz correspondente de $f(x)$. Isso demonstra que o ataque no cenário transformado é matematicamente idêntico ao ataque na configuração original.
• Falha da Estratégia de Migração: A análise confirma que, se um ataque baseado em raízes falha na instância PLWE original (devido ao alto ruído ou falta de distinguibilidade), ele também falhará em qualquer instância isomórfica. O isomorfismo não "limpa" o ruído; pelo contrário, ele preserva a dificuldade subjacente do problema.
• Análise de Raízes Específicas: O artigo analisa casos específicos onde a raiz de avaliação $\beta$ é $0$, $1$ ou uma raiz arbitrária. Em todos os casos, a avaliação resultante reduz-se à avaliação do polinômio original em uma raiz correspondente, confirmando que nenhuma vantagem é obtida.

Significância
O artigo conclui que a intuição referente à segurança das instâncias PLWE totalmente partidas está correta: se os ataques baseados em raízes não forem bem-sucedidos contra uma instância PLWE inicial, eles permanecerão malsucedidos mesmo se as amostras forem transferidas para uma configuração de PLWE potencialmente mais fraca via isomorfismos de anel.

Este resultado fornece uma fonte de confiança para a segurança das instâncias PLWE totalmente partidas, que são comuns em construções criptográficas devido à sua eficiência (por exemplo, em Transformadas de Número Teórico - NTT). O trabalho efetivamente descarta a "migração por isomorfismo" como um vetor viável para gerar novos ataques contra essas instâncias específicas. Os autores observam que, embora esta análise seja específica para polinômios totalmente partidos, ela cobre a vasta maioria das instâncias PLWE criptograficamente relevantes. O artigo não pretende resolver a segurança de instâncias PLWE não totalmente partidas ou outros vetores de ataque (como os ataques de ideal de Stickelberger mencionados na introdução), mas sim solidificar o entendimento dos ataques baseados em raízes dentro do domínio totalmente partido.