證明一次性墊是完全秘密的
我正在閱讀 Katz 和 Lindell 的“現代密碼學簡介”中的一次性便箋簿。我能理解完美保密的定義。但是，如何證明 OTP 是完全安全的？我對機率很生疏，所以請解釋一下步驟。
書中的證明是這樣的，
$ M $ 是一組消息（所有可能的長度位串 $ \ell $ )，消息空間。 $ K $ （密鑰空間）等於消息空間，密碼是電腦 $ c=k\oplus m $ ， 在哪裡 $ k $ 屬於 $ K $ （均勻隨機選擇）和m屬於 $ M $ ,
$$ \begin{align*} \Pr&[C=c\mathrel|M=m] \ &= \Pr[M \oplus K = c \mathrel| M = m] \&\quad\text{(How did the random variable $C$ become $M\oplus K$ here?)} \ &= \Pr[m \oplus K = c] \&\quad\text{(where did the conditional probability go ? what rule should I apply here ?)} \ &= \Pr[K = m \oplus c] \&\quad\text{(what is this ?)} \ &= 1/2^\ell \&\quad\text{(how should I arrive at this finally ?)} \end{align*} $$ 我不明白這四個步驟中的任何一個。請解釋這些步驟背後的原因。這個結果被用來表明它滿足完全保密的定義。請幫助我理解這個結果。
首先，注意大小寫：
- 大寫字母表示某個機率空間中的隨機變數。
- 小寫字母表示相應隨機變數域中的特定值。
例如，如果機率空間是 $ \Omega $ ， 然後 $ C\colon \Omega \to {0,1}^\ell $ 是一次性密文系統中密文的隨機變數，並且 $ c \in {0,1}^\ell $ 是密文的特定值，在某些樣本中 $ \omega \in \Omega $ 可能是 $ C(\omega) = c $ .
隨機變數 $ C $ 與隨機變數有關 $ M $ 和 $ K $ 經過 $ C = M \oplus K $ ，這是對隨機變數表示法的標準輕度濫用，這意味著 $ C(\omega) = M(\omega) \oplus K(\omega) $ 在任何樣本中 $ \omega \in \Omega $ . 任何固定值 $ c $ , $ m $ ， 和 $ k $ 可能或可能不相關 $ c = m \oplus k $ ，儘管如果在某些樣本中 $ \omega $ 我們有 $ C(\omega) = c $ 和 $ M(\omega) = m $ 和 $ K(\omega) = k $ 然後 $ c $ , $ m $ ， 和 $ k $ 確實與 $ c = m \oplus k $ .
對於任何固定消息 $ m \in {0,1}^\ell $ , 在事件 $ E = {\omega \in \Omega \mathrel: M(\omega) = m} $ 消息在哪裡 $ M $ 承擔價值 $ m \in {0,1}^\ell $ , 你能得出什麼結論 $ C $ ? 換句話說，如果對於任何 $ \omega $ 我們有 $ M(\omega) = m $ , 你能說什麼 $ C(\omega) $ ? 你能用這個來消除 $ C $ 從省略號 $ \Pr[;\cdots \mathrel| M = m] $ ?
接下來，如果你有一個關於隨機變數的方程 $ K $ 不參考 $ M $ ，給定一個關於 $ M $ ，回憶一下隨機變數獨立性的定義以及它與條件機率的關係。最後，使用機率質量函式 $ K $ ，你就會有答案。