⚛️ quantum physics

Unconditional Certified Randomness without Structure

Este artículo presenta un protocolo no interactivo y públicamente verificable para la aleatoriedad certificada incondicional en el modelo de oráculo aleatorio cuántico, logrando seguridad contra un número subexponencial de consultas cuánticas adaptativas sin depender de la conjetura de Aaronson–Ambainis ni restringir la profundidad de las consultas.

Autores originales: Andrea Coladangelo, Dakshita Khurana, Saachi Mutreja, Bhaskar Roberts, Joseph Slote, Avishay Tal

Publicado 2026-09-01

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Andrea Coladangelo, Dakshita Khurana, Saachi Mutreja, Bhaskar Roberts, Joseph Slote, Avishay Tal

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 cuántico, la aleatoriedad no es solo una falta de información; es una característica fundamental de la realidad. Incluso si se sabe todo lo posible sobre un sistema cuántico, todavía no se puede predecir el resultado de una medición con certeza. Esta imprevisibilidad inherente es el motor detrás de la computación cuántica, pero también presenta un desafío único para la seguridad. ¿Cómo puede una persona que utiliza una computadora clásica estándar estar segura de que un dispositivo cuántico distante y no confiable está produciendo realmente una aleatoriedad verdadera, en lugar de simplemente fingirla con un truco ingenioso? Esta pregunta constituye el corazón de la "aleatoriedad certificada", un campo donde los investigadores intentan construir protocolos que permitan al usuario clásico verificar la calidad del ruido cuántico. Durante años, las soluciones más prometedoras dependieron de suposiciones complejas sobre los límites de la computación o requirieron que el dispositivo cuántico estuviera físicamente aislado de otros, condiciones que son difíciles de imponer en el mundo real.

Un equipo de investigadores ha demostrado ahora una nueva forma de certificar la aleatoriedad que elimina estas pesadas restricciones. Han diseñado un protocolo que funciona en un entorno teórico conocido como el modelo de oráculo aleatorio cuántico, un marco donde una computadora puede consultar una base de datos masiva e impredecible. Su avance es un método que es no interactivo, lo que significa que el dispositivo cuántico simplemente produce una respuesta sin necesidad de conversar de ida y vuelta con el verificador, y es públicamente verificable, lo que permite a cualquiera comprobar el resultado. Lo más importante es que demostraron que este protocolo funciona incondicionalmente contra cualquier adversario, siempre que dicho adversario no pueda realizar un número imposiblemente grande de consultas a la base de datos. Este resultado resuelve una pregunta de larga data sobre si la verdadera aleatoriedad puede certificarse sin depender de conjeturas matemáticas no probadas, ofreciendo una base robusta para futuros sistemas criptográficos.

La historia de este descubrimiento comienza con un acertijo específico propuesto por investigadores anteriores, que involucraba encontrar una solución oculta dentro de un vasto espacio de posibilidades. Imagine una cuadrícula gigante donde cada celda contiene un código secreto. Una computadora cuántica puede encontrar un patrón específico en esta cuadrícula mucho más rápido de lo que una computadora clásica puede, pero la versión original de este acertijo tenía un fallo: para demostrar que la solución era verdaderamente aleatoria, los investigadores tuvieron que asumir que una compleja conjetura matemática era cierta. Esta conjetura, aunque ampliamente aceptada, nunca había sido probada. El nuevo trabajo de Coladangelo, Khurana y sus colegas muestra que, al retocar ligeramente las reglas del acertijo, la necesidad de esta suposición no probada desaparece por completo.

