Có thể cho một khóa khác để giải mã đúng không?

Tôi đang nghĩ về bảo mật CPA cho mã hóa đối xứng.

Cho nên $A$ có quyền truy cập vào một tiên tri mã hóa và nó có thể tiếp tục đặt câu hỏi (giai đoạn đào tạo). Trong giai đoạn đào tạo này, anh ấy yêu cầu $m_i$ và nhận lại $y_i$. Anh ta cũng có thể kiểm tra xem anh ta có thể tìm thấy khóa giải mã cho cùng một tin nhắn mà anh ta đã mã hóa hay không, chỉ cần kiểm tra xem $\Pi.\mathsf{Dec}(k, y_i) = m_i$ cho một số $k$ điều đó $A$ phỏng đoán. Anh ta cũng có thể làm điều tương tự trong giai đoạn thử thách và xem liệu $y^*$ anh ấy đã giải mã trở lại một trong hai $m_0,m_1$.

Bây giờ tôi có thể cho rằng thật khó để tìm thấy $k$ (nó được chọn một cách ngẫu nhiên), nhưng liệu có thể tìm thấy một khóa khác không $k'$ điều đó xảy ra để làm việc trên một số truy vấn đào tạo? Tôi đoán điều này sẽ không xảy ra với xác suất không đáng kể nếu $\Pi$ CPA có an toàn không, nhưng nó có thể xảy ra, phải không?

Câu hỏi của tôi có thể tương tự như: Có thể giải mã bản mã bằng khóa riêng khác không?

Trong mật mã đối xứng, những gì bạn mô tả có thể xảy ra, ít nhất là về mặt lý thuyết. Nó được gọi là cuộc tấn công Khôi phục khóa nhất quán, trái ngược với cuộc tấn công Khôi phục khóa mục tiêu phổ biến hơn. Phục hồi khóa nhất quán là khi kẻ tấn công tìm thấy một khóa nhất quán với bất kỳ cặp đầu vào-đầu ra nào. Phục hồi khóa mục tiêu là khi kẻ tấn công tìm thấy khóa thực (sẽ nhất quán với tất cả các cặp đầu vào-đầu ra). Nếu kẻ tấn công đang tiến hành một cuộc tấn công Tìm kiếm khóa toàn diện, anh ta có khả năng gặp phải khóa nhất quán (sẽ hoạt động trên một hoặc một vài truy vấn) trước khi gặp khóa thực (sẽ hoạt động trên tất cả các truy vấn).

Vấn đề đặt ra là khoảng cách giữa lợi thế của việc tìm khóa nhất quán và lợi thế của việc tìm khóa mục tiêu là bao xa. Tôi đã tìm thấy một bài giảng của Bellare nói về vấn đề này (nhưng không có gì ở dạng văn bản). Trong bài giảng đó, Bellare đề cập rằng khoảng cách gần như không xuất hiện (nghĩa là lợi thế gần như giống nhau) nếu mật mã khối là mật mã khối thực (như AES). Ông nói rằng một kết luận như vậy dựa trên bằng chứng kinh nghiệm hoặc kinh nghiệm. Nếu các ưu điểm gần như giống nhau, điều đó có nghĩa là khóa mục tiêu là khóa DUY NHẤT phù hợp với các truy vấn đầu vào-đầu ra. Nhưng về lý thuyết, một khóa nhất quán (khác với khóa mục tiêu) là có thể và có thể được khôi phục theo cách trước khi khóa mục tiêu được khôi phục. Bạn có thể xem toàn bộ bài học vì tôi chắc rằng Bellare có thể giải thích nó RẤT NHIỀU hơn tôi có thể.