【密码学百科】零知识证明入门：如何证明你知道而不泄露

在日常生活中，“证明”往往意味着展示——出示身份证以证明身份，打开保险箱以证明你拥有钥匙，写出答案以证明你会解题。然而密码学提出了一个大胆的问题：能否在不泄露任何秘密本身的前提下，让对方完全相信你确实拥有这个秘密？ 这就是零知识证明(Zero-Knowledge Proof, ZKP)的核心追问。

零知识证明的概念由 Goldwasser、Micali 和 Rackoff 于 1985 年正式提出，它彻底改变了人们对”证明”的理解。传统数学证明是一段可以被任何人独立验证的静态文本，而零知识证明是一场精心设计的交互式对话——证明者(Prover)通过与验证者(Verifier)的多轮交互，使后者确信某个断言为真，同时验证者除了”该断言为真”这一事实之外，不会获得任何额外信息。

本文是密码学百科系列的第 25 篇。我们将从直觉出发，逐步建立零知识证明的形式化理解，探讨经典的图同构与哈密顿回路零知识协议，深入 Sigma 协议的通用框架，最终通过 Python 代码实现 Schnorr 身份认证协议与 Fiat-Shamir 变换。

一、零知识的直觉

在进入严格的数学定义之前，让我们先通过三个经典的类比建立对零知识证明的直觉理解。

阿里巴巴洞穴

这是密码学文献中最著名的零知识类比，由 Quisquater 等人在 1989 年提出。设想一个环形洞穴，入口处分为左右两条通道，在洞穴深处两条通道被一扇魔法门隔开，只有知道咒语的人才能打开这扇门。

证明者 Peggy 声称她知道咒语。验证者 Victor 站在洞穴入口处。协议如下进行：首先，Peggy 随机选择从左通道或右通道走入洞穴深处，此时 Victor 看不到她的选择。然后，Victor 走到分叉口，随机喊出”从左边出来”或”从右边出来”。如果 Peggy 确实知道咒语，无论 Victor 要求哪个方向，她都能打开魔法门从指定方向走出；如果她不知道咒语，她只有在恰好猜对 Victor 要求的方向时才能成功，概率为二分之一。

重复这个过程 n 次后，一个不知道咒语的冒充者成功欺骗 Victor 的概率降为 (1/2)^n，当 n 足够大时，这个概率可以忽略不计。关键在于：Victor 在整个过程中完全没有获得关于咒语本身的任何信息——他只看到 Peggy 每次都能从正确的方向出来。即使 Victor 用摄像机记录了全过程，这段录像也无法说服第三方，因为 Victor 完全可以与 Peggy 合谋事先约定方向来伪造这样的录像。

寻找沃尔多

“Where’s Waldo”是一系列寻找隐藏人物的图画书。假设 Peggy 知道沃尔多在图中的位置，她想向 Victor 证明这一点但不想泄露具体坐标。方法是：Peggy 用一块巨大的不透明纸板盖住整幅图画，然后在纸板上沃尔多所在的位置开一个小孔，刚好露出沃尔多的形象。Victor 可以确认那确实是沃尔多，但由于纸板远大于原图且覆盖了所有参照物，他无法推断出沃尔多在原图中的具体位置。

这个类比展示了零知识证明的一个核心思想：选择性披露(selective disclosure)。证明者精确地控制信息的流向，只释放足以让验证者信服的最少信息量。

色盲朋友与两个球

你的朋友是红绿色盲，你手中有一红一绿两个完全相同大小的球。你想向他证明这两个球颜色不同而不告诉他哪个是红色哪个是绿色。方法如下：让朋友将两个球分别握在左右手中并放到背后，他可以选择交换或不交换两个球，然后再拿出来给你看。由于你能分辨颜色，你总能正确地说出他是否交换了球。重复多次后，朋友就能确信两个球确实颜色不同，因为如果两球颜色相同，你正确猜对的概率每轮只有二分之一。

这三个类比虽然不完全精确，但它们传达了零知识证明的本质特征：证明者拥有某种知识或秘密，她可以通过巧妙的交互协议让验证者确信这个知识的存在性，而验证者在此过程中没有学到关于该知识的任何具体信息。

二、形式化定义

