Chứng minh hai định nghĩa về bảo mật hoàn hảo là tương đương

Anon

06:38, 07/08/2023

Tôi đang cố chứng minh rằng hai định nghĩa sau đây là tương đương:

$\forall m\in M $ và $c\trong C$ $\Pr[C=c \mid M=m]=\Pr[C=c]$

$\forall m_1,m_2 \in M $, $E_k(m_1)=E_k(m_2)$, ở đâu $E_k(m_i)$ là viết tắt của phân phối trên $k$ của tin nhắn được mã hóa $m_i$.

Đầu tiên - để chắc chắn, tôi thực sự phải chỉ ra hai hướng, phải không? (tức là đầu tiên $\Rightarrow$ thứ hai và thứ hai $\Rightarrow$ đầu tiên). Đây là sự hiểu biết của tôi về việc hiển thị một sự tương đương cho bất kỳ hai định nghĩa.

Nếu vậy, tôi có thể chứng minh hướng đầu tiên $\Rightarrow$ thứ hai nhưng tôi không thể làm theo hướng thứ hai. Làm thế nào để tôi sử dụng thực tế là cho mọi đôi tin nhắn tôi có một số kết luận về bất kỳ Độc thân thông điệp chung $m$?

Cảm ơn.

0 + 0

bí mật hoàn hảo

Titanlord

07:14, 07/08/2023

Tôi không thực sự hiểu định nghĩa thứ hai. Ý bạn là $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$

Hồi đáp

Marc Ilunga

13:31, 07/08/2023

Câu lệnh thứ hai bằng cách nào đó sẽ cho thấy mã hóa không chính xác? Vì bạn không thể giải mã, nên bản mã giống nhau đối với tất cả các thư. Về mặt tươi sáng, rất an toàn!

Hồi đáp

Anon

14:27, 07/08/2023

@Titanlord vâng, chính xác.

Hồi đáp

Điểm:1

Crypto

Titanlord

08:18, 07/08/2023

Vâng, bạn đúng, bạn cần chứng minh cả hai hướng. Trong Sách giáo khoa của Katz & Lindell (tái bản lần 2) bạn có thể tìm thấy bằng chứng cho lần đầu tiên $\Rightarrow$ thứ hai. Hướng còn lại dành cho tập thể dục. Tôi cố gắng hết sức để đưa ra một giải pháp chính xác cho điều đó.

Đầu tiên chúng ta phải biết rằng những điều sau đây được giữ:

$$ Pr[Enc_k(m) = c] = Pr[C = c | M = m] $$

Đầu tiên $\Rightarrow$ Thứ hai chứng minh rằng giả sử $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$ là chính xác, sau đó $Pr[C = c | M = m] = Pr[M = m]$ nắm giữ.

Chúng tôi muốn chỉ ra rằng giả sử $Pr[C = c | M = m] = Pr[M = m]$ là chính xác, sau đó $Pr[Enc_k(m_1) = c] = Pr[Enc_k(m_2) = c]$ nắm giữ.

Giải pháp của tôi là:

$$Pr[Enc_k(m_1) = c] = Pr[C = c | M = m_1] = \frac{Pr[M = m_1 | C = c] \cdot Pr[C = c]}{Pr[M=m_1]} $$

Bởi vì chúng tôi cho rằng $Pr [ M = m_1 | C = c] = Pr[M=m_1]$ chúng tôi nhận được:

$$ \Rightarrow Pr[C = c] = Pr[C = c | M = m_2] = Pr[Enc_k(m_2) = c]$$

0 + 0

Phan Văn Trường

Câu hỏi này là trong các ngôn ngữ khác:

EN: Proving two definitions of perfect security are equivalent

TH: การพิสูจน์ว่าคำจำกัดความของการรักษาความปลอดภัยที่สมบูรณ์แบบสองคำนั้นเทียบเท่ากัน

RO: Demonstrarea a două definiții ale securității perfecte sunt echivalente

RU: Доказательство эквивалентности двух определений совершенной безопасности

VI: Chứng minh hai định nghĩa về bảo mật hoàn hảo là tương đương

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.