Không. Không những không có chung cách để xây dựng một hệ thống mật mã dựa trên bài toán quyết định, không có một bài toán quyết định nào đã biết mà:
- là NP-Complete, và
- chúng ta có thể xây dựng mật mã từ
"Bất kỳ mật mã nào" có vẻ hơi mơ hồ, nhưng nó có thể được cụ thể hóa khá dễ dàng --- hầu hết các nguyên hàm khóa đối xứng (Hàm một chiều, Hàm/Trình tạo giả ngẫu nhiên và Hàm không thể đoán trước) được biết là tương đương, theo nghĩa là nếu bạn có một (giả sử là OWF), bạn có thể dễ dàng xây dựng những cái khác và ngược lại.
Tại sao chưa có mật mã được xây dựng từ giả định này? Một lý do cơ bản là "định lý tầm thường" rằng:
Nếu tồn tại một bảo mật (OWF/PRG/PRF/UF), thì $P\neq NP$
Điều này là do đối với bất kỳ khái niệm hợp lý nào về "bảo mật", vấn đề phá vỡ OWF/PRG/PRF/UF là:
- Dễ dàng trong NP ("đoán" khóa bí mật, sau đó bất kể khái niệm bảo mật nào cũng bị tầm thường hóa)
- Không phải trong P (nếu không, một đối thủ hiệu quả có thể phá vỡ nó, vì vậy nó sẽ không "an toàn").
Ngoài ra, còn có câu hỏi (liên quan) về
Làm cách nào để tận dụng kiến thức về một vấn đề khó khăn cụ thể để xây dựng mật mã?
Câu trả lời hơi phức tạp. Nếu bạn có thể xây dựng một nguyên hàm mật mã tiêu chuẩn (PRG/PRF/OWF/UF, hoặc OWF cửa sập), thì mọi thứ sẽ trở nên rất dễ dàng rất nhanh chóng.
Ngoài ra, tôi sẽ chỉ ra rằng nếu bạn có thể xây dựng "các nguyên mẫu tiêu chuẩn" là "đồng hình", mọi thứ cũng trở nên khá đơn giản.
Nhưng câu chuyện chung vẫn đang được giải quyết --- mã hóa dựa trên mạng có lẽ được đề xuất lần đầu tiên cách đây 25 năm, nhưng phải đến khoảng một thập kỷ trước chữ ký dựa trên mạng mới được phát triển.
Điều này có nghĩa là biết cách phát triển mã hóa (khóa công khai) không dẫn đến chữ ký "miễn phí" (mặc dù PKE là "nguyên thủy khó xây dựng hơn" theo một nghĩa chính thức nhất định).
Đã có một số tiến bộ trong việc hiểu những công trình chung nào mà một người có được từ việc xây dựng một số công trình nguyên thủy nhất định (đây là điều mà bài báo tôi đã liên kết thực hiện), nhưng tất cả đều khá gần đây.