直觉虽好，但密码学需要严格的数学定义。一个零知识证明系统由证明者 P 和验证者 V 之间的交互式协议组成，它必须同时满足三个核心性质。

完备性(Completeness)

如果断言 x 为真，且证明者 P 诚实地遵循协议，那么验证者 V 最终会以压倒性的概率接受这个证明。形式化地说，对于所有属于语言 L 的实例 x：

Pr[⟨P(w), V⟩(x) = accept] ≥ 1 - negl(n)

其中 w 是证明者持有的证据(witness)，negl(n) 是一个关于安全参数 n 的可忽略函数。完备性保证了这个证明系统是”有用的”——真实的断言总是能够被成功证明。

可靠性(Soundness)

如果断言 x 为假，那么无论恶意证明者 P* 采用何种策略，她使验证者接受的概率都是可忽略的。形式化地说，对于所有不属于语言 L 的实例 x，以及所有(可能是计算无界的)证明者策略 P*：

Pr[⟨P*, V⟩(x) = accept] ≤ negl(n)

可靠性确保了验证者不会被欺骗。值得注意的是，这里的可靠性有两个变体：统计可靠性(statistical soundness)对任意强大的恶意证明者成立，而计算可靠性(computational soundness)只对概率多项式时间(PPT)的恶意证明者成立。后者也称为论证(argument)系统。

零知识性(Zero-Knowledge Property)

这是最核心也最微妙的性质。直觉上，它要求验证者在与证明者交互之后，不会获得任何超出”x 为真”这一事实的额外知识。形式化的表述采用模拟范式(simulation paradigm)：存在一个概率多项式时间的模拟器(Simulator) S，它在不访问证明者的秘密证据 w 的情况下，能够产生一个与真实交互转录(transcript)在某种意义上不可区分的模拟转录。

根据不可区分性的强度，零知识性分为三个层次：

• 完美零知识(Perfect Zero-Knowledge)：模拟器的输出分布与真实转录的分布完全一致，即统计距离为零。这是最强的零知识保证，但在实践中较难实现。

• 统计零知识(Statistical Zero-Knowledge)：模拟器的输出分布与真实转录的分布之间的统计距离是安全参数的可忽略函数。即使是计算能力无限的区分者也无法有效地分辨两者。

• 计算零知识(Computational Zero-Knowledge)：任何概率多项式时间的区分者都无法有效地区分模拟器的输出与真实转录。这是实践中最常用的定义。

模拟范式是理解零知识性的关键。它说的是：验证者从交互中能够计算出来的任何东西，他不需要与证明者交互也能自己计算出来(通过运行模拟器)。因此，交互确实没有给验证者带来任何新知识。

三性速记表

个人思考。 在密码学的所有概念中，零知识性是最违反直觉的——它断言”证明”可以不携带任何知识。完备性和可靠性还比较好理解：前者说系统有用，后者说系统可靠。但零知识性要求我们接受一个看似矛盾的命题：交互确实让验证者”相信”了什么，却没有让他”学到”什么。理解这一点的钥匙就是模拟范式：如果验证者能自己生成一份与真实交互不可区分的转录，那他从真实交互中得到的东西就不算”新知识”。模拟器的存在性把一个哲学问题变成了一个精确的数学命题——这正是零知识理论最精妙之处。初学者往往纠结于”既然能证明，怎么可能没信息泄露”，而一旦真正理解了”模拟器能不靠秘密就伪造出同分布的对话”这件事，零知识的整个理论框架就豁然开朗了。

从更宏观的视角来看，模拟器范式（simulation paradigm）的意义远远超出零知识证明本身——它是现代密码学中最核心的概念工具之一。一旦你理解了”安全性意味着存在一个模拟器”，你就掌握了解读几乎所有现代密码学安全定义的钥匙。多方安全计算的安全性？存在一个模拟器能仅凭各方的输入和输出模拟出真实协议的完整视图。可否认加密的安全性？存在一个模拟器能在不知道真实明文的情况下生成与真实密文不可区分的”假”密文。通用可组合安全（UC security）？存在一个模拟器能在理想世界中模拟出与真实世界不可区分的执行过程。模拟器范式之所以如此强大，是因为它把一个本质上模糊的直觉——“攻击者什么也学不到”——转化为一个精确的存在性命题：存在一个算法，它不知道秘密却能产生与真实世界相同的输出分布。理解这一范式后，密码学中看似互不相关的众多安全定义突然呈现出统一的底层逻辑。

