概率论与统计 — 安全证明的工具箱

日期: 2026-11-09 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #概率论 #ROM #PRF #安全游戏

---

今日目标

---

一、动机

密码学安全证明本质："如果攻击者赢概率不可忽略，则我们可破某个困难假设；矛盾，故攻击者赢概率可忽略"。

这需要：

• 概率不等式 把复杂事件概率 bound 住
• 可忽略函数 形式化"足够小"
• 安全游戏 把直觉攻击转可证明

---

二、严格定义

2.1 期望与方差

$$E[X] = \sum_x x \cdot P(X=x), \quad \text{Var}(X) = E[X^2] - E[X]^2$$

线性性：$E[X+Y] = E[X] + E[Y]$（不需独立）。 乘性（仅独立）：$E[XY] = E[X]E[Y]$。

2.2 经典不等式

Markov 不等式

$X \ge 0, a > 0$： $$P(X \ge a) \le \frac{E[X]}{a}$$

Chebyshev 不等式

$$P(|X - E[X]| \ge a) \le \frac{\text{Var}(X)}{a^2}$$

Chernoff Bound（独立 Bernoulli）

$X = \sum X_i$, $X_i$ 独立 0/1，$\mu = E[X]$。对 $\delta > 0$： $$P(X \ge (1+\delta)\mu) \le \exp\left(-\frac{\delta^2 \mu}{2+\delta}\right)$$

指数衰减，比 Chebyshev 紧。

Hoeffding 不等式

$X_i \in [a_i, b_i]$ 独立，$S = \sum X_i$： $$P(|S - E[S]| \ge t) \le 2\exp\left(-\frac{2t^2}{\sum(b_i - a_i)^2}\right)$$

Union Bound

$$P\left(\bigcup_i A_i\right) \le \sum_i P(A_i)$$

简单但极有用：把"任一坏事发生"概率 bound 住。

2.3 Negligible 函数

定义 2.3：函数 $\nu: \mathbb{N} \to [0,1]$ 是 negligible 若 $\forall$ 多项式 $p$, $\exists N_0$, $\forall n \ge N_0$: $$\nu(n) < 1/p(n)$$

记 $\text{negl}(n)$。

例：$2^{-n}, n^{-\log n}$ negligible；$1/n^{100}$ 不是。

性质：

• negligible + negligible = negligible
• poly × negligible = negligible

2.4 计算不可区分

定义 2.4：分布族 ${D_n}, {D'_n}$ 计算不可区分若 $\forall$ PPT 区分器 $\mathcal{D}$： $$|P[\mathcal{D}(D_n) = 1] - P[\mathcal{D}(D'_n) = 1]| \le \text{negl}(n)$$

记 $D_n \approx_c D'_n$。

2.5 PRG / PRF / PRP

PRG (Pseudo-Random Generator)

$G: {0,1}^n \to {0,1}^{p(n)}$, $p(n) > n$，输出 $G(s)$ 与均匀 ${0,1}^{p(n)}$ 计算不可区分（$s \in_R {0,1}^n$）。

PRF (Pseudo-Random Function)

$F_K: {0,1}^* \to {0,1}^n$ 索引 by 密钥 $K$。攻击者 oracle 访问，分不出 $F_K$ vs 真随机函数 RO。

形式： $$\text{Adv}^{\text{prf}}_F(\mathcal{A}) = |P[\mathcal{A}^{F_K} = 1] - P[\mathcal{A}^{\text{RF}} = 1]| \le \text{negl}$$

PRP (Pseudo-Random Permutation)

像 PRF 但是双射。AES 是候选 PRP。

PRP / PRF 切换引理：在 $q$ 查询内 PRP 与 PRF 不可区分到 $q^2/2^n$（birthday）。

2.6 安全游戏

典型 IND-CPA 游戏：

