你能幫我證明完全保密嗎？
我實際上是密碼學的新手，我的一個朋友要求我閱讀 Katz 和 Lindell 的書——“現代密碼學導論”。
當我閱讀這本書時，我發現它非常有趣，但我發現在回答書中的幾個問題時遇到了一些問題，（對於像我這樣的新人，我設法回答了第 1 部分和幾乎第 2 部分），但是我說得夠多了直奔問題：
首先，我需要證明這兩個假設的女巫是完全秘密的：
- 消息空間是 $ M = {m \in {0, 1}^l \text{ | the last bit of }m \text{ is }0} $ . Gen 從中選擇一個統一的密鑰 $ {0, 1}^{l−1} $ . $ Enc_k(m) $ 返回密文 $ m \oplus (k || 0) $ ， 和 $ Dec_k(c) $ 返回 $ c \oplus (k || 0) $ .
- 消息空間是 $ M = {0,…, 4} $ . 算法 Gen 從密鑰空間中選擇一個統一的密鑰 $ {0,…, 5} $ . $ Enc_k(m) $ 返回 $ [(k + m) \bmod 5] $ ， 和 $ Dec_k(c) $ 返回 $ [(c − k) \bmod 5] $ .
假設我們有 $ \pi(Gen,Enc,Dec) $ .
對於第一個，我想我已經回答了，但我需要你們糾正我，因為我不確定我的方法是否正確：
$ M = {0, 1}^l $ $ n $ 和 $ k = {0, 1}^{l-1} $ 和 $ Enc_k(m) $ 輸出 $ c = m_{[1,ℓ-1]} \oplus (k||0) $ ，即第一個的異或 $ (l-1) $ 位 $ m $ 用鑰匙 $ k $ . 解密輸出 $ Dec_k(c) $ 作為 $ c \oplus (k||0) $ 與隨機的 1 位字元串連接（每種情況下為 0 $ Enc $ & $ Dec $ ）。該方案滿足 $ 2^{−1} $ 財產 $ Pr[Dec(Enc(m)) = m] \geq 2^{-1} $ 對於每個 $ m $ ，這意味著在第一個假設中該方案是完全安全的。
對於第二種情況，我不知道如何證明這一點。
如果您重新審視書中完美保密的定義，那就太好了。您為第一個候選方案證明的是正確性屬性，而不是安全屬性（通常），尤其不是完全保密。
非正式地，您要證明的是加密然後解密將保留原始消息。你需要證明的是猜測 $ m $ 會心 $ c $ （在哪裡 $ c=Enc_k(m) $ ) 這和猜測一樣難 $ m $ 不見 $ c $ .
作為一般策略，證明某事安全的一個好方法是將你的證明建立在類似的、已經證明的結構上。Scheme 1 與 one-time pad 非常相似，因此證明應該是可適應的。
為了證明不安全的東西，描述特定攻擊甚至反例通常更簡單。例如，方案 2 並不是完全保密的。由於您獲得了小的、具體的值，您可以嘗試使用筆和紙來計算一些範例加密，看看是否有問題。