如何构造一个数学例子来证明零知识证明可行？ 第1页

1. 概念

零知识证明 zero-knowledge proofs，简写为 ZKPs，最初由 S.Goldwasser、S.Micali 及 C.Rackoff 在 1985 年的论文《互动证明系统的知识复杂性》提出，指的是证明者能够在不向验证者提供任何有用信息的情况下，使验证者相信某个论断是正确的。

2. 基于同态隐藏的零知识证明实现

用数学语言描述零知识证明的过程：
已知两个数 和 ，需要在不泄漏这两个数的前提下，证明 。（注：这只是零知识证明的一种场景）

要实现这一点，需要引入一个同态隐藏函数 ，该函数满足一下3个条件：

（1）知道 的值，无法反推 的值；

（2）如果 ，那么 ；

（3）根据 和 ，可以算出 ，比如： g

使用同态隐藏函数，则零知识证明过程为：

证明者把 和 告诉验证者，验证者算出 ，然后判断是否等于 。也就是说，把验证 转化成了验证 。

根据同态隐藏函数的3个条件，以上证明过程显然是成立的。

3. 同态隐藏的实现

3.1 数据基础

3.1.1 模 加法

模 加法，就是加完之后对 取模。比如（ ）：

集合 称为有限群。集合中元素的个数，称为有限群的阶。

3.1.2 模 乘法

模 乘法，就是相乘之再对 取模。比如（ ）：

使集合 中每个元素对自身不对地做模 乘法，则有：

观察元素3和5，可以发现集合中每个元素都可以被生成出来。这种群称为循环群，元素3和5称为一个生成元。实际上，所有素数阶的有限群都是循环群。

3.2 函数构建

生成元 ，取，则 。

以下验证满足前面的3个条件：

（1）由于生成的元素是乱的，所以无法根据 反推出 。（在实际应用中，p通常是一个大素数，比如 量级的数，以目前计算机的计算能力，是没有办法算出完整的表的，术语叫离散对数难题）；

（2）如果 ，那么 。这条是满足的，因为生成元的作用就是生成集合中的每一个元素，从表中的数据也可以看出来；

（3）根据 和 可以算出 。根据指数运算法则： 。

3.3 扩展

实际上，基于同态隐藏的ZKPs，不仅仅支持加法，也支持所有的“线性组合”，比如 ：

【参考】
[1]稀土掘金 - 什么叫同态隐藏

—— 更多内容，请访问专栏：【隐私计算】