Hispanopedia Wiki
Articulo de referencia

oráculo aleatorio

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 uniformeme...

Hispanopedia WikiContenido en espanolLectura gratuita

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 una consulta se repite, responde de la misma manera cada vez que se envía.

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 a cada consulta posible 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, donde 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 demostró que eran distintas con respecto a un oráculo aleatorio casi con seguridad . [ 1 ] Se incorporaron a 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 suelen utilizar cuando la prueba no puede llevarse a cabo utilizando supuestos 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 , lo que lo diferencia de ser seguro en el modelo estándar de criptografía .

Aplicaciones

Los oráculos aleatorios se utilizan habitualmente como un sustituto idealizado de las funciones hash criptográficas en esquemas donde se requieren fuertes supuestos de aleatoriedad en la salida de la función hash. Dicha prueba suele demostrar que un sistema o protocolo es seguro al mostrar que un atacante debe exigir un comportamiento imposible del oráculo o resolver algún problema matemático considerado difícil para romperlo. Sin embargo, solo prueba dichas propiedades en el modelo de oráculo aleatorio, asegurando que no existan fallos de diseño importantes. En general, no es cierto que dicha prueba implique las mismas propiedades en el modelo estándar. Aun así, una prueba en el modelo de oráculo aleatorio 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 preimágenes , resistencia a segundas preimágenes , etc.) a menudo pueden demostrarse 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 Asymmetric 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 ] utilizaron oráculos aleatorios para demostrar una separación entre funciones unidireccionales e intercambio de claves secretas, al presentar un oráculo respecto del cual existen las funciones unidireccionales pero no el intercambio de claves secretas , y por lo tanto, tampoco el cifrado de clave pública . Sus resultados muestran que no existe una construcción de caja negra del cifrado de clave pública a partir de funciones unidireccionales, lo que sugiere que las funciones unidireccionales constituyen una suposición más débil que el cifrado de clave pública.

En 1993, Mihir Bellare y Phillip Rogaway [ 2 ] fueron los primeros en abogar por 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, este se pone a disposición de todos los jugadores, incluido el adversario o los adversarios.

Separación de dominios

Un único oráculo puede tratarse como múltiples oráculos anteponiendo una cadena de bits fija al inicio de cada consulta (por ejemplo, las consultas formateadas como "1||x" o "0||x" pueden considerarse llamadas a dos oráculos aleatorios separados; de forma similar, "00||x", "01||x", "10||x" y "11||x" pueden usarse para representar llamadas a cuatro oráculos aleatorios separados). Esta práctica se suele denominar separación de dominios . La clonación de oráculos consiste en la reutilización del oráculo aleatorio construido una vez dentro de la misma prueba (en la práctica, esto 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 inadecuada rompe las pruebas de seguridad y puede conducir a ataques exitosos. [ 8 ]

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 necesitan ser especificadas individualmente por cualquier descripción).

De hecho, se conocen ciertos esquemas de firma y cifrado artificiales que han demostrado ser seguros en el modelo de oráculo aleatorio, pero que resultan 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 la seguridad de un protocolo, los ataques a dicho protocolo deben estar fuera de lo demostrado o romper alguno de los supuestos de la prueba; por ejemplo, si la prueba se basa en la dificultad de la factorización de enteros , para romper este supuesto se debe descubrir un algoritmo rápido de factorización de enteros. En cambio, para romper el supuesto del oráculo aleatorio, se debe descubrir alguna propiedad desconocida e indeseable de la función hash; para buenas funciones hash en las que se considera improbable que existan tales propiedades, el protocolo en cuestión puede considerarse seguro.

hipótesis del oráculo aleatorio

Aunque el teorema de Baker-Gill-Solovay [ 12 ] demostró que existe un oráculo A tal que P A = NP A , trabajos posteriores de Bennett y Gill [ 13 ] demostraron 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 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 , que establece 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 ] ). Posteriormente 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 que IP A ⊊ PSPACE A para un oráculo aleatorio A con probabilidad 1. [ 15 ]

cifrado ideal

Un cifrado ideal es un oráculo de permutación aleatoria que se utiliza para modelar un cifrado de bloques idealizado. Una permutación aleatoria descifra cada bloque de texto cifrado en un único bloque de texto plano y viceversa, por lo que existe una correspondencia uno a uno . Algunas pruebas criptográficas ponen a disposición de todos los participantes no solo la permutación "directa", 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 ] .

permutación ideal

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 acceso adicional a la permutación ideal y a su inversa. Este modelo puede considerarse un caso especial del modelo de cifrado ideal, donde el acceso se otorga únicamente a una sola permutación, en lugar de a una familia de permutaciones como en el caso del modelo de cifrado ideal.

Oráculos aleatorios accesibles cuánticamente

La criptografía postcuántica estudia los ataques cuánticos a los esquemas criptográficos clásicos. Dado que un oráculo aleatorio es una abstracción de una función hash , es lógico 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.

Véase también

