Resumo Técnico: Complexidade de Resolução de Sistemas de Equações de Mesmo Grau

Enunciado do Problema

A segurança de inúmeros esquemas criptográficos, particularmente em criptografia multivariada e em contextos pós-quânticos, baseia-se na dificuldade computacional de resolver sistemas de equações polinomiais multivariadas sobre corpos finitos. A complexidade de resolver tais sistemas via métodos de base de Gröbner é governada primordialmente pelo grau de regularidade ($d_{reg}$) e pelo grau de resolução (solving degree). Embora o grau de regularidade forneça um limite superior para a complexidade das computações de base de Gröbner, ele é frequentemente difícil de computar ou estimar para sistemas de tamanho criptográfico.

A prática comum baseia-se na suposição heurística de que os sistemas são semirregulares (ou criptograficamente semirregulares), o que gera fórmulas explícitas para o grau de regularidade. No entanto, essa suposição nem sempre é válida; existem escolhas de parâmetros e corpos onde nenhum sequência semirregular existe. Consequentemente, há uma necessidade de limites superiores provados, não heurísticos, para o grau de regularidade e o grau de resolução que se apliquem a sistemas onde o grau de regularidade é finito, sem depender da suposição de semirregularidade.

Metodologia

Os autores abordam o problema utilizando ferramentas da álgebra comutativa, focando especificamente em sistemas onde o ideal gerado pelas partes de grau superior dos polinômios contém uma sequência regular de $n$ polinômios em um determinado grau $D$.

1. Estrutura: O artigo considera um sistema $F = \{f_1, \dots, f_m\}$ de $m$ polinômios em $n$ variáveis sobre um corpo $F$. A análise assume que as partes de grau superior $f_1^{top}, \dots, f_m^{top}$ são linearmente independentes e que o sistema é regular no grau $D$ (significando que o ideal gerado pelas partes de grau superior contém uma sequência regular de $n$ polinômios de grau $D$).
2. Redução para Ideais LPP: Para limitar a regularidade de Castelnuovo-Mumford (que é igual ao grau de regularidade quando este é finito), os autores utilizam a Conjectura de Eisenbud-Green-Harris (EGH). Esta conjectura postula que, entre todos os ideais homogêneos que contêm uma sequência regular de graus específicos, o ideal Lex-Plus-Powers (LPP) possui a regularidade máxima.
3. Análise Combinatória: Os autores constroem ideais LPP específicos associados aos dados ($n, m, D$). Ao analisar a estrutura desses ideais sob a ordem lexicográfica, eles determinam a regularidade do ideal LPP, que serve como um limite superior para a regularidade do sistema original (condicional à Conjectura EGH).
4. Equações de Campo: A metodologia é estendida para sistemas aumentados com equações de campo ($x_i^q - x_i$), o que é crítico para sistemas sobre corpos finitos $\mathbb{F}_q$, particularmente quando o grau das equações $D$ é maior ou igual ao tamanho do corpo $q$.

Contribuições Principais e Resultados

1. Limites Superiores para Sistemas Regulares no Grau $D$ (Sem Equações de Campo)

O Teorema 23 fornece um limite superior agudo para o grau de regularidade de um sistema de $m$ equações de grau $D$ em $n$ variáveis, assumindo que o sistema é regular no grau $D$.

• O limite depende do número de equações ($m$), variáveis ($n$) e grau ($D$).
• A fórmula envolve a identificação de inteiros únicos $k$ e $t$ tais que $m-n$ caia dentro de um intervalo específico definido por somas combinatórias ($\sigma_{k,t}$).
• O limite resultante é: $d_{reg}(F) \le (D - t) + (n - k)(D - 1)$.
• Este limite é agudo (sharp) para todos os valores de $m, n, D$ e é atingido por sistemas onde as partes de grau superior formam um ideal LPP específico.

O Corolário 27 traduz isso em um limite superior para o grau de resolução para algoritmos mutantes:
$$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$$

2. Limites Superiores para Sistemas com Equações de Campo

O artigo aborda o caso em que equações de campo são adicionadas ao sistema, o que é essencial quando $D \ge q$.

• Proposição 31: Para sistemas muito superdeterminados (onde $m$ excede a dimensão do espaço de polinômios módulo as equações de campo), o grau de regularidade é exatamente $D$.
• Teorema 33: Para sistemas onde $q \le D \le n(q-1)$ e as partes de grau superior são linearmente independentes módulo as equações de campo, os autores fornecem um limite superior para o grau de regularidade.
  • O limite é derivado pela análise da posição do $m$-ésimo monômio na ordenação lexicográfica dos monômios de grau $D$ módulo $(x_1^q, \dots, x_n^q)$.
  • O limite é expresso em termos de $B = q - t + (n - k)(q - 1)$, onde $k$ e $t$ são determinados pelo intervalo contendo $m$.
  • Dependendo de condições específicas de $m, D$ e $t$, o limite é $B$ ou $B-1$.

O Corolário 34 especializa estes resultados para sistemas binários ($q=2$), fornecendo fórmulas simplificadas para o grau de regularidade e grau de resolução para sistemas de grau $D$ sobre $\mathbb{F}_2$.

3. Aplicação a Esquemas Específicos

Os autores aplicam seus limites a esquemas criptográficos concretos:

• Cubic Simple Matrix: Eles derivam um limite provado $d_{reg} \le 2n - 1$, que é o primeiro limite provado para este sistema, contrastando com estimativas heurísticas anteriores.
• Unbalanced Oil and Vinegar (UOV): Os limites são aplicados a sistemas UOV sobre $\mathbb{F}_2$, demonstrando como o grau de regularidade se comporta quando as equações de campo são incluídas.

Significância e Alegações

O artigo alega significância principalmente ao fornecer limites provados e não heurísticos para a complexidade de resolução de sistemas polinomiais.

• Confiabilidade: Diferente das estimativas baseadas na suposição de semirregularidade (que podem falhar para certos parâmetros), estes limites valem para qualquer sistema onde o grau de regularidade é finito e o sistema é regular em um dado grau.
• Generalidade: Os resultados aplicam-se a sistemas sobre corpos arbitrários e cobrem ambos os casos, com e sem equações de campo.
• Agudeza (Sharpness): Os limites são descritos como "agudos", o que significa que são alcançados por sistemas específicos (ideais LPP), oferecendo uma estimativa realista de pior caso para análise de segurança.
• Limitações: Os autores explicitamente reconhecem que seus limites são geralmente menos apertados (ou seja, mais altos) do que os obtidos sob a heurística de semirregularidade. No entanto, eles argumentam que esse compromisso é necessário para evitar suposições não provadas, particularmente em cenários onde sequências semirregulares não existem.

O trabalho não propõe novos algoritmos ou implementações experimentais, mas estabele-ce limites teóricos na complexidade de métodos de base de Gröbner existentes (tanto padrão quanto mutantes) para uma ampla classe de sistemas polinomiais relevantes para a criptografia.