Los investigadores lograron esto cambiando dos ingredientes clave del acertijo original. Primero, alteraron el "código" utilizado para definir las soluciones válidas. En la configuración original, el código era rígido, pero el equipo introdujo una estructura más flexible que aún podía verificarse de manera eficiente pero que era más difícil de predecir para un atacante. Segundo, y quizás más crucial, cambiaron la naturaleza de la propia base de datos. En lugar de que cada entrada en la base de datos fuera igualmente probable de ser un cero o un uno, hicieron que la base de datos fuera "sesgada". En esta versión sesgada, los ceros son mucho más comunes que los unos. Este sutil cambio resulta ser la clave de la prueba. Asegura que, cuando una computadora cuántica resuelve el acertijo, se ve obligada a explorar la base de datos de una manera que deja una firma distintiva y aleatoria, mientras que simultáneamente hace que sea imposible para una computadora clásica fingir el resultado sin un esfuerzo astronómico.

El núcleo de su argumento se basa en una técnica de conteo ingeniosa. Razonaron que, si una computadora cuántica intentara producir una respuesta no aleatoria y predecible, tendría que centrar su atención en partes específicas de la base de datos. Sin embargo, debido a la forma en que la base de datos está sesgada y el código está estructurado, cualquier intento de centrarse en una respuesta específica requeriría que la computadora realizara tantas consultas que excedería los límites de lo que es físicamente posible dentro de las restricciones del protocolo. Los investigadores demostraron que, si un adversario intenta producir una solución predecible, se ve obligado a "consultar" la base de datos tan intensamente que el protocolo detectaría la anomalía. Por el contrario, si el adversario se mantiene dentro de los límites permitidos, la única forma de tener éxito es producir un resultado que sea genuinamente aleatorio.

Este resultado es significativo porque elimina el último gran obstáculo para un tipo específico de ventaja cuántica. Durante algún tiempo, los únicos ejemplos conocidos de computadoras cuánticas superando a las clásicas en un entorno "sin estructura" —uno que no depende de propiedades matemáticas especiales como la factorización de números grandes— estaban ligados a conjeturas no probadas. Al demostrar que la aleatoridad puede certificarse sin estas conjeturas, el equipo ha mostrado que esta nueva fuente de ventaja cuántica es real y robusta. Su protocolo también es práctico en su diseño: requiere solo un dispositivo cuántico, no implica comunicación de ida y vuelta y permite que cualquiera con acceso a la base de datos verifique el resultado.

La prueba del equipo es rigurosa y cubre una amplia gama de posibles atacantes. Demostraron que incluso un adversario con poder de cómputo ilimitado, que solo está limitado por el número de veces que puede hacer preguntas a la base de datos, no puede romper el sistema. La seguridad se mantiene siempre que el número de consultas permanezca por debajo de cierto umbral, el cual es exponencialmente grande pero aún finito. Esto significa que, para cualquier escenario realista, la aleatoriedad generada está garantizada de ser de alta calidad. Los investigadores también abordaron un problema técnico sutil: aunque su protocolo fue diseñado utilizando una base de datos sesgada, demostraron cómo simular este sesgo utilizando una base de datos uniforme estándar, asegurando que el método pueda implementarse en el mundo real sin necesidad de un oráculo especial.

En el panorama más amplio de la información cuántica, este trabajo proporciona un ejemplo limpio e incondicional de cómo se puede aprovechar la mecánica cuántica para generar y verificar la aleatoriedad. Cierra la brecha entre la posibilidad teórica y la seguridad práctica, ofreciendo un protocolo que es tanto simple de describir como matemáticamente sólido. Al mostrar que la aleatoriedad es inherente al proceso y no un artefacto de una suposición no probada, los investigadores han fortalecido los cimientos para futuras aplicaciones en criptografía y comunicación segura. El trabajo es un testimonio del poder del razonamiento matemático cuidadoso, convirtiendo un complejo problema teórico en una realidad clara y verificable.

Resumen Técnico: Aleatoriedad Certificada Incondicional sin Estructura

Planteamiento del Problema

El artículo aborda el desafío de generar aleatoriedad certificada en el Modelo de Oráculo Cuántico (QROM). Específicamente, busca un protocolo que sea:

