⚛️ quantum physics

Compressed Permutation Oracles Revisited

Este artículo revisita la técnica del oráculo de permutación comprimida para establecer un límite de seguridad de $\Omega(N^{1/2})$ ajustado mediante una prueba conceptualmente más simple, permitiendo así análisis de seguridad cuántica rigurosos para construcciones criptográficas como SHA3, SHA1 y SHA2 que anteriormente estaban limitadas por límites más débiles.

Autores originales: Joseph Carolan, Christian Majenz

Publicado 2026-09-24

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Joseph Carolan, Christian Majenz

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 mundo digital, la seguridad a menudo se basa en la idea de una máquina perfecta e impredecible. Los criptógrafos imaginan un dispositivo que toma cualquier entrada y arroja una salida completamente aleatoria, pero con una regla crucial: si introduces la misma entrada dos veces, obtienes la misma salida cada vez. Esto se conoce como una permutación aleatoria. Es el motor invisible detrás de muchas de las herramientas que utilizamos para mantener nuestros datos seguros, desde la forma en que se almacenan nuestras contraseñas hasta los algoritmos que verifican la integridad de nuestras comunicaciones. Para probar si estas herramientas son verdaderamente seguras, los científicos imaginan a un atacante poderoso que puede hacer preguntas a esta máquina. En el mundo clásico, un atacante hace una pregunta a la vez. Pero en el mundo cuántico, un atacante puede hacer muchas preguntas a la vez, superponiéndolas de una manera que se siente como si estuviera haciendo todas las preguntas posibles simultáneamente. Esta capacidad de consultar en superposición hace que la tarea de probar la seguridad sea increíblemente difícil, porque el atacante obtiene información de una manera que desafía nuestra intuición habitual.

Durante años, los investigadores han intentado construir un modelo matemático para rastrear lo que un atacante cuántico aprende de estas preguntas. Un método prometedor, llamado el oráculo comprimido, actúa como un cuaderno simplificado. En lugar de rastrear la máquina entera y masiva, el cuaderno solo registra los pares específicos de entradas y salidas sobre los que el atacante ha preguntado hasta el momento. Esto hace que las matemáticas sean manejables, permitiendo a los científicos probar que ciertos sistemas de seguridad son seguros. Sin embargo, un problema significativo plagaba este método: el cuaderno no era perfectamente preciso. Solo se demostró que funcionaba correctamente cuando el atacante hacía un número relativamente pequeño de preguntas. Si el atacante hacía demasiadas preguntas, las predicciones del cuaderno podían alejarse de la realidad, dejando las pruebas de seguridad poco fiables. Esta limitación significaba que, para muchos sistemas criptográficos modernos, no podíamos estar seguros de que resistirían ante un adversario cuántico decidido.

Un equipo de investigadores ha revisado ahora este método y ha corregido su fallo más crítico. Han demostrado que el cuaderno comprimido es mucho más fiable de lo que se pensaba anteriormente. Su nuevo análisis demuestra que el método funciona correctamente incluso cuando el atacante hace un número de preguntas mucho mayor que antes; específicamente, hasta la raíz cuadrada del número total de entradas posibles. Este es un avance masivo sobre el límite anterior, que era solo una pequeña fracción de ese número. Los investigadores lo lograron cambiando la forma en que construyeron la conexión entre la máquina real y compleja y el cuaderno simplificado. En lugar de una construcción complicada e indirecta, demostraron que el cuaderno puede verse como una medición directa del estado subyacente de la máquina. Esta nueva perspectiva no solo hace que las matemáticas sean más limpias y directas, sino que también elimina el techo artificial de cuántas preguntas puede hacer el atacante antes de que la prueba se rompa.

