⚛️ quantum physics

Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli

Este artículo introduce el Problema del Coseno Ciclotómico (CCP) como una generalización del Problema del Coseno Diedral que preserva el subgrupo oculto y presenta un algoritmo de cribado cuántico que resuelve CCP, EDCP uniforme y Gaussian S|LWE> en tiempo cuasi-polinomial para módulos de potencia de números primos, aunque todavía no ofrece una solución en tiempo cuasi-polinomial para LWE estándar debido a las limitaciones en la generación de estados de la reducción.

Autores originales: Mathias Boucher, Pierre-Alain Fouque, Yixin Shen

Publicado 2026-09-29

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Mathias Boucher, Pierre-Alain Fouque, Yixin Shen

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el silencioso y de alto riesgo mundo de la seguridad digital, un desafío fundamental ha sido durante mucho tiempo cómo proteger la información frente a la amenaza futura de los ordenadores cuánticos. Durante décadas, los criptógrafos han dependido de un rompecabezas matemático conocido como Aprendizaje con Errores (Learning With Errors). Imagine intentar encontrar un camino oculto a través de un bosque denso, pero cada vez que da un paso, el suelo bajo sus pies se desplaza ligeramente, alterando sus mediciones. Este "ruido" hace que el rompecabezas sea increíblemente difícil de resolver para los ordenadores estándar, pero sigue siendo la base de muchos sistemas de cifrado propuestos y diseñados para resistir ataques cuánticos. La seguridad de estos sistemas depende de la suposición de que incluso un potente ordenador cuántico no puede realizar ingeniería inversa de forma eficiente al camino oculto a partir de los datos ruidosos.

Para comprender la fuerza de esta suposición, los investigadores suelen traducir el problema a un lenguaje diferente, uno que involucra estados cuánticos y grupos ocultos. Piense en un estado cuántico como una moneda invisible y delicada que puede existir en una superposición de cara y cruz simultáneamente. En algunas versiones del problema, estas monedas están dispuestas de una manera que revela un patrón oculto, de forma muy parecida a encontrar un ritmo específico en una canción compleja. Durante años, los científicos han sabido cómo resolver una versión específica y simplificada de esta tarea de búsqueda de patrones, pero las versiones más complejas y realistas han permanecido obstinadamente resistentes a las soluciones cuánticas. La pregunta era si un ordenador cuántico podría eventualmente descifrar la versión completa y ruidosa del rompecabezas, o si el ruido es lo suficientemente fuerte como para mantenerlo a salvo para siempre.

Un equipo de investigadores de Rennes, Francia, ha dado ahora un paso significativo para responder a esta pregunta mediante la introducción de un nuevo marco matemático que cierra la brecha entre lo simple y lo complejo. Desarrollaron un método para resolver una versión generalizada del problema de búsqueda de patrones, que denominan el Problema del Coseno Ciclotómico. Este nuevo enfoque funciona sobre un tipo específico de sistema numérico que se comporta de manera diferente a los números enteros estándar, lo que permite a los investigadores aplicar una técnica poderosa conocida como cribado cuántico (quantum sieving). Al filtrar y combinar cuidadosamente los estados cuánticos, su algoritmo puede despojar las capas de complejidad, revelando gradualmente el secreto oculto. El resultado es un algoritmo cuántico que puede resolver este problema generalizado específico en un tiempo significativamente más rápido que el exponencial, aunque todavía más lento que la velocidad vertiginosa de una solución de tiempo polinómico.

Sin embargo, los investigadores son cuidadosos al aclarar qué significa y qué no significa su descubrimiento para el futuro del cifrado. Aunque su método resuelve con éxito el problema generalizado para una amplia gama de parámetros, aún no rompe el problema de Aprendizaje con Errores estándar utilizado en la criptografía del mundo real. La razón reside en la cantidad de muestras requeridas. El algoritmo necesita una vasta cantidad de datos cuánticos para funcionar eficazmente, mucho más de lo que está disponible actualmente a partir de la reducción estándar que convierte el problema de cifrado en el problema de búsqueda de patrones. En esencia, los investigadores han construido una llave muy poderosa, pero la cerradura que intentan abrir requiere un llavero demasiado grande para ser producido por los métodos actuales.

