第一週我們用「金鑰、加密、解密」三個直覺描述了秘密金鑰加密。本節把它寫成嚴格的定義，每個字都有用意。

語法（syntax）

一個是三個演算法的三元組 \(\SKE=(\KGen,\Enc,\Dec)\)，並附帶三個集合： \(\calK\)、 \(\calM\)、 \(\calC\)。

  • \(\KGen\) 是隨機化演算法，抽樣並輸出秘密金鑰 \(\sk\in\calK\)，記作 \(\sk\gets\KGen\)。

  • \(\Enc\) 是可能隨機化的演算法，輸入 \(\sk\in\calK\) 與 \(m\in\calM\)，輸出 \(c\in\calC\)： \[c\gets\Enc(\sk,m)\ \text{（若隨機化）}\qquad\text{或}\qquad c=\Enc(\sk,m)\ \text{（若確定性）}.\]

  • \(\Dec\) 是確定性演算法，輸入 \(\sk\in\calK\) 與 \(c\in\calC\)，輸出 \(m\in\calM\) 或特殊的 \(\bot\)： \[m=\Dec(\sk,c)\qquad\text{或}\qquad \bot=\Dec(\sk,c).\]

SKE 的三個演算法與資料流。\(\KGen\) 一定用到隨機性；\(\Enc\) 可選；\(\Dec\) 不用。

「隨機化」是什麼意思？（講義 p. 3）

講義問：一個函數是「隨機化的」是什麼意思？答案是：它隱含地多拿了一個隨機的輸入。

取一個 \(\calR=\bits^r\)，先抽 \(\rho\gets\calR\)，再計算 \[c=\Enc(\sk,m;\rho).\] 分號後面是隨機帶（random coins）。一旦把 \(\rho\) 也當成輸入，\(\Enc\) 就是一個完全確定的函數 \(\calK\times\calM\times\calR\to\calC\)；「隨機化演算法」只是「確定性演算法 + 由系統幫你抽好的 \(\rho\)」。 實作上 \(\rho\) 來自作業系統的亂數來源，例如 Python 的 、Rust 的 、Linux 的 。

這個觀點有三個用處：

  1. 分析：所有「機率」都可以明確地說成「對 \(\rho\)（以及 \(\sk\)、敵手的隨機帶）取機率」。

  2. 正確性的量化：對隨機化加密，「正確」可以要求對每一個 \(\rho\) 都成立（完美正確），或以壓倒性的機率成立（KL-IMC 允許後者）。

  3. 安全性：§[sec:ind] 會證明確定性加密不可能通過 IND-CPA。講義 p. 3 的評語「歷史密碼的一個根本問題是 \(\Enc\) 是確定性的」就是這個意思——同一個明文每次都加密成同一個密文，重複與模式會洩漏。

收件人需要一個明確的答案：這個密文到底是什麼訊息？如果 \(\Dec\) 擲硬幣，「正確性」就只能是機率性的，而且沒有任何好處——任何隨機化的 \(\Dec\) 都可以把隨機帶固定成全零而不失正確性。 同理，\(\Vf\) 的輸出是「接受／拒絕」的判決，必須確定。 反過來，\(\KGen\) 必須隨機：若金鑰是確定地產生，人人都能算出同一把金鑰（這也是 Kerckhoffs 第二條原則的要求：演算法公開，秘密只在金鑰）。

正確性（correctness，講義 p. 4）

\(\SKE=(\KGen,\Enc,\Dec)\) 是，若 \[\forall\,\sk\in\calK,\ \forall\,m\in\calM:\qquad \Dec(\sk,\Enc(\sk,m))=m .\] 若 \(\Enc\) 是隨機化的，等式應對所有隨機性 \(\rho\) 成立：\(\Dec(\sk,\Enc(\sk,m;\rho))=m\)。

注意量詞：是所有金鑰、所有訊息，不是「大部分」。這條性質講的是「用同一把 \(\sk\) 加密再解密會回到原訊息」；它完全沒有提到敵手。

\(\Enc(\sk,m)=m\)、\(\Dec(\sk,c)=c\) 滿足正確性定義的每一個字，卻什麼都沒保護。第一週的「什麼都不做」方案在這裡再次出現，提醒我們：語法與正確性只是入場券，安全性需要另外定義（§[sec:ind]）。

為什麼需要 \(\bot\)？

正式定義允許 \(\Dec\) 輸出 \(\bot\)。這不是裝飾，有三個理由：

  • 不在像集裡的密文：\(\Esk\colon\calM\to\calC\) 不一定是滿射（Problem 1 (vi)）。對一個從未被任何訊息加密出來的 \(c\in\calC\)，\(\Dec\) 必須說點什麼——\(\bot\) 就是「這不是合法密文」。

  • 格式錯誤：長度不對、填充（padding）不合法、版本欄位不認得。

  • 完整性失敗：第一週的 Encrypt-then-MAC 中，\(\Vf\) 失敗時「先驗證、後解密」的 \(\Dec'\) 就輸出 \(\bot\)。到了 §[sec:ind] 的 IND-CCA 遊戲，解密預言機對挑戰密文也回 \(\bot\)。

正確性只約束「合法產生」的密文：對 \(c\gets\Enc(\sk,m)\) 必須回 \(m\)；對其他 \(c\)，\(\Dec\) 可以回 \(\bot\)，也可以回任何東西（但 §[sec:ind] 會看到「回任何東西」常常是安全漏洞的來源）。

  • 能一字不差地寫出 SKE 的語法與正確性，並標出哪個演算法「一定隨機」「可能隨機」「一定確定」。

  • 能解釋 \(\Enc(\sk,m;\rho)\) 記號：隨機化 = 確定性演算法 + 隨機輸入 \(\rho\in\calR=\bits^r\)。

  • 能說明 \(\bot\) 的用途，以及為何正確性只對「由 \(\Enc\) 產生的密文」有要求。