No interactivo: El probador cuántico envía un único mensaje al verificador.
Verificable públicamente: Cualquier parte con acceso al oráculo aleatorio puede verificar el resultado.
De un solo probador: No depende de supuestos de no comunicación entre múltiples dispositivos.
Incondicionalmente seguro: La seguridad no debe depender de conjeturas teóricas de la complejidad no probadas.

El trabajo previo de Yamakawa y Zhandry (YZ) [YZ24] demostró una ventaja cuántica para un problema de búsqueda NP en el QROM, lo que implicaba un protocolo de aleatoriedad certificada. Sin embargo, su protocolo dependía de la conjetura de Aaronson–Ambais para garantizar que el resultado del algoritmo cuántico poseyera una alta entropía mínima. Sin esta conjetura, no estaba claro si el resultado era verdaderamente aleatorio o si un adversario clásico podría predecirlo. Los resultados incondicionales previos (por ejemplo, [KRT26]) se limitaban a adversarios que realizaban consultas en muy pocas capas adaptativas ( $o(\log n)$ ), fallando en cubrir adversarios adaptativos generales.

Metodología y Técnicas Principales

Los autores proponen una variante del problema de Yamakawa–Zhandry, denominada el problema YZ sesgado, y demuestran que certifica incondicionalmente la entropía mínima contra adversarios que realizan hasta $2^{o(n^c)}$ consultas adaptativas. La estrategia de prueba se basa en argumentos de híbridos y reprogramación de oráculos, utilizando tres innovaciones técnicas principales:

1. Norma de Consulta y el Polítopo de la Norma de Consulta

En lugar de analizar el "peso de consulta" (la probabilidad de consultar una entrada específica), los autores analizan la norma de consulta (la raíz cuadrada del peso de consulta). Definen una estructura geométrica llamada polítopo de la norma de consulta, que representa las restricciones lineales sobre cómo las normas de consulta pueden cambiar cuando un oráculo es reprogramado.

Estabilidad Local: Establecen que si un oráculo es reprogramado en entradas con normas de consulta pequeñas, las normas de consulta en otras entradas cambian solo ligeramente.
Reprogramación de Coordenadas Pesadas: Un lema clave (Lema 4.3) muestra que incluso si un adversario consulta intensamente un gran conjunto de coordenadas ( $M$ ), existen exponencialmente muchas formas de reprogramar el oráculo en un subconjunto de $M$ de tal manera que el adversario aún coloque una norma de consulta significativa en un subconjunto más pequeño, pero aún sustancial, de $M$ (específicamente $\Omega(\sqrt{n})$ coordenadas). Esto supera la dificultad de reprogramar las coordenadas "pesadas" donde el adversario podría detectar cambios.

2. Códigos de Corrección de Errores Modificados

La construcción original de YZ utilizaba un código con propiedades específicas de recuperación de listas que eran insuficientes para los nuevos límites de reprogramación (que solo preservaban $\Omega(\sqrt{n})$ símbolos conocidos en lugar de un número lineal).

Los autores construyen una familia de códigos de Reed–Solomon plegados (FRS) con una tasa menor ( $R \approx 1/\sqrt{n}$ ).
Estos códigos son $(\zeta, \ell, L)$ -recuperables de lista, lo que significa que si un palabra de código concuerda con listas cortas en una fracción evanescente ( $\approx 1/\sqrt{n}$ ) de las coordenadas, el número de tales palabras de código es pequeño. Esto coincide con las $\Omega(\sqrt{n})$ coordenadas pesadas supervivientes garantizadas por el argumento del polítopo.

3. Oráculo Aleatorio Sesgado

Para mantener la completitud del protocolo (asegurando que el probador cuántico honesto tenga éxito) con el nuevo código de baja tasa, los autores introducen un oráculo aleatorio sesgado.

