一頁看懂第二週
必背定義
L3.4cmL11.0cm 概念 & 一句話定義
SKE 語法 & \(\sk\gets\KGen\)；\(c\gets\Enc(\sk,m)\)（或 \(=\)）；\(m/\bot=\Dec(\sk,c)\)；空間 \(\calK,\calM,\calC\)
隨機化演算法 & 確定性演算法 + 隨機輸入 \(\rho\in\calR=\bits^r\)：\(\Enc(\sk,m;\rho)\)
SKE 正確性 & \(\forall\sk\in\calK,\forall m\in\calM\)：\(\Dec(\sk,\Enc(\sk,m))=m\)
MAC 語法／正確性 & \(\ik\gets\KGen\)；\(\tau=\Tag(\ik,m)\)；\(\Vf(\ik,m,\tau)\in\{0,1\}\)；\(\Vf(\ik,m,\Tag(\ik,m))=1\)
典範驗證 & \(\Vf\) 重算 \(\tau'=\Tag(\ik,m)\) 並比對；需要確定性 \(\Tag\)
字母表／Kleene 星號 & \(\alpha^n\) 長度 \(n\) 字串、\(\abs{\alpha^n}=\abs\alpha^n\)；\(\alpha^*=\bigcup_{i\in\N}\alpha^i\ni\varepsilon\)
單射／滿射／雙射 & \(f(x)=f(x')\Rightarrow x=x'\)；\(f(X)=Y\)；兩者皆是
無歧義解密 & \(\Esk\) 單射（對每把 \(\sk\)）；有限時 \(\abs{\calC}\ge\abs{\calM}\)；單射亦充分
Kerckhoffs 原則 & 安全只能依賴金鑰保密，不能依賴演算法保密（第二條）
IND-EAV & \(\adv\) 送等長 \(m_0,m_1\)，收 \(c_b\gets\Enc(\sk,m_b)\)，猜 \(b\)；\(\Prob[\text{win}]\le\tfrac12+\negl\)
IND-CPA／IND-CCA & 同上，加 \(\OEnc\)／加 \(\OEnc,\ODec\)（\(\ODec(c_b)=\bot\)）
EUF-CMA & \(\adv^{\OTag}\) 輸出 \((m',\tau')\)，贏若 \(\Vf=1\) 且 \(m'\notin\calQ\)；\(\Prob[\text{win}]\le\negl\)
PPT & 有隨機性、執行時間是安全參數 \(n\) 的多項式
negligible & 對每個多項式 \(p\)，終究 \(f(n)<1/p(n)\)；例 \(2^{-n}\)；反例 \(1/n^2\)
唯一解距離 & \(U=\log_2\abs{\calK}/D\)；Caesar \(\approx1.5\) 字母、替換 \(\approx28\) 字母
常見誤區
把「\(\Enc\) 可能隨機」寫成「\(\Dec\) 可能隨機」。\(\Dec\) 與 \(\Vf\) 永遠確定性。
以為正確性只要「大部分」訊息成立。是對所有 \(\sk\)、所有 \(m\)。
混淆單射與滿射的方向。單射 \(\Rightarrow\abs{Y}\ge\abs{X}\)（箭頭不合流，右邊夠大）；滿射 \(\Rightarrow\abs{X}\ge\abs{Y}\)。
以為無歧義解密需要滿射或 \(\abs{\calC}=\abs{\calM}\)。只需要單射；\(\bot\) 處理像集之外的密文。
把 Kerckhoffs 原則說成「演算法必須公開」。是「即使公開也要安全」；也不是「金鑰可以公開」。
IND 遊戲忘記 \(\abs{m_0}=\abs{m_1}\) 或 CCA 忘記 \(\ODec(c_b)=\bot\)。前者因長度無法隱藏，後者排除平凡勝利。
以為 IND-EAV 安全的方案可以重複使用金鑰。一次性密碼本是 IND-EAV（單次）卻不是 IND-CPA；多訊息安全需要隨機化。
把「基準 \(\tfrac12\)」套到 EUF-CMA。偽造是創造，不是二選一，基準是 \(0\)。
以為 \(1/n^{10}\) 可忽略、\(2^{-30}\) 可忽略。多項式倒數與常數都不可忽略。
以為金鑰空間大就安全。\(26!\) 的替換密碼與 \(N!\) 的碼書都敗給頻率分析； 是對所有攻擊。