复杂度理论 — P/NP、归约与 ZK 的复杂度位置

日期: 2026-11-08 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #复杂度 #NP #ZK #IP #GMR

---

今日目标

---

一、动机

密码学的"难"必须在复杂度类里找位置：

• 加密安全 = 解密难 = 某语言不在 BPP
• ZK 协议 = 验证 in BPP 但 prover 知道更多
• PCP / IP 给 SNARK 理论基础

不懂复杂度，看不懂 ZK 论文（Groth16 vs Plonk 安全证明引用 KoE 假设、SNARK in NP, …）。

---

二、严格定义

2.1 决策问题与语言

决策问题：输入 $x$，输出 yes / no。 语言：$L \subseteq {0,1}^*$，$x \in L \Leftrightarrow$ 答案 yes。

例：

• $L_{\text{prime}} = {n : n \text{ 是素数}}$
• $L_{\text{SAT}} = {\phi : \phi \text{ 可满足}}$
• $L_{\text{DLP}} = {(g, h, p, x) : g^x = h \pmod p}$（验证版）

2.2 主要复杂度类

已知关系： $$P \subseteq BPP \subseteq BQP \subseteq PSPACE = IP$$ $$P \subseteq NP \subseteq PSPACE$$ $$NP \subseteq IP$$

未知：$P \stackrel{?}{=} NP$（千年大奖问题）。

2.3 NP 的形式化

$L \in NP$ 若存在多项式 $p$ 和 deterministic verifier $V$（多项式时间）使：

• 完整性：$x \in L \Rightarrow \exists w, |w| \le p(|x|), V(x, w) = 1$
• 可靠性：$x \notin L \Rightarrow \forall w, V(x, w) = 0$

$w$ 称证书（witness）。

2.4 NP-hard / NP-complete

$L$ 是 NP-hard 若所有 $L' \in NP$ 都多项式归约到 $L$（$L' \le_P L$）。 $L$ 是 NP-complete 若 $L$ NP-hard 且 $L \in NP$。

例：

• 3-SAT、HamCycle、TSP（决策版）、Subset-Sum、Vertex-Cover 都是 NP-complete (Cook-Levin 1971)。

2.5 归约 (Reduction)

Karp 归约 (poly-time many-one)：$L_1 \le_P L_2$ 若存在 $f$ poly-time 使 $x \in L_1 \Leftrightarrow f(x) \in L_2$。

Cook 归约 (poly-time Turing)：$L_1 \le_T L_2$ 若多项式 oracle Turing 机用 $L_2$-oracle 决 $L_1$。

2.6 IP — 交互式证明

定义 (Goldwasser-Micali-Rackoff 1985)：$L \in IP$ 若存在 $P$（无界算力）和 BPP 验证 $V$ 使：

• 完整性：$x \in L \Rightarrow \Pr[(P, V)(x) = 1] \ge 2/3$
• 可靠性：$x \notin L \Rightarrow \forall P^, \Pr[(P^, V)(x) = 1] \le 1/3$

Shamir 1992：$IP = PSPACE$（交互+随机=多项式空间）。

2.7 Zero-Knowledge

ZK (Goldwasser-Micali-Rackoff 1985)：交互式证明额外满足"verifier 学不到除 $x \in L$ 之外的任何东西"。形式化：存在 simulator $S$（多项式时间）使 $$\text{view}_V(P, V)(x) \approx S(x)$$

三种类型：

• Perfect ZK：分布完全相同
• Statistical ZK：分布统计接近
• Computational ZK：计算上不可区分

2.8 ZK-SNARK

ZK + Succinct + Non-interactive + Argument of Knowledge：

• Succinct：证明大小 + 验证时间次线性
• Non-interactive：单消息（用 Fiat-Shamir 把 IP 转 NIZK）
• Argument of Knowledge：可计算 prover 知道 witness（KoE 假设）

---

三、归约思想推导

3.1 SAT ≤ 3-SAT

把任意 CNF 子句拆为 3-字面： $$(\ell_1 \lor \ell_2 \lor \ell_3 \lor \ell_4) \Leftrightarrow (\ell_1 \lor \ell_2 \lor y) \land (\bar y \lor \ell_3 \lor \ell_4)$$ ($y$ 新变量)

3.2 3-SAT ≤ NP-hard 一切

Cook-Levin 证 SAT 是 NP-hard。然后从 SAT 归约到 3-SAT, 3-Color, HamCycle, … 经典链。

3.3 ZK 给 NP 的协议

GMR 1985 给 graph isomorphism 的 ZK 协议。 GMW 1986 推广：任何 NP 语言 都有 ZK 协议（如 OWF 存在）。

关键：3-Color 有 ZK → 任何 NP 问题归约到 3-Color → 都有 ZK。

---

四、IP = PSPACE 证明思路（Shamir 1992）

步骤：