三、交互式证明系统

零知识证明是交互式证明系统(Interactive Proof System)的一个特例。交互式证明系统的概念同样由 Goldwasser、Micali 和 Rackoff 在 1985 年的同一篇开创性论文中提出，它扩展了传统的确定性验证模型。

在交互式证明系统中，证明者 P 和验证者 V 是两台通过通信信道连接的交互式图灵机。协议进行多轮消息交换：P 发送消息给 V，V 发送消息给 P，如此反复。最终 V 根据所有收到的消息以及自己的随机硬币(random coins)决定接受或拒绝。

形式化地说，我们定义复杂度类 IP(Interactive Polynomial time)为所有可以被交互式证明系统判定的语言的集合。1992 年，Shamir 证明了一个令人震惊的结论：IP = PSPACE。这意味着交互式证明系统的计算能力恰好等价于多项式空间——比人们之前预期的要强大得多。

在零知识的语境下，我们关心的不仅仅是交互式证明的存在性，还有信息泄露的控制。证明者通常被建模为计算无界的(她拥有无限的计算能力)，而验证者是概率多项式时间的。证明者持有一个 NP 证据 w，使得她可以高效地执行协议。

交互式证明系统的一个关键特点是验证者的随机性(randomness)。如果去掉验证者的随机性，整个系统退化为 NP 验证——证明者只需发送证据 w，验证者确定性地验证。正是因为验证者可以随机地提出挑战，交互式证明系统才具有了超越 NP 的能力，也为零知识性质的实现提供了基础。

四、图同构的零知识证明

为了使抽象的定义更加具体，让我们考察图同构(Graph Isomorphism)问题上的一个经典零知识证明协议。

给定两个图 G_0 和 G_1，它们是同构的当且仅当存在一个顶点排列 π 使得 G_1 = π(G_0)。假设证明者 Peggy 知道这个同构映射 π，她想向验证者 Victor 证明 G_0 和 G_1 确实同构，但不想泄露 π 本身。

协议如下进行：

承诺阶段(Commit)：Peggy 随机选择一个顶点排列 σ，计算 H = σ(G_0)。由于 σ 是随机的，H 是 G_0 的一个随机同构副本。Peggy 将 H 发送给 Victor。

挑战阶段(Challenge)：Victor 随机选择一个比特 b ∈ {0, 1}，发送给 Peggy。

响应阶段(Response)：如果 b = 0，Peggy 发送 σ（证明 H 与 G_0 同构）；如果 b = 1，Peggy 计算并发送 τ = σ ∘ π^(-1)（证明 H 与 G_1 同构，因为 τ(G_1) = σ(π^(-1)(G_1)) = σ(G_0) = H）。

验证：Victor 检查收到的排列是否确实将 G_b 映射到 H。如果是则接受本轮，否则拒绝。

完备性显然成立：如果 Peggy 确实知道 π，她总能正确响应。可靠性也容易验证：如果 G_0 和 G_1 不同构，那么 H 最多只能与其中一个图同构，因此冒充者至多以 1/2 的概率通过单轮验证。

零知识性的证明使用模拟器构造。模拟器 S 在不知道 π 的情况下工作如下：先随机猜测 b’ ∈ {0, 1}，然后选择随机排列 σ’ 并计算 H’ = σ’(G_{b’})。将 H’ 作为承诺发送给(模拟的)验证者 V。当 V 返回挑战 b 时，如果 b = b’，模拟器可以正确响应(发送 σ’)；如果 b ≠ b’，模拟器放弃并重新开始。由于 V* 选择 b = b’ 的概率为 1/2，模拟器的期望运行时间为多项式次。

关键观察是：当模拟器成功时(b = b’ 的情况)，其产生的转录 (H’, b, σ’) 与真实交互中的转录具有相同的分布。这是因为在真实协议中，无论 b 的值如何，Peggy 发送的排列都是均匀随机的。因此，这个协议是完美零知识的。

五、哈密顿回路的零知识证明

