完善的安全定義
在我的筆記中，完美安全有兩種定義：
- “為了 $ M \in {0,1}^m $ , 定義分佈 $ D_M $ 在字元串上如下：選擇一個隨機成員 $ D_M $ , 隨機選擇 $ K \in {0,1}^n $ 和輸出 $ Enc(M,K) $ . 然後 $ Enc,Dec $ 是完全安全的，如果 $ D_M $ 對每一個都完全相同 $ M $ . 也就是說，對於每個 $ \alpha \in {0,1}^* $ , 的機率 $ \alpha $ 根據 $ D_M $ 獨立於 $ M $ .
- 對於每兩條消息，沒有函式可以判斷哪一條已被加密。那是， $ Enc,Dec $ 如果對於每個 $ M_0,M_1 \in {0,1}^m $ 並且對於每個 $ f: {0,1}^* \to {0,1} $ ，以下成立：考慮實驗 $ b $ 是隨機選擇的 $ {0,1} $ 和 $ K $ 是隨機選擇的 $ {0,1}^n $ ; 那麼機率 $ f(Enc(M_b,K)) = b $ 等於 $ 1/2 $ 。”
我有兩個問題：
- 有人可以澄清 $ D_M $ （字元串的分佈？）。我不確定我明白“字元串分佈”的含義以及它與 $ M $
- 如果 $ M_0 $ ， 和 $ M_1 $ 是任意兩個 $ m $ -bit消息，它們的加密怎麼可能相等 $ b $ ? 加密消息中的位數不會是 $ m $ ? 如果該數字是例如 10 那麼如何 $ P \left ( f( \mathrm{Enc} (M_b, K)) = b \right ) = 0.5 $ ?
如果 M0 和 M1 是任意 2 m 位的消息，它們的加密怎麼可能等於 b？
定義並沒有說它們的加密是相等的b。它說函式f輸出b。這個函式通常被稱為區分者（或攻擊者），他不應該能夠區分哪個消息M0或M1被加密。換句話說，不存在比猜測機率（0.5）更好地區分哪個消息被加密的區分器。
在第一個定義中， $ D_M $ 是一個機率分佈。正如維基百科頁面所指出的，有多種方法可以指定機率分佈；其中之一，也就是這裡使用的，是指定如何對根據該分佈分佈的隨機變數進行採樣。
具體來說，定義的意思是 $ D_M $ 是加密消息得到的密文分佈 $ M $ 使用隨機選擇的密鑰 $ K $ . 換句話說，對隨機變數進行抽樣 $ X $ 按分佈分佈 $ D_M $ , 你接受消息 $ M $ , 選擇一個隨機鍵 $ K $ 從鍵空間，讓 $ X = Enc(M,K) $ .
（具體來說，關鍵 $ K $ 大概應該從集合中統一選擇 $ n $ 位鍵 $ {0,1}^n $ ，儘管定義沒有明確說明。除非另有說明，否則假定從有限集中選擇的隨機變數是均勻分佈的，這是密碼學中的一個常見約定。）
然後定義說加密是完全安全的當且僅當 $ D_{M_0} = D_{M_1} $ 對於任意兩條消息 $ M_0 $ 和 $ M_1 $ ——也就是說，如果，對於任何給定的消息 $ M_0 $ 和 $ M_1 $ , 任何給定的密文 $ C $ 和一個隨機密鑰 $ K $ , 的機率 $ Enc(M_0,K) = C $ 等於機率 $ Enc(M_1,K) = C $ .
在第二個定義中，符號 $ f:{0,1}^* \to {0,1} $ 意思是 $ f $ 是集合中的一個函式 $ {0,1}^* $ 任意位串的集合 $ {0,1} $ 單個位。那是， $ f $ 將位串作為輸入並輸出一個位。
我們可以考慮輸入 $ f $ 作為加密消息，並輸出 $ f $ 作為猜測 $ M_0 $ 或者 $ M_1 $ 是輸入對應的明文。然後定義說，如果（且僅當）我們的加密系統是完全安全的，那麼對於任何一對消息 $ M_0 $ 和 $ M_1 $ 和任何區分器 $ f $ , 如果我們接收隨機消息 $ M $ 從給定的消息對中選擇，並使用隨機密鑰對其進行加密 $ K $ 得到密文 $ C = Enc(M,K) $ ，然後猜測 $ f(C) $ 不超過（也不少於）50% 的正確變化。