第6章：零知识与后量子密码

证明知识而不公开秘密

零知识证明希望验证某个陈述成立，同时不额外泄露见证。需要分别讨论完备性、可靠性或知识可靠性，以及零知识性质；“没有直接发送秘密”不是零知识证明。

以离散对数知识为例，证明者持有 $x$ ，公开 $y=g^x$ 。先发 $R=g^k$ ，验证者给随机挑战 $e$ ，证明者回 $s=k+ex$ ，验证 $g^s=Ry^e$ 。

诚实双方满足等式，说明完备性。若同一承诺 $R$ 能回答两个不同挑战，就可由差分提取 $x$ ，说明知识提取的核心机制。

对诚实验证者，可先随机选 $e,s$ ，再设 $R=g^s y^{-e}$ ，得到与真实交互同分布的有效记录而不知 $x$ 。这说明记录本身不额外揭示秘密，是诚实验证者零知识的论证。

它不能不加说明地升级为任意恶意验证者下的所有零知识性质。通过哈希产生挑战的 Fiat–Shamir 变换，也需要明确模型和构造条件，不能把交互协议机械改成哈希就宣布安全。

Shor 算法在可扩展容错量子计算模型中高效求解整数分解和离散对数，威胁相应 RSA、DH 与椭圆曲线方案。Grover 提供通用搜索的平方根级查询加速，影响对称密钥和部分哈希参数选择，但不是所有密码都被同样方式破解。

后量子密码是在经典设备上运行、以抵抗已知量子攻击为目标的密码方案。它与使用量子信道的量子密钥分发不同。

格密码常建立在带噪线性关系的困难性上。例如 LWE 形式 $b=As+e\pmod q$ 中，小噪声使直接解线性方程不再恢复秘密；实际安全依赖维度、模数、噪声和具体问题版本。

哈希签名则主要依赖哈希性质，有些方案要求严格管理一次性密钥状态。不同路线在密钥大小、签名长度、性能和假设成熟度上各有代价。