图同构问题目前不知道是 NP 完全的，这限制了上述协议的普适性。一个更深刻的结果是 Blum 在 1986 年为哈密顿回路(Hamiltonian Cycle)问题构造的零知识证明。由于哈密顿回路问题是 NP 完全的，这意味着 NP 中的每一个问题都拥有零知识证明——这是零知识理论中的一个里程碑式定理。

给定一个图 G，假设证明者 Peggy 知道 G 中的一条哈密顿回路 C。协议的基本思路如下：

承诺阶段：Peggy 选择一个随机排列 π，计算 G 的同构副本 G’ = π(G)。然后她对 G’ 的邻接矩阵中的每一个元素分别进行承诺(使用位承诺方案)。也就是说，对于 G’ 中每一对顶点 (i, j)，Peggy 都发送一个承诺 Com(A’_{ij})，其中 A’ 是 G’ 的邻接矩阵。

挑战阶段：Victor 随机选择一个比特 b ∈ {0, 1}。

响应阶段： - 如果 b = 0：Peggy 打开所有承诺并揭示排列 π。Victor 验证 G’ = π(G)，即承诺的确是 G 的一个同构副本。 - 如果 b = 1：Peggy 计算 C’ = π(C)，即 C 在排列 π 下的像。她只打开 C’ 中边对应的承诺。Victor 验证这些打开的承诺确实揭示了 G’ 中的一条哈密顿回路。

完备性显然成立。可靠性来自这样的论证：如果 G 没有哈密顿回路，那么 G 的任何同构副本也没有，因此欺骗者不可能同时满足两个挑战——要么她承诺的不是 G 的合法同构副本(b = 0 时会失败)，要么她无法在承诺的图中展示一条哈密顿回路(b = 1 时会失败)。单轮欺骗成功率至多 1/2。

零知识性的证明同样使用模拟范式，但这里承诺方案的隐藏性(hiding property)起到了关键作用。当 b = 0 时，模拟器可以先生成 G’ = π(G) 并诚实地承诺；当 b = 1 时，模拟器可以构造一个只包含 n 个顶点的简单哈密顿回路的图(而不是真实的 G’ )，并承诺这个图。由于承诺方案的计算隐藏性，验证者无法区分对 G’ 的承诺与对伪造图的承诺。

Goldreich、Micali 和 Wigderson 在 1991 年的论文中将这一结果推广，证明了在单向函数存在的假设下，所有 NP 语言都有计算零知识证明。这一定理是零知识理论的基石。

六、Sigma 协议

上述两个零知识协议都遵循一个共同的三轮结构：证明者发送承诺，验证者发送挑战，证明者发送响应。这种结构被系统地总结为 Sigma 协议(Σ-Protocol)，因为消息的流向像希腊字母 Σ 的形状。

一个 Sigma 协议针对关系 R = {(x, w)} 具有以下结构：

1. 承诺(Commitment)：证明者根据公共输入 x、秘密证据 w 和自己的随机性，计算并发送承诺消息 a。
2. 挑战(Challenge)：验证者从挑战空间 C 中均匀随机地选择一个挑战 e，发送给证明者。
3. 响应(Response)：证明者根据 a、e 和 w 计算并发送响应 z。
4. 验证：验证者根据 (x, a, e, z) 决定接受或拒绝。

Sigma 协议必须满足以下性质：

完备性：当 (x, w) ∈ R 时，诚实执行的协议总是使验证者接受。

特殊可靠性(Special Soundness)：给定同一个承诺 a 下的两个不同挑战 e ≠ e’ 及其对应的合法响应 z 和 z’，存在一个高效算法可以从 (a, e, z, e’, z’) 中提取出一个有效的证据 w。这意味着，如果某人能够对同一个承诺回答两个不同的挑战，那他就”实际上知道”证据。

特殊诚实验证者零知识(Special Honest-Verifier Zero-Knowledge, SHVZK)：存在一个多项式时间的模拟器 S，给定公共输入 x 和一个挑战 e，可以输出一个转录 (a, e, z)，使得该转录与真实交互(在验证者恰好发送挑战 e 的条件下)的分布不可区分。

注意 SHVZK 比一般的零知识性质要弱——它只要求对”诚实”的验证者(即按协议规定均匀随机选择挑战的验证者)成立。但在许多实际应用中，特别是在通过 Fiat-Shamir 变换将交互式协议转化为非交互式时，SHVZK 已经足够。

