Bằng chứng bảo mật trong mật mã chủ yếu sử dụng kỹ thuật chứng minh rút gọn. Bây giờ tôi đã đọc rất nhiều bằng chứng về giảm thiểu và cũng đã tự làm một số và tôi nghĩ rằng tôi hiểu nó khá rõ. Trong khi đọc những bằng chứng đó, tôi nhận thấy hai phong cách chính của việc giảm thiểu như vậy.
Nói rằng chúng ta có kế hoạch $B$ dựa trên $A$. Chúng tôi biết $A$ an toàn. Nếu một người muốn chứng minh sự an toàn của $B$ bằng cách giảm nó xuống mức an toàn của $A$ anh ta có thể tiến hành như sau:
- Phong cách: Giả sử một đối thủ có thể phá vỡ $B$ $\Rightarrow$ Để giảm bớt, người ta có thể xây dựng một kẻ thù mới phá vỡ $A$ sử dụng sự phá vỡ đối thủ $B$ $\Rightarrow$ Kết quả là một mâu thuẫn cho thấy, không có đối thủ đáng kể chống lại $B$
- Phong cách: Giả sử một đối thủ ppt tùy ý chống lại $B$ $\Rightarrow$ Hiển thị (ví dụ: với phân tích thử nghiệm ngẫu nhiên) phá vỡ $B$ khó như phá vỡ $A$, do đó làm giảm sự phức tạp của việc phá vỡ $B$ đến sự phức tạp của việc phá vỡ $A$ $\Rightarrow$ Bởi vì chỉ có những đối thủ không đáng kể chống lại $A$ không có đối thủ không đáng kể chống lại $B$
Tất nhiên điều này được đơn giản hóa, nhưng tôi muốn cung cấp cho bạn ý tưởng về những gì tôi nhận thấy.
Những câu hỏi của tôi: Những phong cách này có thực sự tồn tại không? Liệu cả hai (được viết ra một cách chính xác) có thể chứng minh giống nhau không? Cả hai (đặc biệt là kiểu 1.) đã hoàn thành chưa? Đối với những bằng chứng nào người ta nên sử dụng phong cách nào?
Chỉnh sửa: Một định nghĩa chính xác hơn về phong cách 2.: Trong Giới thiệu về mật mã hiện đại chứng minh một hệ thống mật mã trên PRG: Trong phân tích ngẫu nhiên, họ tuyên bố rằng việc phá vỡ hệ thống mật mã cũng có khả năng phá vỡ PRG.Họ sử dụng điều này để ngụ ý rằng bất kỳ đối thủ tùy ý nào cũng phải không đáng kể theo kiểu: Bởi vì điều này là không đáng kể và chúng có cùng xác suất, nên đối thủ kia cũng phải không đáng kể.
(Lưu ý: Tóm lại, tôi sẽ mô tả 1. như: $B \rightarrow A \rightarrow \unicode{x21af} \rightarrow B$ và 2. như: $B \rightarrow A \rightarrow (B = A) \rightarrow B$)
