Utilizing Circulant Structure to Optimize the Implementations of Linear Layers

Resumo Técnico: Utilização da Estrutura Circulante para Otimizar as Implementações de Camadas Lineares

Declaração do Problema
A otimização de camadas lineares em criptografia simétrica é crítica tanto para implementações leves (constrangidas pela contagem de portas e área) quanto para avaliações de segurança quântica (constrangidas pela profundidade do circuito e custo DW). Embora algoritmos heurísticos existam para sintetizar circuitos CNOT (quânticos) e circuitos XOR (clássicos) para matrizes invertíveis gerais, eles frequentemente falham em explorar plenamente estruturas algébricas específicas inerentes a projetos criptográficos. Muitas matrizes amplamente utilizadas, como as em MixColumn do AES e Whirlwind, possuem uma estrutura circulante. Métodos existentes de última geração, como os de Shi e Feng [SF24], tratam essas matrizes como matrizes binárias gerais $n \times n$, potencialmente perdendo oportunidades de reduzir a profundidade do circuito e a contagem de portas ao alavancar suas propriedades circulantes subjacentes.

Metodologia
Os autores propõem um novo framework que utiliza explicitamente a estrutura circulante de matrizes para guiar a síntese de circuitos eficientes. A metodologia central envolve uma estratégia de decomposição recursiva que transforma uma matriz circulante sobre uma extensão de corpo (e.g., $F_{2^k}$ ou $GL(F_2, m)$) em uma forma mais simples, especificamente uma matriz triangular superior, antes de aplicar otimização heurística padrão.

Componentes técnicos-chave incluem:

1. Transformação Recursiva de Blocos: O Teorema 3 estabelece que uma matriz circulante $2^k \times 2^k$ sobre $F_2[x]$ pode ser transformada em uma matriz triangular superior em blocos usando operações elementares de linhas e colunas. O algoritmo divide recursivamente a matriz em blocos $A$ e $B$ (onde $M = \begin{smallmatrix} A & B \\ B & A \end{smallmatrix}$), aplicando operações para zerar blocos específicos (e.g., transformando em $\begin{smallmatrix} A+B & B \\ A+B & \dots \end{smallmatrix}$).
2. Exploração de Caminhos de Transformação: Os autores observam que diferentes escolhas de operações de linhas e colunas durante o passo recursivo levam a diferentes matrizes intermediárias. O algoritmo (Algoritmo 1) explora múltiplos caminhos de transformação (até $4^{2^k-1}$ possibilidades para pequenos $k$) para encontrar o caminho que produz o circuito subsequente mais eficiente.
3. Parada Antecipada e Fallback: Reconhecendo que o benefício da recursão diminui em maiores profundidades, os autores introduzem uma estratégia (Algoritmo 2) para parar a recursão antecipadamente. O algoritmo itera através de diferentes "tamanhos de bloco", variando efetivamente a profundidade de recursão. Se a recursão for interrompida antecipadamente, a matriz resultante é passada para um otimizador heurístico padrão (Heu) para síntese geral de CNOT/XOR. Isso inclui uma estratégia de "fallback" onde a profundidade de recursão é zero, tratando efetivamente a matriz como um caso geral.
4. Otimização Automatizada: Diferentemente de abordagens manuais anteriores (e.g., Zhang et al. [ZSWS24] para AES), este método automatiza o processo de encontrar a forma de matriz "mais simples" e as sequências de portas correspondentes, removendo a necessidade de intervenção humana.

Contribuições Principais

• Framework Inovador: Este é o primeiro trabalho a utilizar sistematicamente a estrutura circulante de camadas lineares para otimizar implementações de circuitos, preenchendo a lacuna entre propriedades algébricas de matrizes e heurísticas de síntese de circuitos.
• Síntese Automatizada: Os autores fornecem um algoritmo automatizado que substitui otimizações manuais e específicas de caso. Ele gera sequências de matrizes de transformação que permitem que heurísticas a jusante encontrem implementações mais eficientes.
• Otimização Dual: O framework é aplicável tanto a circuitos quânticos (minimizando contagem e profundidade de CNOT) quanto a circuitos clássicos (minimizando contagens de XOR, especificamente g-XOR e s-XOR).

Resultados
Os autores avaliaram seu método em um conjunto de dados de camadas lineares de cifras de bloco (incluindo AES, Whirlwind, Clefia, PRIDE, etc.) e matrizes MDS construídas.

• Profundidade de Circuito Quântico:

  • Whirlwind M0: O método proposto reduziu a profundidade do circuito de 28 (estado da arte anterior por [SF24]) para 17, uma melhoria de 39%. A contagem de portas também foi reduzida de 286 para 200.
  • MixColumn do AES: O método automatizado alcançou uma profundidade de 10, igualando o resultado otimizado manualmente de última geração por Zhang et al. [ZSWS24]. A contagem de portas foi de 107, que é apenas 2 CNOTs a mais que o resultado manual (105) e significativamente melhor que os 131 CNOTs alcançados por [SF24].
  • Outras Matrizes: Reduções significativas de profundidade foram observadas para matrizes com alta densidade (e.g., Whirlwind, SKOP15 8x8), enquanto melhorias foram marginais ou inexistentes para matrizes esparsas onde as heurísticas já performam bem.

• Circuito Clássico (Contagem de XOR):

  • Whirlwind M0: O método alcançou uma contagem s-XOR de 159, superando o melhor anterior de 173 (Yuan et al. [YWS+24]) em aproximadamente 8%.
  • Desempenho Geral: Embora o método geralmente incorra em sobrecarga de tamanho para muitas matrizes, ele conseguiu superar resultados de última geração para matrizes específicas de alta densidade como Whirlwind M0 e M1.

Significado e Alegações
O artigo alega que explorar a estrutura circulante é uma via poderosa, anteriormente subutilizada, para otimizar camadas lineares. Os autores afirmam que sua abordagem:

1. Supera heurísticas existentes para matrizes específicas e densas onde estratégias ganancias padrão lutam.
2. Automatiza a otimização manual, alcançando resultados comparáveis a circuitos ajustados por especialistas humanos (como visto no MixColumn do AES) sem exigir intervenção manual.
3. Fornece uma nova linha de base para avaliações de segurança quântica, oferecendo estimativas de profundidade mais precisas para camadas lineares, o que é crucial para calcular o custo DW (Profundidade $\times$ Largura) em avaliações de segurança pós-quântica.

Os autores concluem que, embora o método não seja universalmente superior para todos os tipos de matriz (particularmente as esparsas), ele oferece uma vantagem significativa para matrizes com estruturas circulantes e alta densidade, demonstrando o potencial de integrar propriedades algébricas na síntese de circuitos.