語法
一個是三元組 \(\MAC=(\KGen,\Tag,\Vf)\)，附帶金鑰空間 \(\calK\)、訊息空間 \(\calM\) 與 \(\calT\)。
\(\KGen\) 是隨機化演算法，輸出 \(\ik\in\calK\)：\(\ik\gets\KGen\)。
\(\Tag\) 是可能隨機化的演算法，輸入 \(\ik\in\calK\)、\(m\in\calM\)，輸出標籤 \(\tau\in\calT\)：\(\tau\gets\Tag(\ik,m)\) 或 \(\tau=\Tag(\ik,m)\)。
\(\Vf\) 是確定性演算法，輸入 \(\ik\in\calK\)、\(m\in\calM\)、\(\tau\in\calT\)，輸出 \(0\)（拒絕）或 \(1\)（接受）。
與 SKE 對照：\(\Enc\leftrightarrow\Tag\) 產生東西、\(\Dec\leftrightarrow\Vf\) 檢查東西；差別在 \(\Vf\) 不需要「還原」什麼，只需判決。注意 MAC 的輸出 \(\tau\) 是附加在 \(m\) 旁邊傳送的，訊息本身不被隱藏。
確定性 \(\Tag\) 與典範驗證（講義 p. 6）
本課程只考慮確定性的 \(\Tag\)，即 \(\tau=\Tag(\ik,m)\)。此時可以「不失一般性」地假設 \(\Vf\) 是：
\(\Vf(\ik,m,\tau)\) 的做法是：計算 \(\tau'=\Tag(\ik,m)\)；若 \(\tau=\tau'\) 輸出 \(1\)，否則輸出 \(0\)。
講義問：「典範驗證需要確定性的 \(\Tag\)，為什麼？」
設 \(\MAC\) 使用典範驗證。則 \(\MAC\) 正確（對所有 \(\ik,m\)，\(\Vf(\ik,m,\Tag(\ik,m))=1\)）若且唯若對每一組 \((\ik,m)\)，\(\Tag(\ik,m)\) 只有一個可能的輸出值，亦即 \(\Tag\) 是確定性的。
Proof. （\(\Leftarrow\)）若 \(\Tag\) 確定，驗證時重新計算得到同一個 \(\tau'=\Tag(\ik,m)=\tau\)，故輸出 \(1\)。
（\(\Rightarrow\)）反之，若存在 \((\ik,m)\) 使 \(\Tag(\ik,m)\) 可能輸出兩個不同值 \(\tau_1\ne\tau_2\)（各以正機率出現），則發送端可能產生 \(\tau_1\)，驗證端重算卻可能得到 \(\tau_2\)，此時 \(\tau_1\ne\tau_2\)，\(\Vf\) 輸出 \(0\)：合法標籤被拒絕，正確性以正機率失敗。 ◻
若 \(\Tag\) 確定且 \(\MAC\) 正確，任何 \(\Vf\) 都必須接受 \(\tau=\Tag(\ik,m)\)（這是正確性的要求）；典範的 \(\Vf\) 則只接受這一個值。換言之，在所有正確的驗證演算法中，典範驗證接受的集合最小，因此它永遠不會比其他 \(\Vf\) 更不安全。第一週 Problem 1 (vii) 已經證明：典範驗證的 MAC 一旦 EUF-CMA 安全，就自動是強不可偽造（SUF-CMA）的。
隨機化 \(\Tag\) 在理論上存在（例如標籤附帶一個隨機 nonce，\(\Vf\) 用 nonce 重算），但 HMAC、CMAC、Poly1305 等實務 MAC 都是確定性的，典範驗證就是它們實際的驗證方式——實作上要用常數時間比較（Week 1 §4.4），否則 \(\tau=\tau'\) 的逐位元組比較會洩漏時間側通道。
正確性（講義 p. 7）
\(\MAC=(\KGen,\Tag,\Vf)\) 正確，若 \[\forall\,\ik\in\calK,\ \forall\,m\in\calM:\qquad \Vf(\ik,m,\Tag(\ik,m))=1 .\]
永遠輸出 \(1\) 的 \(\Vf\) 滿足正確性，但任何人都能「偽造」任何訊息。第一週 Problem 1 (v) 證明過：正是因為正確性保證「合法標籤一定被接受」，所以「對任何訊息都不可偽造」 是不可能達成的目標——我們只能要求新訊息不可偽造（§[sec:eufcma]）。
寫出 MAC 的語法、正確性；知道本課程假設 \(\Tag\) 確定、\(\Vf\) 典範。
能用一句話回答「為什麼典範驗證需要確定性 \(\Tag\)」：否則重算的 \(\tau'\) 可能不等於合法的 \(\tau\)，正確性失敗。