导语
本文是“零知识证明引论”系列的第二部分。在第一部分中， 我们了解了零知识证明提出的背景,定义以及相关概念。下面我们将介绍零知识证明中的核心数学工具，其包括椭圆曲线，同态隐藏和 多项式规约过程。由于长度限制，我们将分两个部分介绍。本文主要介绍椭圆曲线以及同态隐藏。
核心数学工具
1、椭圆曲线
自从1976年Diffie和Hellman提出了公钥密码体制的思想后, 人们提出了大量公钥密码体制的实现方案, 所有这些方案的安全性都是基于求解某个数学难题. 1985 年, Koblitz和 Miller 各自独立的将有限域上的椭圆曲线用于设计公钥密码系统, 自那以后, 常见的公钥密码体制按所基于的数学难题分类, 大体有两类三种:
1.1、 离散对数难题
如果对于一个整数 ?和质数 ?的一个原根 ? (数论:如何理解原根 – YouTube [https://www.youtube.com/watch?v=xYnDhWAQ4fU])，可以找到一个唯一的指数 ? ，使得：
b=a^i bmod p
其中 0≤?≤ ?−1 成立，那么指数 ? 称为 ? 的以 ? 为基数的模 ? 的离散对数。
离散对数难题是指：当已知一个大质数 ? 和它的一个原根 ? ，如果给定一个 ? ，要计算 ? 的值是相当困难的。
1.2、椭圆曲线上的离散对数难题
椭圆曲线就是二元三次等式。
能被写成各种各样的形式,但是大家常见的是short Weierstrass form:
图像形如（b=1, a从2到-3）
Koblitz曲线家族和Pesudo-Random Curve属于这一类（secp256k1）
现在还有两种常用形式：
蒙哥马利（Montgomery）形式
爱德华（Edwards）形式
以short Weierstrass form为例，定义点加法：
定义2A=A+A
于是可以定义标量乘法：
椭圆曲线上的离散对数难题：
已知椭圆曲线上的一个点G(x,y)，一个大数n，计算nG=P很容易，但是知道P和G，计算n比较难，但不是特别难，这是个对数问题，不是对数难题。
如果我们将椭圆曲线通过mod运算定义在有限域上，那么知道P和G，计算n将变成一个离散对数难题。
我们可以这样理解：mod运算类似一种压缩算法，会在保留群的基本性质的情况下，损失掉计算因子，变成了有限域的循环，从而无法进行倒推还原计算因子。
以secp256k1为例，曲线表达为：
离散图像为：
以上的离散对数难题，就是椭圆曲线加密及签名算法的基础。
在区块链中，椭圆曲线主要用于签名，大部分的区块链系统采用了ECDSA (https://okg-block.larksuite.com/docx/doxusyqO3Im5zGmfPiUaeoDvLHd)算法，主要用于交易的溯源和验证，但是在零知识证明中，我们主要用到的是椭圆曲线的同态特性来进行同态隐藏。
2、同态隐藏
加密技术很早就存在了，经典的加密技术主要为了隐藏信息，因此加密后的数据具备不可读、不可操作的特性。而部分场景下，我们希望能对加密后的数据进行某些操作，然后还原回明文时保留这些操作，于是我们在非对称加密算法中找到一些具备这种特性的算法，称之为同态。
假设加密函数为E(x)，那么同态加密可以用下列公式表示：
而减法可以转换为加法处理，除法在有限域内可以转换为乘逆元。
全同态则表示该加密函数既满足加法同态，又满足乘法同态，目前可商用性不强，不在本文讨论范围内。
举个及其简单的例子，如果令加密函数
，那么该加密函数满足加法同态的性质，因为
而如果令加密函数
那么该函数满足乘法同态的性质，因为
常用的加法同态算法如Palliar，常用的乘法同态算法如ElGamal、RSA
2.1、椭圆曲线盲验证
椭圆曲线满足加法同态：
所以我们可以构造出一个基于椭圆曲线的加法同态加密算法用于多项式盲验证：
假定Alice知道一个最高d次的多项式P，而Bob想要验证Alice知道这个多项式的系数，要怎么办呢？
最简单的办法，设置一个或多个大家都知道的多项式的解。例如：
Alice 宣称他知道一个阶数为 3，其中两个根分别为 1 和 2 的多项式，也就是说这个多项式的形式为：
(x-1)(x-2) · …
换句话说 (x–1) 和 (x –2) 是问题中多项式的两个因式。因而如果 Alice 想要在不揭示多项式的前提下证明他的多项式确实有这两个根，那么他就需要去证明他的多项式 p(x) 是 t(x) = (x- 1)(x- 2) 和一些任意多项式 h(x) 的乘积，即：
p(x) = t(x) · h(x)
自然算出 h(x) 的方式就是直接相除：
如果Alice 不能找到这样一个 h(x) 也就意味着 p(x) 中不包含因式 t(x)，那么多项式相除就会有余数。例如我们用 p(x) = x³ – 3x² + 2x 除以 t(x) = (x – 1)(x – 2) = x² – 3x+ 2
我们算出结果 h(x) = x，没有余数。
而如果我们用p′(x) = 2x³ – 3x² + 2x, 除以 t(x) = (x – 1)(x – 2) = x² – 3x+ 2，会得到余数7x – 6，无法提交正确结果。
利用以上的方法，我们就可以构造一个多项式一致性检查协议：
•Bob 挑选一个随机值 s, 计算 t = t(s) ，然后将 s 发送给 Alice。
•Alice 计算 h(x) =p(x) / t(x) ，并对 p(s) 和 h(s) 进行求值，将计算结果 p, h 提供给 Bob。
•Bob 验证 p= t⋅h，如果多项式相等，就意味着 Alice知道全部的系数。
但是上述方法是有缺点的，如下：
•Alice 可能并不知道他所声称的 p(x)，他可以先算一下 t = t(s)，然后选择一个随机值 h，由此计算出 p = t⋅h。因为等式是成立的，所以也能通过 Bob 的校验。
•因为 Alice 知道随机点 x = s ，他可以构造出一个任意的多项式，这个任意多项式与 t(s) ⋅ h(s) 在 s 处有共同点。
•在前面的「陈述」中，Alice 声称他知道一个特定阶数的多项式，但现在的协议对阶数并没有明确的要求。因而 Alice 完全可以拿一个满足因式校验的更高阶数的多项式来欺骗 Bob。
上述问题的关键是是s值的暴露，所以接下来我们用同态加密来解决上述问题
Bob可以通过椭圆曲线构造一个，然后取一个随机数s。
此时Alice知道P不知道s，Bob知道s不知道P，Bob不能直接告知Alice关于s的值，因为这样无法验证多项式系数，Bob计算,给到Alice。
Alice利用同态特性，可以计算出
然后将该结果发给Bob，E(h(s))的计算同理，现在Bob有了E(p(s))和E(h(s))，就可以用他的私钥来解密得到p(s)和h(s)。
那么，他怎么能确保Alice是用正确的多项式计算来的呢？Alice依然可以不使用 Bob 所提供的加密值进行计算，而是通过其它的方式来伪造证明。
光有一个单一的s肯定不够，验证验证，肯定还需要另一个值来作为参照。
所以我们引出对这个概念：
在有限循环群G中，如果且，那么就称为一个对
也就是说，b是a的倍。有了这个概念，就可以进行一项”系数知识假设”（Knowledge of Coefficient Assumption，KCA）：
•Bob秘密选一个随机的α值，生成一个对：
•Bob把这个α对发送给Alice
•Alice需要回复一个不同的α对：
•Bob验证是不是对
•如果是则接受该回复
得益于椭圆曲线的离散对数难题，Alice是无法知道的，既然Alice不知道，那么她就只有一种方法可以生成新的对：给a和b各乘上同一个系数。
有了前边的KCA工具，Bob可以基于s构造一个d阶系数知识假设（d-KCA）[3]：
•Bob秘密选一个随机的值和s值
•生成d个对发送给Alice
•Alice利用椭圆曲线的同态原理和知道的多项式系数，来生成新的对
最终，经过以上步骤，Bob就可以确认Alice是知道多项式系数的了。整体过程如下图所示：
第2章我们提到过非交互性，显然上述的盲验证过程是交互性的，我们接下来用另一套数学工具，来构造这个多项式盲验证的非交互性协议。
2.2、双线性配对
构造非交互性协议，我们就需要一个可以被重复使用，公开，可信，又不会被滥用的秘密参数。
在上述盲验证协议中，我们发现，用于验证的秘密值主要是s和α，而如果我们要构造非交互证明，就要把验证过程中的t(s)和α作为公共参数，这样就可以实现一步公开验证了，而不需要任何单一的Verifier实体参与。
所以，接下来要思考的是如何在构造出秘密值 (t(s),α) 之后保证它的安全性。
当然还是用椭圆曲线来加密了，方式与 Bob 在发送加密值给 Alice 之前对s的幂使用的加密方式一致。但是我们使用的椭圆曲线同态加密是加法同态，并不支持两个秘密值的相乘，这一点对t(s) 和h(s)的加密值相乘以及 p(s) 和α的加密值相乘的验证都很重要。
似乎陷入了死胡同，难道我们要用全同态算法？好在数学家们已经给我们准备好了工具——Bilinear Pairing 双线性配对。
双线性配对最早由法国数学家André Weil在1946年二战中的监狱里提出，当时还没有系统的密码学（3年后香农发表著名论文《保密系统的通信理论》奠定密码学理论基础，而公钥密码学的发展更在30年之后）。目前主要用于BLS聚合签名和零知识证明等领域。
配对可以直观地理解为，椭圆曲线 1 中两个点 P、Q，通过「乘法」运算（准确地讲，是一种经过精心构造的超椭圆曲线对，具体理论参考[4][5]），能够映射成为椭圆曲线 2 中的点 R。
同时，他们之间有着类似「乘法」结合律、交换率那样的关系：
我们就称R为点P和Q的双线性映射，记为
设 P=αG1，Q=βG1，有 R=P·Q=(αβ)G2，其中 G1 是椭圆曲线 E1 中的基点，G2 是椭圆曲线 E2 中的基点。则映射关系可以表示为：e(αG1, βG1) =αβ· e(G1, G1)。
其通俗解释为：E1 中点 P、点 Q「乘法」运算后，映射到 E2 中的点 R，相当于 E1 中基准点 G1 和 G1 进行「乘法」运算「映射成」E2 中的一个点，再由该点「标量乘」α·β次得到 R 点。
就好像有限元宇宙中的两个元素，通过某种「运算」，能够「生成」平行元宇宙中的一个元素，它们之间有着类似「乘法」的联系。
这样我们就构造出了一个基于椭圆曲线配对的弱化版同态乘法运算，之所以是弱化版，是因为只支持两个加密值的相乘。
有了以上工具，通过 P 点隐藏t(s)，Q 点隐藏h(s)，就可以通过验证 P·Q 是否等于，来验证t(s)·h(s)是否等于p(s)。同理，通过P’点隐藏，Q’点隐藏,可以验证对。
总结一下，我们使用了结合椭圆曲线的d-KCA算法（对，同态加密），可以实现交互式的多项式零知识验证，然后再使用椭圆曲线配对，将公共随机值进行隐藏，从而将该协议升级为非交互协议。
本篇文章介绍了零知识证明中的一些核心数学工具 ，包括椭圆曲线和同态隐藏。下篇文章， 我们将继续介绍零知识证明中的其他核心数学攻击， 欢迎大家继续关注。
参考文献
[3] Groth J. Short pairing-based non-interactive zero-knowledge arguments[C]. International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2010: 321-340.
[4] D. Boneh, B. Lynn, and H. Shacham, Short signatures from the Weil pairing,Asiacrypt 2001, LNCS 2248, pp.514-532, Springer-Verlag, 2001.
[5] S. D. Galbraith, K. Harrison, and D. Soldera, Implementing the Tate pairing,ANTS 2002, LNCS 2369, pp.324-337, Springer-Verlag, 2002.
原文始发于微信公众号（Numen Cyber Labs）：Numen | 零知识证明引论Part 2
