Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE

Each language version is independently generated for its own context, not a direct translation.

¡Hola! Vamos a desglosar este artículo científico complejo en una historia sencilla, usando analogías de la vida cotidiana para entender qué descubrió el autor, Vipin Singh Sehrawat.

Imagina que el mundo de la criptografía moderna (la que protege tus datos en internet) es como un gigantesco castillo digital. Para que este castillo sea seguro, necesita usar "llaves" matemáticas muy especiales. Una de estas llaves se llama PRIM-LWE.

1. El Problema: La Llave Maestra y el "Filtro"

En este castillo, hay una puerta secreta que solo se abre si la "llave maestra" (una matriz de números) tiene una propiedad muy rara: su "determinante" (un número que calculamos a partir de la llave) debe ser un generador primitivo.

Piensa en esto como un filtro de seguridad en una fiesta VIP:

Hay millones de personas (matrices) intentando entrar.
Solo algunas tienen el "código de acceso" correcto (el determinante primitivo).
La pregunta clave es: ¿Qué porcentaje de la gente en la fila tiene este código correcto?

A este porcentaje lo llamamos densidad ( $c(p)$ ).

Si la densidad es alta (ej. 50%), es fácil encontrar una llave válida.
Si la densidad es baja (ej. 0.0001%), tienes que revisar miles de personas antes de encontrar una que pueda entrar. Esto hace que el sistema sea lento e ineficiente.

2. La Gran Duda: ¿Podría la densidad ser CERO?

Antes de este trabajo, los expertos sabían que la densidad nunca era exactamente cero para un número primo fijo. Pero se preguntaban: "¿Existe algún número primo tan 'malo' que la densidad sea tan pequeña que se acerque a cero, haciendo que el sistema sea inútil?"

Algunos pensaban que esto solo pasaría si existieran infinitos "números primos primoriales" (una especie de super-números primos muy raros), pero nadie podía probarlo.

El descubrimiento del autor:
Vipin demostró que sí, la densidad puede hacerse arbitrariamente pequeña (cercana a cero), pero sin necesidad de asumir que esos super-números raros existen. Solo usó reglas matemáticas clásicas y probadas (como el Teorema de Dirichlet).

La analogía:
Imagina que tienes un embudo. Si eliges el tamaño del embudo (el número primo) de una manera muy específica (que tenga muchos factores pequeños), el agujero se vuelve tan pequeño que casi nada pasa. El autor demostró que siempre podemos encontrar un embudo con un agujero casi cerrado, sin necesidad de magia, solo con matemáticas básicas.

3. La Velocidad de la Caída: ¿Qué tan rápido se cierra el agujero?

El autor no solo dijo "sí, puede ser pequeño", sino que midió qué tan lento es ese proceso.

La analogía del caracol: La densidad no cae de golpe como una piedra. Caída tan lentamente como un caracol subiendo por una pared. Matemáticamente, cae a una velocidad de $1 / \log(\log(x))$.
Traducción: Incluso si el número primo es inmensamente grande (como los que usan los ordenadores cuánticos), la densidad sigue siendo un número positivo, aunque pequeño. No desaparece mágicamente.

4. La Distribución: ¿Cómo se comportan los números?

El estudio también analizó la "personalidad" de estos números primos.

Descubrió que la densidad sigue una distribución continua y singular.
Analogía: Imagina que lanzas millones de dados (números primos) y anotas la densidad de cada uno. No verás picos altos ni valles profundos; verás una "niebla" suave que cubre todo el rango desde 0 hasta 0.5.
Lo importante: La mayoría de los números primos que usamos en la vida real (como los de los estándares de seguridad de EE. UU., NIST) caen en la parte "segura" de esta niebla. No son los extremos raros.

5. El Impacto en la Seguridad Real (Lo que te importa a ti)

Aquí es donde el papel se vuelve práctico. El autor calculó qué pasa con los números que realmente usamos hoy en día:

Los estándares NIST (ML-KEM y ML-DSA): Estos son los nuevos estándares de seguridad que se están implementando en todo el mundo.
El resultado: Para estos números específicos, la densidad es bastante buena.
- Para el número 3329, la densidad es tal que solo necesitas revisar, en promedio, 2.17 matrices para encontrar una válida.
- Para el número 8380417, necesitas revisar 3.42.
Conclusión: ¡Es muy eficiente! No tienes que revisar millones de veces. El "sobrecosto" es mínimo.

6. El Consejo Final: Elegir bien tus números

El autor nos da una lección de sabiduría para los ingenieros de seguridad:

No basta con que un número sea "amigable" para la computación rápida (llamado NTT-friendly).
Lo que realmente importa es cómo se descompone el número anterior al primo ( $q-1$ ).
Si $q-1$ tiene muchos factores primos pequeños, la densidad baja.
Si $q-1$ tiene pocos factores (como los números seguros que ya elegimos), la densidad se mantiene alta y el sistema es rápido.

Resumen en una frase

El autor demostró que, aunque matemáticamente es posible crear un sistema criptográfico tan lento que casi no funcione (porque la densidad de llaves válidas es casi cero), los números que usamos en la vida real son seguros y rápidos, y el "freno" que impone esta teoría es tan lento que no nos preocupa en la práctica.

En pocas palabras: La teoría dice "cuidado, podría ser lento", pero la práctica dice "tranquilos, con los números que usamos, va a ir rápido".

Each language version is independently generated for its own context, not a direct translation.

A continuación presento un resumen técnico detallado del artículo "Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE" de Vipin Singh Sehrawat.

1. Planteamiento del Problema

El artículo aborda el problema PRIM-LWE (Learning with Errors con determinante de raíz primitiva), una variante del problema LWE introducida previamente por Sehrawat, Yeo y Desmedt. En esta variante, la matriz secreta $S$ debe tener un determinante que sea una raíz primitiva del cuerpo finito $\mathbb{F}_p$ .

La seguridad de la reducción desde el problema LWE estándar hasta PRIM-LWE depende de una constante de muestreo uniforme en la dimensión, denotada como $c(p)$ . Esta constante representa la densidad límite de matrices $n \times n$ sobre $\mathbb{F}_p$ cuyo determinante genera el grupo multiplicativo $\mathbb{F}_p^*$ . La fórmula para esta densidad es:

$c(p) = \frac{\phi(p-1)}{p-1} \prod_{j=1}^{\infty} \left(1 - \frac{1}{p^j}\right)$

donde $\phi$ es la función indicadora de Euler.

La pregunta abierta:
Sehrawat, Yeo y Desmedt observaron que si existieran infinitos primoriales primos (primos de la forma $p = p_1 p_2 \dots p_k + 1$ ), entonces $\inf_p c(p) = 0$ . Sin embargo, la infinitud de los primoriales primos es una conjetura no resuelta. El objetivo central de este trabajo es determinar si $\inf_p c(p) = 0$ puede probarse incondicionalmente, sin depender de conjeturas sobre la existencia de primoriales primos.

2. Metodología

El autor utiliza herramientas clásicas de la teoría analítica de números para resolver el problema:

Teorema de Dirichlet sobre primos en progresiones aritméticas: Se utiliza para garantizar la existencia de infinitos primos $p \equiv 1 \pmod{N_k}$ , donde $N_k$ es el $k$ -ésimo primorial.
Fórmula del producto de Mertens: Se emplea para estimar el comportamiento asintótico del producto $\prod (1 - 1/p_i)$ , que tiende a cero lentamente.
Teorema de Linnik: Se utiliza para acotar el menor primo en una clase de residuos, lo cual es crucial para establecer cotas superiores y inferiores precisas sobre la magnitud de $c(p)$ .
Teoría de distribuciones de funciones aditivas: Se aplica el marco de Erdős–Wintner para funciones aditivas evaluadas en $p-1$ (específicamente la función $\phi(n)/n$ ) para estudiar la distribución límite de $c(p)$ sobre el conjunto de los números primos.
Lema de transporte: Se demuestra que la densidad $c(p)$ comparte la misma distribución límite que la razón $\phi(p-1)/(p-1)$ , ya que el factor del producto infinito tiende a 1.

3. Contribuciones Clave y Resultados Principales

A. Resolución Incondicional de la Conjetura

