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 como abstracción matemática se utilizaron por primera vez en pruebas criptográficas rigurosas en la publicación de 1993 de Mihir Bellare y Phillip Rogaway (1993). [1] Por lo general, se utilizan cuando la prueba no puede llevarse a cabo utilizando supuestos más débiles sobre la función hash criptográfica . Un sistema que ha demostrado 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 , en lugar de seguro en el modelo estándar de criptografía .
Aplicaciones
Los oráculos aleatorios se utilizan normalmente como un reemplazo idealizado de las funciones hash criptográficas en esquemas en los que se necesitan supuestos de aleatoriedad sólidos 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 requerir un comportamiento imposible del oráculo, o resolver algún problema matemático que se cree difícil para romperlo. Sin embargo, solo demuestra estas 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 tal demostración 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. [2]
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 la segunda preimagen , etc.) a menudo se pueden probar 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 , [3] y muchos esquemas han demostrado ser seguros en el modelo de oráculo aleatorio, por ejemplo , el relleno de cifrado asimétrico óptimo , RSA-FDH y el esquema de firma probabilística . En 1986, Amos Fiat y Adi Shamir [4] mostraron una aplicación importante de 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 [5] mostraron 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 [1] 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 se puede truncar 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 al pre-pendiente una cadena de bits fija al comienzo de cada consulta (por ejemplo, las consultas formateadas como "1 | x" o "0 | x" se pueden considerar como llamadas a dos 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).
Limitaciones
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 deben ser especificado individualmente por cualquier descripción).
De hecho, se conocen ciertos esquemas de cifrado y firma artificial que han demostrado ser seguros en el modelo de oráculo aleatorio, pero que son trivialmente inseguros cuando se sustituye cualquier función real por el oráculo aleatorio. [6] [7] No obstante, para cualquier protocolo más natural, una prueba de seguridad en el modelo de oráculo aleatorio da una evidencia muy fuerte de la seguridad práctica del protocolo. [8]
En general, si se demuestra que un protocolo es seguro, los ataques a ese protocolo deben estar fuera de lo que se probó o romper una de las suposiciones en 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 del oráculo aleatorio, uno debe descubrir alguna propiedad desconocida e indeseable de la función hash real; para buenas funciones hash donde se cree que tales propiedades son poco probables, el protocolo considerado puede considerarse seguro.
Hipótesis de Oracle aleatoria
Aunque el teorema de Baker-Gill-Solovay [9] mostró que existe un oráculo A tal que P A = NP A , el trabajo posterior de Bennett y Gill, [10] mostró que para un oráculo aleatorio B (una función de {0, 1} na {0,1} tal que cada elemento de entrada se corresponda con cada uno de 0 o 1 con probabilidad 1/2, independientemente del mapa 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 , 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 [10] ). 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 [11] a pesar de IP A ⊊ PSPACE A para un oráculo aleatorio A con probabilidad 1. [12]
Cifrado ideal
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 solo un bloque de texto plano y viceversa, por lo que hay una correspondencia uno a uno . Algunas pruebas criptográficas hacen que no sólo 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 Feistel de 10 rondas [13] o incluso de 8 rondas [14] .
Oráculos aleatorios accesibles a Quantum
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 asumir que un atacante cuántico puede acceder al oráculo aleatorio en superposición cuántica . [15] Muchas de las pruebas de seguridad clásicas se rompen en ese modelo de oráculo aleatorio cuántico y necesitan ser revisadas.
Ver también
- Función de esponja
- Máquina de Oracle
- Temas de criptografía
Referencias
- ^ a b Bellare, Mihir ; Rogaway, Phillip (1993). "Los oráculos aleatorios son prácticos: un paradigma para diseñar protocolos eficientes" . Conferencia de ACM sobre seguridad informática y de comunicaciones : 62–73.
- ^ Katz, Jonathan; Lindell, Yehuda (2015). Introducción a la criptografía moderna (2 ed.). Boca Ratón: Chapman & Hall / CRC. págs. 174-175, 179-181. ISBN 978-1-4665-7027-6.
- ^ Bennett, Charles H .; Gill, John (1981), "Relative to a Random Oracle A, P ^ A! = NP ^ A! = Co-NP ^ A with Probability 1", SIAM Journal on Computing , 10 (1): 96-113, doi : 10.1137 / 0210008 , ISSN 1095-7111
- ^ Fiat, Amos; Shamir, Adi (1986). "Cómo demostrar su valía: soluciones prácticas para problemas de identificación y firma". CRYPTO . págs. 186-194.
- ^ Impagliazzo, Russell; Rudich, Steven (1989). "Límites de las consecuencias demostrables de las permutaciones unidireccionales". STOC : 44–61.
- ^ Ran Canetti, Oded Goldreich y Shai Halevi, La metodología de Oracle aleatoria revisada, STOC 1998, págs. 209-218 (PS y PDF) .
- ^ Craig Gentry y Zulfikar Ramzan. "Eliminación de oráculos de permutación aleatoria en el cifrado Even-Mansour" . 2004.
- ^ Koblitz, Neal; Menezes, Alfred J. (2015). "El modelo de Oracle al azar: una retrospectiva de veinte años" (PDF) . Otra mirada . Consultado el 6 de marzo de 2015 .
- ^ Baker, Theodore; Gill, John; Solovay, Robert (1975). "Relativizaciones de la pregunta P =? NP". SIAM J. Comput . SIAM. 4 (4): 431–442. doi : 10.1137 / 0204037 .
- ^ a b Bennett, Charles; Gill, John (1981). "Relativo a un oráculo aleatorio A, P! = NP! = Co-NP con probabilidad 1". SIAM J. Comput . SIAM. 10 (1): 96-113. doi : 10.1137 / 0210008 .
- ^ Shamir, Adi (octubre de 1992). "IP = PSPACE" . Revista de la ACM . 39 (4): 869–877. doi : 10.1145 / 146585.146609 . S2CID 315182 .
- ^ Chang, Richard; Oded Goldreich, Benny Chor; Hartmanis, Juris; Hastad, Johan; Ranjan, Desh; Rohatgi, Pankaj (agosto de 1994). "La hipótesis del oráculo aleatorio es falsa" . Revista de Ciencias de la Computación y Sistemas . 49 (1): 24–39. doi : 10.1016 / S0022-0000 (05) 80084-4 . ISSN 0022-0000 .
- ^ Dachman-Soled, Dana; Katz, Jonathan; Thiruvengadam, Aishwarya (2016). "Feistel de 10 rondas es indiferenciable de un cifrado ideal". EUROCRYPT 2016 . Saltador. págs. 649–678. doi : 10.1007 / 978-3-662-49896-5_23 .
- ^ Dai, Yuanxi; Steinberger, John (2016). "Indiferenciabilidad de las redes Feistel de 8 rondas". CRYPTO 2016 . Saltador.
- ^ Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner y Mark Zhandry (2011). Oráculos aleatorios en un mundo cuántico . Saltador. págs. 41–69. arXiv : 1008.0931 . doi : 10.1007 / 978-3-642-25385-0_3 .CS1 maint: varios nombres: lista de autores ( enlace )