En criptografía , una familia de funciones pseudoaleatorias , abreviada PRF , es una colección de funciones computables de manera eficiente que emulan un oráculo aleatorio de la siguiente manera: ningún algoritmo eficiente puede distinguir (con una ventaja significativa ) entre una función elegida al azar de la familia PRF y una oráculo aleatorio (una función cuyas salidas se fijan completamente al azar). Las funciones pseudoaleatorias son herramientas vitales en la construcción de primitivas criptográficas , especialmente esquemas de cifrado seguro .
Las funciones pseudoaleatorias no deben confundirse con los generadores pseudoaleatorios (PRG). La garantía de un PRG es que una única salida parece aleatoria si la entrada se eligió al azar. Por otro lado, la garantía de un PRF es que todas sus salidas parecen aleatorias, independientemente de cómo se eligieron las entradas correspondientes, siempre que la función se extraiga al azar de la familia PRF.
Se puede construir una familia de funciones pseudoaleatorias a partir de cualquier generador pseudoaleatorio, usando, por ejemplo, la construcción "GGM" dada por Goldreich , Goldwasser y Micali . [1] Si bien en la práctica, los cifrados de bloque se utilizan en la mayoría de los casos en los que se necesita una función pseudoaleatoria, en general, no constituyen una familia de funciones pseudoaleatorias, ya que los cifrados de bloque como AES se definen solo para un número limitado de entradas y claves. Tamaños. [2]
Motivaciones de funciones aleatorias
Un PRF es una función determinista eficiente (es decir, computable en tiempo polinomial) que mapea dos conjuntos distintos (dominio y rango) y parece una función verdaderamente aleatoria.
Esencialmente, una función verdaderamente aleatoria estaría compuesta por una tabla de búsqueda llena de entradas aleatorias distribuidas uniformemente. Sin embargo, en la práctica, un PRF recibe una cadena de entrada en el dominio y una semilla aleatoria oculta y se ejecuta varias veces con la misma cadena de entrada y semilla, siempre devolviendo el mismo valor. No obstante, dada una cadena de entrada arbitraria, la salida parece aleatoria si la semilla se toma de una distribución uniforme.
Un PRF se considera bueno si su comportamiento es indistinguible de una función verdaderamente aleatoria. Por lo tanto, dada una salida de la función verdaderamente aleatoria o de una PRF, no debería haber un método eficiente para determinar correctamente si la salida fue producida por la función verdaderamente aleatoria o la PRF.
Definicion formal
Una familia de funciones,
, dónde , y
es pseudoaleatorio si se cumplen las siguientes condiciones:
- Dado cualquier y tal que , siempre existe un algoritmo de tiempo polinomial para calcular .
- Dejar ser la distribución de funciones dónde se distribuye uniformemente sobre , y deja denotar la distribución uniforme sobre el conjunto de todas las funciones de a . Entonces requerimos y son computacionalmente indistinguibles, donde n es el parámetro de seguridad. Es decir, para cualquier adversario que pueda consultar el oráculo de una función muestreada desde o , la ventaja de que pueda distinguir qué tipo de oráculo se le otorga es insignificante. [3]
Funciones pseudoaleatorias ajenas
En una función pseudoaleatoria ajena, abreviada OPRF, la información se oculta a dos partes que están involucradas en un PRF. [4] Es decir, si Alice codifica criptográficamente su valor secreto, ciega criptográficamente el hash para producir el mensaje que envía a Bob, y Bob mezcla su valor secreto y le devuelve el resultado a Alice, quien lo desenmascara para obtener el resultado final. , Bob no puede ver el valor secreto de Alice ni la salida final, y Alice no puede ver la entrada secreta de Bob, pero Alice ve la salida final que es una PRF de las dos entradas: una PRF del secreto de Alice y la de Bob. secreto. [5] Esto permite que las transacciones de información criptográfica sensible sean seguras incluso entre partes que no son de confianza.
Un OPRF se utiliza en algunas implementaciones de acuerdos de claves autenticadas por contraseña . [5]
Un OPRF se usa en la funcionalidad de Monitor de contraseñas en Microsoft Edge . [6]
Solicitud
Los PRF se pueden utilizar para: [7]
- hash dinámico perfecto ; incluso si el adversario puede cambiar la distribución de claves en función de los valores que la función hash ha asignado a las claves anteriores, el adversario no puede forzar las colisiones.
- Construir esquemas de autenticación deterministas y sin memoria ( basados en códigos de autenticación de mensajes ) que sean demostrablemente seguros contra el ataque de mensajes seleccionados.
- Distribuir números de identificación que no se pueden falsificar , que pueden ser verificados localmente por estaciones que contienen solo una pequeña cantidad de almacenamiento.
- Construyendo sistemas de identificación de amigos o enemigos .
Ver también
Notas
- ^ Goldreich, Oded ; Goldwasser, Shafi ; Micali, Silvio (octubre de 1986). "Cómo construir funciones aleatorias" (PDF) . Revista de la ACM . 33 (4): 792–807. doi : 10.1145 / 6490.6503 . página web y preimpresión
- ^ Lindell, Yehuda; Katz, Jonathan (2008). Introducción a la criptografía moderna . Chapman y Hall / CRC. pag. 88. ISBN 978-1-58488-551-1.
- ^ FoC de Goldreich, vol. 1, def. 3.6.4. Notas de pase, def. 96,2
- ^ M. Bellare ; S. Keelveedhi; T. Ristenpart (agosto de 2013). Dupless: cifrado asistido por servidor para almacenamiento deduplicado (PDF) . Actas del 22º Simposio de Seguridad de USENIX. Washington, DC, EE.UU .: Asociación USENIX. págs. 1-16.
- ^ a b Matthew Green. "Hablemos de PAKE" . 2018.
- ^ Lauter, Kristin; Kannepalli, Sreekanth; Laine, Kim; Cruz Moreno, Radames (1 de enero de 2021). "Monitor de contraseña: protección de contraseñas en Microsoft Edge" . Blog de investigación de Microsoft . Consultado el 1 de enero de 2021 .
- ^ Goldreich, O .; Goldwasser, S .; Micali, S. (1985). "Sobre las aplicaciones criptográficas de funciones aleatorias (resumen extendido)". Avances en criptología . Apuntes de conferencias en informática. 196 . pag. 276. doi : 10.1007 / 3-540-39568-7_22 . ISBN 978-3-540-15658-1.
Referencias
- Goldreich, Oded (2001). Fundamentos de la criptografía: herramientas básicas . Cambridge: Cambridge University Press. ISBN 978-0-511-54689-1.
- Pass, Rafael, A Course in Cryptography (PDF) , consultado el 22 de diciembre de 2015