Tôi muốn hỏi tại sao một hoán vị sửa chữa không phải là một cách.
Cho dù đó là một cách tùy thuộc vào cách bạn xác định vấn đề.
Nếu bạn được cấp quyền truy cập Oracle vào hoán vị một chiều, nghĩa là bạn được phép cung cấp một số truy vấn $x$ và Oracle cung cấp cho bạn đánh giá về $F(x)$, tốt, chúng tôi hy vọng rằng (giả sử kích thước lớn) đó là một chiều. Xét cho cùng, nếu chúng ta định nghĩa $F$ là mã hóa khối AES dựa trên khóa bí mật (vì vậy $n = 2^{128}$), tốt, mô hình Oracle này chính xác là một cuộc tấn công CPA tiêu chuẩn và chúng tôi hy vọng rằng AES an toàn trước nó. Và, thực sự có thể chính thức chứng minh rằng xác suất thành công mà bạn đưa ra cho một hoán vị ngẫu nhiên là gần (xác suất giới hạn trên thực tế cao hơn một chút vì kẻ tấn công có thể đoán đầu vào mà anh ta không cung cấp cho Oracle, làm tăng nhẹ xác suất thành công của anh ta ).
Mặt khác, nếu bạn được cung cấp mô tả về $F$, nó trở nên rắc rối hơn. Cách dễ nhất (và phổ biến nhất) để tạo ra một hoán vị mạnh là lấy một loạt các hoán vị yếu (các vòng) và nối chúng lại với nhau; đây là cách tiếp cận mà Keccak (SHA-3) sử dụng. Điều này hoạt động, nhưng rất dễ đảo ngược (chỉ tính toán nghịch đảo của các hoán vị yếu theo thứ tự ngược lại).
Mặt khác, đó không phải là cách duy nhất để xác định một hoán vị; một ví dụ về một cách khác là xác định hoán vị $F(x) = x^e \bmod n$ cho một mô-đun RSA $n$ và một số mũ công khai $e$. Đây là một hoán vị của $x \in [0 ... n-1]$và nếu $n, e$ được chọn tốt, rất khó để đảo ngược ngay cả khi đưa ra các giá trị $n, e$ (hoặc vì vậy chúng tôi hy vọng; nếu không thì RSA không an toàn)