El autor prueba que $\inf_p c(p) = 0$ de manera incondicional.

Mecanismo: En lugar de buscar primos primoriales ( $p = N_k + 1$ ), el autor demuestra que para cada primorial $N_k$ , el Teorema de Dirichlet garantiza infinitos primos $p \equiv 1 \pmod{N_k}$ . Para tales primos, $N_k$ divide a $p-1$ , lo que implica que el producto $\phi(p-1)/(p-1)$ está acotado superiormente por el producto parcial de Mertens sobre los primeros $k$ primos.
Resultado: A medida que $k \to \infty$ , este producto tiende a 0, demostrando que la densidad puede ser arbitrariamente pequeña sin necesidad de la hipótesis de primoriales primos.

B. Orden Asintótico del Mínimo

Se establece el orden exacto de la densidad mínima para primos hasta un límite $x$ :
$\min_{p \le x} c(p) \asymp \frac{1}{\log \log x}$
Esto indica que la densidad decae hacia cero, pero extremadamente lentamente. Para valores criptográficos típicos (ej. $2^{128} $o$ 2^{4096}$), el logaritmo doble es pequeño, lo que sugiere que la densidad no colapsa rápidamente en rangos prácticos.

C. Distribución Límite

El artículo caracteriza la distribución estadística de $c(p)$ sobre los primos:

Existe una función de distribución límite continua y puramente singular $G$ .
El soporte de esta distribución es exactamente el intervalo $[0, 1/2]$ .
La función $G$ es estrictamente creciente en este intervalo.
Esto implica que, aunque la densidad puede ser muy pequeña, también hay una densidad positiva de primos donde $c(p)$ es cercana a $1/2$.

D. Cotas Explícitas para Modulos Criptográficos

Se derivan cotas inferiores explícitas para $c(q)$ basadas en el número de factores primos distintos de $q-1$ , denotado como $\omega(q-1)$ .

Fórmula general: $c(q) \ge P_3 \prod_{i=1}^{\omega(q-1)} (1 - 1/p_i)$ , donde $P_3 \approx 0.56$ .
Aplicación a estándares NIST:
- Para ML-KEM ( $q = 3329$ ): El sobrecosto esperado de muestreo de rechazo ($1/c(q)$) es de aproximadamente 2.17.
- Para ML-DSA ( $q = 8380417$ ): El sobrecosto es de aproximadamente 3.42.
Cota universal: Para cualquier primo $q > 2^{30}$ , el sobrecosto está acotado por $1.79 \log q $, aunque la cota más ajustada es$ O(\log \log q)$.

4. Significado e Implicaciones

Seguridad de PRIM-LWE: El resultado confirma que la reducción de LWE a PRIM-LWE es válida para cualquier primo fijo $p$ , ya que $c(p) > 0$ . Sin embargo, la "tightness" (estrechez) de la reducción depende de la estructura de factorización de $p-1$ .
Selección de Parámetros: El trabajo demuestra que la "amigabilidad con NTT" (Number Theoretic Transform) por sí sola no garantiza una buena densidad $c(p)$ , ya que la condición $q \equiv 1 \pmod{2^t}$ solo controla la parte par de $q-1$ . Lo crucial es que $q-1$ tenga pocos factores primos impares pequeños.
Impacto Práctico: A pesar de que el mínimo asintótico tiende a cero, para los modulos estándar utilizados en criptografía post-cuántica (NIST), la densidad $c(q)$ es suficientemente alta (entre 0.29 y 0.46), resultando en un sobrecosto de muestreo de rechazo constante y manejable (menor a 4).
Teoría de Números: El artículo cierra una brecha teórica importante al eliminar la dependencia de conjeturas sobre primos primoriales y proporciona una comprensión completa de la distribución límite de la densidad de determinantes de raíz primitiva.

En conclusión, el papel de Sehrawat resuelve una cuestión abierta fundamental, demostrando que la densidad puede ser arbitrariamente pequeña pero lo hace de manera controlada y lenta, asegurando que el esquema PRIM-LWE sigue siendo práctico y seguro para los parámetros criptográficos actuales, siempre que se elijan modulos con una estructura de factorización adecuada.