證明給定的加密方案是完全保密的
我正在為即將到來的考試而學習，但我無法弄清楚以下範例問題：
讓 $ \Pi = (\operatorname{Gen}, \operatorname{Enc}, \operatorname{Dec}) $ 是具有密鑰空間的加密方案 $ \mathcal K $ , 消息空間 $ \mathcal M $ , 和密文空間 $ \mathcal C $ 在哪裡 $ \mathcal K =\mathcal M =\mathcal C = {0, 1, 2, 3} $ . 算法 $ \operatorname{Gen} $ 返回一個均勻隨機的密鑰 $ k $ 在 $ \mathcal K $ . 對於任何鍵 $ k $ 在 $ \mathcal K $ 和任何消息 $ m $ 在 $ \mathcal M $ , $ \operatorname{Enc}(m) $ 使用密鑰 $ k $ 定義為 $ (m + k) \bmod 4 $ . 對於任何鍵 $ k $ 在 $ \mathcal K $ 和密文 $ c $ , $ \operatorname{Dec}(c) $ 使用密鑰 $ k $ 定義為 $ (c - k) \bmod 4 $ .
a) 證明 $ \operatorname{Dec}(\operatorname{Enc}(m)) = m $ 使用密鑰 $ k $ 持有任何鑰匙 $ k $ 在 $ \mathcal K $ 和任何消息 $ m $ 在 $ \mathcal M $ .
b) 證明或反駁： $ \Pi $ 是完全秘密的。
使用的“完全機密”的正式定義是：
消息空間上的加密方案（Gen、Enc、Dec） $ \mathcal M $ 如果對於每個機率分佈 $ \mathcal M $ , 每一條消息 $ m $ 在 $ \mathcal M $ , 和每一個密文 $ c $ 在 $ \mathcal C $ 為此 $ Pr[\mathcal{C} =c] > 0: Pr[\mathcal{M}=m | \mathcal{C}=c] = Pr[\mathcal{M}=m] $ .
在該方案中，可以重複使用密鑰。
- 對於每一個鍵 $ k \in \mathcal K $
$$ Dec(Enc(m)) \overset{\underset{\mathrm{def}}{}}{=} (Enc(m) - k) \bmod 4, $$在哪裡$$ Enc(m) \overset{\underset{\mathrm{def}}{}}{=} (m + k) \bmod 4, $$所以，結合它，我們有$$ Dec(Enc(m)) = (((m + k) \bmod 4) - k) \bmod 4, $$根據模算術（或更準確地說，全等）的性質，它等價於$$ (m \bmod 4) + (k \bmod 4) - (k \bmod 4) = m + k - k = m $$ 2. 這實際上是一個很好的例子，因為它展示了安全性數學定義的終極優雅。加密方案 $ (E, D) $ 超過 $ (\mathcal K, \mathcal M, \mathcal C) $ 是完全秘密的，如果對所有人來說 $ m_i, m_j \in \mathcal M, c \in \mathcal C $
$$ Pr[E(k, m_i) = c] = Pr[E(k, m_j) = c], $$ 在哪裡 $ k $ 是均勻的 $ \mathcal K $ . 這是一個加密表 $ m $ 帶鑰匙 $ k $ 對所有人 $ m \in {0, 1, 2, 3} $ 和 $ k \in {0, 1, 2, 3} $ : $$ \begin{array}{c|lc} m/k & 0 & 1 & 2 & 3 \ \hline 0 & 0 & 1 & 2 & 3 \ 1 & 1 & 2 & 3 & 0 \ 2 & 2 & 3 & 0 & 1 \ 3 & 3 & 0 & 1 & 2 \end{array} $$ 如您所見，對於每個 $ m $ , $ Pr[Enc(m) = c] = 1/4 $ ，因此給定的加密方案是完全安全的。