协议：Ｆ—Ｓ 身份认证协议［８］ （１）Ｐ 从 ０ 到 ｎ－１ 中随机选取一个数 ｒ，并计算 ｘ＝ｒ２ｍｏｄｎ； （２）Ｐ 将 ｘ 发送给 Ｖ； （３）Ｖ 将 ｃ 发送给 Ｐ，其中 ｃ 为 ０ 或 １； （４）Ｐ 计算 ｙ＝ｒｓｃ，其中 ｒ 是在（１）中 Ｐ 选取的一个 随机数，ｓ 是 Ｐ 的私钥； （５）Ｐ 将 ｙ 再发送给 Ｖ，从而证明其知道其所声 称的私钥 ｓ； （６）Ｖ 计算 ｙ２ｍｏｄｎ 和 ｘｖｃ，如果 ｙ２ｍｏｄｎ＝ｘｖｃ，则 Ｐ 或者知道 ｓ 的值（Ｐ 是诚实的）或者 Ｐ 已经用其他的 方法计算出了 ｙ 的值（Ｐ 是不诚实的），因为：
（２）可靠性：如果 Ｐ 对 Ｖ 的声称是假的，则 Ｖ 以
概念是由 Ｇｏｌｄｗａｓｓｅｒ 等人［１，２］在 ２０ 世纪 ８０ 年代初 一个大的概率拒绝 Ｐ 的声称．
提出的．从提出到现在已经有 ３０ 多年的时间了，在
（３）零知识性：如果 Ｐ 对 Ｖ 的声称是真的，在 Ｖ
零知识证明的研究中，已经取得了许多重要的成 没有违反协议的前提下，则无论 Ｖ 采用任何方法，
（６）证明者 Ｐ 和验证者 Ｖ 可以反复执行（１）～（５）
ｎ 轮．
在上述的零知识洞穴的例子中，若 Ｐ 没有掌握
秘密通道的咒语，则他只能从他原来进入通道的一
侧出来．若 Ｐ 靠猜测，在整个协议执行的 ｎ 轮过程
中，Ｐ 在每一轮中均能按照 Ｖ 的要求从相应的一侧
出来的概率只有
１ ２ｎ
．经过 １６
轮后，Ｐ 只有
质上是一种涉及两方的协议，其中的一方称为证明 １＜ｘ＜ｎ－１．
者，一般用 Ｐ 表示，另一方称为验证者，一般用 Ｖ ２．３．２ 大整数分解问题
表示．在协议的执行过程中，证明者 Ｐ 向验证者 Ｖ
大整数分解问题是指，给定两个素数 ｐ，ｑ，计算
声称其已经掌握了某种信息，证明者 Ｐ 和验证者 Ｖ 乘积 ｐ＊ｑ＝ｎ 很容易；但是，反过来给定整数 ｎ，求 ｎ
协议：数独的零知识证明协议［５］ 证明者： （１）证明者随机选择一个置换 σ：｛１，２，…，９｝ａ｛１，２， …，９｝； （２）对于每个单元（ｉ，ｊ）的值 ｖ，证明者发送 σ（ｖ）给 验证者； 验证者： 验证者随机选择下列可能性中的一种：或者一 行、或者一列、或者一个子网格，或直接打开已经填 充好的一个单元格，并要求证明者公开相应的承诺． 当验证者做出回应后， 如果验证者选择了一行、一 列或一个子网格，验证者检查其中的所有的值是否 确实是不同的．如果验证者选择的是直接打开已经 填充好的一个单元格，验证者将所填充的单元格中 的数据与证明者所发送的数据做比较，与原来相同 的现在仍然相同，与原来不同的现在仍然不同，这 样就可以说明 σ 的确是单元格中所填充数字的一 种置换． ３．３ 多项式函数根的零知识证明协议 多项式函数是数学中许多重要研究内容之一， 在计算机科学中，多项式函数的研究也有着举足轻 重的作用． 假如 Ｐ 已经知道了某个整系数高次 ｆ（ｘ） 的一个整数根 ｘ０，现在他想向 Ｖ 证明自己已经知道 了多项式函数 ｆ（ｘ）的某一个根，但又不想让 Ｖ 了解 有关 ｘ０ 的任何相关信息，这个问题就是多项式函 数根的零知识证明问题．假设某整系数高次多项式
由 Ｑｕｉｓｑｕａｔｅｒ 等人［４］最先给出了有关零知识证 明解释的通俗例子，如图 １ 所示，在位置 Ｃ 与位置 Ｄ 之间有一个秘密的通道，而这个秘密通道只有知 道相应咒语的人才可以通过．如果证明者 Ｐ 知道通 过秘密通道的咒语，他如何在不泄露咒语的前提下 向验证者 Ｖ 证明他知道咒语呢？可以按照如下协 议的步骤执行：
ｎ
Σ 函数 ｆ（ｘ）＝ ａｉｘｉ，其主要证明过程如下： ｉ＝０ 协议：多项式函数根的零知识证明协议［６］
－７－
（１）Ｐ 与 Ｖ 共同选取 ｐ 和 Ｚ＊ｐ 的生成元 α；
ｉ
ｘ
（２）Ｐ 计算 βｉ＝α ｍｏｄｐ，（ｉ＝１，２，…，ｎ），并将所计算 的 βｉ 返回给 Ｖ；
（３）Ｖ 要求 ｐ 证明他拥有一个数 ｘ０，使得 βｉ≡βｘｉ－０１ （ｍｏｄｐ），（ｉ＝１，２，…，ｎ）；
摘 要：在当代密码学中，零知识证明占据着重要的位置.已经成为信息安全领域身份认证的关键技术
之一,吸引了许多学者的注意，并得到了一系列的重要研究成果.文章首先阐述了零知识证明的主要思想、
零知识证明协议的性质以及零知识证明协议所主要基于的几类数学问题.接着，着重研究了零知识证明在
相关问题中的应用.最后，对本文进行了总结,以期能够吸引更多的学者在更广泛的领域对零知识证明协议
2 零知识证明相关概念
于密码学中的公钥密码体制，都是主要基于如下几
２．１ 零知识证明的主要思想
类数学问题的．
ห้องสมุดไป่ตู้
零知识证明指的的就是一方（证明者）能够在不 ２．３．１ 模 ｎ 平方根问题
向另一方（验证者）提供任何有用的信息的前提下，
设 ｎ 是一个正整数，若存在一个 ｘ，使得 ｘ２≡ｙ
也能使得另一方能够相信某个论断是正确的．其本 （ｍｏｄｎ），则称 ｘ 是 ｙ 的模 ｎ 平方根．其中：１＜ｙ＜ｎ－１，
第 30 卷 第 4 期（上） 2014 年 4 月
赤 峰 学 院 学 报（ 自 然 科 学 版 ） Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｆｅｎｇ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ）
Ｖｏｌ． ３０ Ｎｏ．４ Ａｐｒ． ２０１４
零知识证明协议研究
张引兵， 王 慧
（淮北师范大学 数学科学学院， 安徽 淮北 235000）
进行研究.
关键词：密码学；零知识证明；数独；多项式函数根；身份认证
中图分类号：ＴＰ３９３．０８ 文献标识码：Ａ
DOI:10.13398/ki.issn1673-260x.2014.07.004
文章编号：１６７３－２６０Ｘ（２０１４）０４－０００６－０４
1 引言
一个大的概率接受 Ｐ 的声称．
“零知识证明”－ｚｅｒｏ－ｋｎｏｗｌｅｄｇｅ ｐｒｏｏｆ，这一
图的同构问题：有两个图 Ｇ０（Ｖ０，Ｅ０）和 Ｇ１（Ｖ１，Ｅ１）， 其中这两个图的顶点数和边数都相同，并且存在一 个置换 π，当（ｕ，ｖ）∈Ｅ０ 时，（π（ｕ），π（ｖ））∈Ｅ１，则称图 Ｇ０ 和图 Ｇ１ 同构，记作 Ｇ１＝πＧ０．
协议：图的同构的零知识证明协议［７］ 公共输入：初始化数据：两个图 Ｇ０（Ｖ０，Ｅ０）和 Ｇ１ （Ｖ１，Ｅ１），并且 Ｇ０＝φ（Ｇ１） 使用独立的随机掷币协议执行如下 ４ 步 ｍ 轮． （１）Ｐ 随机选择一个置换 π 生成图 Ｇ０ 的一个置 换图 Ｈ，即：Ｈ＝π（Ｇ０），并将 Ｈ 发送给 Ｖ； （２）Ｖ 随机选择 α∈｛０，１｝，并将 α 发送给 Ｐ； （３）如果 α＝０，Ｐ 将置换 π 发送给 Ｖ；否则，如果 α≠０，Ｐ 将置换 π·φ－１ 发送给 Ｖ； （４）Ｖ 验证 Ｈ＝ψ （Ｇα）（其中当 α＝０ 时，ψ＝π；当 α≠０ 时，ψ＝π·φ－１）是否成立，若成立则继续，否则， 拒绝 Ｐ 的声称． 如果如上协议成功执行了 ｍ 轮，Ｖ 则接受 Ｐ 的证明． 在上述协议中，若 Ｐ 确实掌握了图 Ｇ０ 和图 Ｇ１ 的同构关系 Ｇ１＝φ （Ｇ０），则对所有的置换 πφ 总有 Ｈ＝π（Ｇ０）＝π（φ（Ｇ１）），又因为置换 π 是随机选择的，所 以整个过程中没有泄露有关置换 覬 的任何信息．又 因为 Ｖ 要求证明 Ｈ 与图 Ｇ０ 同构或与图 Ｇ１ 同构是 随机的，所以 Ｐ 只有掌握了置换 φ 才能或者证明 （Ｈ，Ｇ０）同构或者证明（Ｈ，Ｇ１）同构． ３．５ 身份认证中的零知识证明—Ｆ－Ｓ 身份认证协 议 在密码学中，零知识证明最早是作为实体认证 的一种方法进行应用的．Ｆｉａｔ 和 Ｓｈａｍｉｒ 在 １９８６ 年 首先给出了这种身份认证的零知识证明方法，也就
所掌握信息的具体内容，这是一种全新的思想．
解大整数问题将是非常困难的．
２．２ 零知识证明协议的性质
２．３．３ 离散对数问题
一般说来，一个零知识证明协议应该下面三个
离散对数问题指的是整数中一种基于同余运
条件：
算和原根的对数运算，也可以按照如下方式进行简
（１）可行性：如果 Ｐ 对 Ｖ 的声称是真的，则 Ｖ 以 单描述：任意给定一个质数 ｐ，和有限域 Ｚｐ 上的一
－８－
是 Ｆ－Ｓ 认证协议．Ｆ－Ｓ 认证协议一般不单独应用于 现在的认证系统中，但它当今应用的零知识证明身 份 认 证 系 统 的 基 础 ， 像 Ｆｅｉｇｅ－Ｆｉａｔ－Ｓｈａｍｉｒ 和 Ｇｕｉｌｌｏｕ－Ｑｕｉｓｑｕａｔｅｒ 中，都用到了 Ｆ－Ｓ 认证协议．
在 Ｆ－Ｓ 认证协议中，首先找一个证明者和验证 者两方都信任的第三方，第三方选取两个大的素数 ｐ 和 ｑ，然后计算 ｎ＝ｐ×ｑ，其中 ｎ 的值是公开的，而 ｐ 和 ｑ 的值是不公开的．Ｐ 选取一个私钥 ｓ （１≤ｓ≤ ｎ－１），接着计算 ｖ＝ｓ ｍｏｄ ｎ，将 ｖ 作为公钥由可信的 第三方保存．Ｖ 可以按照如下步骤对 Ｐ 进行认证：
ｘ
（４）Ｐ 证明自己拥有 ｎ 个表达式 βｉ≡βｉ－１ （ｍｏｄｐ），
０
（ｉ＝１，２，…，ｎ）同时成立的解 ｘ＝ｘ０，由于 β０＝αｘ０ ＝α 是 Ｚ＊ｐ 的生成元，因而这是可行的；
ｎ
仪 （５）Ｖ 进一步验证 （βｉ）αｉ≡１（ｍｏｄｐ）； ｉ＝０
（６）重复执行（１）￣（５）ｋ 轮． ３．４ 图论中的零知识证明—图的同构的零知识证 明协议
果，但仍有许多问题有待进一步的研究，近年来已 Ｖ 除了能够接受 Ｐ 的声称外，而无法获有关 Ｐ 所声
经成为密码学研究中的热点问题之一．零知识证明 称内容的任何信息［３］．
的思想是许多密码学协议的基础，在安全协议的设 ２．３ 零知识证明协议主要基于的几类数学问题
计中有着比较广泛的应用．
通常零知识证明协议所基于的数学问题，类似
６５５３６ 分
之一的机会猜中．若进过 １６ 轮的验证，Ｐ 在每一轮中
均能按照 Ｖ 的要求从相应的一侧出来，那么 Ｖ 就可