El núcleo de su trabajo implica una manipulación ingeniosa de los estados cuánticos sobre una estructura llamada anillo ciclotómico. En términos más sencaderos, crearon una nueva forma de organizar la información cuántica para que conserve una estructura oculta, incluso cuando el problema original parecía haberla perdido. Lo lograron definiendo un nuevo tipo de grupo, una estructura matemática que les permite utilizar un "cribado" para filtrar la información no deseada. Este cribado funciona combinando repetidamente los estados cuánticos de una manera que cancela el ruido y amplifica la señal del secreto oculto. El proceso es iterativo, avanzando paso a paso a través de diferentes niveles de precisión matemática, de forma muy parecida a refinar una piedra bruta para convertirla en una gema eliminando pequeñas astillas de material capa por capa.

Sus hallazgos muestran que, para una clase específica de problemas que involucran módulos de potencia de primos, el secreto oculto puede recuperarse en lo que se conoce como tiempo cuasi-polinómico. Este es un punto medio entre el tiempo exponencial lento que tardan los ordenadores clásicos en resolver problemas difíciles y la velocidad instantánea del tiempo polinómico. El algoritmo utiliza un número de muestras cuánticas que crece lo suficientemente lento como para ser considerado eficiente para ciertos parámetros, pero los investigadores enfatizan que esta eficiencia no se traduce automáticamente en una ruptura del cifrado estándar. La reducción del problema de cifrado estándar al nuevo problema produce un número limitado de los estados cuánticos necesarios, lo que crea un cuello de botella que impide que el algoritmo pueda aplicarse directamente para romper los sistemas criptográficos actuales.

El artículo también explora la relación entre su nuevo problema y otros desafíos cuánticos conocidos, como el Problema del Coseno Diedral y el Problema del Coseno Diedral Extrapolado. Demuestran que su método puede resolver estos problemas relacionados cuando el módulo es una potencia de un número primo, extendiendo los resultados previos que estaban limitados a las potencias de dos. Esta generalización es significativa porque muestra que la estructura matemática subyacente es más robusta y versátil de lo que se pensaba. Al demostrar que estos problemas son equivalentes bajo ciertas condiciones, los investigadores proporcionan un mapa más claro del panorama de la criptografía resistente al ámbito cuántico, mostrando dónde podrían estar los puntos débiles y dónde permanecen sólidas las defensas.

En última instancia, este trabajo sirve como una prueba de estrés rigurosa para las suposiciones que sustentan la criptografía post-cuántica. Confirma que, si bien los ordenadores cuánticos poseen el poder teórico para resolver ciertos problemas complejos de búsqueda de patrones mucho más rápido que las máquinas clásicas, el ruido y las restricciones específicos del Aprendizaje con Errores proporcionan una barrera formidable. Los investigadores han demostrado que, incluso con técnicas cuánticas avanzadas, el camino para romper el cifrado no es tan directo como se podría esperar. El "ruido" en el sistema no es solo un inconveniente menor; es una característica fundamental que, combinada con las limitaciones de la generación actual de muestras cuánticas, mantiene el camino oculto seguro. El estudio concluye que, aunque el campo ha avanzado significativamente en la comprensión de la mecánica de estos rompecabezas cuánticos, los métodos de cifrado estándar permanecen seguros frente a esta línea de ataque en particular, al menos en el futuro previsible.

Resumen Técnico: Cosets Cíclotómicos, Subgrupo Oculto y Tamizado Cuántico para Módulos de Potencia de Primos

1. Contexto y Motivación del Problema