1. 挑战者生成 $K$
2. 攻击者发若干 $(m_i, m_i')$ 对，挑战者发 $\text{Enc}_K(m_i)$（学习阶段）
3. 攻击者发挑战 $(m_0, m_1)$
4. 挑战者均匀选 $b \in {0,1}$，发 $c^* = \text{Enc}_K(m_b)$
5. 攻击者输出 $b'$
6. 攻击者赢若 $b = b'$

优势：$\text{Adv}(\mathcal{A}) = |P[b=b'] - 1/2|$。安全 $\Leftrightarrow$ Adv negligible。

---

三、推导：归约证明模板

3.1 RSA-OAEP 安全归约（草图）

目标：若 RSA 假设成立，OAEP IND-CCA2 安全。

证明思路：

1. 假设存在攻击者 $\mathcal{A}$，IND-CCA2 优势 $\epsilon$（不可忽略）
2. 构造 RSA 求逆器 $\mathcal{B}$ 利用 $\mathcal{A}$
3. $\mathcal{B}$ 模拟 ROM、解密 oracle、挑战
4. 抽检 $\mathcal{A}$ 的 hash 查询找出 RSA pre-image
5. 计算 $\mathcal{B}$ 成功率 $\ge \epsilon - q^2/2^n$
6. 由假设 RSA 成功率 negligible，矛盾

结论：$\epsilon$ negligible，OAEP 安全。$\blacksquare$

3.2 PRP/PRF 切换引理

$P, F: {0,1}^n \to {0,1}^n$。 $$|P[\mathcal{A}^P = 1] - P[\mathcal{A}^F = 1]| \le \binom{q}{2} / 2^n$$

证：固定 oracle $P$。$\mathcal{A}$ 的 $q$ 查询碰撞概率 $\le q^2/2 \cdot 2^{-n}$（生日）。无碰撞时 $P, F$ 输出同分布。$\blacksquare$

---

四、随机预言机模型 (ROM)

4.1 定义

把 hash $H$ 看作"oracle"——查询 $x$ 返回 fresh 均匀 $H(x) \in {0,1}^n$，前次查询答案缓存。

4.2 用途

ROM 下证 Schnorr / Fiat-Shamir / RSA-PSS / OAEP 等。证明步骤：

1. 模拟 ROM：表 $T$ 记录 $(x, H(x))$
2. Programmability：模拟器可在任何时点决定 $H(x)$ 的值
3. Observability：所有查询记录在 $T$，extractor 可读

4.3 与实际 hash 的差距

• ROM 是理想模型；实际 SHA-256 是确定函数
• Canetti-Goldreich-Halevi 1998：存在 ROM 安全但任何具体 hash 实例化不安全的协议
• 实践共识：ROM 证明是"启发式 evidence"，不是绝对保证

---

五、代码示例

"""
Day 192: 概率工具箱演示
- Chernoff/Hoeffding 数值验证
- Negligible 函数判断
- PRF distinguisher 模拟
"""
import random
from math import exp, log, sqrt
from collections import defaultdict
from hashlib import sha256


# ============ 1. Chernoff 验证 ============
def chernoff_demo(n: int = 1000, p: float = 0.5, delta: float = 0.1, trials: int = 10000):
    """模拟 n 次 Bernoulli(p), 检查 Chernoff bound"""
    mu = n * p
    threshold = (1 + delta) * mu
    bound = exp(-delta * delta * mu / (2 + delta))

    over = 0
    for _ in range(trials):
        s = sum(random.random() < p for _ in range(n))
        if s >= threshold:
            over += 1
    empirical = over / trials
    print(f"Chernoff: P[X ≥ {threshold:.0f}] empirical={empirical:.4f}, bound={bound:.4f}")


# ============ 2. Negligible 检查 ============
def is_negligible_candidate(f, max_n: int = 1000) -> bool:
    """启发式检查 f(n) 是否 negligible (decay 快于任何 1/poly)"""
    for power in [2, 5, 10, 50]:
        # 检查 f(n) < 1/n^power 对足够大 n
        for n in range(10, max_n):
            if f(n) >= 1 / (n ** power):
                if n > max_n - 100:  # 给点 slack
                    pass
                # break out check
        # 简化判断: 比较 f(max_n) vs 1/max_n^power
        if f(max_n) >= 1 / (max_n ** power):
            return False
    return True


# ============ 3. PRF distinguisher 模拟 ============
def hmac_sha256(key: bytes, msg: bytes) -> bytes:
    """HMAC-SHA256 作为候选 PRF"""
    if len(key) > 64: key = sha256(key).digest()
    key = key.ljust(64, b'\x00')
    o = bytes(b ^ 0x5c for b in key)
    i = bytes(b ^ 0x36 for b in key)
    return sha256(o + sha256(i + msg).digest()).digest()


def prf_distinguisher_demo():
    """简单区分器: 查询同一 msg 两次, 检查输出一致 (PRF) vs 真随机"""
    K = random.randbytes(32)
    msg = b"test"
    h1 = hmac_sha256(K, msg)
    h2 = hmac_sha256(K, msg)
    print(f"HMAC 一致: {h1 == h2}")
    # 真随机函数也应一致 (oracle), 所以不是有效 distinguisher
    print("(单次重复查询不是有效 PRF distinguisher; 需统计大量查询)")


# ============ 4. Birthday Bound 验证 ============
def birthday_simulation(n_bits: int = 32, trials: int = 100):
    """模拟从 2^n 中抽样直到碰撞, 看 q ≈ 2^(n/2)"""
    N = 2 ** n_bits
    expected = int(sqrt(N))
    samples = []
    for _ in range(trials):
        seen = set()
        q = 0
        while True:
            q += 1
            x = random.getrandbits(n_bits)
            if x in seen:
                samples.append(q)
                break
            seen.add(x)
    avg = sum(samples) / trials
    print(f"Birthday n={n_bits}: empirical avg q={avg:.0f}, expected √N={expected}")


# ============ 演示 ============
if __name__ == "__main__":
    chernoff_demo()
    print()
    print(f"f(n)=2^-n negligible: {is_negligible_candidate(lambda n: 2**-n)}")
    print(f"f(n)=1/n^2 negligible: {is_negligible_candidate(lambda n: 1/n**2)}")
    print()
    prf_distinguisher_demo()
    print()
    birthday_simulation(20, 200)
    birthday_simulation(24, 50)

输出：

Chernoff: P[X ≥ 550] empirical=0.0008, bound=0.0084
f(n)=2^-n negligible: True
f(n)=1/n^2 negligible: False
HMAC 一致: True
Birthday n=20: empirical avg q=1280, expected √N=1024
Birthday n=24: empirical avg q=5040, expected √N=4096

---

六、密码学应用关联

6.1 加密安全模型链

6.2 签名安全

6.3 零知识系统

---

七、真实参数

7.1 安全级别 → negligible threshold

7.2 PRF/PRP 实例

• AES-128: PRP 候选, $2^{128}$ 状态
• HMAC-SHA256: PRF 候选, $2^{256}$
• ChaCha20: PRG / stream cipher
• BLAKE2: 高速 hash + PRF mode

7.3 安全证明 reduction loss

• Tight reduction: Adv${\mathcal{A}} \le c \cdot $ Adv${\mathcal{B}}$
• Non-tight: Adv${\mathcal{A}} \le q^2 \cdot $ Adv${\mathcal{B}}$（损失 $q^2$，需更大参数）

例：BLS sig 在 ROM + co-CDH 下 tight；Schnorr 在 ROM + DLP 下 non-tight (forking lemma 损失 $q$)。

---

八、常见陷阱

1. 混淆 negligible 与 small：$1/100$ 不是 negligible（不是 $1/$ poly 衰减）。$2^{-30}$ 也不是 negligible（asymptotic 概念）。仅 $2^{-\Omega(\lambda)}$ 等指数衰减是。
2. Union bound 过紧/松：用 union bound 对独立事件可能极度宽松；若有正相关甚至失效（fix: Lovász local lemma）。
3. Chernoff 不适用相关变量：要求独立或弱相关。相关时用 Azuma–Hoeffding 鞅。
4. Forking lemma 忘损失：Schnorr 安全归约用 forking → Adv${\mathcal{B}} \approx \text{Adv}{\mathcal{A}}^2 / q$，即 $\mathcal{A}$ 优势 $1%$ 反推 DLP 求解 $0.0001%$，参数需巨大。
5. ROM 在 Quantum 下需 QROM：量子攻击者可 superposition 查询 ROM。证明要重做（Boneh-Zhandry 等）。
6. Birthday bound 忽略：CTR 模式 nonce 重复概率 $q^2/2^{|n|}$，IV 64-bit 时 $q = 2^{32}$ 即 $1$ 概率冲突。GCM 用 96-bit nonce 是为此。

---

九、关键速查

概率不等式选择

安全证明模板

1. 假设 ∃ adversary A 优势 ε (假设 non-negligible)
2. 构造 B 利用 A 解某困难问题
3. B 模拟 A 的 view (oracles, ROM 等)
4. 计算 B 成功率 ≥ ε - reduction loss
5. 由困难假设 B 成功率 negligible
6. 故 ε ≤ negligible, 矛盾 (or 直接得 bound)

---

十、面试题

Q1: 解释 IND-CPA 与 IND-CCA 的区别。

答：

• IND-CPA：攻击者可加密查询，但不能解密。AES-CTR with random IV 即可。
• IND-CCA1 (lunchtime)：解密 oracle 限于挑战之前。CBC + MAC 安全。
• IND-CCA2 (adaptive)：解密 oracle 在挑战后仍可（不能解挑战密文本身）。AEAD 模式（GCM, ChaCha20-Poly1305）安全。

实际系统必须 IND-CCA2：网络协议中攻击者可重放/修改密文，要求解密 oracle 不泄露 bits。

Q2: forking lemma 是什么？为什么 Schnorr 证明用它？

答： Forking lemma (Pointcheval-Stern)：在 ROM 下，若攻击者 $\mathcal{A}$ 通过 hash 查询前缀 $\rho$ 后伪造签名 $\sigma$ 概率 $\epsilon$，则 rewind $\mathcal{A}$ 在同一 $\rho$ 给不同 hash 答案，得两份签名 $\sigma_1, \sigma_2$ 概率 $\Omega(\epsilon^2 / q)$。

用途：Schnorr 签名 $(R, s)$，$s = k + H(R||m) d$。若攻击者伪造，rewind 得 $s_1, s_2$ 同 $R$ 但不同 $H$，可解出 $d$（DLP）。

代价：reduction loss 从 $\epsilon$ 到 $\epsilon^2/q$，所以参数需更大。BLS / DDH-based 证明 tight 优于 Schnorr。

Q3: 为什么后量子安全证明用 QROM 而非 ROM？

答：经典 ROM 假设攻击者每次查询 hash 一个 input，得一个 output。量子攻击者可对查询做 superposition：$|\psi\rangle = \sum_x \alpha_x |x\rangle |H(x)\rangle$。

含义：

• 经典 reduction 中 simulator 可"修改"hash 答案（programmability），量子下 superposition 让此操作复杂
• Boneh-Zhandry 2011 证明许多协议在 QROM 下仍安全，但需新技术（compressed oracle, OW2H lemma）
• Kyber / Dilithium 安全证明都在 QROM

Q4: Chernoff vs Chebyshev 的实际区别？

答：

• Chebyshev：$P(|X-\mu| \ge a) \le \sigma^2/a^2$，多项式衰减
• Chernoff：$P(X \ge (1+\delta)\mu) \le e^{-\delta^2\mu/3}$，指数衰减

例：100 次硬币，$\mu = 50$。$P(X \ge 70)$:

• Chebyshev: $25/400 = 6.25%$
• Chernoff ($\delta = 0.4$): $e^{-50 \cdot 0.16/2.4} \approx 4%$

Chernoff 紧得多但需要独立性。对密码 reduction（独立查询）总是用 Chernoff。

Q5: PRF 与 hash 函数的关系？

答：

• Hash 是unkeyed，公开映射
• PRF 是keyed，输出对未知 $K$ 看似随机
• HMAC 把 hash 转成 PRF：$\text{HMAC}(K, m) = H((K \oplus o) || H((K \oplus i) || m))$
• 在 ROM 下任何 hash 都"是" PRF；实际 SHA-2 直接做 PRF 有 length-extension 攻击，必须 HMAC
• SHA-3 / BLAKE2 设计为可直接 keyed (no length-ext)

KDF 用 PRF 派生：HKDF = HMAC + extract/expand。

---

十一、明日预告

Day 193: 计算困难假设 — 系统对比 DLP / RSA / LWE / SIS / isogeny。后量子假设的崛起。理解 Kyber/Dilithium 的数学基础。

核心问题：为什么 LWE 比 DLP 更"通用"？

参考文献：

• Goldreich, Foundations of Cryptography, Vol. 1 + 2.
• Katz & Lindell, Introduction to Modern Cryptography.
• Pointcheval & Stern, "Security Arguments for Digital Signatures and Blind Signatures", J. Cryptology 2000.
• Bellare & Rogaway, "Random Oracles are Practical", CCS 1993.
• Boneh, Dagdelen, Fischlin, Lehmann, Schaffner, Zhandry, "Random Oracles in a Quantum World", ASIACRYPT 2011.