¿Cuáles de esas funciones son PRF?
Asumir que $F: \{0,1 \}^n \rightarrow \{0,1 \}^n$es PRF. Examine si las siguientes funciones son PRF:
$$ \begin{align} 1. \, F_1(k,x) &= F(k,x) \oplus x \\ 2. \, F_2(k,x) &= F\left(F(k,0^n), x\right) \\ 3. \, F_3(k,x) &= F\left(F(k,0^n), x\right)|| F(k,x) \end{align} $$
dónde $||$ denota concatenación.
Intento:
por $1.$ un distintivo estándar sería: $x_1 \oplus x_2 == y_1 \oplus y_2$, dónde $x_1, x_2$ son dos entradas y $y_1, y_2$son sus salidas respectivamente. Entonces$F_1$ no es un PRF.
por $2.$ Yo creo eso $F(k,0^n) = k'$ actúa como una llave, entonces $F_2(k',x) = F(k',x)$ debería seguir siendo un PRF.
por $3.$ Yo diría que la concatenación de dos PRF seguiría siendo un PRF, ya que combina dos salidas pseudoaleatorias juntas para producir $F_3$salida de.
¿Pueden verificar mis resultados?
Respuestas
Desafortunadamente, no tengo tiempo para entrar en todos los detalles, pero tal vez sea suficiente para llevarlo por el camino correcto.
1. Es un PRF.
Idea de prueba:
Supongamos que tenemos un distintivo $\mathcal{D}_{F_1}$ distintivo $F_1$de una función aleatoria con probabilidad no despreciable. Entonces podemos construir un distintivo$\mathcal{D}_F$ distintivo $F$ de una función aleatoria con probabilidad no despreciable.
$\mathcal{D}_F$ tiene acceso a un oráculo $f(\cdot)$ eso es bien $F(k, \cdot)$ o una función aleatoria $g(\cdot)$.
$\mathcal{D}_F$ carreras $\mathcal{D}_{F_1}$y puede responder a sus consultas. Cuando$\mathcal{D}_{F_1}$ peticiones $x$, $\mathcal{D}_{F}$ consultas $f$ en $x$ y vuelve $f(x) \oplus x$ a $\mathcal{D}_{F_1}$. Esto simula$\mathcal{D}_{F_1}$consultas de: cuando $f$ es $F(k, \cdot)$ regresamos $F(k, x) \oplus x$, que es exactamente $F_1(k, x)$.
Cuando $\mathcal{D}_{F_1}$ está hecho, replicamos su salida: cuando dice que está hablando con $F_1$ (salida = 1), $\mathcal{D}_F$salidas iguales. Cuando dice que está hablando con una función aleatoria (salida = 0),$\mathcal{D}_F$ salidas iguales.
Ahora tendría que demostrar que la ventaja: $|\Pr[\mathcal{D}_F^{F(k, \cdot)}(1^n)=1] - \Pr[\mathcal{D}_F^{g(\cdot)}(1^n) = 1]|$ de $\mathcal{D}_F$ no es despreciable, utilizando el supuesto de que la ventaja de $\mathcal{D}_{F_1}$ es nada despreciable.
Esta última parte suele ser la más difícil, donde pueden surgir errores silenciosamente, así que tenga cuidado con saltarse pasos o hacer suposiciones no válidas.
2.
Es un PRF.
Intuitivamente, la pregunta de si se trata de un PRF parece reducirse a si un adversario puede predecir $F(k, 0^n)$. Sin embargo, una función en la que esto es posible para muchos$k$ no es un PRF.
3.
No es un PRF.
Podemos construir un diferenciador $\mathcal{D}$ con una ventaja nada despreciable. $\mathcal{D}$ se le da acceso a $f(\cdot)$, que es $F_3(k, \cdot)$o una función aleatoria. Denoto la primera mitad de$z$ como $z_L$ y la segunda mitad de $z$ como $z_R$.
- $\mathcal{D}$ consultas $y^0 = f(0)$
- $\mathcal{D}$ calcula $y^1 = F(y^0_R, x)$ para algunos al azar $x$.
- $\mathcal{D}$ consultas $y^2 = f(x)$
- Si $y^1 = y^2_L$, $\mathcal{D}$ salidas que $f$ es $F_3$.
- De otra manera, $\mathcal{D}$ salidas que $f$ es una función aleatoria.
$\mathcal{D}$ tiene una ventaja no despreciable: si $f$ es $F_3$, entonces $y^1 = y^2_L$:
$y^1 = F(y^0_R, x) = F(f(0^n), x) = F(F(k, 0^n), x)$
$y^2_L = f(x)_L = F_3(k, x)_L = F(F(k, 0^n), x)$
La probabilidad de que esto se mantenga cuando $f$ es una función aleatoria es insignificante.
¡Espero poder ayudar!
Dado que @fgrieu estaba interesado en la pregunta 2, voy a romper con la política del sitio y dar una respuesta completa para esa parte, aunque es casi seguro que esto sea una tarea.
Teorema. Dejar$F : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ser un PRF. Entonces,$F_2 : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$, definido como $$F_2(k,x) := F(F(k,0^n),x)$$ también es un PRF.
Antes de dar una prueba formal, construyamos una intuición de por qué debería ser así. Tenga en cuenta que la invocación interna de$F$ no está en alguna parte de la entrada, sino en una constante (es decir, $0^n$). Esto significa que una vez que arreglemos la llave$k$, la clave utilizada por la invocación externa de $F$para todas las evaluaciones de$F_2$ es una clave fija $k' := F(k,0^n)$. Ya que$k$ no se utiliza en ninguna otra parte de la construcción, $k'$ debe, por la seguridad de la PRF subyacente, ser indistinguible de una clave uniformemente aleatoria $k''$, Mientras $k$se elige uniformemente al azar. Esto significaría que un oráculo evaluando$F_2(k,\cdot)$ y un oráculo evaluando $F(k,\cdot)$de hecho, debería ser indistinguible. Ya que$F(k,\cdot)$ ya se sabe que es indistinguible de una función aleatoria elegida uniformemente $f(\cdot)$ y la indistinguibilidad (en el sentido asintótico) es transitiva, se seguiría que $F_2$ también debe ser un PRF.
Así que formalicemos esta intuición.
Prueba. Dejar$A$ ser un algoritmo PPT arbitrario con $$\Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|=\epsilon(n).$$ Buscamos dar un límite superior insignificante para $\epsilon$. Para ello probaremos una serie de afirmaciones.
Reclamación 1. $\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$
Considere el siguiente adversario $B$ contra la seguridad de PRF de $F$. Tras la entrada$1^n$ y dado acceso a un oráculo, $B$ consultas $0^n$ al oráculo se le devuelve un valor $k'$. Luego invoca$A$ en la entrada $1^n$. Cuando$A$ envía una consulta $x$ a su oráculo, $B$ responde computando $y:=F(k',x)$. Finalmente,$A$ saldrá un poco $b$ cuales $B$ también salidas.
Es fácil ver eso $$\Pr_k[B^{F(k,\cdot)}(1^n)=1] = \Pr_k[A^{F(F(k,0^n),\cdot)}(1^n)=1]$$ y $$\Pr_f[B^{f(\cdot)}(1^n)=1] = \Pr_f[A^{F(f(0^n),\cdot)}(1^n)=1].$$ Además, dado que $F$ es un PRF seguro, debe mantener que $$\Bigl|\Pr_k[B^{F(k,\cdot)}(1^n)=1]-\Pr_f[B^{f(\cdot)}(1^n)=1]\Bigr|\leq \mathsf{negl}(n)$$ y el reclamo sigue.
Reclamación 2. $\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] = \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]$
Para ver que este es el caso, es más fácil pensar en $f$como muestra perezosa cuando se le pregunta. Ya que$f$ solo se invoca en $0^n$, muestreo $f$ es equivalente a simplemente muestrear $f(0^n)$ una vez como valor uniformemente aleatorio $k\in \{0,1\}$, que es idéntico al lado derecho.
Reclamación 3. $\Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$
Esta afirmación es, de hecho, solo una reafirmación del supuesto de que $F$ es un PRF y, por lo tanto, sigue trivialmente.
Usando la desigualdad del triángulo, podemos concluir \begin{align} \epsilon(n) =&\quad \Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|\\ \leq&\quad\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr|\\ &+ \Bigl|\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] - \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]\Bigr|\\ &+ \Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr|\\ &\leq 2\cdot\mathsf{negl}(n) \end{align} y el enunciado del teorema sigue inmediatamente.$\tag*{$\cuadrado$}$