所有安全定義都長這樣：「沒有有效率的敵手能以明顯異於 \(\tfrac12\)（或 \(0\)）的機率獲勝」。講義 p. 23 把兩個關鍵詞翻譯成術語：有效率 = PPT，明顯異於 = 不可忽略。講義說本課程不要求形式定義，但理解它們能避免許多誤解。
安全參數
現代密碼學不是定義「一個」方案，而是定義由 \(n\) 索引的一族方案：\(n\) 通常就是金鑰長度（\(\calK=\bits^n\)）。所有東西都是 \(n\) 的函數：敵手的執行時間、獲勝機率、金鑰空間大小。慣例上把 \(1^n\)（\(n\) 個 1 的字串）當輸入交給演算法，使「多項式時間」以 \(n\) 為基準。
有效率 = PPT
演算法 \(\adv\) 是的，若它可以使用隨機性（擲硬幣），且存在多項式 \(p\) 使得對所有輸入，\(\adv\) 的執行步數至多 \(p(n)\)，\(n\) 是輸入長度（安全參數）。
為什麼多項式？它與計算模型無關（圖靈機、RAM、C 程式互相模擬只差多項式），且在組合下封閉：PPT 呼叫 PPT 多項式次仍是 PPT。這讓「歸約」（用敵手 \(\adv\) 造出敵手 \(\bdv\)）保持在同一個類別裡——Week 1 Problem 1 (viii) 的 \(\bdv\) 就是這樣。
暴力搜尋不是 PPT：嘗試全部 \(2^n\) 把金鑰需要 \(2^n\) 步，不是任何多項式。這正是為什麼「金鑰空間有限所以理論上總能破」不構成對計算安全的威脅。
警告：\(n^{100}\) 也是多項式。漸近定義不在乎常數與次數，所以「PPT 敵手無法攻破」在實務上必須搭配具體的數字（見 §1.4）。
明顯異於 = 不可忽略
函數 \(f\colon\N\to\mathbb{R}_{\ge0}\) 是，若對每一個正多項式 \(p\)，存在 \(N\) 使得對所有 \(n>N\)， \[f(n)<\frac{1}{p(n)} .\] 也就是：\(f\) 終究（eventually）比任何多項式的倒數都小。記作 \(f(n)=\negl(n)\)。
L4.2cmC2.2cmL7.6cm 函數 & 可忽略？ & 理由
\(2^{-n}\) & & 對任何 \(p\)，\(2^n\) 終究超過 \(p(n)\)
\(2^{-\sqrt n}\)、\(n^{-\log_2 n}\) & & 比任何多項式倒數小，但比 \(2^{-n}\) 大得多（「次指數」）
\(1/n^2\)、\(1/n^{100}\) & & 取 \(p(n)=n^{101}\) 就不成立
\(2^{-30}\)（常數） & & 常數不隨 \(n\) 變小；在實務上 \(2^{-30}\) 也不夠小
\(1/\text{poly}(n)\) & & 定義就是要排除這類
\(\negl_1(n)+\negl_2(n)\) & & 引理 [lem:negl-closure]
\(p(n)\cdot\negl(n)\)（\(p\) 多項式）& & 引理 [lem:negl-closure]——這就是為什麼允許敵手查詢多項式次
若 \(f,g\) 可忽略、\(p\) 是正多項式，則 \(f+g\) 與 \(p\cdot f\) 都可忽略。
Proof. 任取正多項式 \(q\)。對 \(f\) 用 \(2q\)、對 \(g\) 用 \(2q\) 得 \(N_1,N_2\)；當 \(n>\max(N_1,N_2)\) 時 \(f(n)+g(n)<\frac{1}{2q(n)}+\frac{1}{2q(n)}=\frac1{q(n)}\)。對 \(p\cdot f\)：對 \(f\) 用多項式 \(p\cdot q\) 得 \(N\)；當 \(n>N\) 時 \(p(n)f(n)<p(n)\cdot\frac{1}{p(n)q(n)}=\frac1{q(n)}\)。 ◻
漸近安全 vs. 具體安全
L2.6cmL5.6cmL6.0cm & 漸近（asymptotic） & 具體（concrete）
句型 & 對每個 PPT \(\adv\)，\(\Adv(\adv)\le\negl(n)\) & 任何執行時間 \(\le t\) 的 \(\adv\)，\(\Adv(\adv)\le\eps\)（「\((t,\eps)\)-安全」）
例子 & 「AES 是偽隨機排列」（以 \(n\) 為金鑰長度的一族）& 「AES-128：\(t=2^{100}\) 時 \(\eps\le 2^{-28}\)」（即 \(t/\eps\approx2^{128}\)）
優點 & 乾淨、與機器無關、組合容易 & 可以設定金鑰長度、估計真實風險
缺點 & 隱藏常數、說不出「幾位元安全」& 數字依附於計算模型與年代（摩爾定律、GPU、量子）
課堂定義採漸近版本，但實務上每個標準都附具體數字：「128 位元安全」意指最佳已知攻擊的 \(t/\eps\approx2^{128}\)。Kerckhoffs 的 「matériellement, sinon mathématiquement」恰好對應這個區分：數學上不可破譯 = 資訊論安全（即使無限算力也破不了，如一次性密碼本）；實務上不可破譯 = 計算安全（PPT 敵手破不了）。
「安全 = 不可能被破」。錯：定義允許可忽略的機率與超多項式的時間。暴力搜尋總是存在。
「PPT 敵手不能贏 = 任何真實程式不能贏」。錯：\(n^{100}\) 是多項式；真實保證要看具體數字。
「\(\tfrac12+2^{-30}\) 的勝率沒什麼」。錯（在實務上）：\(2^{-30}\) 是常數，不可忽略；且敵手重複 \(2^{30}\) 次就能放大優勢。
PPT：有隨機性、時間是輸入長度（安全參數）的多項式。
negligible：對每個多項式 \(p\) 終究小於 \(1/p(n)\)；舉得出可忽略與不可忽略的例子各兩個。
能把講義的兩句話翻譯成形式：「\(\Prob[\text{win}]\le\tfrac12+\negl(n)\)」「\(\Prob[\text{win}]\le\negl(n)\)」。