Sigma 协议的特殊可靠性还蕴含了一个重要概念：知识证明(Proof of Knowledge)。它不仅证明某个断言为真，还证明证明者”实际拥有”相应的证据。这在密码协议设计中至关重要——例如，在身份认证中，我们需要确信对方确实持有私钥，而不仅仅是”存在”某个私钥使公钥合法。

七、Schnorr 身份认证

Schnorr 身份认证协议是 Sigma 协议最经典的实例，由 Claus-Peter Schnorr 于 1989 年提出。它是离散对数(Discrete Logarithm)知识的零知识证明，构成了现代数字签名和身份认证的基础。

协议设定

设 p 为大素数，q 为 p-1 的大素因子，g 为 Z_p* 中阶为 q 的生成元。证明者 Peggy 的私钥为 x ∈ Z_q，公钥为 y = g^x mod p。Peggy 要向 Victor 证明她知道满足 y = g^x mod p 的 x。

协议流程

1. 承诺：Peggy 随机选择 k ←_R Z_q，计算 r = g^k mod p，将 r 发送给 Victor。
2. 挑战：Victor 随机选择 e ←_R {0, 1, …, 2^t - 1}（其中 t 是安全参数），将 e 发送给 Peggy。
3. 响应：Peggy 计算 s = (k - x·e) mod q，将 s 发送给 Victor。
4. 验证：Victor 检查 g^s · y^e ≡ r (mod p)。如果等式成立则接受，否则拒绝。

正确性分析

完备性：如果 Peggy 诚实执行，则 g^s · y^e = g^(k - xe) · g^(xe) = g^k = r，验证通过。

特殊可靠性：假设对同一承诺 r，存在两个合法的转录 (r, e, s) 和 (r, e’, s’)，其中 e ≠ e’。则 g^s · y^e = r = g^{s’} · y^{e’}，化简得 g^(s - s’) = y^(e’ - e)，因此 x = (s - s’) · (e’ - e)^(-1) mod q。这表明从两个不同挑战的合法响应中可以提取出私钥 x。

SHVZK：模拟器 S 给定 y 和 e，随机选择 s ←_R Z_q，计算 r = g^s · y^e mod p，输出转录 (r, e, s)。由于 s 是均匀随机的，r 也是均匀随机的，因此模拟转录与真实转录不可区分。

Python 实现

以下代码实现了完整的 Schnorr 身份认证协议：

import hashlib
import secrets

def generate_params(bit_length=256):
    """生成 Schnorr 协议所需的群参数（简化演示版本）。
    实际部署应使用标准化参数或椭圆曲线。"""
    # 演示用小参数；生产环境应使用 2048 位以上的素数
    # 这里使用一组预定义的安全参数
    # q 为 256 位素数，p = 2q + 1 也是素数（安全素数）
    from sympy import isprime, nextprime, mod_inverse  # 需要安装：pip install sympy

    q = nextprime(secrets.randbits(bit_length))
    # 寻找 p = kq + 1 为素数
    k = 2
    while True:
        p = k * q + 1
        if isprime(p):
            break
        k += 1

    # 寻找阶为 q 的生成元
    while True:
        h = secrets.randbelow(p - 2) + 2
        g = pow(h, k, p)
        if g != 1:
            break

    return p, q, g


class SchnorrProver:
    """Schnorr 协议的证明者"""

    def __init__(self, p, q, g, x):
        self.p = p
        self.q = q
        self.g = g
        self.x = x  # 私钥
        self.y = pow(g, x, p)  # 公钥
        self._k = None

    def commit(self):
        """第一步：生成承诺 r = g^k mod p"""
        self._k = secrets.randbelow(self.q - 1) + 1
        r = pow(self.g, self._k, self.p)
        return r

    def respond(self, e):
        """第三步：根据挑战 e 计算响应 s = (k - x*e) mod q"""
        s = (self._k - self.x * e) % self.q
        self._k = None  # 清除临时随机数
        return s


