MDS matrices from skew polynomials with automorphisms and derivations

Resumo Técnico: Matrizes MDS de Polinômios Assimétricos com Automorfismos e Derivações

Definição do Problema
Matrizes de Distância Máxima Separável (MDS) são fundamentais para o design de camadas de difusão em criptografia de chave simétrica, proporcionando resistência ótima contra criptoanálise diferencial e linear. Embora matrizes circulantes e recursivas sejam amplamente estudadas devido às suas descrições algébricas eficientes e propriedades de implementação, as construções existentes frequentemente enfrentam limitações. Especificamente, matrizes circulantes clássicas de ordem par não podem ser simultaneamente MDS e involutórias (autoinversas), uma propriedade altamente desejável para reduzir os custos de implementação em primitivas criptográficas. Generalizações anteriores utilizando anéis de polinômios assimétricos com automorfismos (matrizes $\theta$-circulantes) abordaram alguns desses problemas, mas muitas vezes permanecem confinadas a campos finitos específicos ou produzem apenas matrizes quase-involutórias. Além, disso, a incorporação de derivações nessas estruturas algébricas para generalizar ainda mais a classe de matrizes MDS construíveis não foi totalmente explorada.

Metodologia
Os autores desenvolvem suas construções dentro do framework de anéis de polinômios assimétricos $F_q[X; \theta, \delta]$, onde $F_q$ é um campo finito, $\theta$ é um automorfismo de $F_q$ e $\delta$ é uma $\theta$-derivação. A multiplicação neste anel não comutativo é definida pela regra $Xa = \theta(a)X + \delta(a)$.

O artigo procede através dos seguintes passos metodológicos:

1. Definição de Matrizes $\delta\theta$-Circulantes: Os autores introduzem uma nova classe de matrizes estruturadas, denominadas matrizes $\delta\theta$-circulantes, que generalizam as matrizes circulantes e $\theta$-circulantes clássicas ao incorporar a $\theta$-derivação $\delta$. A estrutura dessas matrizes é analisada via sua associação com transformações lineares no anel quociente $F_q[X; \theta, \delta] / \langle X^m - 1 \rangle$.
2. Caracterização Algébrica: Condições necessárias e suficientes são derivadas para que essas matrizes satisfaçam a propriedade MDS e a propriedade involutória ($A^2 = I$). Isso envolve a análise do peso de polinômios no anel assimétrico e a relação entre o polinômio gerador e a matriz resultante.
3. Construções Quase Recursivas: O estudo estende-se a matrizes MDS quase recursivas, definidas via um produto específico de matrizes envolvendo potências do automorfismo e da derivação. Os autores focam em matrizes companheiras associadas a polinômios assimétricos mônicos.
4. Aplicação do Produto de Hadamard: O artigo utiliza o produto de Hadamard de polinômios para gerar novas famílias de matrizes MDS a partir de existentes, preservando a propriedade MDS sob condições específicas.

Principais Contribuições e Resultados

• Matrizes $\delta\theta$-Circulantes:

  • O artigo define matrizes $\delta\theta$-circulantes e estabelece uma correspondência entre essas matrizes e transformações lineares no anel de polinômios assimétricos.
  • O Teorema 2 fornece uma condição necessária e suficiente para que uma matriz $\delta\theta$-circulante seja MDS: para qualquer polinômio não nulo $Q_1(X)$, a soma dos pesos de $Q_1(X)$ e $Q_1(X)h(X) \pmod{X^m-1}$ deve ser pelo menos $m+1$.
  • O Teorema 3 estabelece a condição para uma matriz $\delta\theta$-circulante ser involutória, ligando-a ao produto do polinômio gerador e seu inverso no anel assimétrico.
  • Os autores observam que, enquanto as matrizes $\theta$-circulantes (onde $\delta=0$) podem produzir matrizes MDS involutórias de ordem par, a introdução de $\delta$ expande a classe de matrizes construíveis.

• Matrizes MDS Involutórias Quase Recursivas:

  • Uma contribuição central é a construção de matrizes MDS quase recursivas que são estritamente involutórias (não apenas quase-involutórias).
  • O Teorema 5 demonstra que, para uma escolha específica de automorfismo $\theta(a) = a^{q^2}$ e um polinômio $g(X)$ que gera um código MDS, a matriz quase recursiva $N_g$ resultante satisfaz $N_g^2 = I_m$. Isso representa uma melhoria estrita sobre resultados anteriores (ex: Cauchois et al. [15]) que produziam matrizes quase-involutórias confinadas a classes de campos restritas.
  • O Teorema 6 estende o critério para matrizes MDS recursivas para o cenário quase recursivo, relacionando a propriedade MDS ao peso dos múltiplos à direita do polinômio gerador.

• Geração de Novas Matrizes:

  • O Teorema 8 mostra que, se um polinômio $g(X)$ produz uma matriz MDS quase recursiva, então sua potência de Hadamard $(g(X))^{\diamond 2t}$ também produz uma matriz MDS quase recursiva. Isso permite a geração de múltiplas novas matrizes MDS a partir de um único polinômio semente.
  • O Teorema 7 estabelece que o polinômio recíproco de um gerador para matrizes MDS involutórias também gera matrizes MDS involutórias.

Significância e Alegações
O artigo alega que sua principal significância reside na generalização das construções existentes de matrizes MDS através da inclusão de $\theta$-derivações. Especificamente:

• Introduz matrizes $\delta\theta$-circulantes como uma classe mais ampla do que as matrizes $\theta$-circulantes, oferecendo um ambiente algébrico unificado tanto para estruturas circulantes quanto recursivas.
• Fornece uma construção para matrizes MDS quase recursivas involutórias de ordem par, abordando uma limitação na literatura anterior onde tais matrizes eram ou inexistentes no cenário clássico ou apenas quase-involutórias no cenário assimétrico. Isso é significativo para a eficiência criptográfica, pois matrizes involutórias eliminam a necessidade de implementações de inversas separadas.
• O trabalho oferece critérios explícitos para as propriedades MDS e involutória, facilitando a construção sistemática de tais matrizes.

Os autores reconhecem que uma caracterização completa de matrizes $\delta\theta$-circulantes MDS permanece um problema em aberto, particularmente quando o parâmetro $\beta$ (que define a derivação) não pertence ao corpo fixo do automorfismo. Eles também questionam se essas matrizes possuem propriedades de ortogonalidade como uma direção para trabalhos futuros.