Tôi đang tự nghiên cứu bằng cách sử dụng "Giới thiệu về mật mã hiện đại (tái bản lần 2)"
Tôi đang cố gắng hiểu làm thế nào giải pháp cho vấn đề sau đây là hợp lệ:
Chứng minh rằng một lược đồ thỏa mãn Định nghĩa 2.5 phải có $|K| \geq |M|$ không sử dụng Bổ đề 2.4. Cụ thể, hãy để $\Pi$ là một sơ đồ mã hóa tùy ý với $|K| < |M|$ Hiển thị một $A$ mà $Pr[PrivK^{eav}_{A,\Pi} = 1] > \frac{1}{2}$
Một số ký hiệu:
Định nghĩa 2.5 là:
sơ đồ mã hóa $\Pi = (Gen, Enc, Dec)$ với không gian tin nhắn $M$ là hoàn hảo không thể phân biệt nếu cho mọi $A$ nó giữ điều đó
$$
Pr[Priv^{eav}_{A,\Pi} = 1] = \frac{1}{2}
$$
Ký hiệu nói rằng xác suất mà kẻ thù đoán chính xác thông báo đầu vào phải bằng $\frac{1}{2}$ cho sự hoàn hảo không thể phân biệt để nắm giữ.
Tuy nhiên, giải pháp không có ý nghĩa với tôi.
Giải pháp là:
Xem xét những điều sau đây $A$: đầu ra thống nhất $m_0, m_1 \in M$. Khi nhận được bản mã $c$, kiểm tra bằng cách (tìm kiếm mệt mỏi) xem có tồn tại khóa không $k$ như vậy mà $Dec_k(c) = m_0$. Nếu vậy xuất 0; đầu ra khác 1.
Giải pháp này có vẻ có vấn đề vì nó nói rằng nó hợp lệ để đối thủ thực hiện tìm kiếm toàn diện trên không gian khóa. Nhưng nếu đây là trường hợp, đối với bất kỳ thử nghiệm không thể phân biệt nào, chúng ta có thể có một đối thủ chỉ thực hiện tìm kiếm mệt mỏi trên không gian khóa để xác định văn bản mật mã giải mã thành gì.
Có ai hiểu chuyện gì đang xảy ra không?