class SchnorrVerifier:
    """Schnorr 协议的验证者"""

    def __init__(self, p, q, g, y, challenge_bits=32):
        self.p = p
        self.q = q
        self.g = g
        self.y = y  # 证明者的公钥
        self.challenge_bits = challenge_bits

    def challenge(self):
        """第二步：生成随机挑战 e"""
        e = secrets.randbelow(2 ** self.challenge_bits)
        self._e = e
        return e

    def verify(self, r, e, s):
        """第四步：验证 g^s * y^e ≡ r (mod p)"""
        lhs = (pow(self.g, s, self.p) * pow(self.y, e, self.p)) % self.p
        return lhs == r


def schnorr_interactive_demo():
    """演示 Schnorr 交互式身份认证的完整流程"""
    print("=== Schnorr 交互式身份认证 ===\n")

    p, q, g = generate_params(64)  # 演示使用较小参数
    x = secrets.randbelow(q - 1) + 1  # 私钥

    prover = SchnorrProver(p, q, g, x)
    verifier = SchnorrVerifier(p, q, g, prover.y, challenge_bits=32)

    rounds = 5
    all_passed = True

    for i in range(rounds):
        # 步骤 1：证明者生成承诺
        r = prover.commit()

        # 步骤 2：验证者生成挑战
        e = verifier.challenge()

        # 步骤 3：证明者计算响应
        s = prover.respond(e)

        # 步骤 4：验证者验证
        ok = verifier.verify(r, e, s)
        status = "通过" if ok else "失败"
        print(f"第 {i+1} 轮: r={r % (10**8)}..., e={e}, 验证={status}")
        all_passed = all_passed and ok

    print(f"\n最终结果: {'身份认证成功' if all_passed else '身份认证失败'}")
    return all_passed

八、Fiat-Shamir 变换

Schnorr 协议是交互式的——它要求证明者与验证者进行实时的消息交换。在许多实际场景中，交互是不方便甚至不可能的，例如数字签名(签名者在签名时不知道未来的验证者是谁)。Fiat-Shamir 变换(Fiat-Shamir Transform)提供了一种将交互式 Sigma 协议转化为非交互式证明的通用方法。

基本思想

核心观察是：在 Sigma 协议中，验证者唯一的作用就是发送一个随机挑战。如果我们用一个密码学哈希函数 H 来代替验证者，让证明者自己通过对承诺和公共输入进行哈希来生成”挑战”，就消除了交互的需要。

具体来说，给定一个 Sigma 协议 (commit, challenge, respond)，Fiat-Shamir 变换后的非交互式证明为：

1. 证明者计算承诺 a。
2. 证明者计算挑战 e = H(x || a)，其中 x 是公共输入，H 是密码学哈希函数。
3. 证明者计算响应 z。
4. 非交互式证明为 π = (a, z)。验证者可以独立地重新计算 e = H(x || a) 并验证。

安全性分析

Fiat-Shamir 变换的安全性证明在随机预言模型(Random Oracle Model, ROM)中进行。在 ROM 中，哈希函数被建模为一个真正的随机函数——对于每个新的输入，其输出是均匀随机且独立的。在这个模型下，证明者无法预测或控制哈希函数的输出，因此哈希输出与验证者的随机挑战具有相同的效果。

需要注意的是，在标准模型(即不假设随机预言的模型)中，Fiat-Shamir 变换的安全性并不总是成立。存在人为构造的反例，其中某个安全的交互式协议在经过 Fiat-Shamir 变换后变得不安全。但在实践中，使用 SHA-256 或 SHA-3 等具体哈希函数时，Fiat-Shamir 变换被广泛认为是安全的。

笔者认为，Fiat-Shamir 变换是密码学史上最具戏剧性的”奇迹与陷阱”并存体。它的奇迹在于：仅仅用一个哈希函数替代交互中的验证者，就把一整类需要实时通信的协议变成了可以离线生成、任何人任何时候都能验证的非交互式证明。从 Schnorr 签名到现代 zkSNARK 的递归组合，Fiat-Shamir 变换是将零知识从理论工具变为实用基础设施的关键桥梁。但陷阱同样深刻：它的安全性证明依赖于随机预言模型（Random Oracle Model），即假设哈希函数的行为与一个真正的随机函数完全一致。而现实中的 SHA-256 或 SHA-3 当然不是随机预言——它们是确定性算法，具有可利用的内部结构。更令人不安的是，存在已知的人工构造反例：某些在随机预言模型下可证明安全的方案，在将随机预言替换为任何具体哈希函数后变得完全不安全。这意味着”在 ROM 中安全”并不能逻辑上保证”在实践中安全”。密码学界在这一问题上形成了一种务实的共识：我们接受 ROM 证明作为有意义的安全论据（而非严格的安全保证），同时承认它留下了一个理论缺口。这种”理论不完美但实践可靠”的张力，或许是密码学作为一门同时追求数学严格性与工程实用性的学科所特有的困境。