1. PSPACE-complete 问题：$\text{TQBF}$ (true quantified boolean formula)
2. 把 TQBF 算术化（arithmetization）：变量 $\to$ 多项式系数
3. Sumcheck 协议：交互式证明 $\sum_x p(x)$ 等于声明值
4. Verifier 用 BPP 资源校验，得 IP $\supseteq$ PSPACE
5. 逆向 IP $\subseteq$ PSPACE 由 deterministic 模拟得

意义：IP 等价于 PSPACE 让"无穷算力 prover + 概率 verifier"覆盖远超 NP 的问题。

---

五、直觉与图像

5.1 P / NP / PSPACE

• P：1 分钟 solve 的问题（如排序、最短路径）
• NP：1 分钟 verify 的问题（如 SAT、SUDOKU 解）
• PSPACE：用 1MB 内存能 solve 的问题（含 NP）
• EXP：但需要 100 年时间

P=NP 问题：所有"易验证"也"易 solve" 吗？广泛猜测 P ≠ NP。

5.2 ZK 的"魔术"

证明 "x ∈ L" 但不泄露 witness $w$：

• Verifier 看到的 transcript 可由 simulator 仅知 $x$ 生成
• 等价于：transcript 不携带 $w$ 信息

类比：你证明你知道 sudoku 解，但 verifier 看完不会自己解 sudoku。

---

六、代码（不可计算的复杂度，但可演示归约）

"""
Day 191: SAT 归约示意 (理论性质, 不实际 solve NP-complete)
"""

def cnf_to_3cnf(clauses):
    """把任意 CNF 子句拆成 3-CNF"""
    next_var = max(abs(l) for cl in clauses for l in cl) + 1
    new_clauses = []
    for cl in clauses:
        if len(cl) <= 3:
            new_clauses.append(cl)
        else:
            # (l1, l2, l3, ..., lk) → (l1, l2, y1) ∧ (-y1, l3, y2) ∧ ... ∧ (-y_{k-3}, l_{k-1}, l_k)
            cur = list(cl)
            while len(cur) > 3:
                y = next_var; next_var += 1
                new_clauses.append([cur[0], cur[1], y])
                cur = [-y] + cur[2:]
            new_clauses.append(cur)
    return new_clauses


def schwartz_zippel_demo():
    """SZ Lemma: 非零 d 次多项式在 |F|^n 上零点 ≤ d/|F|"""
    # 用于 IP / sumcheck 的可靠性证明
    print("Schwartz-Zippel: 非零次数 d 多项式")
    print("  在 |F|=p 上随机点取零的概率 ≤ d/p")
    print("  ZK / IP / sumcheck 用此证可靠性")


def zk_3coloring_idea():
    """GMR 风格 ZK 3-着色协议简述"""
    print("""
    ZK Proof of 3-Coloring (NP-complete):

    Prover 知道图 G 的 3-着色。
    Repeat n times:
      1. Prover: 随机置换颜色, 把每节点颜色 commit (hidden boxes)
      2. Verifier: 随机选一条边 (u, v)
      3. Prover: 打开 u, v 两节点的盒子
      4. Verifier: 检查颜色不同 ∧ 都是 {R, G, B}

    Soundness: 假 prover 每轮被抓到 ≥ 1/|E|
    ZK: simulator 不需 knowledge of coloring

    n 轮后假 prover 通过率 ≤ (1 - 1/|E|)^n → 0
    """)


# ============ 演示 ============
if __name__ == "__main__":
    # CNF → 3CNF 归约
    clauses = [[1, 2, 3, 4, 5], [-1, 2], [3, -4, 5]]
    print(f"原 CNF: {clauses}")
    print(f"3-CNF: {cnf_to_3cnf(clauses)}")

    schwartz_zippel_demo()
    zk_3coloring_idea()

---

七、密码学应用关联

7.1 SNARK 和 NP

任何 NP 语言可以做 SNARK 证明：

1. 编码 problem 为 R1CS / Plonkish 约束
2. 转算术电路 in $\mathbb{F}_p$
3. Prover 给见证 $w$ 满足
4. Verifier 通过约束多项式 + 多项式承诺验证

复杂度：Prover poly(|circuit|), Verifier polylog(|circuit|).

7.2 IP / IPP / SNARG

7.3 PCP 定理

PCP Theorem (1992)：$NP = PCP[O(\log n), O(1)]$ — Verifier 用 $\log n$ 随机比特 + 读 $O(1)$ 比特证书可判 NP 语言。

重要：这是 SNARK 的理论根基（FRI、Plonk）。

---

八、真实参数 / 例子

8.1 SAT 实例规模

• 工业 SAT solver (CaDiCaL, Glucose) 处理 $10^7$ 子句
• ZK 应用电路 $10^6 - 10^9$ gates
• Plonk on BLS12-381 prove $2^{20}$ gates ~ 1 sec / 1 GB RAM

8.2 IP 协议实例