El problema de Aprendizaje con Errores (LWE) es un supuesto fundamental en la criptografía post-cuántica. Mientras que Regev estableció una reducción cuántica de LWE al Problema del Coset Diedral (DCP), y Brakerski et al. introdujeron posteriormente el Problema del Coset Diedral Extrapolado (EDCP) para probar la equivalencia con LWE, existe una limitación estructural significativa. A diferencia del DCP, los EDCP generales no poseen una estructura de subgrupo oculto exacta porque el conjunto de traslaciones no forma un subgrupo. Esta limitación impide la aplicación directa de técnicas eficientes de subgrupo oculto, particularmente para módulos que no son potencias de dos.

Un trabajo reciente de Bai et al. (CRYPTO 2025) logró un algoritmo cuántico de tiempo casi-polinomial para EDCP y Gaussian $S|LWE\rangle$ sobre módulos de potencia de dos ( $q=2^t$ ) explotando una cadena específica de ideales 2-ádicos. Sin embargo, generalizar esto a módulos de potencia de primos arbitrarios ( $q=p^t$ ) ha resultado difícil porque el grupo diedral de orden $2q$ es nilpotente solo si $q$ es una potencia de dos. En consecuencia, las técnicas estándar de tamizado de grupos nilpotentes (como las de Imran e Ivanyos) no podían aplicarse directamente a EDCP o DCP con módulos que no fueran potencias de dos.

2. Metodología y Construcción Central

2.1 El Problema del Coset Cíclotómico (CCP)

Para superar la falta de una estructura de subgrupo oculto en EDCP para potencias de primos generales, los autores introducen el Problema del Coset Cíclotómico (CCP). Este problema se define sobre el anillo cíclotómico $R_q = \mathbb{Z}_q[\zeta_p]$ , donde $p$ es un primo, $q=p^t$ , y $\zeta_p$ es una raíz $p$ -ésima primitiva de la unidad.

Los autores definen un grupo de producto semidirecto $G_{n,q,p} = R_q^n \rtimes \mathbb{F}_p$ . Demuestran que este grupo es nilpotente con una clase de nilpotencia de $t(p-1)$ . Dentro de este grupo, identifican un subgrupo oculto $H_s$ generado por $(s, 1)$ , donde $s$ es el vector secreto. Los estados de coset asociados con este subgrupo toman la forma:
$|\phi_{x,s}\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} |j\rangle |x + \lambda_j s \rangle$
donde $\lambda_j = \sum_{i=0}^{j-1} \zeta_p^i$ . Cuando $p=2$ , esta construcción se reduce exactamente al DCP estándar.

2.2 Transformada de Fourier Cuántica (QFT) sobre Anillos Cíclotómicos

Un componente técnico crítico es la definición e implementación eficiente de la Transformada de Fourier Cuántica sobre el anillo $R_L = R/\pi^L R$ , donde $\pi = \zeta_p - 1$ . Utilizando la traza del cuerpo y la descomposición $\pi$ -ádica del ideal $(p) = (\pi)^{p-1}$ , los autores construyen una QFT que mapea las muestras de CCP a estados de fase.

Esta transformación convierte el problema de recuperar $s$ de los estados de coset en el Problema del Estado de Fase (PSP), donde el secreto está codificado en la fase del estado cuántico:
$|\psi_y\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} \chi_y(\lambda_j s) |j\rangle$
Aquí, $\chi_y$ es un carácter del grupo aditivo del anillo.

2.3 El Algoritmo de Tamizado Cuántico

Los autores adaptan el marco "Simon-meets-Kuperberg" al entorno cíclotómico. El algoritmo opera reduciendo iterativamente el nivel del módulo usando la cadena de ideales $\pi$ -ádica:
$R_q \cong R_{\pi^L} \to R_{\pi^{L-1}} \to \dots \to R_{\pi} \cong \mathbb{F}_p$

El proceso de tamizado implica:

Búsqueda de Suma Cero: Dada una serie de muestras de estado de fase con etiquetas $y_i$ , el algoritmo encuentra una subsecuencia tal que $\sum y_i \equiv 0 \pmod \pi$ . Esto se logra mediante un algoritmo de búsqueda de suma cero determinista (basado en Imran e Ivanyos) aplicado a los residuos módulo $\pi$ .
Combinación de Estados: Al realizar el producto tensorial de los estados cuánticos correspondientes y ejecutar cambios de base y mediciones específicas, el algoritmo produce una nueva muestra de estado de fase con una etiqueta en el anillo inferior $R_{\pi^{L-1}}$ .
Iteración: Este proceso se repite $L-1$ veces para reducir el problema al caso base sobre $\mathbb{F}_p$ , donde el secreto puede recuperarse mediante álgebra lineal.
Levantamiento (Lifting): Una vez encontrado $s \pmod p$ , el algoritmo resuelve recursivamente para las potencias superiores de $p$ para recuperar el secreto completo $s \in \mathbb{Z}_q^n$ .

3. Contribuciones Clave

Introducción de CCP y CyLWE: El artículo define el Problema del Coset Cíclotómico (CCP) y el LWE Cíclotómico (CyLWE). Establece que, para una $p$ constante, estos problemas son equivalentes a sus contrapartes clásicas (DCP y LWE) y poseen una estructura de subgrupo oculto sobre un grupo nilpotente, a diferencia del EDCP general.
QFT Cíclotómica y Estados de Fase: Los autores definen rigurosamente la QFT sobre anillos cíclotómicos y demuestran cómo transformar las muestras de CCP en estados de fase, permitiendo la aplicación de técnicas de tamizado.
Algoritmo de Tamizado de Tiempo Casi-Polinomial: Presentan un algoritmo cuántico (Algoritmo ctor 1) que resuelve el CCP en tiempo casi-polinomial ( $2^{O(\log n \log q)}$ ) utilizando espacio cuántico polinomial, siempre que el número de muestras también sea casi-polinomial.
Generalización de Resultados Previos: El trabajo extiende los resultados de tiempo casi-polinomial de Bai et al. (que estaban limitados a $q=2^t$ ) a cualquier módulo de potencia de primo $q=p^t$ .
Pruebas de Equivalencia: El artículo proporciona reducciones cuánticas mostrando que:
- El EDCP uniforme y el $S|LWE\rangle$ Gaussiano sobre módulos de potencia de primos pueden reducirse a CCP.
- Consecuentemente, existen algoritmos cuánticos de tiempo casi-polinomial para el EDCP uniforme y el $S|LWE\rangle$ Gaussiano cuando $q=p^t$ .

4. Resultados y Complejidad

Complejidad: El algoritmo propuesto resuelve el CCP con una complejidad de tiempo y de muestras de $2^{O(\log n \log q)}$ utilizando espacio cuántico polinomial.
Alcance: Los resultados se aplican a cualquier módulo $q = p^t$ donde $p$ es un primo fijo.
Reducciones: El artículo establece que resolver el CCP permite resolver el EDCP uniforme y el $S|LWE\rangle$ Gaussiano en tiempo casi-polinomial bajo las mismas restricciones de parámetros.

5. Significado y Limitaciones

Los autores enfatizan que, si bien este trabajo avanza significativamente en la comprensión de los algoritmos cuánticos para problemas de redes sobre módulos de potencia de primos, no produce un algoritmo de tiempo casi-polinomial para el LWE estándar.

La limitación surge de la cadena de reducción:

El LWE estándar se reduce a DCP (o EDCP).
DCP/EDCP se reduce a CCP.
El resolvedor de CCP requiere un número casi-polinomial de muestras.

Las reducciones conocidas de LWE a DCP/EDCP producen solo un número limitado (polinomial) de estados aproximados. Dado que el número de muestras requerido por el resolvedor de CCP excede el número de muestras disponibles de la reducción de LWE, la complejidad global para resolver el LWE estándar sigue siendo exponencial.

Por lo tanto, la contribución principal del artículo es teórica: extiende el poder del tamizado de grupos nilpotentes a una clase más amplia de módulos y proporciona un marco unificado para problemas de coset sobre anillos cíclotómicos, manteniendo una postura modesta sobre la amenaza inmediata para la seguridad de LWE estándar.