The Closure of LCD-to-GI Reductions via Generalized Inner Products

Resumo Técnico: O Fechamento das Reduções de LCD para GI via Produtos Internos Generalizados

1. Formulação do Problema

O Problema de Equivalência por Permutação (PEP) para códigos lineares pergunta se dois códigos lineares dados são idênticos até uma permutação de coordenadas. Este problema é fundamental tanto para a classificação de códigos lineares quanto para a análise de segurança de criptografia baseada em códigos (por exemplo, o esquema de assinatura LESS e o esquema SPECK).

A complexidade do PEP está intimamente ligada ao problema do Isomorfismo de Grafos (GI). Embora o PEP seja geralmente considerado difícil, um avanço significativo de Bardet et al. [3] demonstrou que o PEP para códigos Dual Complementário Linear (LCD) (códigos com um casco trivial, isto é, $C \cap C^\perp = \{0\}$) reduz-se ao GI em tempo polinomial. Esta redução mapeia um código LCD para um grafo ponderado através de seu projetor ortogonal $\Pi_C = G^T(GG^T)^{-1}G$.

No entanto, este método depende da matriz de Gram $GG^T$ ser não singular, o que restringe sua aplicabilidade a códigos LCD. Códigos com cascos não triviais (onde $\dim(\text{Hull}(C)) \ge 1$) não podem ser processados por esta construção específica. A questão central abordada neste artigo é: Até onde o método do projetor ortogonal pode ser estendido? Especificamente, pode ele ser generalizado para códigos com cascos não triviais usando uma forma bilinear diferente e, se sim, quais são os limites estruturais precisos de tal redução?

2. Metodologia

Os autores generalizam o produto interno padrão para formas bilineares simétricas não degeneradas arbitrárias representadas por uma matriz de estrutura $M$.

• Projetores Generalizados: Eles definem um código $M$-dual $C^{\perp_M}$ e um casco $M$ $\text{Hull}_M(C)$. Para um código $M$-LCD (onde $\text{Hull}_M(C) = \{0\}$), eles constroem um projetor ortogonal generalizado:
  $$\Pi_{C,M} = M G^T (G M G^T)^{-1} G$$
• Condição de Redução: O cerne da redução baseia-se na identidade $\Pi_{CP, M} = P^T \Pi_{C,M} P$, onde $P$ é uma matriz de permutação. Esta identidade garante que, se dois códigos forem equivalentes por permutação, seus projetores serão isomorfos como grafos ponderados.
• Caracterização de $M$: Os autores investigam quais matrizes de estrutura $M$ satisfazem a condição de que $P M P^T = M$ (ou um múltiplo escalar disso) para todas as permutações $P$. Isso é necessário para garantir que o projetor se comporte corretamente sob permutação.
• Enumeração e Algoritmos: Usando somas de caracteres sobre formas quadráticas (especificamente o teorema de Weil), os autores derivam fórmulas de enumeração exatas para o número de códigos redutíveis. Eles também constroem um algoritmo de tempo polinomial que tenta encontrar uma $M$ adequada para reduzir um par dado de códigos ao GI.

3. Contribuições e Resultados Principais

A. Caracterização das Matrizes de Estrutura Válidas (Teorema 3.5)
O artigo prova que o método do projetor ortogonal produz uma redução válida ($C_1 \cong C_2 \iff \Pi_{C_1, M} \cong \Pi_{C_2, M}$) se e somente se a matriz de estrutura $M$ tiver a forma:
$$M = aI + bJ$$
onde $I$ é a matriz identidade, $J$ é a matriz de todos os uns, e $a, b \in \mathbb{F}_q$ satisfazem condições de não degenerescência ($a \neq 0$ e $a + nb \neq 0$). Nenhuma outra forma bilinear simétrica não degenerada permite esta redução. Isso estabelece o fechamento da abordagem do projetor ortogonal: não é possível estender o método escolhendo formas bilineares arbitrárias; a forma deve ser uma combinação linear da identidade e da matriz de todos os uns.

B. Caracterização Completa dos Códigos Redutíveis (Teorema 4.5)
Os autores determinam exatamente quais códigos admitem tal redução:

• Um código $C$ é redutível ao GI por este método se e somente se:
  1. $C$ é um código LCD (caso padrão, $M=I$), OU
  2. $\dim(\text{Hull}(C)) = 1$ e o único vetor do casco $x$ satisfaz $(x, \mathbf{1}) \neq 0$ (onde $\mathbf{1}$ é o vetor de todos os uns).
• Característica 2: Em corpos de característica 2, a condição $(x, \mathbf{1}) \neq 0$ é impossível para qualquer vetor no casco (pois $(x, x) = (x, \mathbf{1})^2 = 0$ implica $(x, \mathbf{1}) = 0$). Consequentemente, apenas códigos LCD são redutíveis em característica 2.
• Impossibilidade para Cascos Superiores: Códigos com $\dim(\text{Hull}(C)) \ge 2$ são comprovadamente não redutíveis pelo método do projetor ortogonal, independentemente da escolha de $M = aI + bJ$.

C. Fórmulas de Enumeração (Teorema 5.3)
O artigo fornece fórmulas exatas para contar o número de códigos $[n, k]_q$ redutíveis ao GI (para $q$ ímpar). A contagem é a soma de:

1. O número de códigos LCD padrão, $L(n, k, q)$.
2. O número de códigos com dimensão de casco 1 satisfazendo a condição da soma das coordenadas, derivado usando a contagem de vetores isotrópicos com somas de coordenadas não nulas e as fórmulas de massa para códigos LCD sobre espaços quocientes com discriminantes específicos.

D. Algoritmo de Redução (Seção 6)
Um algoritmo de tempo polinomial é apresentado:

1. Verificar dimensões de casco. Se $\ge 2$, retornar "não redutível ao GI".
2. Se LCD, usar $M=I$.
3. Se a dimensão do casco for 1, procurar um escalar $b$ tal que $M = I + bJ$ torne ambos os códigos $M$-LCD.
4. Construir os projetores generalizados e resolver o problema de Isomorfismo de Grafos resultante.

4. Significado e Alegações

O artigo alega fornecer uma caracterização completa das capacidades do método do projetor ortogonal.

• Fechamento: Ele fecha definitivamente a porta para estender a redução de Bardet et al. a códigos com cascos grandes ($\ge 2$) usando esta técnica específica. Ele prova que o método é inerentemente limitado a códigos com dimensão de casco no máximo 1 (e apenas códigos LCD em característica 2).
• Limites Estruturais: Ele identifica a estrutura algébrica específica ($M = aI + bJ$) necessária para que a redução funcione, mostrando que nenhuma outra forma bilinear simétrica pode facilitar este mapeamento.
• Implicações Criptográficas: Os resultados oferecem um critério para selecionar parâmetros em esquemas criptográficos baseados em códigos (como SPECK) para garantir que possuam dimensões de casco $\ge 2$, colocando-os assim além do alcance deste vetor de ataque específico de redução ao GI.

Os autores concluem levantando uma questão em aberto: se existem outras estratégias de redução (não baseadas em projetores ortogonais) que possam mapear o PEP para códigos com $\dim(\text{Hull}(C)) \ge 2$ para o GI, ou se tais reduções são comprovadamente impossíveis.