今天在刷校内论坛的时候，看到了关于黄杨某甜的讨论帖，提到“调查组已经尽力想取得原始购买记录了，但很可惜，就是没有，就是拿不出来（年代久远，还是在实体商店买的，拿不出凭证也可以理解）。所以他们换了个思路，说明当事人一家没有购买真货的记录。”忽然让我想起来了零知识证明中的指数知识假设（Knowledge-of-Exponent Assumption, KEA）。
回想起去年大概也是这个时间，在看Marlin的论文的时候，为了解决Knowledge Soundness的问题，提到了两种解决办法：KoE假设和AGM，在当时可以说是完全无法接受这两个假设，理解也不够深入，整天拉着老大哥Snowolf问，最终也没有搞懂。今天写篇博客来讲一下我现在对于这个假设的浅显理解。
在公钥密码学的世界里，我们通常会依赖各种“困难问题假设”来构建安全的系统。比如我们相信大整数分解是困难的（RSA 假设），或者在特定群中计算离散对数是困难的 (DL Assumption)。这些假设通常是关于计算能力的限制，也更容易理解一些。
而在学习零知识证明中涉及到基于pairing的PCS时，我们会接触到一个新的假设：指数知识假设。这个假设不只是关于计算能力的，而是关于知识本身的限制，进一步又会涉及到一个概念：可证伪性。常常会看到言论，KEA假设是一个不可证伪假设，那么到底为什么是不可证伪呢？
指数知识假设
给定一个元组 $(g,h=g^s,q)$，其中 $g$ 是一个阶为 $q$ 的群 $\mathbb{G}$ 的生成元，$s$ 是一个从 $\mathbb{Z}_q$ 中均匀随机选取的秘密值。
知识指数假设 (KEA1) 声称：对于任何能输出一对值 $(C,Y)$ 并满足 $C \equiv Y$ 的攻击者 $\mathcal{A}$，必然存在一个“知识提取器” $\mathcal{B}$，它能在相同的输入下，从攻击者 $\mathcal{A}$ 的内部状态中提取出一个值 $x$，使得 $g^x \equiv C$。
即，如果攻击者 $\mathcal{A}$ 能输出一对值 $(C,Y)$ 并满足 $C \equiv Y$，那么他必然知道 $x$。
可证伪 vs. 不可证伪
为什么我们对 RSA 或 DDH 这类假设更“容易相信/理解”？答案在于一个关键的科学哲学概念——可证伪性 (Falsifiability)。一个假设如果是“可证伪”的，意味着如果它错了，我们原则上可以拿出一个明确的、可被轻易验证的证据（a witness）来驳倒它。
可证伪假设
RSA 假设：“分解大合数 $N=pq$ 是困难的。”
如何证伪？ 如果这个假设是错的，就意味着存在一个高效的分解算法 $\mathcal{A}$。要证明 RSA 假设是错的，你只需要把这个算法 $\mathcal{A}$ 展示出来。
验证证据：任何人都可以随机生成一个大合数 $N$，用你给的算法 $\mathcal{A}$ 去跑。如果它真的能快速分解出 $p$ 和 $q$，那么 RSA 假设就被无可辩驳地攻破了。这个算法 $\mathcal{A}$ 就是一个具体的、可验证的“见证者”。
不可证伪假设
相比之下，KEA 是“不可证伪”的。假设 KEA 是错误的，这意味着什么？
这意味着，存在一个攻击者 $\mathcal{A}$，它能成功输出 $(C,Y)$，但它并不知道对应的指数 $x$。
这里的困境在于，攻击者 $\mathcal{A}$ 要如何向我们证明它“不知道”那个 $x$ 呢？
它不能只说：“看，我成功了，但我发誓我不知道 $x$。” 这不是科学证明。
我们无法打开算法 $\mathcal{A}$ 的“大脑”（其内部状态）来检查里面到底有没有存储 $x$ 的信息。
证明一个“不存在”（即能提取 $x$ 的知识提取器不存在）远比证明一个“存在”（即存在一个有效的攻击算法）要困难得多。我们无法通过简单地运行攻击者 $\mathcal{A}$ 并观察其输出，来验证“KEA 假设是错的”这一论断。
进一步思考：NP & co-NP
这种“存在”与“不存在”证明难度的不对称性，又可以想到著名的 NP vs. co-NP 问题。
NP 类问题 (存在性问题)：这类问题的特点是，如果答案是“是”，那么存在一个简短的证据（witness），可以被快速验证。
经典问题 (SAT)：给定一个逻辑公式，是否存在一组变量赋值使它为真？如果存在，你把这组赋值给我，我代入一算便知。这个赋值就是那个简短的证据。
co-NP 类问题 (不存在性问题)：这类问题的特点是，如果答案是“否”，那么存在一个简短的证据，可以被快速验证。
经典问题 (TAUTOLOGY)：一个逻辑公式是否对所有赋值都为真？这等价于“是否存在一个赋值使它为假？不，不存在。” 如果它不是重言式，你只需给我一个能让它为假的反例赋值，我一验便知。
困境：但如果这个公式是重言式，你要如何给我一个“简短的证明”呢？你不能把所有可能的赋值（指数级多）都列出来给我看。似乎没有一个简短的证据能让我快速信服“没有任何反例存在”。
学术界普遍相信 NP ≠ co-NP，这正是“证明不存在比证明存在更困难”这一直觉的数学化身。它意味着，有些问题的“是”答案有简短证明，但其“否”答案却没有。
总结
可证伪性是科学哲学中的一个重要概念，它要求一个假设如果错了，必须能被实验或观察所证伪。在零知识证明中，KEA 假设是不可证伪的，因为攻击者 $\mathcal{A}$ 无法向我们证明它“不知道”对应的指数 $x$。
参考文献
[1] https://crypto.stackexchange.com/questions/6117/how-much-do-we-trust-kea1-assumption
[2] https://gemini.google.com