Referencias

  1. ↑ Bennett, Charles; Gill, John (1981). "Relativo a un oráculo aleatorio A, N^A  != NP^A  != coNP^A con probabilidad 1" . SIAM Journal on Computing : 96–113 . doi : 10.1137/0210008 .
  2. 1 2 Bellare, Mihir ; Rogaway, Phillip (1993). "Los oráculos aleatorios son prácticos: Un paradigma para el diseño de protocolos eficientes". Actas de la 1.ª conferencia ACM sobre seguridad informática y de comunicaciones - CCS '93 . págs. 62–73 . doi : 10.1145/168588.168596 . ISBN  0-89791-629-8. S2CID 3047274 . 
  3. ↑ Katz, Jonathan; Lindell, Yehuda (2015). Introducción a la criptografía moderna (2.ª ed.). Boca Raton: Chapman & Hall/CRC. págs. 174–175 , 179–181 . ISBN   978-1-4665-7027-6.
  4. ↑ Bennett, Charles H. ; Gill, John (1981), "Relativo a un oráculo aleatorio A, P^A != NP^A != co-NP^A con probabilidad 1", SIAM Journal on Computing , 10 (1): 96– 113, doi : 10.1137/0210008 , ISSN 1095-7111   
  5. ↑ Fiat, Amos; Shamir, Adi (1986). "Cómo demostrar tu identidad: soluciones prácticas a los problemas de identificación y firma". CRYPTO . págs. 186–194 . 
  6. ↑ Impagliazzo, Russell; Rudich, Steven (1989). "Límites de las consecuencias demostrables de las permutaciones unidireccionales". STOC : 44–61 .
  7. ↑ Bellare, Davis y Günther 2020 , p. 3.
  8. ↑ Bellare, Davis y Günther 2020 , p. 4.
  9. ↑ Ran Canetti, Oded Goldreich y Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 (PS y PDF) .
  10. ↑ Craig Gentry y Zulfikar Ramzan. "Eliminación de oráculos de permutación aleatoria en el cifrado Even-Mansour" . 2004.
  11. ↑ Koblitz, Neal; Menezes, Alfred J. (2015). "El modelo del oráculo aleatorio: una retrospectiva de veinte años" (PDF) . Otra mirada . Archivado del original (PDF) el 2 de abril de 2015. Recuperado el 6 de marzo de 2015 .
  12. ↑ Baker, Theodore; Gill, John; Solovay, Robert (1975). "Relativizaciones de la pregunta NP P =?". SIAM J. Comput . 4 (4). SIAM: 431– 442. doi : 10.1137/0204037 .
  13. 1 2 Bennett, Charles; Gill, John (1981). "Relativo a un oráculo aleatorio A, P != NP != co-NP con probabilidad 1". SIAM J. Comput . 10 (1). SIAM: 96– 113. doi : 10.1137/0210008 .  
  14. ↑ Shamir, Adi (octubre de 1992). "IP = PSPACE" . Journal of the ACM . 39 (4): 869–877 . doi : 10.1145/146585.146609 . S2CID 315182 . 
  15. ↑ Chang, Richard; Chor, Benny ; Goldreich, Oded; Hartmanis, Juris; Hastad, Johan; Ranjan, Desh; Rohatgi, Pankaj (agosto de 1994). "La hipótesis del oráculo aleatorio es falsa" . Journal of Computer and System Sciences . 49 (1): 24–39 . doi : 10.1016/S0022-0000(05)80084-4 . ISSN 0022-0000 . 
  16. ↑ Dachman-Soled, Dana; Katz, Jonathan; Thiruvengadam, Aishwarya (2016). "10-Round Feistel is Indifferentiable from an Ideal Cipher". EUROCRYPT 2016. Springer. pp. 649–678 . doi : 10.1007/978-3-662-49896-5_23 . 
  17. ↑ Dai, Yuanxi; Steinberger, John (2016). "Indiferenciabilidad de redes Feistel de 8 rondas". CRYPTO 2016. Springer.
  18. ↑ Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner y Mark Zhandry (2011). «Oráculos aleatorios en un mundo cuántico». Avances en criptología – ASIACRYPT 2011. Notas de clase en ciencias de la computación. Vol. 7073. Springer. págs. 41–69 . arXiv : 1008.0931 . doi : 10.1007/978-3-642-25385-0_3 . ISBN   978-3-642-25384-3.{{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace )

Fuentes

  • Bellare, Mihir; Davis, Hannah; Günther, Felix (2020). «Separa tus dominios: KEMs PQC del NIST, clonación de oráculos e indiferenciabilidad de solo lectura» . Avances en criptología – EUROCRYPT 2020. Notas de clase en informática. Vol.  12106. Cham: Springer International Publishing. pp. 3–32 . doi : 10.1007/978-3-030-45724-2_1 . hdl : 20.500.11850/392433 . ISBN  978-3-030-45723-5. ISSN 0302-9743 . S2CID 214642193 .