課程資訊
L3.2cmL11.6cm 課程 & 6CCS3CIS Cryptography（King’s College London，2025/26）
講師 & Ngoc Khanh Nguyen、Eamonn W. Postlethwaite
本週講義 & Second lecture（2025 年 10 月 9 日，60 張投影片含逐步顯示，實際內容 24 頁）
本週習題 & Problem Set 2（2025 年 10 月 6 日，三大題共 14 小題）
課本 & Katz & Lindell, Introduction to Modern Cryptography, 3rd ed.（簡稱 KL-IMC）
本週對應章節 & KL-IMC §1.3（Kerckhoffs 原則）、§3.1（計算安全、PPT、negligible）、§3.2.1（IND-EAV）、§3.4.2（IND-CPA）、§4.2（EUF-CMA）、§5.1.2（IND-CCA）
本週在整門課的位置
第一週用故事（Francis 與 Henry 的羊皮紙）建立直覺：語法 → 正確性 → 安全性三層分開、保密不等於完整、安全定義要同時說清「敵手不能做什麼」與「敵手能做什麼」。 第二週把這些直覺全部寫成數學：
SKE 與 MAC 的正式語法（哪些演算法是隨機的、哪些是確定的、\(\bot\) 是什麼）；
空間 \(\calK,\calM,\calC,\calT\) 到底是什麼（集合、字母表、Kleene 星號）；
把 \(\Enc(\sk,\cdot)\) 當成函數來看：單射、滿射、雙射，以及它們的計數；
1883 年 Kerckhoffs 的六條原則，以及其中第二條為何成為現代密碼學的基石；
用遊戲（game）定義安全：IND-EAV、IND-CPA、IND-CCA（加密）與 EUF-CMA（MAC）；
「有效率的敵手」（PPT）與「可忽略的機率」（negligible）這兩個詞的精確意義。
下週開始的歷史密碼（Caesar、Vigenère 等）會不斷回到這些定義：它們為什麼不安全？用哪一個遊戲可以精確說明？
學習目標
讀完本教材你應該能夠：
默寫 SKE 與 MAC 的正式定義（含空間、隨機性、正確性），並解釋為何 \(\Dec\) 與 \(\Vf\) 是確定性的、為何需要 \(\bot\)。
判斷一個函數是否單射／滿射／雙射，計算 \(\calM\to\calC\) 的函數、單射與雙射個數，並證明「解密無歧義 \(\Rightarrow\) \(\Esk\) 單射 \(\Rightarrow\) \(\abs{\calC}\ge\abs{\calM}\)」。
列出 Kerckhoffs 六原則，分辨「Kerckhoffs 原則」（第二條）與其他五條，並用現代語言重寫。
畫出 IND-EAV、IND-CPA、IND-CCA、EUF-CMA 四個遊戲，解釋每一行規則存在的理由（\(\abs{m_0}=\abs{m_1}\)、\(c\ne c_b\)、\(m'\notin\calQ\)、為何是 \(\tfrac12\) 與 \(0\)）。
證明「確定性加密不可能 IND-CPA 安全」，並說明三個 IND 概念的強弱關係與分離例子。
解釋 PPT 與 negligible 的定義、舉例，並說明漸近安全與具體安全的差別。
完整解答 Problem Set 2 的全部 14 小題，包括用程式驗證 Caesar 密碼的暴力破解極限。
教材結構
第一部分（§[sec:ske]–§[sec:adversaries]）：依講義順序精讀，每節標明對應的講義頁碼（講義右下角頁碼，共 24 頁），並補充 KL-IMC 與原始文獻的內容。
第二部分（§[sec:p1]–§[sec:p3]）：Problem Set 2 逐題詳解。每題先完整引述原題，再給出可直接寫在作業或考卷上的「標準答案」，最後補充延伸討論。
第三部分：一頁重點整理、中英術語對照表、自我測驗與參考資料。
記號慣例
L4.2cmL10.6cm 記號 & 意義
\(x\gets X\) & 從集合 \(X\) 均勻隨機抽出 \(x\)；若 \(X\) 是隨機演算法，表示執行它並把輸出記為 \(x\)
\(c\gets\Enc(\sk,m)\) vs. \(c=\Enc(\sk,m)\) & 箭頭表示 \(\Enc\) 可能是隨機的；等號表示確定性
\(\Enc(\sk,m;\rho)\) & 把隨機性 \(\rho\in\calR\) 明寫成輸入後，\(\Enc\) 變成確定性函數
\(\Esk(\cdot)\)、\(\Dsk(\cdot)\) & 固定金鑰後的函數 \(\Esk\colon\calM\to\calC\)、\(\Dsk\colon\calC\to\calM\cup\{\bot\}\)
\(\alpha^n\)、\(\alpha^*\)、\(\varepsilon\) & 字母表 \(\alpha\) 上長度 \(n\) 的字串、任意長度的字串（Kleene 星號）、空字串
\(\abs{X}\)、\(\abs{m}\) & 有限集合的元素個數；字串的長度
\(\OEnc,\ \ODec,\ \OTag\) & 加密／解密／標籤預言機（oracle）：敵手可呼叫但看不到內部的黑盒
\(\game{IND-EAV}\) 等 & 安全遊戲的名稱；「\(\SKE\) 是 安全的」指沒有 PPT 敵手能以明顯高於 \(\tfrac12\) 的機率獲勝
\(\negl(n)\) & 可忽略函數：比任何多項式的倒數都小（§[sec:adversaries]）
– & Kerckhoffs 的第一至第六條原則（§[sec:kerckhoffs]）
講義本身很精簡（許多頁只有一兩句話），真正的內容在「為什麼這樣定義」。建議讀每一節時先遮住解釋，自己回答每個「Why?」（為什麼 \(\Dec\) 要確定？為什麼 \(\tfrac12\)？為什麼 \(0\)？），再對照教材。 第二部分的 Problem 2 附有可執行的 Python 程式，請務必自己跑一次。