（计算机软件与理论专业论文）全无泄露的位承诺协议与不可否认数字签名方案研究.pdf

摘要 零知识证明是一种高级密码协议，它是指声称者要向验证者证明某断言 的真实性，却并不向验证者泄露任何与该断言有关的其他信息。零知识证明是构 建安全密码协议的强大工具，它在密码学中得到了广泛的应用，尤其是在身份认 证、数字签名方面。 位承诺是实现零知识证明的重要工具。自b l u m 于1 9 8 2 年首先提出了位承诺 【l 】的概念后，它已经成为了密码学研究的一个活跃领域。密码学家指出如果有了 好的加密算法，任何n p 命题都有一个零知识证咧2 1 。这里的加密算法本质上就 是位承诺算法。位承诺是构建零知识证明的重要子协议，不仅如此，位承诺的类 型直接影响着其所构建的上层零知识证明的零知识类型。 不可否认数字签名是个与零知识证明紧密联系的概念。在不可否认数字签名 中，签名的接受者无法自行验证签名，双方通过执行一个签名验证协议，签名者 可向签名的接收者零知识地证明签名是否有效。不可否认数字签名可用于防止数 字签名的复制及传播，保护签名者的隐私。 本文以几个身份识别的零知识证明为例，详尽地证明了它们的正确性、合理 性，分析了它们所达到的零知识类型。总结了“验证者挑战 和“验证者提问 的两种零知识证明结构，指出在第二种结构下，通过使用一个全无泄露的位承诺， 可构建出完善的零知识证明。从构建零知识证明的角度出发，将位承诺协议区分 为全无泄露的、统计上无泄露的、计算上无泄露的不同类型。指出位承诺协议的 类型决定着上层零知识证明的零知识类型，而全无泄露的位承诺是实现完善零知 识证明的前提保证。基于本文提出的“离散对数对碰撞 问题理论，提出了一个 新的全无泄露的位承诺协议，它的使用完全不会增加上层协议信息泄露的可能， 是构建零知识证明的完美子协议。通过图的三着色命题的零知识证明实例，证明 了以此新的全无泄露的位承诺协议可构建出n p 问题的完善零知识证明。 对d a v idc h a u m 的零知识不可否认数字签名方案进行了改进，运用分割选择 以及新提出的全无泄露的位承诺技术，构造了新的完善零知识的确认协议和否认 协议。新的否认协议与c h a u m 的方案相比，在同样的安全级别下所需的模乘运算 呈指数级别地降低。分别基于s c h n o r r 签名和广义e l g a m a l 型签名，提出了新的 随机化的不可否认数字签名生成算法，消除了之前签名方案所具有的存在性伪造 问题同时可以复用之前的签名验证及否认协议。 关键词：零知识证明；完善的零知识证明：离散对数问题；位承诺协议；不 可否队数字签名 a b s t r a c t az e r o - k n o w l e d g ep r o o fa l l o w so n ep e r s o nt oc o n v i n c ea n o t h e rp e r s o no fa s t a t e m e n t ，w i t h o u tr e v e a l i n ga n y t h i n go t h e rt h a nt h ev e r a c i t yo ft h es t a t e m e n t a sa p o w e r f u lt o o lf o rc o n s t r u c t i n gs e c u r ec r y p t o g r a p h i cp r o t o c o l ，z e r o - k n o w l e d g ep r o o f i s w i d e l ya p p l i e di nc r y p t o l o g yd o m a i n ，e s p e c i a l l yi ni d e n t i t ya u t h e n t i c a t i o na n dd i g i t a l s i g n a t u r e 一 s i n c eb l u mf i r s t l yp r o p o s e dt h ec o n c e p to fb i tc o m m i t m e n t 【1 1i n 19 8 2 ，i th a s a l r e a d yb e c o m ea na c t i v ed o m a i ni nc r y p t o l o g yr e s e a r c h t h ec r y p t o l o g ys c i e n t i s t p o i n t e do u tt h a ti ft h e r ee x i t s tas e c u r ee n c r y p t i o ns c h e m et h e ne v e r yn pl a n g u a g eh a s az e r o k n o w l e d g ep r o o t f 2 1 t h ee n c r y p t i o ns c h e m eh e r ee s s e n t i a l l yi sm eb i t c o m m i t m e n ts c h e m e t h eb i tc o m m i t m e n tp r o t o c o li st h ei m p o r t a n ts u b - p r o t o c o li n c o n s t r u c t i n gz e r o - k n o w l e d g ep r o o f n o to n l yt h a t ，t h et y p e o fi t i m m e d i a t e l y i n f l u e n c e st h ez e r o - k n o w l e d g et y p eo fz e r o k n o w l e d g ep r o o fw h i c hi sc o n s t r u c t e db y i t u n d e n i a b l ed i g i t a ls i g n a t u r ei st h ec o n c e p t i o nt h a ti sr e l a t e dt oz e r o - k n o w l e d g e p r o o f i nu n d e n i a b l es i g n a t u r es c h e m e ，t h er e c e i v e ro fas i g n a t u r ec a n tc o n f i r mt h e v a l i d i t yo ft h es i g n a t u r eb yh i m s e l f , u s i n gaz e r o - k n o w l e d g ev e r i f i c a t i o np r o t o c o l ，t h e s i g n e rc a l lp r o v et o t h er e c e i v e rw e t h e rt h es i g n a t u r ei st u r eo rn o t u n d e n i a b l e s i g n a t u r ec a np r e v e n tt h er e p r o d u c t i o na n dd i s s e m i n a t i o no ft h es i g n a t u r ea n dp r o t e c t t h ep r i v a c yo ft h es i g n e r t h i sp a p e r sw o r ka n dr e s e a r c ha r ea sf o l l o w s ： t a k es e v e r a lz e r o - k n o w l e d g ep r o o f so fi d e n t i t ya u t h e n t i c a t i o na se x a m p l e st o p r o v et h ec o m p l e t e n e s s a n ds o u n d n e s so ft h e mi nd e t a i l ， a n da n a l y z et h e z e r o k n o w l e d g et y p e w h i c h t h e y c a na c h i e v e s u m m a r i z et w ok i n d so f z e r o k n o w l e d g ep r o o fs t r u c t u r e s ： v e r i f i e rc h a l l e n g i n g a n d v e r i f i e rq u e s t i o n i n g ” u n d e rt h es e c o n dk i n do fs t r u c t u r e ，b yu s i n gab i tc o m m i t m e n tw h i c hi sa b s o l u t e l yn o r e v e a l i n g ，i tc a nc o n s t r u c tap e r f e c tz e r o k n o w l e d g ep r o o f p r o p o s e dad e f i n i t i o n ： “d i s c r e t el o g a r i t h mp a i rc o l l i s i o np r o b l e m ”，a n dp r o v et h a tt h es o l u t i o nd i f f i c u l t yi s e q u i v a l e n tt ot h e “d i s c r e t el o g a r i t h mp r o b l e m ”a c c o r d i n gt ot h ec o n s t r u c t i o no f z e r o - k n o w l e d g ep r o o f , t h eb i tc o m m i t m e n tp r o t o c o li n c l u d e sd i f f e r e n tt y p e s ：p e r f e c t n o n - r e v e l a t i o n ，s t a t i s t i c a ln o n r e v e l a t i o na n dc o m p u t a t i o n a ln o n r e v e l a t i o n p o i n t e d o u tt h a tt h et y p eo fb i tc o m m i t m e n td e t e r m i n e st h ez e r o k n o w l e d g et y p eo fu p p e r z e r o - k n o w l e d g ep r o o f , w h i l et h ep e r f e c tn o n r e v e l a t i o nb i tc o m m i t m e n t i st h e p r e c o n d i t i o nf o rr e a l i z i n gt h ep e r f e c tz e r o - k n o w l e d g ep r o o f b a s e do nt h e “d i s c r e t e l o g a r i t h mp a i r c o l l i s i o n p r o b l e m ”，p r o p o s e an e w p e r f e c tn o n r e v e l a t i o nb i t c o m m l t m e n t s c h e m e ，w h i c hc o m p l e t e l yd o e s n ti n c r e a s et h e p r o b a b i l i t y o f r e f o r m a t i o nr e v e l a t i o no f u p p e rp r o t o c o la n dc a ns e r v ea st h em o s tp e r f e e t s u b - p r o t o c o l mc o n s t r u c t i n g z e r o - k n o w l e d g ep r o o f t h r o u g ht h ee x a m p l eo f z e r o 。k n o w l e d g ep r o o fo fg r a p ht h r e ec o l o r a b i l i t y ( g 3 c ) l a n g u a g e ，p r o v et h a tt h e p e r f e c tz e r o k n o w l e d g ep r o o fo fn pl a n g u a g ec a l lb ec o n s 仃u c t e da c c o r d i i l gt ot l l i s n e wp e r f e c tn o n - r e v e l a t i o nb i tc o m m i t m e n ts c h e m e m a k es o m em a p r o v e m e n t st ot h ez e r o k n o w l e d g eu n d e n i a b l e d i l g i t a ls i g n a t u r e s c h e m ep r o p o s e db yd a v i dc h a u m b y u s i n g “c u ta n dc h o i c e a i l dt l l en e w l v p r o p o s e dp e r f e c tn o n r e v e l a t i o nb i tc o m m i t m e n t t e c h n o l o g y , t h en e wp e r f e c t z e r o 。k n o w l e d g ec o n f i r m a t i o np r o t o c o la n dd i s a v o w a lp r o t o c o lc a nb ec o n s t r u c t e d c o m p a r e dw i t ht h es c h e m eo fc h a u m ，u n d e rt h es a m es e c u r i t yr a n k t h er e q u i r e d m o d u l a rm u l t i p l i c a t i o no p e r a t i o n sa r er e d u c e de x p o n e n t i a l l y b a s e d t h es c h n o r r s i g n a t u r ea n dt h eg e n e r a l i z e de l g a m a ls i g n a t u r e ，t h en e wr a n d o m l yu n d e n i a b l e d i g i t a ls i g n a t u r ea l g o r i t h mi sp r o p o s e d t h i sa l g o r i t h me l i m i n a t e st h ee x i s t e n c ef o r 2 e p r o b l e mo ff o r m e rs i g n a t u r es c h e m e s ，a n dr e p e t i t i o u s l yu s e st h ef o r m e rs i g n a t u r e c o n f i r m a t i o na n dd i s v o w a la g r e e m e n ta tt h es a m et i m e k e yw o r d s ：z e r o k n o w l e d g ep r o o f ；p e r f e c tz e r o k n o w l e d g ep r o o f ；d i s c r e t el o g 矗t h i i l p r o b l e m ；b i tc o m m i t m e n tp r o t o c o l ；u n d e n i a b l es i g n a t u r e i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：签字日期：年月 e t 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：年 月 日 导师签名： 签字日期：年月 日 全无泄露的位承诺协议与不可否认数字签名方案研究 1绪论 1 1 研究背景 8 0 年代初，g o l d w a s s e r 3 】等人提出了零知识证明这一概念。零知识证明包括 两个方面，一方为证明者，另一方为验证者。证明者试图向验证者证明某个断言 是正确的，但并不向验证者泄露任何与该断言有关的其他信息，而验证者也无法 使用一次证明的脚本转而使第三方相信该断言的真实性。零知识证明是构建安全 密码协议的强大工具，它在密码学中得到了广泛的应用，尤其是在身份认证、数 字签名方面。 零知识证明可用于身份识别。用户a 拥有能够标志他身份的某个秘密，通过 证明对该秘密的拥有，a 可向用户b 证明自己的身份。b 不能在证明中获取a 的秘密 从而进行冒充，也不能向第三方证实a 的身份。已提出的一些著名的身份证明方 案有f i a t - s h a m i r 身份识别、g u i l l o u - q u i s q u a t e r 身份识别、s c h n o r r 身份识别等。 国内的学者也对身份识别进行了深入的研究，并将身份识别与智能卡技术结合起 来应用于用户的身份验i 正c 4 1 t 5 i t 6 1 ；在实现零知识证明的同时也解决了密钥的安全 保存问题。 在不可否认数字签名中，通过执行签名确认及否认协议，签名者可零知识地 向验证者证明某个签名的合法性，从而又不增加泄露签名密钥的风险，也不会为 敌手伪造有效签名提供可能。 零知识证明按照安全级别可分为完善的、统计的、计算的、无用的不同类型 【7 】。完善的零知识证明是指存在一个多项式时间模拟器，能够自行产生一些协议 运行的脚本，该脚本与真实脚本具有相同的概率分布。完善的零知识证明具有最 完美的零知识属性。 位承诺是指协议的一方a 向另一方b 给出某一密文的承诺值，根据该承诺值b 无法探知该密文。直到某个时间以后，a 再向b 揭示之前的密文。而另一方面，b 希望确信a 在给出承诺值之后并没有改变原来的密文。 刍b l u m 于1 9 8 2 年首先提出 了位承诺【1 】的概念后，它已经成为了密码学研究的一个活跃领域。位承诺是构建 其他许多密码协议的重要子协议，它可用来在密码协议中产生双方都可信赖的随 机源，它也是构建零知识证明协议的重要工具。 密码学家指出，假设有了单向函数并因此有了好的加密算法，则任何n p 命 题都有一个零知识证明1 2 】。b l u m 证明了任何数学定理都能被转化为一个图，使得 这个定理的证明等价于证明图的汉密尔圈。因此，任何数学证明都能被转化为一 硕士学位论文 个零知识证明。密码学家进一步证明【8 】，假设存在一个安全的加密函数，则能用 交互式证明来证明的每一件事，也能用零知识交互式证明来证明。在这里，好的 安全的加密函数指的就是位承诺算法。 很多的文献阐述了构建零知识证明的一般性方法【2 】【8 】【9 】【1 0 】，但并没有着重对 位承诺算法进行深入讨论，而是假定已有一个“安全的”位承诺加密算法。而实 际上，从构建零知识证明的角度出发，存在着不同类型的位承诺算法，并且位承 诺协议的零知识类型直接决定着其所构建的上层零知识证明协议的零知识类型。 之前的文献给出了一些用哈希函数、二次剩余【l l 】加密实现的位承诺，它们都 是属于统计上或是计算上无泄露的位承诺，以它们为子协议所构建的零知识证明 的安全类型也只能是统计的、计算的，而不能成为完善的零知识证明。文献 9 】 以一个图的三着色问题为例，阐述了通过一个安全的位承诺加密算法，一切n p 命题均有一个零知识证明。由于在该图的三着色命题的零知识证明中所使用的是 基于二次剩余问题的位承诺( 属于计算上无泄露的零知识) 算法，使得该证明的 零知识性完全依赖于二次剩余问题的难解性，一旦二次剩余问题被破解，则该证 明的零知识性将荡然无存，图的三着色解将被暴露。文献 1 2 提出的n p 命题的零 知识证明理论也同样是依赖于基于二次剩余的位承诺。 数字签名已经广泛地应用于电子商务以及网络安全中。数字签名可用来保护 信息产品的版权，但普通的数字签名很容易被复制和传播。为了保护签名者的隐 私，防止数字签名的任意传播，d a v i dc h a u m h 】【1 4 】提出了不可否认数字签名的概 念。不可否认数字签名是需要签名者的参与才能验证签名有效性的一种数字签名 方案，签名的接收者不能自行验证签名的有效性，也不能向第三方证明签名的有 效性。研究人员对不可否认数字签名方案进行了扩展，提出了可转化的不可否认 数字签名方案【15 1 、证实数字签名方梨1 6 l 【1 7 】等。 c h a u m 和v a na n t v e r p e n 首先在 1 4 中提出了一个不可否认的数字签名算法 实现，算法分为两部分，确认协议通过它签名者可向验证者证明一个有效的数 字签名，但不能证明一个非法的签名；否定协议一通过它签名者可向验证者否认 一个非法的数字签名，但不能否认一个合法的签名，该算法不具备零知识性。接 着c h a u m 在 1 8 中又提出了一个零知识的不可否认数字签名算法，将签名确认和 否认协议升级为零知识证明。之后a t s u s h if u j i o k a 等人提出了一种“b i p r o o f ” 最小知识证明系统【1 9 】，并将其运用到不可否认数字签名上，给出了一个最小知识 泄露的不可否认数字签名算法，该算法利用位承诺和分割选择技术，将签名的确 认和否认合并为一个协议。 c h a u m v a n t w e r p e n 以及a t s u s h if u j i o k a 等提出的不可否认数字签名方案采 用的是同一个签名生成算法，其属于确定性签名，并且有存在性伪造。 2 全无泄露的位承诺协议与不可否认数字签名方案研究 1 2 本文的研究工作及内容安排 1 2 1 本文的主要研究内容及意义 对零知识证明的思想和方法进行了详细的论述，列举了一些零知识证明的实 例，分析证明了它们各自的正确性、合理性、零知识性，指出了它们所达到的零 知识类型。在讲述实例的同时，总结出零知识证明协议的两种结构一“验证者挑 战 和“验证者提问 。指出在第二种结构下，通过使用一个全无泄露的位承诺 算法，可构建出“完善的”零知识证明。 从构建安全的零知识证明的角度出发，分析了位承诺作为子协议对上层知识 证明协议的零知识性所产生的影响，将位承诺区分为全无泄露的、统计上无泄露 的、计算上无泄露的三种类型。指出了位承诺协议的零知识类型直接决定着上层 零知识证明协议的零知识类型。对于全无泄露的位承诺，承诺值的输出脚本表现 出完全相同的概率分布，不存在任何的信息泄露，是构建零知识证明的极好子协 议，它为实现“完善的零知识证明提供了前提保证。 提出了“离散对数对”及“离散对数对碰撞”问题的定义，形式化地证明了 它们的困难性等同于“离散对数问题”。 提出了一个新的全无泄露的位承诺协议，无论待承诺的密文为何值，该协议 的承诺值输出都表现出相同的均匀分布。在最后揭示被承诺的密文之前，输出的 承诺值完全不会泄露关于被承诺密文的信息。该位承诺协议的不可悔性基于之前 提出的“离散对数对碰撞”问题。将该新的位承诺协议嵌入到上层零知识证明中， 完全不会增加上层协议信息泄露的可能，不会降低上层协议的零知识安全性。在 具有“验证者提问”结构的零知识证明协议中，采用该位承诺协议可构造出完善 的零证明。在之前的图的三着色问题的证明中，由于使用的是计算上的位承诺算 法，因此实现的也只不过是计算上的零知识证明；若使用新提出的全无泄露的位 承诺代替之前的位承诺算法，则可实现该n p 命题的完善零知识证明。 基于分割选择的思想，利用之前提出的全无泄露的位承诺子协议，提出了 一对新的不可否认数字签名的确认协议及否认协议，并对它们的正确性、合理性、 零知识性进行详细的分析和证明。a t s u s h if u j i o k a 的方案实现的是最小知识泄 露，我们的方案实现的是完善的零知识证明。与c h a u m 的零知识否认协议相比， 在同样的安全级别下，我们提出的零知识否认协议所需的模乘运算呈指数级的下 降。 c h a u m v a n t w e r p e n 以及a t s u s h if u j i o k a 等提出的不可否认数字签名方案采 用的是同一个签名生成算法，其属于确定性签名，并且有存在性伪造。 确定性数字签名是指签名函数是消息空间到签名空间的一一映射，它对某 特定消息的签名不变化。如r s a 、r a b i n 签名算法，以及之前提出的不可否认签 3 硕十学位论文 名算法都属于确定性签名。另一类是随机化数字签名，也称概率式数字签名。在 这种方案中，根据签名算法中选择的随机参数值的不同，对同一消息的签名也有 对应的变化。如d s a 、e l g a m a l 等就属于随机化签名方案。 存在性伪造是指在没有获取签名者密钥的情况下，也能伪造出至少一个消 息的签名。r s a 、e l g a m a l 以及之前提出的不可否认签名算法都具有存在性伪造。 本文提出了新的基于离散对数的随机化的不可否认签名生成算法，包括一 个基于s c h n o r r 签名的不可否认签名算法和一类基于广义e l g a m a l 型签名的不可 否认签名算法，新的签名算法属于随机化数字签名，提高了伪造特定消息签名的 困难性，消除了存在性伪造。在新的签名算法下，可以复用之前的各种确认及否 认协议进行签名的验证。证明了新的基于s c h n o r r 签名的不可否认数字签名算法 与s c h n o r r 签名算法具有同样的安全性。 1 2 2 本文的章节安排 第一章： 介绍了本文的研究背景，本文的研究工作及贡献。 第二章： 讲述了零知识的定义和零知识的类型，列举了几个身份识别协议，对它们的 正确性、零知识性进行了详细的分析，指出存在的信息泄露，提出改进的办法。 总结了两种零知识证明协议的结构。分析了在“验证者挑战”的零知识结构 下可能存在选择文本攻击，并且需要避免重复使用同一个证据。指出在“验证者 提问 的零知识结构下，协议的零知识类型直接由位承诺子协议的类型所决定， 通过一个全无泄露的位承诺能够达到完善的零知识性。 第三章： 从构建零知识证明的角度出发，将位承诺协议区分为全无泄露的、统计上无 泄露的、计算上无泄露的不同类型。指出作为零知识证明的子协议，位承诺的信 息泄露导致了上层知识证明的信息泄露，位承诺协议的类型直接影响着上层知识 证明的零知识类型。介绍了以哈希函数以及二次剩余加密实现的位承诺协议，指 出他们分别属于统计上无泄露的和计算上无泄露的位承诺类型，它们不能构造出 完善的零知识证明。只有全无泄露的位承诺才是构造零知识证明的完美工具，它 的使用完全不会增加上层证明信息泄露的可能性。 提出了“离散对数对问题”、“离散对数对碰撞问题”的定义，并形式化地证 明了求解这两个问题的困难性等价于“离散对数难题”。基于“离散对数对碰撞 问题”，提出了个全无泄露的位承诺协议。以此全无泄露的位承诺为子协议， 完全不会增加上层证明协议信息泄露的可能。以此全无泄露的位承诺为子协议构 4 全无泄露的位承诺协议与不可否认数字签名方案研究 建的基于“验证者出示问题”结构的零知识证明将具备完善的零知识性。以此全 无泄露的位承诺为加密函数，得以构建n p 命题的完善零知识证明。 通过一个图的三着色n p 命题的零知识证明，说明了使用密码学家之前提出 的基于二次剩余的位承诺，将使得该n p 命题证明的零知识性完全依赖于位承诺 函数的不可逆性，一旦二次剩余问题被破解，则图的三着色解将被泄露。若以我 们提出的全无泄露的位承诺代替原来的二次剩余位承诺，则将实现该n p 命题的 完善零知识证明。 第四章： 介绍了c h a u m v a n t w e r p e n 不可否认签名方案和c h a u m 的零知识的不可否认 数字签名方案，形式化地分析了签名确认协议及签名否认协议的正确性、合理性、 零知识性。 第五章： 应用第三章提出的全无泄露的位承诺子协议，提出了一个新的基于“验证者 提问 结构的确认协议，该协议具备完善的零知识性。 对d a v i dc h a u m 零知识不可否认签名方案进行了改进，提出一个新的高效的 签名否认协议。与c h a u m 的零知识否认协议相比，在同样的安全级别下，新协议 的模乘运算呈指数级的下降。 之前提出的不可否认签名算法均属于确定性签名，且具有存在性伪造。本文 提出了新的基于离散对数的随机化的不可否认签名生成算法，包括基于s c h n o r r 签名的不可否认签名算法和基于广义e l g a m a l 型签名的不可否认签名算法，新的 算法属于随机化数字签名，有更强的安全性，能消除存在性伪造。证明了基于 s c h n o r r 签名的不可否认数字签名算法具有与s c h n o r r 签名算法同样的安全性。 第六章： 对本文的研究工作进行总结。 硕士学位论文 2 1 引言 2 零知识证明协议 2 1 1 零知识证明定义 g o l d w a s s e r 3 】等人提出了零知识证明这一概念。零知识证明是一种高级密码 协议，它包括两个方面，一方为证明者，另一方为验证者。声称者a 要使验证者b 深信某一断言的真实性，但并不向b 泄露任何与该断言有关的其他信息。在这里， 断言可以是“拥有某一秘密 ，“x 是模n 的二次剩余 等等命题。 一个完美的零知识证明具有如下属性： 1 ) 证明能够税服验证者以很高的概率接受该断言。 2 ) 证明只向验证者提供个信息，那就是断言为真或是为假，除此之外不 会泄露任何与该断言有关的信息。 3 ) 即便恶意的验证者不遵守协议，他也不能获得额外信息或自身本不可计 算的信息。 4 ) 任意多次重复的证明也不会增加敌手窃取秘密信息的可能性。 5 ) 验证者不能通过出示证明的执行脚本使第三方相信这个证明的真实性。 下面给出零知识证明的形式化定义。 零知识证明定义【2 0 】【2 1 】：知识的证明协议具有零知识性，是指存在一个多项式时 间模拟器，能够自行产生一些协议运行的脚本，该脚本与真实脚本有不可区分的 概率分布。 2 1 2 零知识证明的类型 上述零知识证明定义中，“不可区分”在严格意义下可被量化，从而区分出 不同类型的零知识，包括完善的、统计的、计算的、无用的、完全的【7 】。不同的 零知识类型的安全级别不同，其中完善的和完全的零知识证明具有最完美的零知 识性。 完善的零知识是指存在一个使副本与正本具有相同概率分布的模拟器。完全 的零知识是指不但存在一个与正本同样概率分布的模拟器，而且该概率服从均匀 分布。统计的零知识是指除了一定数量的例外，有一个使副本与正本具有相同分 布的模拟器。计算的零知识是指有一个使副本与正本不能区别的模拟器。无用的 零知识是指可能不存在模拟器，但是可以证明验证者不能从证明中得到任何更多 的信息。 6 全无泄露的位承诺协议与不可否认数字签名方案研究 模拟器保证了没有知识的泄露，因为敌手所能获得的协议的执行脚本是他本 身也可单独制造的。模拟器的存在同时也使得证明不可向第三方传递。假如a 向b 证明了一个断言，而b 把该过程的脚本给c 看，以试图说服c 也相信这一断言，但c 不会相信b ，因为b 也可自行制造这一脚本，这就是零知识性质的基本思想。 2 1 3 零知识证明协议 零知识证明不同于一般的静态的数学证明，它是通过验证双方动态地执行多 条挑战一响应信息来实现的，验证者通过随机数构造挑战，而声称者根据自己拥 有的秘密对其作出正确响应，因此也称为零知识证明协议。这种证明是一种交互 式搏弈，证明的结果是概率的而不是绝对的，这种概率可能在一个界定范围内， 也可能任意地接近1 。 2 1 4 需要用到的子协议 构造零知识证明通常需要借助其他的一些子协议，如分割选择协议、位承诺 协议。 在交互式协议和零知识概念未出现之前，m i c h a e lr a b i n 第一个将分割选择 技术用于密码学【2 2 】。它类似于一个将苹果等份的经典协议。a 和b 两个人分苹果， 出于公平考虑，两人协商如下：由a 将苹果切成两半，b 给自己选择一半，剩下 的一半留给a 。为了能得到更多的利益，a 只能尽量地等分苹果。 自b l u m 于1 9 8 2 年首先提出了位承诺【l 】的概念后，它已经成为了密码学研究的 一个活跃领域。位承诺是构件许多其他密码协议的重要子协议，它可用来在密码 协议中产生双方都可信赖的随机源，它也是零知识证明协议的重要工具。密码学 家指出，假设有了单向函数并因此有了好的加密算法，则任何n - p 命题都有一个 零知识证明【2 】。这里所谓的好的加密算法本质上就是位承诺算法，而单向函数是 实现位承诺的一种方式。 在第三章中将详细的讨论位承诺协议的实现方法，并提出一个新的基于离散 对数对碰撞问题的全无泄露的位承诺协议。全无泄露的位承诺是指无论待承诺的 密文为何值，协议输出的承诺值都服从相同的概率分布。使用全无泄露的位承诺 完全不会增加上层协议信息泄露的可能，为实现上层母协议的零知识性提供了保 证，是构建零知识证明的完美子协议。全无泄露的位承诺位可用来实现n p 命题的 完全零知识证明。 2 2 身份识别协议 零知识证明可用于身份识别。身份识别通常都是通过检测声称者是否拥有能 够标志其身份的某个秘密来实现的。实体a 拥有某个秘密s ，且只有a 自己知道这 一秘密。a 通过证明对秘密s 的拥有向任何验证者b 来识别自己，而不泄露在执行 7 硕士学位论文 协议f i i i b 不知道的或不可计算的关于s 的任何信息。 这一节中将列举一些身份识别协议的例子，并对它们的正确性、零知识性进 行分析。 2 2 1fia t - s h a mir 身份识别协议 协议的安全性依赖于计算模n 的平方根的困难性，其中n 是一个未知分解的大 合数，其安全性等价于因子分解n 。 协议由三次消息传递组成，该需要重复执行t 次。 系统参数选择：可信中心t 选择和公开模数n = p q ，其中p 、q 为素数且需要保密。 声称者心鑫择与n 互素的秘密s ，1 耋s - - - - - n 1 ，计算v = s 2m o dn ，将s 作为a 的私钥秘 密保管，将v 向t 注册为自己的公钥。 消息传递： a b ：x = r 2m o dn ( 1 ) a b ：e ( 注：e o ，1 ) ) ( 2 ) a b ：y = r s 。m o dn( 3 ) 执行过程： 1 ) a 选择随机数r ，1 兰r 至1 1 1 ，计算x = r 2m o dn ，将x 作为证据发送给b 。 2 ) b 随机地选择一个挑战e = o 或e = l ，将e 发送给a 。 3 ) a 计算响应y 。若e = 0 ，则令y = r ；若e = 1 ，则令y = r s m o dn 。将y 发送 给b 。 4 ) b 通过验证，= xv 。m o dn 接受证明。 上述过程需要迭代执行t 次，若每一次a 均能正确给出响应，则b 接受a 声称 的身份，带存在一次挑战没有正确作答都将拒绝接受。 协议的正确性： a 需要面对两种可能的问题，一是证明她关于s 的知识，另一个容易的问题用 来防止她欺骗。如果a 是诚实的证明者，则她两个问题都能回答。如果a 是假冒 的，则她在每一轮能正确作答的机会为l 2 。通过了t 轮问答之后，她能成功欺骗 的可能性降至1 2 。如果t 次轮循都能正确作答，则接受证明的正确性概率高达 1 1 2 1 。 协议的零知识性： 协议执行的脚本可由模拟器单独模拟，这只需要按下列步骤进行： 1 e 1 ，e 2 ，e t r o ，1 )( 注：r o ，1 ) 表示e i 在 0 ，1 ) 上随机地取值，下同) 2 若e i = 0 ，则令y i r y1 兰y 耋n 1 ) ，xj = y i 2m o d na 3 若ei = 1 ，则令y i r y1 兰y 三n 一1 ) ，xi = y i 2 v m o dn 。 4 ( x i ，e i ，y i ) 构成了协议的一次执行脚本。 其实a 并不是按照模拟器的方法来构造信息的，因为a 是先计算x ，再根据挑 全无泄露的位承诺协议与不可否认数字签名方案研究 战值来计算y 的，而模拟器则是先计算y ，在根据挑战值计算x 。尽管如此，模拟 器产生的脚本与a 产生的脚本有不可区分的概率分布，这就建立了零知识性质。 2 2 2s c h n o r r 身份识别协议 s c h n o r r 协议的安全性基于离散对数问题的困难性。声称者通过证明自己对 离散对数秘密的拥有，可向任何验证者b 识别自己的身份。 系统参数选择：选择大素数p = 2 q + 1 ，其中q 也是素数。选择一个阶为q 的元素g ， 即满足9 9 = 1r o o d p 。每个用户a ( 声称者) 为自己选择一个私钥a ，1 - - a - - q l ， 计算v = g 3r o o d p 。将v 作为a 的公钥通过可信方t 对外发布。 消息传递： a b ：x = 9 7 r o o dp( 1 ) a b ：e ( 注：1 兰e - - q 1 ) ( 2 ) a b - y = a c + r m o dq( 3 ) 执行过程： 1 ) a 选择随机数r ，1 薹r - - q 1 ，计算证据x = 9 7m o d1 1 ，将x 作为证据发送给b 。 2 ) b 选择一个随机数e ，1 耋e q ，将e 发送给a 。 3 ) a 计算响应y = a e + r r o o dq ，将y 发送给b 。 4 ) b 根据与a 所宣称的身份相关联的公钥v ，验证g y = v 。xr o o dp 是否成立， 若成立则接受a 的身份，否则拒绝。 一 协议可迭代执行t 次，以提高正确性概率。 协议的正确性： 如果a 的身份是真实的，并且他正确的履行了协议，那么有： g y 三g 鹭+ 7 兰v 。9 7 三v 。xr o o dp 如果a 的身份是假冒的，他并不知道私钥a ，要计算出满足g y = v 。xm o dp 的y 则需要面临离散对数难题。 协议的零知识性： 协议执行的脚本可按下列步骤由模拟器单独模拟： 1 ee er e1 耋e 量q 一1 ) 2 令y r y1 y 兰q - 1 ) ，x = g y v cr o o dn 。( 其中吒十e 三0m o d q ) 3 ( x ，e ，y ) 构成了协议的一次执行脚本。 按照c h a u m 等人的零知识定义，如果存在一个模拟器，其产生的脚本与真 实的协议执行脚本具有不可区分的概率分布，则该协议是零知识的。这里有一个 前提假设，那就是协议是“v e r i f i e r - p a s s i v e 2 0 】，即验证方给出的挑战值是由双 方信赖的随机源产生的。如果没有这个假设，则有可能存在选择明文攻击。 在s c h n o r r 身份协议中，虽然模拟器也能给出不可区分的脚本，但是该协议 却不是真正零知识的。问题的关键就在于协议的第二步中，b 可在一个值域 e l 9 硕士学位论文 三e 兰q ) 范围内主动地而非随机地选择挑战e 。虽然x 是由a 随机给出的，但是y 却是在e 的干扰下用a 的私钥计算得来，由此构造的响应可能泄露部分信息。 如果a 的私钥同时用作s c l m o r r 签名的话，则敌手b 可实施如下选择文本攻 击。选择文本攻击是指敌手通过有策略地选择挑战以尝试获得本不能单独从声称 者的公钥知识计算出来的信息。在a 给出证据x 之后，b 计算e = h ( m l l x ) ，将e 作为挑战值发送给a 。a 接着回复响应y 给b 。这样的话，b 得到了a 对消息m 的s c h n o r r 签名( y e ) 。因此当密钥用于多个目的时，协议的零知识性可能受到威 胁。 要消除这种选择文本攻击，实现零知识性质，可通过使用硬币投掷子协议， 产生一个双方都信赖的随机源。将协议改进如下： 消息传递： a b ：x = g m o dp ( 1 ) a 一一b