建議先不看解答，每題寫下自己的答案再比對。
在 \(\KGen,\Enc,\Dec,\Tag,\Vf\) 五個演算法中，哪些一定隨機、哪些可以隨機、哪些一定確定？為什麼 \(\Dec\) 不能隨機？\(\bot\) 在定義裡扮演什麼角色？
\(\KGen\) 一定隨機（否則人人算得出同一把金鑰）；\(\Enc\)、\(\Tag\) 可以隨機（本課的 \(\Tag\) 取確定性）；\(\Dec\)、\(\Vf\) 一定確定。\(\Dec\) 若隨機，正確性只能是機率性的且毫無好處——可把隨機帶固定而不失正確性；收件人需要明確答案。\(\bot\) 讓 \(\Dec\) 能對像集之外、格式錯誤或驗證失敗的密文給出「非法」判決，使 \(\Esk\) 不必滿射（Problem 1 (vi)）。
令 \(f\colon\bits^3\to\bits^2\) 為「丟掉最後一個位元」。\(f\) 單射嗎？滿射嗎？\(\bits^2\to\bits^3\) 的函數有幾個？其中單射有幾個？\(f\) 能是某個正確 SKE 的 \(\Esk\) 嗎？
\(f\) 不單射（\(000,001\mapsto00\)）、滿射（每個 2 位元串都有原像）。\(\bits^2\to\bits^3\) 的函數有 \(8^4=4096\) 個，單射有 \(8\cdot7\cdot6\cdot5=1680\) 個（\(\binom84\cdot4!=70\cdot24\)）。\(f\) 不單射，故不可能是正確 SKE 的 \(\Esk\)（定理 [thm:unambiguous-injective]）；方向相反的單射 \(\bits^2\to\bits^3\) 則可以。
證明或反駁：若對每把 \(\sk\)，\(\Esk\) 都是單射，則 \((\sk,m)\mapsto\Enc(\sk,m)\) 也是單射。
反駁。一次性密碼本 \(\Enc(\sk,m)=\sk\oplus m\)（\(\calK=\calM=\calC=\bits^n\)）：每個 \(\Esk\) 是雙射，但 \(\Enc(\sk,m)=\Enc(\sk\oplus1^n,m\oplus1^n)\)，不單射。事實上跨金鑰的碰撞是保密的來源：同一個 \(c\) 可由任何 \(m\)（配適當金鑰）產生。單射只是「每把金鑰各自」的要求。
下列各情況違反了哪一條原則？(a) 金鑰印在卡片上放在皮夾；(b) 系統需要三名操作員同時在場；(c) 加密只能透過傳真機運作；(d) 廠商宣稱「我們的演算法保密，所以更安全」；(e) 操作手冊有 40 頁必須逐條遵守的規則。
(a) （金鑰應不靠筆記）；(b) （一人可用）；(c) （相容於通訊媒介）；(d) （安全不得依賴演算法保密；若同時用強演算法且不依賴保密，則不違反，但缺乏公眾審查通常也連帶危及 ）；(e) （不應要求一長串規則）。
方案把兩個 \(n\) 位元區塊的訊息 \(m=m_1\concat m_2\) 加密為 \(\Enc(\sk,m)=(m_1\oplus\sk)\concat(m_2\oplus\sk)\)，\(\sk\in\bits^n\)。寫出一個必勝的 IND-EAV 敵手。
送 \(m_0=0^n\concat0^n\)、\(m_1=0^n\concat1^n\)。收到 \(c_b=c_1\concat c_2\)：若 \(c_1=c_2\) 輸出 \(0\)，否則輸出 \(1\)。\(b=0\) 時 \(c_1=c_2=\sk\)；\(b=1\) 時 \(c_2=\sk\oplus1^n\ne\sk=c_1\)。獲勝機率 \(1\)。教訓：重複使用金鑰串流讓「兩段明文是否相同」洩漏——這就是 Caesar「\(\mathrm{aa}\) vs. \(\mathrm{ab}\)」攻擊的位元版。
假設 \(\Enc\) 只使用 \(r=10\) 位元的隨機性 \(\rho\)（其餘確定）。說明一個用約 \(2^{10}\cdot10\) 次 \(\OEnc\) 查詢、幾乎必勝的 IND-CPA 敵手。這對實務上 nonce 的長度有何啟示？
固定 \(m_0\ne m_1\)。向 \(\OEnc(m_0)\) 查詢約 \(2^{10}\ln2^{10}\approx7000\) 次（優惠券收集），以高機率收集到 \(m_0\) 的全部 \(\le2^{10}\) 個可能密文，記為集合 \(S\)。送挑戰 \((m_0,m_1)\)，若 \(c_b\in S\) 輸出 \(0\)，否則 \(1\)。\(b=0\) 時 \(c_b\in S\)（已收集完整）；\(b=1\) 時 \(c_b\) 是 \(m_1\) 的密文，由無歧義解密不可能等於任何 \(m_0\) 的密文，故 \(\notin S\)。因此隨機性空間必須大到無法枚舉：這就是 nonce 要 96–128 位元、且絕不能重複的原因。
IND-CCA 遊戲只禁止 \(\ODec(c_b)\)，而非禁止挑戰後的一切解密查詢。後者是另一個（較弱的）定義，為什麼講義採用前者？
只允許挑戰前查詢的版本稱為 CCA1（「午餐時間攻擊」）；講義的版本是 CCA2（適應性）。真實攻擊幾乎都是適應性的：padding oracle 攻擊者先拿到目標密文 \(c_b\)，再送出它的變體 \(c'\ne c_b\) 給伺服器觀察反應。CCA1 擋不住這類攻擊，CCA2 可以；而 \(\ODec(c_b)=\bot\) 是唯一必要的例外（否則平凡獲勝）。
某系統為省頻寬，把 HMAC 的輸出截成 16 位元當標籤。它是 EUF-CMA 安全的嗎？漸近與具體兩個角度各怎麼說？
敵手隨便挑新訊息 \(m'\) 與隨機 \(\tau'\in\bits^{16}\)，獲勝機率 \(2^{-16}\)。若標籤長度固定為 16（不隨安全參數增長），\(2^{-16}\) 是常數、不可忽略——漸近上不安全。具體上，線上協定被試 \(2^{16}=65{,}536\) 次完全可行，所以也不安全。標籤長度應隨 \(n\) 增長，實務上至少 64、通常 128 位元（\(\tau\in\calT\) 的大小決定「明顯異於零」裡的下限）。
判斷下列函數是否可忽略：(a) \(2^{-n/2}\)；(b) \(n^{-3}\)；(c) \(2^{-(\log_2 n)^2}\)；(d) \(1/n!\)。另證明：若 \(f\) 可忽略，則 \(\sqrt f\) 也可忽略。
(a) 是（\(2^{n/2}\) 終究超過任何多項式）；(b) 否（取 \(p(n)=n^4\)）；(c) 是：\(2^{-(\log_2n)^2}=n^{-\log_2 n}\)，指數 \(\log_2n\to\infty\) 超過任何固定次數；(d) 是（\(n!\ge2^n\) 對 \(n\ge4\)）。 證明：任取多項式 \(p\)，對 \(f\) 用多項式 \(p^2\) 得 \(N\)，當 \(n>N\) 時 \(f(n)<1/p(n)^2\)，開根號得 \(\sqrt{f(n)}<1/p(n)\)。
(a) 金鑰為 5 個字母的 Vigenère 密碼（\(\abs\calK=26^5\)），用 \(D\approx3.2\) 估計唯一解距離。(b) 若極短字串的有效冗餘只有 \(D\approx1.4\)，長度 2 的 Caesar 密文預期有幾把偽金鑰？這與 Problem 2 (i) 的結果一致嗎？
(a) \(\log_2 26^5=5\times4.70\approx23.5\) 位元，\(U\approx23.5/3.2\approx7.3\) 個字母：約 8 個字母的密文就足以唯一決定金鑰（不過找到金鑰仍需 Kasiski／頻率分析，下週）。(b) \(\bar s\approx25\cdot2^{-1.4\times2}\approx25\cdot0.144\approx3.6\) 把，與 (i) 找到的 6 個一般單字（扣掉正確的一個約 5 個偽解）同一數量級；允許縮寫時 \(D\to0\)，\(\bar s\to25\)，與「23 個可讀」一致。