En criptografía , un oráculo aleatorio es una función hash idealizada que, para cada nueva solicitud, produce una respuesta aleatoria, distribuida uniformemente en el rango de valores, con la condición: si la misma solicitud llega dos veces, la respuesta debe ser la misma. En otras palabras, un oráculo aleatorio es una función matemática , elegida al azar, que mapea cada consulta posible en una respuesta aleatoria fija de un área de respuesta previamente preparada.
Los oráculos aleatorios como abstracción matemática se utilizaron por primera vez en pruebas criptográficas rigurosas en una publicación de 1993 de Mihir Bellare y Philip Rogaway . Se utilizan comúnmente en casos en los que la prueba no se puede realizar utilizando suposiciones más débiles sobre la función hash criptográfica . Un sistema que ha demostrado ser 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 ser seguro en el modelo de criptografía estándar .
Un oráculo aleatorio es muy poderoso porque tiene tres propiedades: determinismo , eficiencia y asegurar una distribución uniforme de los valores resultantes [1] .
Los oráculos aleatorios se usan comúnmente como un reemplazo idealizado para las funciones hash criptográficas en esquemas donde se necesitan suposiciones sólidas sobre la aleatoriedad de la salida hash [1] . Tal prueba generalmente muestra que el sistema o protocolo es seguro, mostrando que el atacante debe requerir un comportamiento imposible del oráculo, o debe resolver algún problema matemático que se considera difícil de resolver. No todos los usos de las funciones hash criptográficas requieren oráculos aleatorios [2] : los esquemas que requieren solo una o unas pocas propiedades definidas en el modelo estándar (como la resistencia a la colisión , la resistencia a la preimagen , la resistencia a la segunda preimagen , etc.), a menudo se puede demostrar que ser seguro en el modelo estándar (por ejemplo , el criptosistema de Cramer-Shope ).
Los oráculos aleatorios se han considerado durante mucho tiempo en la teoría de la complejidad computacional , y se ha demostrado que muchos esquemas son seguros en el modelo de oráculo aleatorio, como el cifrado asimétrico óptimo , RSA-FDH [3] y el esquema de firma probabilística . En 1986, Amos Fiat y Adi Shamir [4] mostraron la principal aplicación de los oráculos aleatorios: la eliminación de la interacción de los protocolos para crear firmas.
En 1989, Russell Impalazzo y Steven Rudich [5] demostraron una limitación de los oráculos aleatorios, a saber, que su sola existencia no es suficiente para intercambiar una clave secreta .
En 1993, Mihir Bellare y Philippe Rogaway [6] fueron los primeros en abogar por su uso en construcciones criptográficas. Por su definición, un oráculo aleatorio crea una cadena de bits de longitud infinita que se puede truncar a la longitud deseada.
Cuando se usa un oráculo aleatorio como prueba de seguridad, está disponible para todos los jugadores, incluido el oponente u oponentes. Un oráculo se puede considerar como varios oráculos, anteponiendo una cadena de bits fija al comienzo de cada solicitud (por ejemplo, las solicitudes con formato "1| x " o "0| x " se pueden considerar como llamadas a dos números aleatorios separados ). Oráculos, similar a "00 | x ", "01 | x ", "10 | x " y "11 | x " se puede usar para representar llamadas a cuatro oráculos aleatorios separados).
Un oráculo aleatorio es una poderosa función determinista hipotética que calcula de manera eficiente variables aleatorias distribuidas uniformemente . El modelo de un oráculo aleatorio asume la existencia no solo de un oráculo aleatorio, sino también de un agente especial: un imitador . Se supone que el imitador puede imitar cualquier oráculo al azar (incluso un atacante). Por lo tanto, si alguien quiere aplicar un oráculo aleatorio G a un número a , automáticamente enviará una solicitud al simulador a un oráculo aleatorio y obtendrá el resultado G(a) de él . El simulador siempre ejecuta honestamente cualquier solicitud y siempre devuelve su resultado.
Gracias a esta regla, el simulador puede imitar con precisión el comportamiento de un oráculo aleatorio. Deje que el simulador mantenga una lista G para el oráculo G que contiene pares (a, G(a)) donde se almacenan las consultas anteriores a . La simulación es simple: después de recibir la consulta a , el simulador verifica si está almacenada en la lista y, de ser así, devuelve el valor G(a) (el resultado determinista de la consulta), de lo contrario, el simulador extrae un nuevo valor G( a) de la población general de números uniformemente distribuidos , envía una respuesta y completa el par dado (a, G(a)) en una lista ordenada que toma log N unidades de tiempo para buscar (debido a esta característica, el oráculo aleatorio es eficiente).
Por lo tanto, el oráculo aleatorio es exactamente imitado por el algoritmo polinomialmente acotado [7] .
Se conocen algunos esquemas de encriptación y firma artificial que han demostrado ser seguros en el modelo de oráculo aleatorio, pero son trivialmente inseguros cuando cualquier función real reemplaza al oráculo aleatorio. [8] Sin embargo, para cualquier protocolo más natural, la prueba de seguridad en el modelo de oráculo aleatorio proporciona una evidencia muy sólida de la seguridad práctica del protocolo. [9]
En general, si se demuestra que un protocolo es seguro, los ataques a ese protocolo deben ir más allá de lo que se ha probado o violar una de las suposiciones de la prueba; por ejemplo, si la prueba se basa en la complejidad de la factorización de enteros , para romper esta suposición se debe encontrar un algoritmo rápido de factorización de enteros . En cambio, para romper la suposición aleatoria del oráculo, se debe descubrir alguna propiedad desconocida e indeseable de la función hash real ; para buenas funciones hash , donde tales propiedades se consideran poco probables, el protocolo en cuestión puede considerarse seguro. [diez]
Aunque el teorema de Baker-Gill-Solovey [11] [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 n a {0,1} para que cada elemento de entrada se asigne a cada uno de 0 o 1 con probabilidad 1/2, independientemente de asignar todas las demás entradas), P B ⊊ NP B con probabilidad 1. Divisiones similares, y también el hecho de que los oráculos aleatorios separan clases con una probabilidad de 0 o 1 (como consecuencia de la ley cero-uno de Kolmogorov ), lo que 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 solo si son iguales (con probabilidad 1) bajo un oráculo aleatorio (la aceptabilidad de la clase de complejidad se define en BG81 [13] Posteriormente se demostró que esta conjetura era falsa, ya que las dos clases de complejidad aceptables IP y PSPACE se demostró que eran iguales a pesar de que IP A ⊊ PSPACE A para un oráculo aleatorio A con probabilidad 1.
Un cifrado ideal es un oráculo de permutación aleatoria que se utiliza para modelar un cifrado de bloque idealizado [14] .
Una permutación arbitraria descifra cada bloque de texto cifrado en uno y solo un bloque de texto sin formato y viceversa, por lo que existe una correspondencia uno a uno. Algunas pruebas criptográficas no solo ponen a disposición de todos los jugadores una permutación "directa", sino también una permutación "inversa".
Un trabajo reciente ha demostrado que se puede construir un cifrado ideal a partir de un oráculo aleatorio utilizando redes de Feistel de 10 rondas [15] o incluso de 8 rondas [16] .
Canetti, Goldreich y Halevi expresaron una actitud negativa hacia las pruebas basadas en el modelo aleatorio del oráculo [17] . Demostraron que existen esquemas de encriptación y firma digital que son probablemente seguros dentro del marco del modelo aleatorio de Oracle, pero vulnerables a la implementación en aplicaciones reales. Su idea principal era inventar malas firmas digitales o esquemas de encriptación . Bajo condiciones normales, estos esquemas funcionan bien, pero bajo ciertas condiciones (principalmente una violación de la aleatoriedad) se vuelven malos. Sin embargo, los tres autores llegaron a conclusiones diferentes con respecto a la utilidad del modelo de oráculo aleatorio.
Canetti cree que el modelo de oráculo aleatorio representa una abstracción desafortunada y reduce el valor del método de "reducción de contradicción". Sugirió que la investigación científica debería dirigirse a la búsqueda de propiedades útiles específicas del modelo del oráculo aleatorio [18] .
Goldreich cree que el problema radica en lo incompleto del modelo y recomienda que no se incluyan pruebas que utilicen este método. Sin embargo, él cree que el modelo de oráculo aleatorio tiene algún valor en las pruebas de seguridad de los criptosistemas [18] .
Halevi cree que los éxitos actuales del método de reducción a una contradicción son accidentales: “No hay razón para afirmar que todos los esquemas existentes, cuya estabilidad ha sido probada utilizando el modelo del oráculo aleatorio, son de hecho estables” [18] .