直覺（講義 p. 23）
歷史密碼的問題是密文「洩漏了關於訊息的統計資訊」。能不能做到一點都不洩漏？講義 p. 23 的答案是可以：
直覺上：密文不含任何關於訊息的資訊（長度除外）。一點也沒有！
更精確地說：任何同長度的訊息都可能是被加密的那一個，而且每一個都一樣可能。
這是 Shannon 在 1949 年〈Communication Theory of Secrecy Systems〉中提出的，也是史上第一個嚴格的密碼學安全定義——正是 §[sec:reflections] 說的「先有定義」。 講義隨即潑冷水：「那我們為什麼不直接回家？」因為完美保密有不可避免而且嚴重的實際限制（§1.4）。
正式定義
令 \(M\) 為訊息空間 \(\calM\) 上的隨機變數（任意分布，代表敵手對訊息的先驗知識），\(K\) 為 \(\KGen\) 輸出的金鑰（與 \(M\) 獨立），\(C=\Enc(K,M)\)。
SKE \(\Pi\) 在訊息空間 \(\calM\) 上是完美保密的，若對 \(\calM\) 上的每個機率分布、每個 \(m\in\calM\)、每個使 \(\Pr[C=c]>0\) 的 \(c\in\calC\)， \[\Pr[M=m\mid C=c]=\Pr[M=m].\]
白話：看到密文之後，敵手對訊息的信念（後驗）與看之前（先驗）完全相同。注意定義對敵手的計算能力沒有任何限制——這是資訊論式的安全。
\(\Pi\) 完美保密 \(\iff\) 對所有 \(m,m'\in\calM\) 與 \(c\in\calC\)： \[\Pr_{K}\!\big[\Enc(K,m)=c\big]=\Pr_{K}\!\big[\Enc(K,m')=c\big].\]
證明概要. （\(\Leftarrow\)）若密文分布不依賴訊息，則 \(\Pr[C=c\mid M=m]=\Pr[C=c]\)，由 Bayes 得 \(\Pr[M=m\mid C=c]=\Pr[M=m]\)。 （\(\Rightarrow\)）取 \(\calM\) 上在 \(\{m,m'\}\) 各 \(1/2\) 的分布；由定義與 Bayes 推得 \(\Pr[C=c\mid M=m]=\Pr[C=c]=\Pr[C=c\mid M=m']\)。 ◻
這個刻畫最好用：「對每個固定的 \(m\)，\(\Enc(K,m)\) 的分布都一樣」。證明完美保密時幾乎都走這條路。
考慮 Week 2 的 IND-EAV 遊戲 \(\mathsf{PrivK}^{\mathrm{eav}}_{\adv,\Pi}\)，但允許 \(\adv\) 的計算能力無限。\(\Pi\) 是完美不可區分的，若對每個（不受限的）\(\adv\)：\(\Pr[\mathsf{PrivK}^{\mathrm{eav}}_{\adv,\Pi}=1]=\tfrac12\)，即優勢恰為 \(0\)。
KL-IMC Lemma 2.6：完美保密 \(\iff\) 完美不可區分。 所以完美保密就是 Week 2 的 IND-EAV 去掉兩個「讓步」：敵手不再受多項式時間限制、優勢不再是「可忽略」而是「恰好 \(0\)」。
講義的例子：\(\Zn{26}\) 上的一次性密碼本（講義 pp. 24–25）
令 \(\calK=\{0,\dots,25\}^n\)，\(\calM=\calC=\{\ct{a},\dots,\ct{z}\}^{\le n}\)，\(n\) 為正整數。
\(\KGen\)：從 \(\calK\) 均勻抽出 \(\sk=\sk_1\cdots\sk_n\)。
\(\Enc(\sk,m)\)：拆 \(m=m_1\cdots m_\ell\)；對 \(i\in[\ell]\) 令 \(c_i=m_i+\sk_i\)；回傳 \(c=c_1\cdots c_\ell\)。
\(\Dec(\sk,c)\)：拆 \(c=c_1\cdots c_\ell\)；對 \(i\in[\ell]\) 令 \(m_i=c_i-\sk_i\)；回傳 \(m\)。
與 Vigenère 唯一的差別：下標是 \(\sk_i\) 而非 \(\sk_{i\bmod j}\)——金鑰的每個元素只用一次，因此 \(\sk\) 至少與 \(m\) 一樣長。
取 \(n=7\)。每一個 7 字母字串都是可能的明文，而且對每個明文恰有一把金鑰把它送到 （\(\sk_i=\ct{a}-m_i=-m_i\)）：
| 明文 \(m\) | 數字 | 唯一的 \(\sk=-m\) | \(\sk\)（字母） |
|---|---|---|---|
| \((11,4,14,15,0,17,3)\) | \((15,22,12,11,0,9,23)\) | ||
| \((2,0,17,0,2,0,11)\) | \((24,0,9,0,24,0,15)\) | ||
| \((11,8,14,13,4,18,18)\) | \((15,18,12,13,22,8,8)\) | ||
| \((2,7,4,4,19,0,7)\) | \((24,19,22,22,7,0,19)\) | ||
| \((15,0,13,19,7,4,17)\) | \((11,0,13,7,19,22,9)\) |
講義的檢查：\(\Enc(\ct{yajayap},\ct{caracal})\)：\(2+24=26\equiv0\)、\(0+0=0\)、\(17+9=26\equiv0\)……\(=\ct{aaaaaaa}\) ✓。 由於每把金鑰被抽到的機率相同（\(26^{-7}\)），每個明文都「一樣可能」：敵手看到 之後，對「是 leopard 還是 panther」的信念與沒看到之前一模一樣。
對任意固定長度 \(\ell\le n\)，上述方案在 \(\calM_\ell=\alpha^\ell\) 上完美保密。
Proof. 用引理的刻畫。固定 \(m,c\in\alpha^\ell\)。\(\Enc(K,m)=c\) 若且唯若 \(K_i=c_i-m_i\) 對所有 \(i\in[\ell]\) 成立。因為 \(K_1,\dots,K_\ell\) 獨立且在 \(\Zn{26}\) 上均勻， \[\Pr_K[\Enc(K,m)=c]=\prod_{i=1}^{\ell}\Pr[K_i=c_i-m_i]=26^{-\ell},\] 與 \(m\) 無關。故對所有 \(m,m'\)：\(\Pr[\Enc(K,m)=c]=\Pr[\Enc(K,m')=c]\)。 （\(K_{\ell+1},\dots,K_n\) 沒被用到，不影響。） ◻
若 \(\calM\) 包含不同長度的訊息，定義就不成立：看到 7 個字母的密文，敵手就知道 \(m\) 不是 5 個字母。這是講義「other than length」的意思，也是為什麼 Week 2 的 IND 遊戲要求 \(\abs{m_0}=\abs{m_1}\)。實務上可用填充（padding）到固定長度來處理。
限制（講義 p. 26）
講義 p. 26 說：這個方案的強項是「對任何明文與密文，恰有一把金鑰連接它們」；但這同時是它的弱點。
若 \(\Pi\) 在 \(\calM\) 上完美保密，則 \(\abs\calK\ge\abs\calM\)。
Proof. 取 \(\calM\) 上的均勻分布，任取一個 \(\Pr[C=c]>0\) 的 \(c\)。令 \(\calM(c)=\{\Dec(k,c):k\in\calK\}\) 為「\(c\) 可能解密成的訊息」集合，顯然 \(\abs{\calM(c)}\le\abs\calK\)。 若 \(\abs\calK<\abs\calM\)，則存在 \(m'\in\calM\setminus\calM(c)\)。對這個 \(m'\)：沒有金鑰能把 \(m'\) 加密成 \(c\)（否則由正確性 \(\Dec(k,c)=m'\)），所以 \(\Pr[M=m'\mid C=c]=0\ne\frac1{\abs\calM}=\Pr[M=m']\)，違反完美保密。 ◻
講義的句子「need at least as much key as message」就是這個定理：想加密 \(\ell\) 個字母的任意訊息，至少需要 \(26^\ell\) 把金鑰，即 \(\ell\) 個均勻的金鑰字母。
設 \(\abs\calK=\abs\calM=\abs\calC\)。則 \(\Pi\) 完美保密 \(\iff\) (1) \(\KGen\) 以機率 \(1/\abs\calK\) 選每把金鑰，且 (2) 對每對 \((m,c)\) 恰有一把 \(k\) 使 \(\Enc(k,m)=c\)。
這給了一個「驗收」完美保密的檢查表，也解釋了講義 p. 25 為何強調「唯一的 \(\sk\)」與「每把 \(\sk\) 等機率」兩件事都要成立。Problem 2 (v) 會用到：拿掉全零金鑰會破壞 (1)。
若用同一把 \(\sk\) 加密 \(m_1,m_2\) 得 \(c_1,c_2\)，則 \[c_2-c_1=(m_2+\sk)-(m_1+\sk)=m_2-m_1 .\] 敵手不需知道 \(\sk\) 就拿到兩個訊息的差——對英文這幾乎等於拿到兩個訊息（§[sec:otp] 的 crib dragging）。 Vigenère 就是「同一把短金鑰反覆使用」的極端：每隔 \(j\) 個字母就重用一次。 結論：單次使用的金鑰，而且至少和訊息一樣長（講義註腳：可嚴格證明，見 KL-IMC §2.3、§2.4）。
完美保密 \(\Rightarrow\) IND-EAV（優勢恰為 0，對無限算力的敵手）。這比 Week 2 要求的更強。
完美保密 \(\not\Rightarrow\) IND-CPA：一次性方案是確定性的，同一把金鑰用兩次就被區分（Week 2 定理 6.1）。這不矛盾——完美保密只承諾一則訊息。多則訊息的完美保密需要每則訊息各自的新鮮金鑰（KL-IMC §2.2 的討論）。
完美保密只談保密，不談完整性：翻轉 \(c_i\) 的一個位元就翻轉 \(m_i\)（可塑性），這在 Week 1 的 MAC 討論中已經出現。