El impacto de esta mejora es inmediato y concreto. Los investigadores aplicaron su nueva y más ajustada prueba a dos de las estructuras más importantes de la criptografía moderna: la construcción de esponja (sponge construction) y la función de compresión de Davies-Meyer. Estas son las plantillas utilizadas para construir las funciones hash que aseguran nuestro mundo digital, incluyendo el estándar SHA-3 y los sistemas más antiguos SHA-1 y SHA-2. Utilizando su método refinado, el equipo calculó exactamente cuántas consultas cuánticas necesitaría un atacante para romper estos sistemas. Encontraron que la seguridad de estos sistemas es robusta, requiriendo que un atacante realice un número de operaciones que crece con la raíz cuadrada del tamaño del sistema para encontrar colisiones, e incluso más para encontrar preimágenes. Sus resultados proporcionan números explícitos y concretos para la seguridad de las cuatro variantes principales de SHA-3, mostrando que permanecen seguras incluso contra computadoras cuánticas potentes, siempre que dichas computadoras no encuentren una manera de explotar debilidades estructurales específicas en el diseño subyacente.

Los investigadores fueron cuidadosos al distinguir entre probar la seguridad del modelo matemático y la seguridad del hardware real. Su trabajo confirma que, si la permutación aleatoria subyacente se comporta como se espera, las construcciones criptográficas construidas sobre ella son seguras. No afirmaron que la permutación específica utilizada en el estándar SHA-3 del mundo real sea perfecta, sino que el diseño en sí es sólido. Esta distinción es vital; significa que el fallo de un sistema probablemente provendría de un error en la implementación específica de la permutación, y no de una debilidad fundamental en la forma en que el sistema está construido. Al ajustar los límites matemáticos, los investigadores han dado a los criptógrafos una herramienta más poderosa para analizar sistemas futuros, asegurando que la próxima generación de seguridad digital pueda ser diseñada con una comprensión clara y precisa de las amenazas cuánticas que enfrenta.

El núcleo de su descubrimiento reside en cómo manejan la relación entre las consultas del atacante y la base de datos de respuestas conocidas. En el método antiguo, la conexión entre la máquina real y el cuaderno era algo laxa, introduciendo errores que se acumulaban a medida que crecía el número de preguntas. El nuevo enfoque trata al cuaderno como un reflejo directo y coherente del estado de la máquina. Construyeron un puente entre ambos que preserva las relaciones matemáticas exactas, asegurando que el cuaderno nunca pierda el rastro del estado real del sistema, sin importar cuántas preguntas se hagan. Este puente se construye utilizando una técnica que separa la información en niveles distintos, muy parecido a organizar una biblioteca por pisos, y luego normaliza cuidadosamente las conexiones entre ellos. Esta normalización asegura que las probabilidades calculadas en el cuaderno coincidan con las probabilidades en el mundo real, eliminando la deriva que anteriormente limitaba la utilidad del método.

Este trabajo no solo mejora una sola prueba; fortalece todo el fundamento del análisis de seguridad cuántica para la criptografía simétrica. Al empujar el límite del oráculo comprimido desde una pequeña fracción de las entradas posibles hasta la raíz cuadrada, los investigadores han abierto la puerta al análisis de sistemas que antes estaban fuera de su alcance. Los resultados sugieren que la ventaja cuántica para romper este tipo de sistemas criptográficos no es tan grande como se podría temer, siempre que los sistemas se diseñen con la capacidad suficiente. La capacidad del equipo para proporcionar constantes explícitas y límites concretos significa que los ingenieros pueden ahora calcular el nivel exacto de seguridad que ofrece un sistema, en lugar de depender de estimaciones vagas. Esta claridad es esencial para construir la infraestructura digital del futuro, asegurando que nuestros datos permanezcan protegidos en una era donde las computadoras cuánticas se están convirtiendo en una realidad.