El oráculo $H$ devuelve 1 con una pequeña probabilidad $p \approx 1/\sqrt{n}$ y 0 con probabilidad $1-p$ .
Este sesgo asegura que el vector de "error" en la base dual (tras la transformada de Fourier) tenga un peso de Hamming de $O(\sqrt{n})$ con alta probabilidad. Esto entra dentro del radio de decodificación única del código dual $C^\perp$ , permitiendo que el probador honesto decodifique con éxito y devuelva una solución válida.
El artículo demuestra que este oráculo sesgado puede simularse eficientemente en el QROM estándar utilizando un oráculo aleatorio uniforme.

Contribuciones Clave y Resultados

El artículo presenta un Protocolo de Entropía Mínima Certificable con las siguientes garantías (Teorema 1.1):

Seguridad Incondicional: El protocolo es seguro contra cualquier adversario que realice como máximo $2^{o(n^c)}$ consultas cuánticas adaptativas, para cualquier constante $c \in (0, 1/2)$ . Esto elimina la necesidad de la conjetura de Aaronson–Ambais.
Garantía de Entropía Mínima: Si un adversario causa que el verificador acepte con una probabilidad notable, la distribución de salida tiene una entropía mínima de al menos $\Omega(n^c)$ .
Propiedades del Protocolo:
- No interactivo: El probador devuelve una solución candidata $x$ .
- Verificable públicamente: El verificador comprueba si $x \in C$ y si $H_i(x_i) = 0$ para todo $i$ .
- De un solo probador: No se requieren supuestos de comunicación entre dispositivos.

La prueba procede por contradicción:

Afirmación A (Baja entropía implica consultas pesadas): Si un adversario produce una respuesta correcta específica con alta probabilidad (baja entropía), debe haber consultado intensamente la mayoría de los símbolos de esa respuesta.
Afirmación B (El límite de consulta no puede consultar intensamente): Utilizando el lema de reprogramación de coordenadas pesadas y la propiedad de recuperación de lista del código modificado, los autores muestran que para casi todos los oráculos, ninguna respuesta correcta puede ser consultada intensamente por un adversario con el límite de consulta dado.
Conclusión: Estas dos afirmaciones son incompatibles, lo que implica que un adversario no puede producir una distribución de baja entropía con una probabilidad notable.

Significado y Reivindicaciones

El artículo afirma proporcionar el primer protocolo de aleatoriedad certificada incondicional en el QROM que es no interactivo, verificable públicamente y seguro contra adversarios adaptativos generales (hasta límites de consulta subexponenciales).

Perspectiva Estructural: Los autores destacan que el problema de Yamakawa–Zhandry es una fuente "sin estructura" de ventaja cuántica. Al demostrar la aleatoriedad inherente de su solución sin depender de conjeturas, el trabajo proporciona evidencia para la veracidad de la conjetura de Aaronson–Ambais (ya que el resultado implica que una consecuencia de esa conjetura se cumple incondicionalmente para esta variante).
Avance Técnico: El trabajo introduce el marco del polítopo de la norma de consulta, que ofrece una nueva perspectiva geométrica sobre los argumentos de reprogramación. Este marco permite límites más ajustados sobre cómo cambian las distribuciones de consulta bajo modificaciones del oráculo, específicamente manejando las coordenadas "pesadas" que anteriormente eran intratables en pruebas incondicionales.
Limitaciones y Preguntas Abiertas: Los autores señalan que su resultado se aplica a una variante del problema YZ (oráculo sesgado, código modificado). Plantean explícitamente una pregunta abierta (Pregunta 1) sobre si el lema de reprogramación de coordenadas pesadas puede mejorarse para preservar un número lineal de entradas pesadas, lo que potencialmente permitiría el uso del código y el oráculo YZ originales sin sesgo. También reconocen que su prueba requiere actualmente que el límite de consulta del adversario sea subexponencial ( $2^{o(n^c)}$ ), dejando el caso de consultas totalmente polinómicas como un área abierta para la investigación futura.

El artículo no propone implementaciones experimentales ni aplicaciones específicas en el mundo real más allá de la construcción teórica del protocolo. Su principal contribución es un avance teórico en los fundamentos de la certificación de la aleatoriedad cuántica.