Schnorr 签名

将 Fiat-Shamir 变换应用于 Schnorr 身份认证协议，可以直接得到 Schnorr 签名方案。为签名消息 m：

1. 选择随机数 k，计算 r = g^k mod p。
2. 计算 e = H(m || r)。
3. 计算 s = (k - x·e) mod q。
4. 签名为 (e, s)。

验证时，计算 r’ = g^s · y^e mod p，检查 e = H(m || r’)。Schnorr 签名方案是 EdDSA 等现代签名标准的理论基础。

Python 实现

以下代码实现了 Fiat-Shamir 变换以及非交互式 Schnorr 证明：

def fiat_shamir_hash(public_input, commitment, challenge_bits=32):
    """使用 SHA-256 实现 Fiat-Shamir 挑战生成。
    将公共输入和承诺拼接后取哈希，截取所需比特数。"""
    data = f"{public_input}||{commitment}".encode()
    digest = hashlib.sha256(data).hexdigest()
    e = int(digest, 16) % (2 ** challenge_bits)
    return e


class SchnorrNonInteractive:
    """基于 Fiat-Shamir 变换的非交互式 Schnorr 证明"""

    def __init__(self, p, q, g):
        self.p = p
        self.q = q
        self.g = g

    def prove(self, x, y, challenge_bits=32):
        """生成非交互式零知识证明：证明知道 x 使得 y = g^x mod p"""
        # 步骤 1：承诺
        k = secrets.randbelow(self.q - 1) + 1
        r = pow(self.g, k, self.p)

        # 步骤 2：Fiat-Shamir 生成挑战（替代验证者）
        e = fiat_shamir_hash(y, r, challenge_bits)

        # 步骤 3：响应
        s = (k - x * e) % self.q

        # 非交互式证明 π = (r, s)
        return (r, s)

    def verify(self, y, proof, challenge_bits=32):
        """验证非交互式零知识证明"""
        r, s = proof

        # 重新计算挑战
        e = fiat_shamir_hash(y, r, challenge_bits)

        # 验证 g^s * y^e ≡ r (mod p)
        lhs = (pow(self.g, s, self.p) * pow(y, e, self.p)) % self.p
        return lhs == r


def schnorr_signature(p, q, g, x, message, challenge_bits=32):
    """Schnorr 签名：Fiat-Shamir 变换应用于消息签名"""
    y = pow(g, x, p)

    # 承诺
    k = secrets.randbelow(q - 1) + 1
    r = pow(g, k, p)

    # 用消息参与哈希，生成挑战
    data = f"{message}||{r}".encode()
    digest = hashlib.sha256(data).hexdigest()
    e = int(digest, 16) % (2 ** challenge_bits)

    # 响应
    s = (k - x * e) % q

    return (e, s)


def verify_schnorr_signature(p, q, g, y, message, signature, challenge_bits=32):
    """验证 Schnorr 签名"""
    e, s = signature

    # 重建承诺
    r_prime = (pow(g, s, p) * pow(y, e, p)) % p

    # 重新计算挑战
    data = f"{message}||{r_prime}".encode()
    digest = hashlib.sha256(data).hexdigest()
    e_prime = int(digest, 16) % (2 ** challenge_bits)

    return e == e_prime


def fiat_shamir_demo():
    """演示 Fiat-Shamir 变换的非交互式证明与签名"""
    print("\n=== Fiat-Shamir 非交互式零知识证明 ===\n")

    p, q, g = generate_params(64)
    x = secrets.randbelow(q - 1) + 1
    y = pow(g, x, p)

    ni = SchnorrNonInteractive(p, q, g)

    # 非交互式知识证明
    proof = ni.prove(x, y)
    ok = ni.verify(y, proof)
    print(f"非交互式知识证明: {'有效' if ok else '无效'}")

    # Schnorr 签名
    message = "零知识证明是密码学的瑰宝"
    sig = schnorr_signature(p, q, g, x, message)
    ok_sig = verify_schnorr_signature(p, q, g, y, message, sig)
    print(f"消息: {message}")
    print(f"签名验证: {'有效' if ok_sig else '无效'}")

    # 篡改消息后验证应失败
    ok_tampered = verify_schnorr_signature(p, q, g, y, "篡改的消息", sig)
    print(f"篡改消息后签名验证: {'有效' if ok_tampered else '无效'}")


