Câu hỏi đề cập đến việc chứng minh bằng cách rút gọn thành một bài toán khó (ví dụ: Computational DiffieâHellman). Đó không phải là cách sử dụng phổ biến duy nhất của chứng minh bằng cách rút gọn để chứng minh tính bảo mật của hệ thống mật mã: thay vì độ khó của một bài toán, chúng ta thường giả sử sự tồn tại của một khối xây dựng mật mã với một số thuộc tính mã hóa giả định, chẳng hạn như một mật mã khối không thể phân biệt về mặt tính toán với một hoán vị ngẫu nhiên khi khóa là ngẫu nhiên hoặc một hàm băm được cho là chỉ có thể truy cập được đối với kẻ thù dưới dạng một lời tiên tri ngẫu nhiên.
Đối với một số hệ thống, chúng tôi có bằng chứng trực tiếp về bảo mật hoàn hảo bằng lập luận lý thuyết thông tin, ví dụ: thiết lập rằng không có thông tin nào về bản rõ có thể thu được từ bản mã trong One Time Pad.Vấn đề là, tất cả các hệ thống mà tính bảo mật có thể được chứng minh bằng dòng bằng chứng đó đều cần một khóa bí mật lớn bằng toàn bộ bản rõ đã từng được truyền (rõ ràng là nếu bản rõ được giả định là ngẫu nhiên), và do đó là không thực tế. Đặc biệt, không ai có thể là một mật mã an toàn, theo định nghĩa toán học của điều đó. Vì vậy, để chứng minh các hệ thống mật mã thực tế, dòng lập luận lý thuyết thông tin phải được sử dụng kết hợp với chứng minh bằng cách rút gọn và giả định điều gì đó.
Tôi không biết phương pháp chứng minh bảo mật toán học nào khác cho các hệ thống mật mã. Tôi biết không có hệ thống mật mã thực tế nào có bằng chứng toán học đầy đủ về bảo mật. Và ngay cả khi chúng tôi cắt giảm tính thực tế, sự tồn tại của một mật mã an toàn sẽ ngụ ý Pâ NP, và chúng tôi không ở đó.
Tuy nhiên chúng tôi cũng có tranh luận của an ninh. Chúng ta có thể thiết kế một hệ thống mật mã hoặc khối xây dựng (chẳng hạn như mật mã khối hoặc hàm băm) với các tham số (cụ thể là số vòng và độ rộng của biến), kiểm tra độ khó của việc phá vỡ nó bằng các phương pháp phân tích mật mã đã biết trở nên khó khăn hơn khi các tham số này tăng lên, và thuyết phục bản thân rằng xu hướng này sẽ tiếp tục (đây là điều khó nhất và không chắc chắn nhất); sau đó kết luận rằng với một số tham số đủ lớn, chúng tôi an toàn trước các cuộc tấn công đã biết này.
Với ngoại lệ hiếm hoi của One Time Pad, có lẽ được kết hợp với Phân phối khóa lượng tử, tất cả các hệ thống mật mã được triển khai mà nó hợp lý để tin tưởng đều sử dụng dòng lập luận sau này.
