Notes on the LVP and CVP in $p$-adic Fields

Resumo Técnico: Notas sobre o Problema do Vetor Mais Longo (LVP) e o Problema do Vetor Mais Próximo (CVP) em Campos p-ádicos

Autores: Chi Zhang e Mingqian Yao
Instituição: Academia de Ciências Matemáticas e Sistemas, Academia Chinesa de Ciências (CAS).

1. Problema Investigado

O artigo aborda a segurança e a complexidade computacional de dois problemas fundamentais em reticulados (lattices) definidos sobre campos p-ádicos ($\mathbb{Q}_p$):

• Problema do Vetor Mais Longo (LVP): Encontrar um vetor no reticulado com a segunda maior norma p-ádica possível (definido recursivamente, já que o máximo absoluto pode ser arbitrariamente grande em certas definições, mas aqui foca-se na segunda maior norma distinta $\lambda_2$).
• Problema do Vetor Mais Próximo (CVP): Dado um vetor alvo $t$, encontrar o vetor no reticulado que minimize a distância p-ádica $|t - v|_p$.

Estes problemas foram propostos como a base para novos esquemas de criptografia de chave pública e assinaturas digitais pós-quânticas, explorando a estrutura não-Arquimediana dos campos p-ádicos. O objetivo do artigo é demonstrar que, sob condições gerais (quando o campo é especificado por um polinômio mínimo), esses problemas podem ser resolvidos em tempo polinomial, comprometendo a segurança dos esquemas baseados neles.

2. Metodologia e Abordagem

Os autores desenvolvem um algoritmo determinístico de tempo polinomial que resolve o LVP e o CVP. A metodologia baseia-se na exploração da estrutura algébrica dos campos p-ádicos, especificamente a existência de bases ortogonais para reticulados p-ádicos, algo que não é garantido da mesma forma em reticulados euclidianos.

O processo algorítmico segue os seguintes passos principais:

1. Cálculo da Ordem Máxima ($\mathcal{O}_K$):

   • Dado um campo de extensão $K = \mathbb{Q}_p(\theta)$ definido por um polinômio mínimo, o algoritmo calcula a ordem máxima (anel de inteiros) $\mathcal{O}_K$.
   • Utiliza-se o Algoritmo Round 2 (e Round 4), que expande iterativamente uma ordem inicial (como $\mathbb{Z}_p[\theta]$) até atingir a ordem máxima.
   • O núcleo deste processo é o cálculo do $p$-radical ($I_p$), definido como o conjunto de elementos $x$ tais que $x^m \in p\mathcal{O}$ para algum $m$. O cálculo do $p$-radical é feito através do núcleo de mapas de Frobenius elevados a potências adequadas sobre o anel quociente $\mathcal{O}/p\mathcal{O}$.

2. Construção de Bases Ortogonais:

   • Uma vez obtida a ordem máxima, o algoritmo extrai um uniformizador $\pi$ (elemento de valor absoluto p-ádico máximo na ordem máxima, exceto unidades).
   • Calcula-se uma base para o campo residual $k = \mathcal{O}_K / \pi\mathcal{O}_K$.
   • Utilizando o índice de ramificação $e$ e o grau de resíduo $f$ (onde $n = ef$), constrói-se uma base ortogonal para o espaço vetorial $K$ sobre $\mathbb{Q}_p$ da forma:
     $$\{ s_i \pi^j \mid 1 \le i \le f, 0 \le j \le e-1 \}$$
     onde $s_i$ são representantes da base do campo residual.
   • O Teorema 4.3 prova que esta estrutura forma uma base ortogonal, permitindo decompor o espaço em subespaços ortogonais.

3. Resolução do LVP e CVP:

   • Com a base ortogonal em mãos, os problemas LVP e CVP tornam-se triviais e resolvíveis em tempo polinomial.
   • Algoritmo LVP: Ordena os vetores da base e do reticulado pela norma, realizando operações de eliminação (semelhante a Gram-Schmidt, mas adaptado à desigualdade ultramétrica) para encontrar o vetor com a segunda maior norma.
   • Algoritmo CVP: Utiliza a base ortogonal para projetar o vetor alvo e arredondar as coordenadas no anel de inteiros p-ádico, encontrando o vetor mais próximo de forma eficiente.

3. Contribuições Principais

• Algoritmo de Tempo Polinomial Geral: Os autores apresentam o primeiro algoritmo determinístico de tempo polinomial que resolve o LVP e o CVP para reticulados em campos p-ádicos quando o campo é dado explicitamente por um polinômio mínimo.
• Integração de Álgebra Computacional: A combinação de técnicas de cálculo de ordens máximas (Round 2/4) com a teoria de extensões de campos (uniformizadores e campos residuais) para construir bases ortogonais.
• Caracterização de Normas: O artigo inclui uma caracterização teórica (Teorema 7.1) de todas as normas possíveis em espaços vetoriais sobre $\mathbb{Q}_p$, mostrando que qualquer norma pode ser representada por uma matriz invertível e constantes reais, o que implica que a segurança depende criticamente de esconder essa estrutura ortogonal.
• Validação Prática: Fornecimento de um exemplo concreto (Toy Example) sobre $\mathbb{Q}_2(\theta)$ com $\theta$ raiz de $X^3 - 3X^2 + 3X - 5$, demonstrando passo a passo o cálculo da ordem máxima, do $p$-radical e a obtenção da base ortogonal.

4. Resultados

• Complexidade: O algoritmo proposto tem complexidade polinomial em relação ao grau da extensão $n$ e ao logaritmo do primo $p$ ($O(poly(n, \log p))$).
• Quebra de Esquemas Criptográficos: O trabalho demonstra que os esquemas de assinatura e criptografia de chave pública baseados em reticulados p-ádicos propostos anteriormente (por Deng et al. e Zhang et al.) são inseguros quando o campo subjacente é totalmente especificado. O ataque descrito reduz drasticamente a força de segurança desses esquemas.
• Limitação da "Resposta" Anterior: O artigo refuta a eficácia de métodos anteriores que sugeriam o uso de grandes graus de resíduo para mitigar ataques, mostrando que, desde que o campo seja conhecido, a estrutura ortogonal pode ser recuperada e o problema resolvido.

5. Significado e Implicações

• Segurança Pós-Quântica: O trabalho coloca em xeque uma nova classe de candidatos a criptografia pós-quântica baseada em geometria não-Arquimediana. Ele estabelece que a simples existência de uma estrutura algébrica rica (como a decomposição em bases ortogonais) pode ser uma vulnerabilidade fatal se não for protegida adequadamente.
• Direções Futuras: Os autores sugerem que, para que a criptografia baseada em campos p-ádicos seja viável, o modelo de segurança deve mudar. Em vez de fornecer o campo via polinômio mínimo, o sistema deveria fornecer apenas um "oráculo" de norma, sem revelar a base ortogonal subjacente. O desafio futuro seria determinar se o LVP/CVP permanece difícil quando a norma é tratada como um oráculo e a estrutura algébrica é oculta.
• Contribuição Teórica: O artigo preenche uma lacuna na literatura sobre álgebra computacional p-ádica, fornecendo métodos eficientes para decomposição ortogonal e resolução de problemas de reticulados que antes eram considerados difíceis ou apenas resolvidos em casos específicos.

Em suma, o paper demonstra que a "dificuldade" dos problemas LVP e CVP em campos p-ádicos é ilusória quando a descrição completa do campo é pública, tornando os esquemas criptográficos baseados nesses problemas vulneráveis a ataques eficientes.