PRF XORed cu cheia este încă un PRF? (mereu)

Nu.

Lăsa $||$ denotă concatenarea. Lăsa $F''$ fi un PRF pe domeniu $\mathbb{M} \times \{0,1\}$. Remediați orice „mesaj special” $m^* \in \mathbb{M}$. Luați în considerare următoarea construcție pentru $F'$: cheia lui $F'$ este $k_0 || k_1$, Unde $k_0$ este o cheie aleatorie pentru $F''$, și $k_1$ este un șir aleatoriu de aceeași lungime. La intrare $m \in \mathbb{M}$, $F'_{k_0||k_1}(m)$ iesiri $F''_{k_0}(m||0) || k_1$ dacă $m = m^*$, și $F''_{k_0}(m||0) || F''_{k_0}(m||1)$ in caz contrar.

În primul rând, observă asta $F'$ este încă un PRF. Rezultă direct din securitatea $F''$, iar observând că $k_1$ este cu adevărat aleatoriu și este folosit o singură dată, pe intrarea specială $m = m^*$.

În al doilea rând, să $F_{k_0||k_1}: m \rightarrow F'_{k_0||k_1}(m) \oplus (k_0 || k_1)$. Acesta nu este în mod clar un PRF, deoarece a doua jumătate a $F_{k_0||k_1}(m^*)$ este un șir de zerouri (ceea ce este foarte puțin probabil să se întâmple pentru o funcție aleatorie).

(Eu trec peste detalii minore despre ceea ce presupunem cu privire la lungimea tastelor, deoarece nu este greu de gestionat, ci doar un pic mai plictisitor).