El estudio también extiende sus hallazgos a los cifrados ideales, que son los bloques de construcción para muchos esquemas de cifrado. En este modelo, la seguridad depende de una familia de permutaciones, cada una controlada por una clave diferente. Los investigadores demostraron que su método mejorado funciona igual de bien aquí, incluso cuando el atacante puede consultar el sistema en superposición sobre diferentes claves. Este es un resultado significativo porque significa que la seguridad de estos sistemas no se degrada simplemente porque haya muchas claves involucradas. El análisis se mantiene firme independientemente del número de claves, reforzando la idea de que la estructura fundamental de estos diseños criptográficos es sólida contra ataques cuánticos.

En última instancia, este trabajo representa una maduración de las herramientas utilizadas para comprender la seguridad cuántica. Toma un método que alguna vez fue considerado demasiado frágil para un análisis riguroso y lo fortalece convirtiéndolo en un instrumento fiable. Los investigadores han demostrado que el oráculo comprimido no es solo una aproximación heurística, sino una forma matemáticamente sólida de rastrear la información cuántica. Al hacerlo, han proporcionado a la comunidad criptográfica una visión más clara del panorama, permitiéndoles diseñar sistemas que sean demostrablemente seguros contra las amenazas más avanzadas. El trabajo es un testimonio del poder de refinar nuestros modelos matemáticos para reflejar mejor las complejas realidades del mundo cuántico.

Resumen Técnico: Revisitando los Oráculos de Permutaciones Comprimidas

Planteamiento del Problema
El análisis de seguridad de las construcciones criptográficas simétricas, tales como el hashing de esponja (sponge hashing) y la compresión de Davies–Meyer, depende fuertemente de modelar sus primitivas subyacentes como permutaciones aleatorias o cifrados ideales. En el entorno cuántico, los adversarios pueden consultar estas primitivas en superposición (tanto hacia adelante como inversamente), lo que complica las pruebas de seguridad. Si bien la técnica de oráculo comprimido de Zhandry analizó con éxito las funciones aleatorias manteniendo una pequeña base de datos de pares entrada-salida, extender esto a las permutaciones es difícil debido a la restricción de inyectividad, que correlaciona las entradas de la base de datos.

Un marco anterior por Carolan [Car25] introdujo un oráculo de permutación comprimida utilizando permutaciones parciales como base de datos. Sin embargo, su análisis de solidez (soundness) estaba fundamentalmente limitado: la técnica solo se demostró sólida hasta $O(N^{1/12})$ consultas para permutaciones sobre $N$ elementos. Este pobre límite de solidez significaba que los errores de simulación podían dominar los límites de seguridad, impidiendo la derivación de garantías de seguridad concretas y ajustadas para funciones hash estándar como SHA-3, SHA-1 y SHA-2.

Metodología
Los autores revisitan el marco del oráculo de permutación comprimida para mejorar su garantía de solidez. La innovación técnica central es la construcción de la isometría de compresión directamente a partir de la "purificación ingenua" de una permutación aleatoria.

Purificación Ingenua y Estados de Completitud: Los autores consideran un registro inicializado en una superposición uniforme de todas las permutaciones ( $|S_N\rangle$ ). Una permutación parcial (base de datos) $f$ corresponde a un "estado de completitud" $|T_f\rangle$ , que es la superposición uniforme de todas las permutaciones totales consistentes con $f$ .
Niveles Ortogonales y Matrices de Gram: Los autores definen una jerarquía de subespacios (niveles) basada en el tamaño de la base de datos. Observan que los estados de completitud para diferentes bases de datos no son ortogonales. Para construir una isometría válida (un mapa que preserva la norma) desde el registro de la permutación al registro de la base de datos comprimida, separan estos estados en niveles ortogonales.
Construcción de POVM: El mapa de compresión se construye normalizando el marco de los estados de completitud. Esto se logra analizando la matriz de Gram $G_r$ de los estados en el nivel $r$ . Los autores demuestran que $G_r$ es invertible y cercana a la identidad para un número pequeño de consultas. La isometría de compresión $\tilde{V}$ se define como $\Gamma_r^\dagger G_r^{-1/2}$ , donde $\Gamma_r$ proyecta el mapa de síntesis sobre el $r$ -ésimo nivel.
Teoría de la Representación: Para acotar los factores de normalización (autovalores de $G_r$ ), los autores utilizan la teoría de la representación del grupo simétrico. Descomponen el espacio de permutación en representaciones irreducibles (módulos de Specht) y calculan explícitamente la acción de $G_r$ sobre estos subespacios. Esto les permite demostrar que la normalización requerida es pequeña cuando el número de consultas $q$ es pequeño en relación con $N$ .
Comparación de Consultas: La prueba establece que aplicar una consulta purificada seguida del mapa de contracción $V$ es cercano a aplicar el mapa de contracción seguido de la consulta del oráculo comprimido. Al acotar el error para una sola consulta y acumularlo a lo largo de $q$ consultas mediante un argumento de híbrido, derivan el límite de solidez final.

Contribuciones Clave

Límite de Solidez Ajustado: La contribución principal es la mejora del límite de solidez del oráculo de permutación comprimida de $O(N^{1/12})$ a un $\Omega(N^{1/2})$ ajustado. Específicamente, un algoritmo que realiza $q$ consultas distingue el oráculo comprimido de una permutación uniformemente aleatoria con una ventaja de como máximo $O(q/\sqrt{N})$ .
Simplicidad Conceptual: La prueba se describe como conceptualmente más simple y directa que los enfoques anteriores, apoyándose en una implementación coherente de una Medida de Operadores Positivos Valuados (POVM) en la purificación.
Extensión al Cifrado Ideal: Los resultados se extienden al modelo de cifrado ideal, manteniendo el mismo límite independientemente del número de claves o superposiciones sobre las claves.
Constantes Explícitas: El teorema proporciona constantes explícitas, lo que permite la derivación de límites de seguridad concretos y no asintóticos.

Resultados y Aplicaciones
La mejora en la solidez permite derivar límites inferiores concretos y ajustados para la seguridad de las principales construcciones de funciones hash:

Construcción de Esponja (SHA-3):
- Para una esponja con tasa $r$ , capacidad $c$ y longitud de digesto $d$ , los autores derivan probabilidades de éxito explícitas para ataques de preimagen y colisión.
- Probabilidad de éxito de preimagen: $O(T^2/2^d + T^3/2^c)$ .
- Probabilidad de éxito de colisión: $O(T^3/2^d + T^3/2^c)$ .
- Estos límites se aplican a los cuatro conjuntos de parámetros de SHA-3 (SHA3-224, 256, 384, 512). Los resultados confirman que una ventaja de distinción constante requiere $q = \Omega(\sqrt{N})$ consultas, recuperando los exponentes de seguridad cuántica esperados.
Construcción Davies–Meyer (SHA-1, SHA-2):
- Para una función Davies–Meyer de bloque de $n$ bits, los límites son $O(T^2/2^n)$ para preimágenes y $O(T^3/2^n)$ para colisiones en el modelo de cifrado ideal.
- El análisis se mantiene incluso cuando el adversario realiza consultas en superposición sobre las claves.

Significado
El artículo afirma que el teorema de solidez mejorado sirve como una herramienta de propósito general para analizar la seguridad cuántica en entornos donde las permutaciones aleatorias o los cifrados ideales son la primitiva subyacente. Al ajustar el límite de solidez a la escala de consultas de la raíz cuadrada, los autores permiten que el método de la base de datos comprimida proporcione garantías de seguridad fuertes y concretas para los estándares criptográficos ampliamente utilizados. El trabajo demuestra que es poco probable que la criptoanálisis de construcciones como SHA-3 se vea comprometida por computadoras cuánticas, a menos que dichas computadoras exploten debilidades estructurales significativas en la permutación específica (por ejemplo, Keccak) más allá del modelo de permutación aleatoria. El artículo enfatiza que estos son límites concretos dentro del modelo de permutación aleatoria y no afirman que la permutación fija de Keccak en sí misma se comporte como una permutación verdaderamente aleatoria.

Más como este