Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

Resumen Técnico: Criptanálisis de la Función Pseudoaleatoria de Legendre sobre Campos de Extensión

Autores: Daksh Pandey (IIT Roorkee)
Contexto: El artículo presenta el primer análisis criptográfico exhaustivo de la Función Pseudoaleatoria (PRF) de Legendre de grado único ($d=1$) cuando se implementa sobre campos de extensión $\mathbb{F}_{p^r}$, en lugar de los campos primos $\mathbb{F}_p$ tradicionales. Esta primitiva es crucial para la Computación Multi-Parte (MPC) y las Pruebas de Conocimiento Cero (ZKP) debido a su baja complejidad multiplicativa.

1. El Problema

La seguridad de la PRF de Legendre sobre campos primos $\mathbb{F}_p$ ha sido ampliamente estudiada, y se sabe que es vulnerable a ataques de colisión por ventana deslizante. Para mejorar el rendimiento en protocolos criptográficos, se ha propuesto trasladar la operación a campos de extensión $\mathbb{F}_{p^r}$.

La hipótesis inicial era que la aritmética polinómica en $\mathbb{F}_{p^r}$ introduciría una "fractura" en las consultas aditivas secuenciales (debido a la ausencia de "acarreo" o carry entre coeficientes al sumar enteros codificados como polinomios), lo que teóricamente neutralizaría los ataques de colisión clásicos. Sin embargo, este trabajo demuestra que dicha "fractura" no es suficiente para garantizar la seguridad y que la estructura algebraica subyacente sigue siendo explotable.

2. Metodología

El artículo emplea un enfoque dual, analizando la PRF bajo dos modelos de amenaza distintos:

A. Modelo de Amenaza Pasiva (Consultas Aditivas Secuenciales)

• Codificación de Entrada: Se analiza cómo los enteros secuenciales $n$ se mapean a polinomios $X_n$ en $\mathbb{F}_{p^r}$. Se demuestra que la suma $n+1$ no produce una diferencia constante en el campo polinómico, sino una secuencia de diferencias deterministas y periódicas (la "fractura sin acarreo").
• Técnica de "Firma Diferencial" (Differential Signature): En lugar de buscar colisiones en ventanas contiguas (que fallan debido a la fractura), los autores proponen agrupar las ventanas de la secuencia de salida basándose en su "forma" estructural o firma diferencial acumulada.
• Ataque: El atacante clasifica las ventanas observadas en clases de equivalencia según su firma diferencial. Al encontrar una clase con muchas instancias, puede construir una tabla hash y recuperar la clave mediante un ataque de colisión pasiva.

B. Modelo de Amenaza Activa (Consultas Elegidas)

• Estrategia Geométrica: El atacante abandona la adición y utiliza una secuencia geométrica generada por un polinomio primitivo $g(x)$ en el grupo multiplicativo $\mathbb{F}_{p^r}^*$.
• Homomorfismo Multiplicativo: Se demuestra que la evaluación de la PRF sobre esta secuencia geométrica $g^i + K$ permite factorizar la expresión gracias a la multiplicatividad del símbolo de Legendre generalizado.
• Reducción Algebraica: La secuencia se reduce a un desplazamiento discreto (logaritmo discreto) y un signo constante, eliminando por completo la complejidad de la "fractura aditiva". Esto permite generalizar el ataque de colisión de tabla de estado del arte directamente al grupo multiplicativo.

3. Contribuciones Clave

1. Desenmascaramiento de la "Fractura Sin Acarreo": Se demuestra que la ausencia de acarreo en la adición polinómica, lejos de ser una defensa, crea una periodicidad determinista que puede ser explotada mediante el agrupamiento por firmas diferenciales.
2. Ataque Pasivo Optimizado: Se introduce una técnica de "bucketing" (agrupamiento) basada en firmas diferenciales que permite recuperar la clave en un tiempo esperado de $O(U \cdot p^r / M)$, donde $U$ es la distancia de unicidad y $M$ el número de bits observados.
3. Ataque Activo de Colisión Geométrica: Se presenta un ataque de consulta elegida que rompe completamente la seguridad de la variante de grado único, recuperando la clave en $O(p^r / M)$ operaciones, reduciendo la seguridad activa al límite teórico inferior.
4. Límites de Seguridad para Variantes de Grado Superior: Se analiza la variante de grado $d \ge 2$ (donde la clave es un polinomio de grado $d$). Se demuestra que esta variante resiste el ataque geométrico activo porque no permite la factorización algebraica. Sin embargo, se advierte que ataques Meet-in-the-Middle (MITM) podrían reducir la complejidad de $O(p^{dr})$ a $O(p^{\lfloor d/2 \rfloor r})$, sugiriendo que se requieren grados $d \ge 3$ o $4$ para una seguridad exponencial robusta.

4. Resultados

• Inseguridad de Grado Único: La PRF de Legendre de grado único ($d=1$) sobre campos de extensión $\mathbb{F}_{p^r}$ está completamente rota tanto bajo modelos pasivos como activos.
• Complejidad de Ataque:
  • Pasivo: $O(U \cdot p^r / M)$.
  • Activo: $O(p^r / M)$.
• Necesidad de Variantes de Grado Superior: La única defensa viable propuesta es el uso de claves polinómicas de grado $d \ge 2$ (preferiblemente $d \ge 3$ o $4$) para evitar la reducción algebraica y mantener un margen de seguridad exponencial.

5. Significado e Impacto

Este trabajo es fundamental para la implementación segura de la PRF de Legendre en protocolos modernos como MPC y ZKP.

• Advertencia de Seguridad: Desmiente la suposición de que trasladar la PRF a campos de extensión con aritmética polinómica mejora automáticamente la seguridad contra ataques de colisión. De hecho, sin un grado de clave adecuado, la seguridad se degrada significativamente.
• Guía de Implementación: Establece que las implementaciones futuras en $\mathbb{F}_{p^r}$ deben evitar estrictamente la variante de grado único ($d=1$) y adoptar variantes de grado superior ($d \ge 2$) para mitigar las vulnerabilidades estructurales identificadas.
• Avance Teórico: Proporciona nuevas herramientas criptoanalíticas (firmas diferenciales y ataques geométricos) que pueden ser aplicables a otras primitivas criptográficas basadas en símbolos de caracteres sobre campos finitos.

El artículo concluye que, para garantizar la seguridad en entornos de computación distribuida y pruebas de conocimiento cero, la elección de los parámetros del campo y el grado del polinomio clave es crítica, y la variante estándar de grado único no es segura en extensiones de campo.