Familia de funciones pseudoaleatorias

En criptografía , una familia de funciones pseudoaleatorias , abreviada como PRF , es un conjunto de funciones computables eficientemente 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 son completamente aleatorios). Las funciones pseudoaleatorias son herramientas fundamentales en la construcción de primitivas criptográficas , especialmente en esquemas de cifrado seguros .

Las funciones pseudoaleatorias no deben confundirse con los generadores pseudoaleatorios (GPR). La garantía de un GPR es que una única salida parece aleatoria si la entrada se eligió al azar. Por otro lado, la garantía de una función pseudoaleatoria es que todas sus salidas parecen aleatorias, independientemente de cómo se hayan elegido las entradas correspondientes, siempre que la función se haya extraído al azar de la familia de funciones pseudoaleatorias.

Se puede construir una familia de funciones pseudoaleatorias a partir de cualquier generador pseudoaleatorio, utilizando, por ejemplo, la construcción "GGM" propuesta por Goldreich , Goldwasser y Micali . ^{[ 1 ]} Si bien en la práctica se utilizan cifrados de bloques 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 bloques como AES están definidos solo para un número limitado de tamaños de entrada y clave. ^{[ 2 ]}

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

En esencia, una función verdaderamente aleatoria se compone simplemente de una tabla de búsqueda con entradas aleatorias distribuidas uniformemente. Sin embargo, en la práctica, a una función pseudoaleatoria se le proporciona una cadena de entrada del dominio y una semilla aleatoria oculta , y se ejecuta varias veces con la misma cadena y semilla, devolviendo siempre 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 pseudoaleatoria (FPA) es buena si su comportamiento es indistinguible del de una función verdaderamente aleatoria. Por lo tanto, dado un resultado proveniente de una función verdaderamente aleatoria o de una FPA, no debería existir un método eficiente para determinar correctamente si dicho resultado fue producido por la función verdaderamente aleatoria o por la FPA.

Las funciones pseudoaleatorias toman entradas${\displaystyle x\in \{0,1\}^{*}}$, dónde${\displaystyle {}^{*}}$es la estrella de Kleene . Tanto el tamaño de entrada${\displaystyle I=|x|}$y tamaño de salida${\displaystyle \lambda }$depende únicamente del tamaño del índice${\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${\displaystyle f_{s}(x)}$dado cualquier${\displaystyle s}$y${\displaystyle x}$.
• Dejar${\displaystyle F_{n}}$sea ​​la distribución de funciones${\displaystyle f_{s}}$dónde${\displaystyle s}$está distribuido uniformemente sobre${\displaystyle \{0,1\}^{n}}$y dejar${\displaystyle RF_{n}}$denotamos la distribución uniforme sobre el conjunto de todas las funciones de${\displaystyle \{0,1\}^{I(n)}}$a${\displaystyle \{0,1\}^{\lambda (n)}}$Entonces necesitamos${\displaystyle F_{n}}$y${\displaystyle RF_{n}}$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 de cualquiera de las${\displaystyle F_{n}}$o${\displaystyle RF_{n}}$, la ventaja de que pueda distinguir qué tipo de oráculo se le da es insignificante en${\displaystyle n}$. ^{[ 3 ]}

En una función pseudoaleatoria ciega , abreviada OPRF, la información se oculta a dos partes involucradas en una PRF. ^{[ 4 ]} Es decir, si Alice aplica un hash criptográfico a su valor secreto, oculta 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 la salida final, Bob no puede ver ni 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 el secreto de Bob. ^{[ 5 ]} Esto permite que las transacciones de información criptográfica sensible sean seguras incluso entre partes no confiables.

Un OPRF se utiliza en algunas implementaciones de acuerdo de clave autenticado por contraseña . ^{[ 5 ]}

Se utiliza un OPRF en la funcionalidad del Monitor de contraseñas en Microsoft Edge . ^{[ 6 ]}

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 de hash haya 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 de mensajes elegidos.
3. Distribuir números de identificación infalsificables , que pueden ser verificados localmente por estaciones que contienen una pequeña cantidad de almacenamiento.
4. Construcción de sistemas de identificación amigo-enemigo .

• permutación pseudoaleatoria

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