Familia de funciones pseudoaleatorias

Colección de funciones computables de manera eficiente que emulan un oráculo aleatorio

En criptografía , una familia de funciones pseudoaleatorias , abreviada como 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 aleatoriamente de la familia PRF y un oráculo aleatorio (una función cuyos resultados 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 una PRF es que todas sus salidas parecen aleatorias, independientemente de cómo se eligieron las entradas correspondientes, siempre que la función se haya extraído al azar de la familia PRF.

Se puede construir una familia de funciones pseudoaleatorias a partir de cualquier generador pseudoaleatorio, utilizando, 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 donde 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 tamaños de clave y de entrada. ^[2]

Motivaciones a partir de funciones aleatorias

Una PRF es una función determinista eficiente (es decir, computable en tiempo polinomial) que asigna dos conjuntos distintos (dominio y rango) y parece una función verdaderamente aleatoria.

En esencia, una función verdaderamente aleatoria estaría compuesta simplemente por una tabla de búsqueda llena de entradas aleatorias distribuidas uniformemente. Sin embargo, en la práctica, a una función PRF se le da 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, y siempre devuelve 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.

Se considera que una función de repetición de pulsos es buena si su comportamiento es indistinguible del de una función verdaderamente aleatoria. Por lo tanto, dada una salida de la función verdaderamente aleatoria o de una función de repetición de pulsos, no debería haber ningún método eficiente para determinar correctamente si la salida fue producida por la función verdaderamente aleatoria o por la función de repetición de pulsos.

Definición formal

Las funciones pseudoaleatorias toman entradas . Tanto el tamaño de entrada como el de salida dependen únicamente del tamaño del índice . ${\displaystyle x\in \{0,1\}^{*}}$ ${\displaystyle I=|x|}$ ${\displaystyle \lambda }$ ${\displaystyle n:=|s|}$

Una familia de funciones,

${\displaystyle f_{s}:\left\{0,1\right\}^{I(n)}\rightarrow \left\{0,1\right\}^{\lambda (n)}}$

es pseudoaleatorio si se cumplen las siguientes condiciones:

• Existe un algoritmo de tiempo polinomial que calcula dados cualesquiera y . ${\displaystyle f_{s}(x)}$ ${\displaystyle s}$ ${\displaystyle x}$
• Sea la distribución de funciones donde se distribuye uniformemente sobre , y sea la distribución uniforme sobre el conjunto de todas las funciones desde hasta . Entonces requerimos que y sean 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 de o , la ventaja de que pueda distinguir qué tipo de oráculo se le da es insignificante en . ^[3] ${\displaystyle F_{n}}$ ${\displaystyle f_{s}}$ ${\displaystyle s}$ ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle RF_{n}}$ ${\displaystyle \{0,1\}^{I(n)}}$ ${\displaystyle \{0,1\}^{\lambda (n)}}$ ${\displaystyle F_{n}}$ ${\displaystyle RF_{n}}$ ${\displaystyle F_{n}}$ ${\displaystyle RF_{n}}$ ${\displaystyle n}$

Funciones pseudoaleatorias ajenas

En una función pseudoaleatoria inconsciente, abreviada como OPRF, la información se oculta a dos partes que están involucradas en una PRF. ^[4] Es decir, si Alice criptográficamente convierte su valor secreto en hash, criptográficamente ciega 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 ni el valor secreto de Alice ni el resultado final, y Alice no puede ver la entrada secreta de Bob, pero Alice ve el resultado final que es una PRF de las dos entradas: una PRF del secreto de Alice y el secreto de Bob. ^[5] Esto permite que las transacciones de información criptográfica sensible sean seguras incluso entre partes que no son de confianza.

Se utiliza una OPRF en algunas implementaciones de acuerdos de clave autenticados por contraseña . ^[5]

Se utiliza un OPRF en la función de Monitor de contraseñas en Microsoft Edge . ^[6]

Consulte el artículo principal sobre Funciones pseudoaleatorias ajenas .

Solicitud

Los PRF se pueden utilizar para: ^[7]

1. Hashing perfecto dinámico ; incluso si el adversario puede cambiar la distribución de claves dependiendo de los valores que la función hash ha asignado a las claves anteriores, el adversario no puede forzar colisiones.
2. Construir esquemas de autenticación deterministas y sin memoria ( basados ​​en códigos de autenticación de mensajes ) que sean demostrablemente seguros contra ataques a mensajes seleccionados.
3. Distribuir números de identificación infalsificables , que pueden ser verificados localmente por estaciones que contienen solo una pequeña cantidad de almacenamiento.
4. Construcción de sistemas de identificación amigo-enemigo .

Véase también

• Permutación pseudoaleatoria

Notas

1. 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
2. Lindell, Yehuda; Katz, Jonathan (2008). Introducción a la criptografía moderna . Chapman & Hall/CRC. pág. 88. ISBN 978-1-58488-551-1.
3. FoC de Goldreich, vol. 1, def. 3.6.4. Notas de pase, def. 96,2
4. 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.
5. Matthew Green. "Hablemos de PAKE". 2018.
6. Lauter, Kristin; Kannepalli, Sreekanth; Laine, Kim; Cruz Moreno, Radames (1 de enero de 2021). «Password Monitor: Safeguarding passwords in Microsoft Edge». Blog de investigación de Microsoft . Consultado el 1 de enero de 2021 .
7. Goldreich, O .; Goldwasser, S.; Micali , S. (1985). "Sobre las aplicaciones criptográficas de funciones aleatorias (resumen ampliado)". Avances en criptología . Apuntes de clase en informática. Vol. 196. pág. 276. doi :10.1007/3-540-39568-7_22. ISBN 978-3-540-15658-1.

Referencias

• Goldreich, Oded (2001). Fundamentos de criptografía: herramientas básicas . Cambridge: Cambridge University Press. ISBN 978-0-511-54689-1.
• Pass, Rafael, Un curso de criptografía (PDF) , consultado el 22 de diciembre de 2015