• Shamir IP=PSPACE: TQBF 协议
• Sum-check protocol: 验证 $\sum_x p(x) = v$，IP 中常用工具
• GKR 2008: low-depth circuit 验证

---

九、常见陷阱

1. 混淆 NP 与 NP-hard：NP-hard 不要求 in NP（可能更难）。EXP-complete 也是 NP-hard 但不在 NP。
2. "NP = brute force" 的误解：NP 是"可验证"，不是"暴力 search"。NP ⊆ EXP 用枚举证书可解但不一定 NP-complete 都需要 EXP 时间。
3. ZK ≠ "无信息"：ZK 泄露"$x \in L$"这一 bit。strict zero info 是不可能的（statement 本身就是信息）。
4. Argument vs Proof：
   • Proof：safe against unbounded prover
   • Argument：safe against poly-bounded prover（弱，但可 succinct）
   • SNARKs 是 arguments，因 succinctness + sound 不能同时对 unbounded prover
5. Soundness vs Knowledge：
   • Soundness：$x \notin L$ 拒绝
   • Knowledge：prover 必须"知道" witness（不仅是存在）
   • SNARK 要求 "AoK"（argument of knowledge）
6. 量子复杂度被忽略：BQP 包含 IF / DLP，所以 RSA / ECC 在量子下崩。但 BQP ⊆ PSPACE，不是 NP（也许）。

---

十、关键速查

复杂度类层次（已知）

                    PSPACE = IP
                   /
                BQP        co-NP   NP
                 \         |       |
                  \        +-------+
                   \       |
                    BPP    P-NP-hard (无相对位置)
                     \
                      P

关键定理

---

十一、面试题

Q1: SNARK 的"AoK"假设是什么？为什么需要它？

答：Knowledge of Exponent (KoE) 或更一般 extractor：若 prover 能产生有效证明，则存在 extractor 算法能从 prover 内部状态提取 witness $w$。

需要它：单纯 soundness 只保证 $x \in L$ 但不保证 prover 知道 $w$。许多协议（如 BLS sig forgery game）需要"prover actually knows secret"。

KoE 不可证伪（non-falsifiable），所以是 controversial 假设。但 Groth16 / Plonk 等都依赖。

Q2: 解释为什么 IP = PSPACE 是惊人的结果。

答：直觉上 IP 仅"poly verifier + interaction"，PSPACE 是"poly memory"，二者表面无关。Shamir 1992 证它们等价。

意义：

• 无穷算力 prover + 随机化 + 交互 = poly memory 算力
• 把"协议设计"和"复杂度类"打通
• 为 zero-knowledge / SNARKs 提供基础

Q3: ZK 协议在 NP 中处于什么位置？

答：

• 任何 NP 语言都有 ZK 协议（GMW 1986），假设 OWF 存在
• ZK ⊆ IP = PSPACE（任何 ZK 也是 IP）
• 但 ZK ≠ IP：IP 不要求隐藏 witness

ZK-SNARK 进一步要求 succinct + non-interactive，证明大小 $O(\lambda)$ 与电路无关。

Q4: 为什么 P vs NP 对密码学重要？

答：

• 若 P = NP：所有"易验证"也"易解"，OWF 不存在 → 公钥密码全部崩
• 若 P ≠ NP：OWF 可能存在但未保证，所以密码学仍依赖具体困难假设（IF, DLP, LWE）
• 实际：P ≠ NP 是必要不充分。即使 P ≠ NP 也要证 specific OWF candidate 难

→ 密码学界普遍假设 P ≠ NP 但建立在更强假设（IF / DLP / LWE 难）之上。

Q5: PCP 定理对 ZK 系统有什么影响？

答：PCP 说 NP 语言可被"概率验证"——读 $O(1)$ 比特就能判正确性（in poly $1/\epsilon$ 错误率）。

影响：

• SNARK / STARK 的 prover 把 witness 编码为 PCP 证明
• Verifier 抽查若干位置 → succinct verifying
• FRI 是 PCP 的 RS-code 实现
• IPS (Interactive PCP) 是 Plonk 等协议的基础

PCP 把"证明可验证"从 NP 的全读升级到 polylog 读，是 SNARK 实用化的根。

---

十二、明日预告

Day 192: 概率论与统计 — 安全证明常用工具：Chebyshev / Chernoff / union bound、随机预言机模型、negligible function、PRG/PRF 安全游戏。

核心问题：怎么证 "1024-bit RSA 解密成功率 negligible"？

参考文献：

• Goldwasser, Micali, Rackoff, "The Knowledge Complexity of Interactive Proof Systems", STOC 1985.
• Goldreich, Micali, Wigderson, "Proofs that Yield Nothing But Their Validity", JACM 1991.
• Shamir, "IP = PSPACE", JACM 1992.
• Arora, Barak, Computational Complexity, Cambridge.
• Cook, "The Complexity of Theorem-Proving Procedures", STOC 1971.