Certified Randomness with Optimal Rate

En el mundo digital, la confianza es una mercancía frágil. Cuando votamos en línea, generamos códigos secretos para la banca o elegimos líderes para redes descentralizadas, dependemos de una aleatoriedad que sea verdaderamente impredecible. Si esta aleatoriedad es predecible o sesgada, el sistema entero colapsa. Durante décadas, los científicos han buscado una forma de generar tal aleatoriedad sin necesidad de confiar en la máquina que realiza la generación. El escenario ideal implica un dispositivo que produzca una cadena de bits —ceros y unos— que sea tan caótica y uniforme que nadie, ni siquiera el propietario del dispositivo, pudiera haber adivinado el resultado de antemano. Este es el santo grial de la "aleatoriedad certificada": una garantía matemática de que el resultado es verdaderamente aleatorio, verificable por cualquiera, sin requerir una semilla secreta preexistente.

El desafío siempre ha sido que los métodos existentes o producían una aleatoriedad débil que podía ser fácilmente manipulada o requerían que un humano de confianza proporcionara un pequeño número inicial aleatorio. Un nuevo estudio de Siddhartha Jain, Saachi Mutreja y Bhaskar Roberts aborda esta limitación fundamental. Han desarrollado un protocolo que permite a una computadora cuántica demostrar que ha generado una cadena de bits con una aleatoriedad casi perfecta, incluso si la computadora es maliciosa y la persona que comprueba el resultado es completamente determinista, careciendo de sus propios números aleatorios. Este avance elimina la necesidad de cualquier punto de partida de confianza, logrando una tasa de aleatoriedad tan alta como es teóricamente posible.

Los investigadores trabajaron dentro de un marco conocido como el modelo de oráculo aleatorio cuántico, un entorno teórico donde todas las partes tienen acceso a una función pública y perfectamente aleatoria que actúa como un hash universal. En este entorno, construyeron un sistema donde un probador cuántico puede generar una larga cadena de bits y proporcionar una prueba corta de que la cadena es genuinamente aleatoria. La innovación clave es que el verificador, quien comprueba la prueba, no necesita ser aleatorio por sí mismo; puede ser un algoritmo fijo y determinista. Los intentos previos para lograr esto o bien fallaron en garantizar una aleatoriedad de alta calidad o dependieron de que el verificador tuviera una pequeña semilla aleatoria de confianza para poner en marcha el proceso. El nuevo protocolo elimina esa semilla por completo, demostrando que un verificador determinista aún puede ser convencido de la aleatoriedad de una larga cadena generada por un dispositivo cuántico no confiable.

Para entender la importancia, uno debe observar qué sucede cuando un sistema no es perfectamente aleatorio. Si una cadena de bits es solo "débilmente" aleatoria, podría parecer caótica, pero aún podría estar sesgada hacia ciertos patrones, lo que la haría vulnerable a la predicción. Los investigadores demostraron que su método garantiza un nivel de entropía, o desorden, que es casi maximal. En términos prácticos, esto significa que para una cadena de una longitud específica, el número de bits que son verdaderamente impredecibles es casi igual a la longitud total de la cadena. La única pérdida diminuta de aleatoriedad es una cantidad logarítmica, lo cual es inevitable debido a la naturaleza de las leyes de la física y la computación. Este es un avance vasto sobre los métodos anteriores, que a menudo producían cadenas donde la cantidad de aleatoriedad garantizada era una fracción minúscula de la longitud total.

El protocolo funciona en dos etapas principales. Primero, el dispositivo cuántico genera una fuente "débilmente" aleatoria utilizando una construcción matemática específica que ha sido probada segura contra ataques cuánticos. Esta fuente aún no es lo suficientemente buena para aplicaciones de alto riesgo. En la segunda etapa, el dispositivo hace pasar esta fuente a través de una función de compresión, que actúa como un filtro. Este filtro condensa la fuente débil en una cadena de bits más corta y mucho más fuerte. Los investigadores demostraron que incluso si un adversario intenta manipular el proceso eligiendo entradas específicas o observando el comportamiento de la función, no puede forzar a que el resultado final sea predecible. La cadena final retiene un alto nivel de entropía de min, una medida de qué tan difícil es adivinar el resultado más probable, incluso cuando el adversario ha visto todo el historial de la interacción.

Un componente crítico de este trabajo es el concepto de entropía de min "condicional". En muchas aplicaciones del mundo real, como un faro de aleatoriedad pública que transmite un nuevo número aleatorio cada hora, la seguridad del número actual depende del hecho de que no pueda ser predicho incluso si un atacante conoce todos los números anteriores. Los investigadores demostaron que su protocolo garantiza que cada nuevo pulso de aleatoriedad sea impredecible, incluso cuando está condicionado por todos los mensajes y datos que ocurrieron antes. Esto es esencial para aplicaciones como la elección de líderes en redes blockchain o la generación de cadenas aleatorias comunes para protocolos criptográficos, donde la integridad de la ronda actual depende de la impredecibilidad de la ronda pasada.

El equipo también abordó las limitaciones de su propio trabajo con rigurosa honestidad. Demostraron que es imposible lograr una aleatoridad uniforme perfecta con un verificador determinista si se le permite al adversario operar durante un tiempo polinómico. Un atacante podría teóricamente utilizar una técnica llamada muestreo de rechazo para fijar un pequeño número de bits en la salida, efectivamente "manipulando" el sistema para producir un resultado ligeramente sesgado. Sin embargo, los investigadores demostraron que su protocolo logra el mejor resultado posible bajo estas restricciones: garantiza que el número de bits que pueden ser fijados por un atacante es tan pequeño que la aleatoriedad restante sigue siendo suficiente para todos los propósitos criptográficos prácticos. La pérdida es insignificante y la seguridad se mantiene frente a cualquier adversario con capacidad de cómputo realista.

Este trabajo tiene implicaciones inmediatas para el futuro de la comunicación segura y los sistemas descentralizados. Al eliminar la necesidad de una semilla de confianza, el protocolo permite la creación de faros de aleatoriedad que pueden ser ejecutados en un único dispositivo cuántico no confiable. Tal faro podría publicar periódicamente números aleatorios frescos e impredecibles que cualquiera pueda verificar. La seguridad de estos números no dependería de la honestidad del operador del dispositivo, sino de las leyes de la mecánica cuántica y la estructura matemática del protocolo mismo. Aunque la implementación actual depende de modelos teóricos, el camino hacia la aplicación práctica es más claro que nunca, ofreciendo una forma de generar la aleatoriedad confiable que la sociedad digital moderna necesita desesperadamente sin requerir que confiemos en la máquina.

El estudio constituye una respuesta definitiva a una pregunta planteada por investigadores anteriores respecto a los límites de la aleatoriedad certificada. Confirma que, si bien la uniformidad perfecta es matemáticamente inalcanzable para un verificador determinista, se puede lograr un nivel de aleatoriedad que es efectivamente indistinguible de la perfección. Los investigadores no solo han mejorado la tasa de aleatoriedad; han redefinido los límites de lo que es posible en un entorno sin confianza. Su construcción proporciona una garantía robusta e incondicional de seguridad en el modelo de oráculo aleatorio cuántico, estableciendo un nuevo estándar para cómo entendemos la aleatoriedad en la era cuántica. El resultado es un protocolo que es tanto teóricamente sólido como prácticamente relevante, cerrando la brecha entre la teoría cuántica abstracta y las necesidades concretas de una infraestructura digital segura.