En criptografía , un oráculo aleatorio es un oráculo (una caja negra teórica ) que responde a cada consulta única con una respuesta (verdaderamente) aleatoria elegida uniformemente de su dominio de salida. Si se repite una consulta, responde de la misma manera cada vez que se envía esa consulta.
Dicho de otra manera, un oráculo aleatorio es una función matemática elegida uniformemente al azar, es decir, una función que asigna cada consulta posible a una respuesta aleatoria (fija) de su dominio de salida.
Los oráculos aleatorios aparecieron por primera vez en el contexto de la teoría de la complejidad, en el que se utilizaron para argumentar que las separaciones de clases de complejidad pueden enfrentar barreras de relativización, siendo el caso más destacado el problema P vs NP , dos clases que en 1981 se mostraron distintas en relación con una Oráculo aleatorio casi con seguridad . [1] Se abrieron camino en la criptografía con la publicación de Mihir Bellare y Phillip Rogaway en 1993, que los presentó como un modelo criptográfico formal para ser utilizado en pruebas de reducción. [2]
Normalmente se utilizan cuando la prueba no se puede realizar utilizando suposiciones más débiles sobre la función hash criptográfica . Un sistema que demuestra ser seguro cuando cada función hash es reemplazada por un oráculo aleatorio se describe como seguro en el modelo de oráculo aleatorio , a diferencia de lo que es seguro en el modelo estándar de criptografía .
Los oráculos aleatorios se utilizan normalmente como un reemplazo idealizado de las funciones hash criptográficas en esquemas donde se necesitan fuertes suposiciones de aleatoriedad en la salida de la función hash. Tal prueba a menudo muestra que un sistema o un protocolo es seguro al mostrar que un atacante debe exigir un comportamiento imposible del oráculo, o resolver algún problema matemático que se considera difícil para poder romperlo. Sin embargo, solo prueba tales propiedades en el modelo aleatorio de Oracle, asegurándose de que no haya defectos importantes de diseño. En general, no es cierto que tal prueba implique las mismas propiedades en el modelo estándar. Aún así, una prueba en el modelo aleatorio de Oracle se considera mejor que ninguna prueba de seguridad formal. [3]
No todos los usos de las funciones hash criptográficas requieren oráculos aleatorios: los esquemas que requieren solo una o más propiedades que tienen una definición en el modelo estándar (como resistencia a colisiones , resistencia a preimagen , resistencia a segunda preimagen , etc.) a menudo pueden demostrarse como seguros en el estándar. modelo (por ejemplo, el criptosistema Cramer-Shoup ).
Los oráculos aleatorios se han considerado durante mucho tiempo en la teoría de la complejidad computacional , [4] y se ha demostrado que muchos esquemas son seguros en el modelo de oráculo aleatorio, por ejemplo, el relleno de cifrado asimétrico óptimo , RSA-FDH y PSS . En 1986, Amos Fiat y Adi Shamir [5] mostraron una aplicación importante de los oráculos aleatorios: la eliminación de la interacción de los protocolos para la creación de firmas.
En 1989, Russell Impagliazzo y Steven Rudich [6] demostraron la limitación de los oráculos aleatorios, es decir, que su existencia por sí sola no es suficiente para el intercambio de claves secretas.
En 1993, Mihir Bellare y Phillip Rogaway [2] fueron los primeros en defender su uso en construcciones criptográficas. En su definición, el oráculo aleatorio produce una cadena de bits de longitud infinita que puede truncarse a la longitud deseada.
Cuando se utiliza un oráculo aleatorio dentro de una prueba de seguridad, se pone a disposición de todos los jugadores, incluido el adversario o adversarios.
Un solo oráculo puede tratarse como múltiples oráculos anteponiendo una cadena de bits fija al comienzo de cada consulta (por ejemplo, las consultas formateadas como "1|x" o "0|x" pueden considerarse como llamadas a dos oráculos separados). oráculos, de manera similar "00|x", "01|x", "10|x" y "11|x" se pueden usar para representar llamadas a cuatro oráculos aleatorios separados). Esta práctica suele denominarse separación de dominios . La clonación de Oracle es la reutilización del oráculo aleatorio una vez construido dentro de la misma prueba (esto en la práctica corresponde a los usos múltiples del mismo hash criptográfico dentro de un algoritmo para diferentes propósitos). [7] La clonación de Oracle con una separación inadecuada de dominios rompe las pruebas de seguridad y puede conducir a ataques exitosos. [8]
Según la tesis de Church-Turing , ninguna función computable mediante un algoritmo finito puede implementar un verdadero oráculo aleatorio (que por definición requiere una descripción infinita porque tiene infinitas entradas posibles y sus salidas son todas independientes entre sí y necesitan ser especificado individualmente por cualquier descripción).
De hecho, se conocen ciertos esquemas artificiales de firma y cifrado que han demostrado ser seguros en el modelo de oráculo aleatorio, pero que son trivialmente inseguros cuando se sustituye el oráculo aleatorio por cualquier función real. [9] [10] No obstante, para cualquier protocolo más natural, una prueba de seguridad en el modelo de oráculo aleatorio proporciona una evidencia muy sólida de la seguridad práctica del protocolo. [11]
En general, si se demuestra que un protocolo es seguro, los ataques a ese protocolo deben estar fuera de lo que se demostró o romper una de las suposiciones de la prueba; por ejemplo, si la prueba se basa en la dureza de la factorización de enteros , para romper esta suposición se debe descubrir un algoritmo rápido de factorización de enteros. En cambio, para romper la suposición aleatoria del oráculo, uno debe descubrir alguna propiedad desconocida e indeseable de la función hash real; para buenas funciones hash en las que tales propiedades se consideran poco probables, el protocolo considerado puede considerarse seguro.
Aunque el teorema de Baker-Gill-Solovay [12] demostró que existe un oráculo A tal que P A = NPA , el trabajo posterior de Bennett y Gill, [13] demostró que para un oráculo aleatorio B (una función de {0, 1} n a {0,1} de modo que cada elemento de entrada se asigne a cada uno de 0 o 1 con probabilidad 1/2, independientemente del mapeo de todas las demás entradas), P B ⊊ NP B con probabilidad 1. Separaciones similares, como así como el hecho de que los oráculos aleatorios separan clases con probabilidad 0 o 1 (como consecuencia de la ley cero-uno de Kolmogorov ), llevó a la creación de la Hipótesis del Oráculo Aleatorio , de que dos clases de complejidad "aceptables" C 1 y C 2 son iguales si y sólo si son iguales (con probabilidad 1) bajo un oráculo aleatorio (la aceptabilidad de una clase de complejidad se define en BG81 [13] ). Más tarde se demostró que esta hipótesis era falsa, ya que se demostró que las dos clases de complejidad aceptables IP y PSPACE eran iguales [14] a pesar de IP A ⊊ PSPACE A para un oráculo aleatorio A con probabilidad 1. [15]
Un cifrado ideal es un oráculo de permutación aleatoria que se utiliza para modelar un cifrado de bloque idealizado. Una permutación aleatoria descifra cada bloque de texto cifrado en uno y sólo un bloque de texto sin formato y viceversa, por lo que existe una correspondencia uno a uno . Algunas pruebas criptográficas ponen a disposición de todos los jugadores no sólo la permutación "adelante", sino también la permutación "inversa".
Trabajos recientes demostraron que se puede construir un cifrado ideal a partir de un oráculo aleatorio utilizando redes Feistel de 10 rondas [16] o incluso de 8 rondas [17] .
Una permutación ideal es un objeto idealizado que a veces se utiliza en criptografía para modelar el comportamiento de una permutación cuyas salidas son indistinguibles de las de una permutación aleatoria. En el modelo de permutación ideal, se otorga un acceso oráculo adicional a la permutación ideal y su inversa. El modelo de permutación ideal puede verse como un caso especial del modelo de cifrado ideal donde se da acceso a una sola permutación, en lugar de a una familia de permutaciones como en el caso del modelo de cifrado ideal.
La criptografía poscuántica estudia los ataques cuánticos a los esquemas criptográficos clásicos. Como un oráculo aleatorio es una abstracción de una función hash , tiene sentido suponer que un atacante cuántico puede acceder al oráculo aleatorio en superposición cuántica . [18] Muchas de las pruebas de seguridad clásicas fallan en ese modelo de oráculo aleatorio cuántico y necesitan ser revisadas.
{{cite conference}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )