Tôi đang thực hiện bài tập sau trong phần Giới thiệu Mật mã Hiện đại của Katz và Lindell:
Để cho $F$ là hàm giả ngẫu nhiên bảo toàn độ dài. Đối với các cấu trúc sau của hàm khóa $F' : \{0,1\}^n \times \{0,1\}^{n-1} \rightarrow \{0,1\}^{2n}$, Nêu rõ $F'$ là một hàm giả ngẫu nhiên. Nếu có, hãy chứng minh điều đó; nếu không, hiển thị một cuộc tấn công.
(d) $F'_k(x) \stackrel{def}{=} F_k(0||x) || F_k(x||1)$
Tôi hiểu rằng trong trường hợp này $F'_k$ không phải là một hàm giả ngẫu nhiên vì chúng ta có thể, một cách hiệu quả và với xác suất không đáng kể, phân biệt $F'$ từ một chức năng ngẫu nhiên bằng cách truy vấn $x = 0^{n-2}||1$ và $x = 0^{n-1}$và kiểm tra xem ngoài cùng bên trái $n$ bit của truy vấn đầu tiên bằng ngoài cùng bên phải $n$ bit của truy vấn thứ hai.
Tuy nhiên, tôi cũng có thể cho rằng một kẻ thù $A$ phân biệt $F'$ từ một chức năng ngẫu nhiên và sử dụng nó như một chương trình con để tấn công $F$. Đối với bất kỳ truy vấn $x$ từ $A$, tôi truy vấn cho $0||x$ và $x||1$, nối các kết quả và đưa chúng trở lại $A$. Sao cũng được $A$ câu trả lời, đó sẽ là câu trả lời của tôi.
Thật không may, tôi không thể biện minh tại sao bằng chứng là sai. Có lẽ bởi vì có một xác suất thấp mà tôi có thể sử dụng kết quả từ $A$ để phá vỡ $F$? Nhưng làm thế nào để tôi chính thức hóa điều đó nếu tôi không biết gì về $A$?
