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

Aquí presento un resumen técnico detallado del artículo "Notes on the LVP and CVP in p-adic Fields" de Chi Zhang y Mingqian Yao, estructurado según los puntos solicitados.

Resumen Técnico: Soluciones Polinómicas para LVP y CVP en Campos $p$-ádicos

1. El Problema

El artículo aborda la resolución de dos problemas computacionales fundamentales en retículos ($lattices$) definidos sobre campos $p$-ádicos ($\mathbb{Q}_p$):

• Problema del Vector Más Largo (LVP - Longest Vector Problem): Dado un retículo $L$, encontrar un vector $v \in L$ cuya norma $p$-ádica sea el segundo valor máximo posible en la secuencia decreciente de normas de los vectores del retículo.
• Problema del Vector Más Cercano (CVP - Closest Vector Problem): Dado un retículo $L$ y un vector objetivo $t$, encontrar un vector $v \in L$ que minimice la distancia $|t - v|_p$.

Contexto y Motivación:
Estos problemas han sido propuestos como la base de esquemas de criptografía de clave pública y firmas digitales poscuánticas (introducidos por Deng et al. en 2018 y 2021). La seguridad de estos esquemas se basaba en la suposición de que LVP y CVP son difíciles en campos $p$-ádicos, especialmente cuando se utilizan bases ortogonales como "trampas" (trapdoors). Sin embargo, ataques previos (Zhang, 2025) demostraron vulnerabilidades en campos totalmente ramificados. Este trabajo busca cerrar la brecha teórica proporcionando un algoritmo general de tiempo polinomial que resuelve estos problemas siempre que el campo esté especificado mediante un polinomio mínimo, demostrando así la inseguridad de los esquemas actuales que dependen de la estructura de campos $p$-ádicos completos.

2. Metodología

La metodología se basa en explotar la propiedad no arquimediana de la norma $p$-ádica ($|v+w|_p \leq \max(|v|_p, |w|_p)$), la cual permite descomposiciones geométricas distintas a las de los espacios euclidianos. El enfoque se divide en tres etapas principales:

A. Cálculo del Orden Máximo ($O_K$):
Dado un campo de extensión $K = \mathbb{Q}_p(\theta)$ definido por un polinomio mínimo, el algoritmo construye el orden máximo $O_K$ (el anillo de enteros algebraicos de $K$).

• Se inicia con un orden conocido (ej. $\mathbb{Z}_p[\theta]$).
• Se utiliza el $p$-radical ($I_p = \{x \in O \mid \exists m, x^m \in pO\}$) para iterativamente ampliar el orden.
• Se aplican algoritmos deterministas (basados en Round 2 y Round 4) que calculan el núcleo de mapas de Frobenius y matrices de multiplicación para encontrar el orden máximo en tiempo polinomial.

B. Construcción de una Base Ortogonal:
Una vez obtenido $O_K$, el método extrae una base ortogonal para el espacio vectorial $K$ sobre $\mathbb{Q}_p$:

1. Uniformizador ($\pi$): Se identifica un elemento en el $p$-radical con la mayor norma $p$-ádica posible, que actúa como uniformizador del campo.
2. Base del Campo Residual: Se calcula una base del campo residual $k = O_K / \pi O_K$ (una extensión finita de $\mathbb{F}_p$).
3. Descomposición: Se demuestra teóricamente (Teorema 4.3) que la familia de elementos $(s_i \pi^j)$, donde $s_i$ son elementos de la base del campo residual y $j$ varía desde $0$ hasta $e-1$ (índice de ramificación), forma una base ortogonal para $K$.

C. Resolución de LVP y CVP:
Con la base ortogonal en mano, los problemas LVP y CVP se reducen a subproblemas triviales en subespacios ortogonales:

• Algoritmo LVP: Utiliza la ortogonalidad para ordenar los vectores de la base y seleccionar el vector con la segunda norma más grande mediante comparaciones directas de normas, sin necesidad de búsqueda exhaustiva.
• Algoritmo CVP: Utiliza una proyección directa sobre la base ortogonal para encontrar el vector de retículo más cercano al objetivo, aprovechando la propiedad de que la norma de una suma es el máximo de las normas de los componentes ortogonales.

3. Contribuciones Clave

1. Algoritmo Determinista de Tiempo Polinomial: Presentan el primer algoritmo general que resuelve LVP y CVP en campos $p$-ádicos en tiempo polinomial respecto al grado de la extensión ($n$) y el logaritmo del primo ($\log p$), asumiendo que el campo está dado por un polinomio mínimo.
2. Integración de Álgebra Computacional y Geometría: Unifican técnicas de cálculo de órdenes máximos y radicales $p$-ádicos con la construcción de bases ortogonales, llenando un vacío en la literatura donde los métodos existentes (como LLL para retículos euclidianos) no se generalizaban directamente debido a la desigualdad ultramétrica.
3. Caracterización de Normas en Espacios Vectoriales: Proporcionan un teorema (Teorema 7.1) que caracteriza toda norma en un espacio vectorial sobre $\mathbb{Q}_p$ como una combinación de una matriz invertible y constantes reales positivas. Esto revela que si la matriz de cambio de base es conocida, la norma es vulnerable.
4. Validación Práctica: Demuestran la viabilidad del algoritmo mediante un ejemplo concreto sobre el campo $\mathbb{Q}_2(\sqrt[3]{5})$ (definido por $X^3 - 3X^2 + 3X - 5$), mostrando paso a paso el cálculo del orden máximo, el uniformizador y la base ortogonal.

4. Resultados

• Inseguridad de Esquemas Actuales: Los resultados confirman que los esquemas de cifrado y firma basados en retículos $p$-ádicos (como los propuestos por Deng et al. en 2021) son inseguros si el campo subyacente se especifica completamente mediante un polinomio mínimo. El ataque propuesto rompe la suposición de dureza computacional.
• Eficiencia: El algoritmo es determinista y eficiente, superando a los métodos anteriores que eran exponenciales o solo funcionaban bajo condiciones restrictivas (como ramificación total).
• Ejemplo Numérico: En el ejemplo de $\mathbb{Q}_2(\theta)$, el algoritmo calculó exitosamente el orden máximo, identificó el uniformizador $\pi = \frac{1}{2}(\theta^2 - 1)$ y construyó la base ortogonal $\{1, \pi, \pi^2\}$, validando la teoría.

5. Significado e Implicaciones

• Criptografía Poscuántica: El trabajo tiene un impacto crítico en la seguridad de los candidatos a criptografía poscuántica basados en retículos $p$-ádicos. Demuestra que la estructura algebraica de los campos locales, lejos de ser una ventaja, introduce vulnerabilidades estructurales que permiten la resolución eficiente de problemas de retículo.
• Nuevas Direcciones de Investigación:
  • Sugiere que para lograr seguridad, los esquemas futuros no deben revelar el polinomio mínimo completo del campo, sino solo un oráculo de norma computable que no revele la base ortogonal subyacente.
  • Plantea la pregunta abierta sobre la dificultad de encontrar la descomposición de una norma (matriz $A$ y constantes $c_i$ del Teorema 7.1) si solo se tiene acceso a un oráculo de la norma.
• Teoría de Números Computacional: Avanza en el entendimiento de la geometría de espacios vectoriales sobre campos no arquimedianos, proporcionando herramientas algorítmicas robustas para el cálculo de órdenes máximos y bases ortogonales.

En conclusión, el paper establece que, bajo las especificaciones estándar de campos $p$-ádicos, los problemas LVP y CVP no son difíciles, lo que invalida la base de seguridad de los esquemas criptográficos recientes propuestos en este dominio y obliga a replantear las definiciones de seguridad en este contexto.