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 (realmente) aleatoria elegida de manera uniforme 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 otro modo, 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 la que se usaron 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 demostró que eran distintas en relación con un 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 introdujo como un modelo criptográfico formal para ser utilizado en pruebas de reducción. [2]
Se utilizan normalmente cuando no se puede llevar a cabo la prueba utilizando suposiciones más débiles sobre la función hash criptográfica . Un sistema que se demuestra seguro cuando cada función hash se reemplaza por un oráculo aleatorio se describe como seguro en el modelo de oráculo aleatorio , a diferencia de 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 suposiciones de aleatoriedad fuertes de la salida de la función hash. Este tipo de 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 cree difícil de resolver para poder romperlo. Sin embargo, solo prueba tales propiedades en el modelo de oráculo aleatorio, asegurándose de que no haya fallas de diseño importantes. En general, no es cierto que una prueba de este tipo implique las mismas propiedades en el modelo estándar. Aún así, una prueba en el modelo de oráculo aleatorio se considera mejor que ninguna prueba de seguridad formal en absoluto. [3]
No todos los usos de funciones hash criptográficas requieren oráculos aleatorios: los esquemas que requieren solo una o más propiedades que tengan una definición en el modelo estándar (como resistencia a colisiones , resistencia a preimagen , resistencia a segunda preimagen , etc.) a menudo pueden probarse seguros en el modelo estándar (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, Optimal Asymmetry Encryption Padding , 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 recomendar 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 hasta la longitud deseada.
Cuando se utiliza un oráculo aleatorio dentro de una prueba de seguridad, este queda disponible para todos los jugadores, incluido el adversario o los adversarios.
Un único oráculo puede ser tratado 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 aleatorios separados, de manera similar, "00|x", "01|x", "10|x" y "11|x" pueden usarse para representar llamadas a cuatro oráculos aleatorios separados). Esta práctica generalmente se denomina separación de dominios . La clonación de oráculos es la reutilización del oráculo aleatorio una vez construido dentro de la misma prueba (esto en la práctica corresponde a los múltiples usos del mismo hash criptográfico dentro de un algoritmo para diferentes propósitos). [7] La clonación de oráculos con una separación de dominios incorrecta rompe las pruebas de seguridad y puede conducir a ataques exitosos. [8]
Según la tesis de Church-Turing , ninguna función computable por 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 especificadas 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 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 números enteros , para romper esta suposición se debe descubrir un algoritmo rápido de factorización de números enteros. En cambio, para romper la suposición del oráculo aleatorio, se debe descubrir alguna propiedad desconocida e indeseable de la función hash real; para las buenas funciones hash donde se cree que tales propiedades son poco probables, el protocolo considerado puede considerarse seguro.
Aunque el teorema de Baker–Gill–Solovay [12] mostró que existe un oráculo A tal que P A = NP A , el trabajo posterior de Bennett y Gill, [13] mostró que para un oráculo aleatorio B (una función de {0,1} n a {0,1} tal que cada elemento de entrada se asigna a cada uno de 0 o 1 con probabilidad 1/2, independientemente de la asignación de todas las demás entradas), P B ⊊ NP B con probabilidad 1. Separaciones similares, así como el hecho de que los oráculos aleatorios separan las clases con probabilidad 0 o 1 (como consecuencia de la ley cero-uno de Kolmogorov ), llevaron 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 solo si son iguales (con probabilidad 1) bajo un oráculo aleatorio (la aceptabilidad de una clase de complejidad se define en BG81 [13] ). Esta hipótesis se demostró posteriormente que era falsa, ya que se demostró que las dos clases de complejidad aceptables IP y PSPACE eran iguales [14] a pesar de que 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 un único bloque de texto simple y viceversa, por lo que existe una correspondencia uno a uno . Algunas pruebas criptográficas no solo hacen que la permutación "directa" esté disponible para todos los jugadores, sino también la permutación "inversa".
Trabajos recientes han demostrado que se puede construir un cifrado ideal a partir de un oráculo aleatorio utilizando redes de 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 cuyos resultados son indistinguibles de los de una permutación aleatoria. En el modelo de permutación ideal, se otorga un acceso de oráculo adicional a la permutación ideal y a su inversa. El modelo de permutación ideal puede considerarse un caso especial del modelo de cifrado ideal en el que se otorga acceso a una única 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}}: CS1 maint: varios nombres: lista de autores ( enlace )