¿Cuáles de esas funciones son PRF?

Nov 18 2020

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

2 cisnjxqu Nov 21 2020 at 18:01

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

  1. $\mathcal{D}$ consultas $y^0 = f(0)$
  2. $\mathcal{D}$ calcula $y^1 = F(y^0_R, x)$ para algunos al azar $x$.
  3. $\mathcal{D}$ consultas $y^2 = f(x)$
  4. Si $y^1 = y^2_L$, $\mathcal{D}$ salidas que $f$ es $F_3$.
  5. 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!

3 Maeher Nov 24 2020 at 20:25

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$}$