posted at 2022.5.20 12:31 by 风信子
零知识证明(Zero-Knowledge Proof)是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代中期发明的，用来使别人确信你拥有特定的、私有的可证实的信息而不透露该信息。早在16世纪的文艺复兴时期，意大利有两位数学家为竞争一元三次方程求根公式发现者的桂冠，就采用了零知识证明的方法。
在有必要证明一个命题是否正确，又不需要提示与这个命题相关的任何信息时，零知识证明系统是不可或缺的。在零知识证明中有两方，拥有秘密信息的证明者（prover）和想要确认证明者拥有秘密信息的检验者(verifier)。在应用零知识证明时，没有秘密信息的人通过伪装成证明者成功欺骗检验者的概率是极低的。而且，检验者除了知道证明者拥有信息之外，不知道或几乎不知道有关信息的其他任何情况。特别的，检验者不能使第三方相信检验者知道这一信息。
例一，A向B证明自己拥有某个房间的钥匙（该房间只能用钥匙打开锁进入），有2个方法:1是A把钥匙出示给B,B打开锁验证。2是B确定该房间内有某一物体，A把物体拿出来出示给B。第2种方法就属于零知识证明，它的好处在于，在整个证明过程中，B始终不能看到钥匙的样子，从而避免了钥匙的泄露。
例二，你可能想要让别人确信你知道某个大于300位的正整数的两个素因子分解而不告诉他们素因子。应该怎么办呢？采用零知识证明来完成。
下面是例二的一个实际应用：依靠大数难以分解保护个人拥有的私有信息。
应用基于以下事实：一个大数n等于两个素数的乘积（素数都是模4同余于3的大素数），随机选取一个整数x，不知道大数n的素数分解的一方求解x2 (mod n)的平方根很困难，在正常的时间内无法求出。
假设证明者拥有用一列数字v1，v2，···，vm表示的私有信息，其中1<= vj<n，j=1，2,，···，m。这里，n是模4同余于3的两个素数的乘积。证明者公开整数序列s1，s2，···，sm，其中sj≡v2j(mod n)，1<=sj<n。证明者想要检验者确信他知道私有信息v1，v2，···，vm，但不透露信息给检验者，检验者知道的只是她所公开的模n和公开信息s1，s2，···，sm。
此过程的每个循环都有如下的步骤：
（i） 证明者选取随机数r并计算x=r2(mod n)，并将其发送给检验者。
（ii） 检验者选择集合{1，2，···，m}的一个子集S并将其发送给证明者。
（iii）证明者计算r的整数vj的乘积模n的最小正剩余y，其中j∈S，0<=y<n，然后她将y发送给检验者。
（iv） 检验者验证x≡y2z(mod n),其中z是使得j属于S的整数sj的乘积，0<=z<n。
使用随机数r为的是使检验者无法确定秘密信息的部分整数vj的值，这可通过选择集合S={j}来达到目的。当此过程执行后，检验者不会获得能够有助于确定私有信息v1，v2，···，vm的任何新信息。因为集合S有2m种可能，所以不知道私有信息的人利用这一技术欺骗检验者的概率是1/2m。而且，当循环T次时，这一概率缩小为1/2mT。例如：若m=10且T=3，则检验者被欺骗的概率小于十亿分之一。
【演示】
假设保拉想要文斯确信她拥有用整数v1=17，v2=61，v3=55，v4=2011，v5=221，v6=101表示的私有信息。她的秘密模是n=47·53=2491。（在实践中，使用的是具有数百位的素数）
她的公开信息由整数sj和n组成，其中sj≡vj2(mod 2491)，v是v模n的逆，0<sj<2491，j=1，2，3，4，5，6。经过计算，她的公开信息是:
数列{1155，241，835，854，2262，494}以及模2491
保拉通过前文中描述的过程能够使文斯确信她拥有秘密信息。
我们来描述此过程的一个循环。在步骤（i）中，保拉选取一个随机数，比如设为r=1253，然后她将r2模2491的最小正剩余x=679发送给文斯。
在步骤（ii）中，文斯选取{1，2，3，4，5，6}的一个子集（比如s={1,3,4,5}）并告知保拉这一选择。
在步骤（iii）中，保拉计算数字y，0<=y<2491并且
y≡rv1v3v4v5
≡1253·17·55·2011·221
≡1330(mod 2491)
然后，她将y=1330发送给文斯。
最后，在步骤（iv）中，文斯通过验证
x=679≡13302·1155·835·854·2262(mod 2491)
来确认 x≡y2s1s3s4s5(mod 2491)。
文斯可以让保拉对此过程执行多次循环以确认她拥有秘密信息。当他感觉她在欺骗他的概率足够小以满足他的要求时就可以停下来。
以下是辅助零知识证明的工具（求模余、逆）的C#源代码：
public static BigInteger Qiuyu(BigInteger chengshu, BigInteger mod) { x = chengshu % mod; // x = chengshu * chengshu % mod; return x; } public static BigInteger Qiuni(BigInteger chengshu, BigInteger mod) { for (BigInteger y = 1; y < mod; y++) { if ((chengshu * y) % mod == 1) { x=y; } } return x;
}
0e0ad7eb-2afa-4704-a720-7b3ffb681337|0|.0|96d5b379-7e1d-4dac-a6ba-1e50db561b04
Tags: C#, 代码, 方法, 模, 素数, 余
IT技术
