PRF XORed với khóa của nó có còn là PRF không? (luôn)

Không.

Để cho $||$ biểu thị phép nối. Để cho $F''$ là một PRF trên tên miền $\mathbb{M} \times \{0,1\}$. Sửa bất kỳ "tin nhắn đặc biệt" nào $m^* \in \mathbb{M}$. Hãy xem xét việc xây dựng sau đây cho $F'$: chìa khóa của $F'$ Là $k_0 || k_1$, ở đâu $k_0$ là một khóa ngẫu nhiên cho $F''$, và $k_1$ là một chuỗi ngẫu nhiên có cùng độ dài. trên đầu vào $m \in \mathbb{M}$, $F'_{k_0||k_1}(m)$ đầu ra $F''_{k_0}(m||0) || k_1$ nếu $m = m^*$, và $F''_{k_0}(m||0) || F''_{k_0}(m||1)$ nếu không thì.

Đầu tiên, quan sát rằng $F'$ vẫn là một PRF. Nó theo trực tiếp từ sự an toàn của $F''$, và bằng cách quan sát rằng $k_1$ thực sự là ngẫu nhiên và chỉ được sử dụng một lần, trên đầu vào đặc biệt $m = m^*$.

Thứ hai, hãy để $F_{k_0||k_1}: m \rightarrow F'_{k_0||k_1}(m) \oplus (k_0 || k_1)$. Đây rõ ràng không phải là PRF, bởi vì nửa sau của $F_{k_0||k_1}(m^*)$ là một chuỗi các số 0 (điều này rất khó xảy ra đối với một hàm ngẫu nhiên).

(Tôi đang đề cập đến những chi tiết nhỏ về những gì chúng ta giả định về độ dài của các phím, vì nó không khó để xử lý, chỉ hơi tẻ nhạt hơn một chút).