if __name__ == "__main__":
    schnorr_interactive_demo()
    fiat_shamir_demo()

上述代码仅用于教学演示目的，使用了较小的参数以便快速运行。在实际部署中，应当使用椭圆曲线群(如 Curve25519)替代 Z_p* 群，以获得更高的安全效率比。

九、零知识证明的应用与展望

零知识证明从诞生之初的纯理论概念，已经发展为密码学中最活跃、最具应用前景的领域之一。本节概述其主要应用方向及其与本系列后续文章的联系。

身份认证

Schnorr 协议及其变体是零知识身份认证的原型。与传统的密码认证不同，零知识身份认证不需要向服务器发送任何密码或密钥——即使服务器被攻陷，攻击者也无法获得用户的身份凭证。这一思想在智能卡认证、硬件安全模块(HSM)和无密码认证(passwordless authentication)系统中得到了广泛应用。

匿名凭证

零知识证明使得选择性披露成为可能。例如，用户可以证明自己年满 18 岁而不泄露具体出生日期；证明自己是某个组织的成员而不泄露具体身份；证明自己的信用分数超过某个阈值而不泄露具体分数。这些功能由匿名凭证(anonymous credentials)系统实现，如 IBM 的 Idemix 方案和微软的 U-Prove 系统，其底层核心机制都是零知识证明。

区块链与隐私保护

区块链领域是近年来零知识证明应用最爆发式增长的方向。Zcash 使用 zk-SNARKs(简洁非交互式零知识论证)实现了完全隐私的加密货币交易——交易金额、发送者和接收者地址都被隐藏，但网络中的节点仍然可以验证交易的合法性。以太坊生态系统中的 zk-Rollups 利用零知识证明将大量交易压缩为一个简洁的证明，在保证安全性的同时极大地提升了区块链的可扩展性。

安全多方计算的基础组件

零知识证明是构建安全多方计算(Secure Multi-Party Computation)协议的关键子协议。在多方计算中，各参与方需要向其他方证明自己确实按照协议规定的方式执行了计算，而不泄露自己的私有输入。这种”遵守协议的证明”正是零知识证明的用武之地。

与后续文章的联系

本文介绍的是零知识证明的经典理论基础。在本系列后续的第六部分(高级零知识证明专题)中，我们将深入探讨更先进的零知识证明系统：

• zk-SNARKs：简洁非交互式零知识论证，证明大小为常数级别，验证时间极短，但需要可信设置。
• zk-STARKs：可扩展透明零知识论证，无需可信设置，基于哈希函数实现后量子安全。
• Bulletproofs：无可信设置的简洁零知识范围证明，广泛应用于隐私加密货币。
• PLONK 与通用 SNARKs：通用、可更新的结构化参考字符串，简化了零知识证明系统的部署。

零知识证明的发展历程展示了密码学理论与实践之间的良性互动。最初它只是一个令人惊叹的理论可能性——“你可以证明你知道某件事而不泄露任何信息”。几十年后，它已经成为保护数十亿美元数字资产、守护用户隐私的实用工具。从 1985 年 Goldwasser、Micali 和 Rackoff 的开创性论文，到今天以太坊上每天处理的数百万笔 zk-Rollup 交易，零知识证明完成了从纯粹的智力探索到广泛工程实践的华丽转身。

理解零知识证明的基本原理——完备性、可靠性和零知识性这三大支柱，以及 Sigma 协议、Fiat-Shamir 变换等核心工具——是深入学习现代密码学不可或缺的基础。希望本文能为读者开启这扇通向密码学最深邃领域的大门。

密码学百科系列 · 第 25 篇

← 上一篇：密码认证协议 | 系列目录 | 下一篇：安全信道构造 →