Perfect-Secrecy
（我）完美保密：|K|< |M|
我對完全保密有一個基本的了解。在 |K| 的情況下 == |M|，我看到只有一個密鑰可以將給定的 m 加密為給定的 c。因此，每個 m 都具有相同的機率 1/|K|。
對於 |K|<|M| 的情況，我有一些直覺，如果 |x|，則不可能將集合 x 上的隨機變數映射為集合 y 上的隨機變數。< |y|。但我想要一個正式的證明。或者也許這是看待這個問題的錯誤方法——我只是想看看我們如何證明 |K|<|M| 導致不完全保密。
|K|<|M|的這種情況 不是作業題；它在 Boneh 的 Cryptography I 中被簡要提及，但沒有得到證明。
這是在 Boneh 和 Shoup 的建設中教科書的 Theorem 2.5 中完成的。
簡而言之，假設 $ |K| < |M| $ . 挑一些 $ k \in K $ , $ m \in M $ ， 然後讓 $ c = E(k, m) $ . 現在，對於所有可能的鍵 $ k’ \in K $ , 有一組明文 $ { D(k’, c) : k’ \in K } $ . 但是因為 $ |K| < |M| $ ，會有一些 $ m’ $ 不在這個集合中，這樣 $ \mathbf{Pr}[E(k, m) = c] > 0 $ 和 $ \mathbf{Pr}[E(k, m’) = c] = 0 $ . 但是根據完美安全的定義，我們應該有 $ \mathbf{Pr}[E(k, m) = c] = \mathbf{Pr}[E(k, m’) = c] $ 對於任何 $ m, m’ $ .
換句話說，沒有足夠的密鑰來生成消息中的每個可能的密文，或者密文中的每個可能的消息。這破壞了完美的安全性。