Câu hỏi này có thể liên quan đến cái này, mặc dù việc xây dựng khác nhau.
Chúng ta hãy xem xét một PRF $f$. Chúng tôi xác định $g_k$ như $g_k(x)=f(x)\oplus f(x\oplus k)$. Là $g_k$ một PRF, giả sử $k$ được chọn ngẫu nhiên?
Tôi đã cố gắng chứng minh điều này như sau. Chúng ta hãy xem xét một đối thủ $\mathcal{A}$ mà có thể phân biệt giữa $g_k$ và một PRF với lợi thế không đáng kể. Để cho $\mathcal{R}$ là một giảm có quyền truy cập vào $\mathcal{A}$ và muốn phá vỡ bảo mật PRF của $f$. Trong cả hai trò chơi, $b=0$ biểu thị thế giới thực và $b=1$ thế giới ngẫu nhiên, nơi một chức năng thực sự ngẫu nhiên được áp dụng thay vì $f$ hoặc $g_k$.
Khi bắt đầu trò chơi, $\mathcal{R}$ chọn $k$ ngẫu nhiên. Khi nào $\mathcal{A}$ truy vấn cho $x$, $\mathcal{R}$ truy vấn cho $x$ và $x\oplus k$, XOR kết quả và gửi lại cho $\mathcal{A}$. Khi nào $\mathcal{A}$ trả về dự đoán của nó $b'$, $\mathcal{R}$ trả về cùng một bit.
để chứng minh rằng $\mathcal{R}$ có một lợi thế không đáng kể, chúng ta chỉ cần chứng minh rằng nó mô phỏng hoàn hảo việc triển khai tiên tri $g_k$. Trong trường hợp $b=0$, nó là trường hợp, không có gì khác biệt $\mathcal{R}$ từ một oracle thực hiện $g_k$. Nếu $b=1$ Tuy vậy, $\mathcal{A}$ mong đợi để có được $\pi(x)$ cho một chức năng ngẫu nhiên $\pi$, trong khi nó nhận được $\pi(x)\oplus\pi(x\oplus k)$. $\pi(x)$ là ngẫu nhiên thống nhất và, theo định nghĩa của một hàm ngẫu nhiên, không liên quan đến $\pi(x\oplus k)$, Vậy thì sao $\mathcal{R}$ trở lại đây $\mathcal{A}$ là thống nhất ngẫu nhiên quá. Nó được biểu thị rằng bây giờ $\pi$ đã được xác định trên $x$ và hơn thế nữa $x\oplus k$, $\mathcal{A}$ có thể dự đoán giá trị mã hóa của $x\oplus k$ vì điều này sẽ giống như $x$'S. Từ $\mathcal{A}$ không biết $k$, đây không phải là một chiến lược khả thi. Vì thế, $\mathcal{A}$ không phân biệt được giữa các tình huống này.
Bằng chứng này có đúng không? Điều làm tôi khó chịu là PRF mới này có rất nhiều va chạm, điều này khá ngạc nhiên đối với PRF, nhưng tôi nghĩ rằng đối thủ không thể tìm thấy chúng trừ khi họ biết $k$.
