（计算机软件与理论专业论文）缩短串承诺协议长度的通用方法研究.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究威果论文中 除了特盈4 加以标注和致谢的地方外，不包含其他入或其它机构已经发表或撰写 过的研究j 6 窝果其他同志对本研究的启发和所做的贡献| 均已在论文中作了明确 的声明并表示了谢意 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的裁定。即：学校有权保 留送交论文的复印件。允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容可以采用影印、缩印或其它复制手段保存论文保密的论文在解密后 遵守此规定 作者签名 摘要 摘要 承诺协议在密码学中具有广泛的应用，它允许发送者延迟公布某个秘密信息。 承诺协议依据其承诺信息的位数分为位承诺协议和串承诺协议。承诺的长度与 安全参数和承诺信息的长度都具有相关性本文深入分析了串承诺协议的性质。 提出了一种通用的缩短串承诺长度的方案该方案是可证明安全的，而且应用该 方法不需要额外的计算理论假设。当把该方法应用于以往的多个著名承诺协议 时，承诺的长度被极大的缩减。这充分说明该通用方案的有效性。 在分析承诺协议时，本文创新性提出了另一类可以满足非交互零知识特性的 位承诺协议。比起以往协议，该协议使用了更少的计算理论假设。但是该协议的 承诺长度与安全参数成正比而当应用通用方案在该新协议上时，承诺长度不再 与安全参数有关，为一个较小的常数值。同时原有的安全性质没有改变。这再次 证明了通用方案在缩短承诺长度上的有效性。 关键词：串承诺协议，抗碰撞哈希函数，通用单向哈希函数，单向函数，非交互零 知识 中图分类号：t p 3 0 9 7 a b s t r a c t a b s t r a c t 2 c o m m i t m e n ts c h e m ep l a y sa l li m p o r t a n tr o l ei nm o d e r nc r y p t o g r a p h yp r o o f s u c h 越z e r ok n o w l e d g ep r o t o c o l ，p r o o fo fk n o w l e d g ea n d o n i nt h es c h e m e ， ac o m m i t m e n ts e n d e ri sa l l o w e dt op o s t p o n et h ep u b l i c a t i o no ft h es e c r e tw i t h i n t h a tc o m m i t m e n t t h ec o m m i t m e n ts c h e m ei sd i v i d e di n t ot w ok i n d sb yt h eb i t s o fs e c r e t i e b i tc o m m i t m e n ts c h e m ea n ds t r i n gc o m m i t m e n ts c h e m e t h el e n g t h o fc o m m i t m e n ti sr e l a t e dt ot h e8 e c l l r i t yp a r a m e t e ra l o n gw i t ht h eb i t so fs e c r e t i t s e l f i nt h i sp a p e r ，r e s e a r c h e r si n v e s t i g a t e so nt h ec o m m i t m e n tl e n g t ho fp r e v i o u s c o m m i t m e n tp r o t o c o l sa n dp r e s e n tag e n e r i cm e t h o do ns h o r t e n i n gs t r i n gc o m m i t m e n t r e s e a r c h e r sp r o v et h a tt h a tm e t h o dc a nb ea d a p t e di nm o s tc o m m i t m e n t s c h e m e s f u r t h e r m o r e ，i ti sp r o v e di nt h i sp a p e rt h a tw i t h o u ta d d i t i o n a lc o m p u - t a t i o nt h e o r e t i ca s s u m p t i o n ，as t r i n gc o m m i t m e n ts c h e m ec a nb et r a n s f e r r e dt o i t ss h o r t e n i n gv e r s i o n t h eo t h e rp a r to fo u l r e s e a r c hp r e s e n t san o n - i n t e r a c t i v eb i tc o m m i t m e n t s c h e m eh o l d i n gn o n - i n t e r a c t i v ez e r ok n o w l e d g e ( n i z k ) a p p l i e do u rm e t h o do n ， t h es c h e m eb e c o m e sm o r ee f f e c t i v ew h i l em a i n t a i n i n gg o o dp r o p e r t yi n c l u d i n g n i z k k e yw o r d s ：s t r i n gc o m m i t m e n ts c h e m e ，c o l l i s i o nr e s i s t a n th a s h i n gf u n c t i o n ， u n i v e r s a lo n e w a yh a s h i n gf u n c t i o n ，o n e - w a yf u n c t i o n ，n o n i n t e r a c t i v ez e r o k n o w l e d g e 第一章绪论 第一章绪论 3 1 1 背景介绍 密码学从其诞生以来就服务于一个古老的目标如何保证通信的私密性这 构成了古典密码学的主要内容，包括各式各样堪称艺术的密码系统，例如维吉尼 亚系统。伴随而生的就是密码分析学，这构成了二战前密码学的主要发展内容， 也是好莱坞电影钟爱的神秘题材。然而，战后计算机的飞速发展与信息论，计算 理论的深入分析将密码学从艺术中解放，赋予其更加科学化，理论化的内涵。一 个公认的里程碑是d i 伍e 和h e l l m a n 发表的关于密钥交换的论文，该论文第一次公 开提出了如何在不泄漏信息的情况下传递密钥，这大大方便了密钥的管理，随后 著名的r s a 系统更标志着一门新的学科：公钥密码学的产生，尽管论述r s a 的论 文曾被编辑以过于耗时，不符实际而被拒稿。公钥密码学可以看作现代密码学的 一个有机组成部分，与原来的非公钥密码学组合在一起，产生了许多新奇的应 用，例如数字签名，电子钱包，承诺协议，共同计算，零知识，电子追捕等等 在公钥密码学中，许多基础的体制被称为原语( p r i n j t i v e ) 。例如数字签名协议 可以被表示为原语( sk ) ，即签名算法s ，验证算法y 和密钥对生成算法。这 个三元组概括了数字签名协议的共性。而去除了特性。因此，无论是群签名协议 盲签名协议，抑或一次签名协议都可以用这个原语来代表。类似的原语还有数 字签名，多方计算等等。原语也可以按照共性的多少进行划分越抽象的原语， 其共性越大，能代表的具体协议也越多。反之越具体的原语，其能代表的具体协 议种类也越少例如在上面的例子中，原语( s ，k k ) 代表了数字签名协议，而原 语( s ，vk o p e n ) 则代表了群签名协议，其中耳生成的密钥中包含了管理密钥，而 算法o p e n 表示辨识签名用户身份算法。可以看到后者是前者的一个子类，因而 也具有更多的特性因而在研究协议性质时，原语的选择有益于简化讨论。 本文集中讨论的原语被称为为承诺协议。其原理可以用上锁的箱子来描绘。 假设有一发送方想给接收者某样东西，但是不想直接给他，那么可以先把东西放 在箱子上锁再把箱子给对方。对方收到箱子后可以知道里面装的是某样东西，但 是不能确定是什么。最后发送方把钥匙给接收者，接收者收到之后就得到了该样 东西，并确认和发送方声称的是同一件东西。承诺协议因此可以分为两个阶段， 第一个阶段上锁封箱并送箱子给对方，第二阶段将对东西的描述和钥匙一起送 给接收者，让其验证。承诺协议给以发送者一种有趣的能力，可以延迟告诉对方 某个秘密，却无法随心所欲的篡改秘密。秘密和箱子一起被称做一个承诺。对承 诺协议的安全性衡量可以分别从发送者和接收者角度进行考量。对于发送者来 第一章绪论4 说，他希望箱子足够牢固，这样接收者无法猜对箱子里面的秘密，这个性质被称 作隐藏性( h i d i n g ) 。从接收者的角度，他希望发送者能够诚实，而非任意解释箱 子中的秘密，即发送者无法让他相信箱子里的秘密是另一件东西。这被称作绑定 性( b i n d i n g ) 承诺协议按照隐藏性和绑定性的不同组合而分作不同种类。承诺 协议也可以按照秘密的长度分类，当只需要对一个比特进行承诺时，此时的协议 被称做位承诺协议。反之，对多个比特的承诺协议称为串承诺协议可以证明这 两者在黑盒归约的意义上是等价的，即一方的存在性可以由另一方的存在性推 导出。为了清楚的表示承诺协议，本文用( s ，月) 表示原语承诺协议，其中蹑示发 送方的算法，r 表示接收方算法 承诺协议在密码学中扮演了重要的角色。尤其是在零知识证明等领域。当应 用承诺协议到具体程序中时，有一个突出的问题。即承诺值的长度。当使用了公 钥密码学算法时，许多承诺值长度一般都要和相应的安全参数成线性关系。而安 全参数一般取至1 j 1 0 2 4 ，这样生成的承诺值长度就很可观了当将承诺协议运用到 服务器上时，不得不对每一个会话需要的开销进行慎重考虑。在串承诺协议中， 承诺的大小与具体协议有关，一般来说取决于安全参数和需要承诺的比特数。当 需要承诺的比特数较大时，承诺的大小可能也随之增加。同时当实际应用对安全 参数要求较高时，承诺大小也可能线形增加。通常需要承诺的消息长度都是安全 参数的倍数，而安全参数一般取1 0 2 4 或者2 0 4 8 ，依赖于具体选取的数论假设。因 此对于需要经常执行协议的服务器来说是一个较为沉重的传输负担。 但是如果简单的消减承诺值长度，就会面临一个问题。隐藏性和绑定性可能 无法保证。承诺值所在空间的大小影响了隐藏性和绑定性空间越大，承诺值得 取值范围就越大，隐藏性可能就更高正如在花园寻找一个人和在森林寻找一个 人的难度是完全不同的。从绑定性考虑，空间越大，发生重合的概率倾向于越小。 正如森林里碰到同一个人两次的概率要小于在花园。因此，当每个被承诺的比特 串都能在空间中找到唯一确定的承诺值，那么绑定性就可以算是完美。但是，从 另一个方向考虑，空间缩小时，如何能够使得隐藏性和绑定性不受影响，而承诺 值长度却相应的缩小。这就是本篇论文需要讨论的核心问题。 在缩短承诺值长度时，另一个需要考虑的问题就是通用性现实生活中有许 多不同的承诺协议，其具体算法千差万别。唯一共同之处就是遵照原语规定的协 议步骤，并且满足隐藏性和绑定性缩短方案的通用性取决于对协议细节的了解 程度。如果需要协议内部许多具体的信息，则限制了方案的使用范围。通用往和 细节信息的了解程度表现为一个此消彼长的相关关系。因此，确保通用性就需要 方案尽可能少的依赖于具体协议的特性，而最大限度利用承诺协议的共性。 此外，在密码学中，经常会碰到原语之间的联系。在缩短承诺值时，当不需要 具体协议的内部信息时，即通用性达到最大程度，几乎可以应用于每个承诺协议 第一章绪论 5 而不考虑承诺协议的内在结构，此时必然有额外的密码学原语引入。引入的原语 与承诺协议之间的推导关系也是令人感兴趣的课题。如果原语能够被承诺协议 推导出，或者在计算理论意义上等价于承诺协议，那么就意味着通用方案在本质 上是自洽的，不需要引入更强的假设。如何证明引入原语与承诺协议之间的推导 关系也是工作的重要部分。 1 2 相关工作 本文标记n 为需要承诺的消息的长度，k 为安全参数。承诺协议最先由b l u m 等 人于【l l 提出。在他们的论文中，每个比特都被承诺成一个长度为尼的比特串。 当g o l d w a s s e r ，m i c a l i 和r i v e s t 于【2 1 中提出c l n w - f r e e 置换时， 3 l 的作者提出了基 于该原语的承诺协议。h a l e v i 等人展示了一个高效的具有完美隐藏性的串提交协 议，每7 , 比特长的消息被承诺成o ( k ) 比特长的串。n a o r 在【4 】提出了另一类利用 了伪随机数产生器和纠错码的承诺协议，其中承诺长度为o ( m a z ( 七，n ) ) 。i - i s l e v i 和m i c e d i 在f 5 】中构造了一类具有统计隐藏性的串承诺协，他们的协议需要使用 到抗碰撞哈希函数和通用哈希函数。其承诺长度为d ( 后) 且k 在他们论文中推荐 为1 2 8 。c a n e t t i 和f i s c h l i n 【6 1 为承诺协议引入了通用组合性且每个比特都被承诺 成一个长度为o ( k ) 的串。而d a m g f i r d 与n i e l s e n 【7 1 展示了另一类同样具有通用 组合性的承诺协议，其中n 比特的串被承诺成o ( n 】长的串。 另一个研究热点是，从哪个最小计算理论假设出发，缩短方案是可证安全的 这里需要涉及的安全原语除了承诺协议外，还有哈希函数和单向函数。其中哈希 函数与单向函数之间的联系已经g o l d r e i c h 在【2 0 】中得到阐述。而单向函数与承 诺协议之间的联系则已经有类似的相关工作。r i m s g l i a z z o 和m l u b y 最早在【2 6 】 证明单向函数的存在性可以由承诺协议的存在性推导而出，且他们的结论包括 了完美绑定性位承诺协议。和【2 l ，2 3 ，2 4 ，2 5 ，2 6 】的结论结合在一起，单向函数实 际上和位承诺协议等价。但是目前还不清楚完美隐藏性位承诺协议是否仅仅可 以由单向函数推导而出。最近的研究结果 2 7 】表明统计隐藏性位承诺协议可以由 一类特殊的单向函数a p p r o x i m a b l e p r e i m a g e - s i z e 单项函数构造得到。 以往的许多位承诺协议需要多轮的交互并且不满足零知识的特性，本文提 出了一类新的具有非交互零知识性质的位承诺协议该协议受到了非交互式 零知识协议和b 协议的启发。零知识协议最早由g o l d w a a s e r ，m i c s l i 和r n c k o f f 在 1 6 1 中提出并且由g o l d r e i c h ，m i c a l i 和w i d g e r s o n 在【1 7 】给出严格定义。零知 识协议在现代计算理论密码学中占据了核心的位置。零知识一个重要应用 就是协议。b 协议最早由c r a m e r 在| 8 1 提出并应用在数字签名，电子支付等 领域。f i a t 和s h a m i r 在 1 0 t 创新地提出了将d 协议转化为非交互性零知识证 明的方法。在他们的方案中，中间的一条随机信息由一个哈希函数生成，而 第一章绪论 6 在理论证明中，该哈希函数被替换成r a n d o mo r a c l e ，这就是r a n d o mo r a c l e m o d e l 的核心思想。然而s g o l d w a s s e r 和y t a u m a nf 1 5 揭示了f i a ts h a m i r 方案 的不安全性。g o l d r e i c h 等f 1 4 】也提出运用r a n d o mo r a c l em o d e l 在安全证明上 实际上是有漏洞的。c r a m e r 和d a m g 缸d 【1 8 】提出了一类高效的经由e 协议转化 得到的非交互式零知识协议，他们的转化需要基于密钥零知识模型( 8 e c r e t k e y z e r o - k n o w l e d g em o d e l ) 。在其模型中，验证者和证明者所持有的私钥彼此相关 另一个非交互零知识的构造由d 缸n g 打d 等在【1 9 l 中提出。他们的转化方式需要在 注册公钥模型中实现他们的方案调用一个同构加密算法第二条消息e ，并将密 文作为公钥，而明文e 作为私钥同构加密算法在整个转化过程中扮演了极其重 要的角色。然而，他们的协议因为使用了同构加密而有点运算资源效耗过多。而 且作者假设密钥生成涉及的难题要远远难于已协议涉及的难题 1 3 我们的贡献 本文讨论了缩减承诺长度的通用性方案。该方案以类似黑盒的方式，不需要 承诺协议内部信息和承诺值在空间上的概率分布信息，提供一种缩短承诺长度 通用方法该方法被证明可以适用于几乎所有承诺协议，且缩短后的承诺长度将 为一个依赖于哈希函数的固定值，不随安全参数和承诺信息长度面变化。该方案 可以直接运用于现实的承诺协议，并提供了严格的理论证明。这样的方式。 该方案通过引入哈希函数，缩减了原有承诺长度，大大减少了传输数据量，尤 其是对于复杂的承诺协议而言同时保持了隐藏性与绑定性的安全强度。在引入 哈希函数时，文中证明了可以由承诺协议本身推导出哈希函数。这需要以单向函 数做为中介原语。因此理论上该通用方案不需要额外的计算理论假设。 本文提出了一类新的非交互式零知识位承诺协议。该协议在部分依赖r a n d o m o r a c l em o d e l 的条件下，能在将三轮b 协议转化为非交互的一轮非交互零知识协 议。不同于以往的协议，该协议可以在任何安全的哈希函数的情况下，证明非交 互零知识性质，并只需要在证明可靠性时候用到随机预取模型。其关键之处在于 引入了一个额外的随机量，该随机量打破了第一条消息和第二条消息之间的耦 合性。该协议在离散对数假设难解的状况下是安全且高效的。本文将该非交互 协议应用于等离散对数问题( e d l p ) 和e o a 协议上，并基于此构建了一类新的非 交互式位承诺协议。该协议的优势在于在证明非交互零知识时，不需要r a n d o m o r a c l e 。但是原有协议的承诺长度与安全参数成正比，当安全参数取2 0 4 8 时，承 诺长度对于实际应用过于冗长了因此当运用本文提出的通用方案在该协议上 时，其承诺长度有了极大缩短，这充分证明了通用方案的有效性。 第一章绪论 7 1 4 文章结构 本论文第二章将介绍涉及的基础知识和概念第三章将介绍通用缩短方案， 并分析了该方案成立的必要条件，并给出了承诺长度缩减对比数据。第四章则证 明了该方案的安全性。第五章将通用方案应用于一类新的非交互零知识位承诺 协议，并给出应用通用方案前后的对比数据第六章对全文进行了总结。 第二章预备知识 第二章预备知识 8 2 1 所用符号 本节将介绍论文里出现的基本概念和基本的标记符号。论文将使用那些 应用于概率算法，实验和交互协议中的符号和定义。设 为一个概率算法， 则a ( x l ，z 2 ，r ) 表示以；r 1 ，x 2 等为输入，r 为算法所用的随机量后算法a 得到 的结果。同样，y a ( x l ，x 2 ，) 则表示为随机选取r ，l ，a ( z l ，z 2 ，r ) 的运 算结果。设s 为一个有限集合，则z s 表示从s 中以均匀概率选取一个元 素z 如果d 既不是随机算法也不是集合，则z o 表示一个赋值操作。标 记m l ；心：t ，】，这表示经过r 1 ；尼；r n 事件发生过后，随机变量口的值域 及其分布。而旧l ；f 5 , ：e l 表示事件e 发生的条件概率。设( 只v ) 表示为概率 交互协议，则( 可l ，伽) 一( p 缸1 ) ，y ( z 2 ) ) ( o ) 表示协议一方尸以z l 为私有输入，另一 方y 以z 2 为私有输入，两者以z 为共同输入后协议运行的输出，其中掣l 和船分别 为p 和矿的输出不失一般性，假设尸和y 的输出都包括了两者之间的交互信息， 包括来往消息和公共输入。本质上，所有的信息都可以由交互信息和双方的随机 量得到。 2 2 相关概念 本节给出在本文中将会用到的概念，这些概念分为几类，一是数学概念，包括 可忽略函数，计算不可区分性，统计不可区分性。第二类是密码学原语，包括单 向函数，串承诺协议，位承诺协议，零知识协议，非交互零知识协议，b 协议和其 离散对数难题的版本。 2 2 1 概率相关概念 定义1 ( 可忽略函数) 函数，( ) ，如果对于任何正多项s o p ( ) ，以及所有足够丈 瓶， 1 跏) 南 那么称函教，( ) 是关于n 可忽略的。 定义2 ( 计算不可区分性) x , u ：l 弱) 。n 和y 答 虼 。斟是两个分布 蕨( e n s e m b l e ) ，如果对每个概率多项式时_ i 可算法d ，每个正多项式p ( ) ，以及 所有足够大的n 。 i p r 【d ( ，1 ”) = 1 】- p 【d ( 碥，1 ”) = 1 1 1 高 第二章预备知识 9 那么说分布族x 和y 是多项式对阃不可区分的也称计算不可区分。 定义3 ( 统计7 5 可区分性) x 些 墨刷釉y 些 k ，矧是两个分布 族( e n s e m b l e ) 如果定义如t 的方差可忽略， ( n ) 兰；i 尸r = a 】- p r i f = q 】i n 那么说分布族x 和y 是统计不可区分。 统计不可区分的定义和计算不可区分乍看上去不相同，但是统计不可区分也 可以第一种风格定义，即对于一个拥有无限计算能力的分辨者，在取样多项式次 的情况下，也无法以不可忽略的概率分辨出两个集合。这种定义和以上的定义是 等同的 2 2 2 密码学原语概念 在密码学中，有一类极为重要的原语，称为单向函数( o n e - w a yf u n c t i o n ) 顾 名思义，其行为是单向的，即计算函数值容易，从函数值反推原象则很难。单向 函数已经被证明可以推导出许多重要原语的存在性。例如零知识协议，伪随机产 生器，承诺协议等等。按照单向的强度，单向函数中也分为强单向和弱单向函数， 按照函数值域可以分为单向置换和非单向置换函数等。作为密码学中极其重要 的原语，单向函数与许多密码学原语之间的关系已经被研究的非常彻底。以下给 出单向函数的形式化定义。 定义4 ( 单向函数) 当以下两个条件满足时：函j 鼢 o ，1 ) 一 o ，1 ) 被称为单向 函兹 易于计算：存在某个概率多项式的算法a 当输入z 时a 输出 ， 难以求逆：对任意概率多项式算法a 。任意正多项式p 和所有足够大 鼽。 所阻( f ( u n ) , i n 】，一1 ( ，( 驯 丽1 运里代表均匀分布在 0 ，1 ) “上的髓祝变量。 串承诺协议一般分为两个阶段。在第一个阶段即提交阶段，发送者试图向接 收者提交关于某个串的信息，通过两者之问的交互，接收者在阶段结束之前得到 关于串的一个承诺。但是接收者无法得知这个承诺所包含的串值。类似于一个锁 上的箱子，唯一能确定的是箱子中存在一个串，但是无法确定具体值。这就是承 第二章预备知识1 0 诺的隐藏性。在第二阶段，发送者将开锁的钥匙，即解提交信息发送给接收者， 接收者打开承诺，验证串值是否是发送者所声称的那个值。此时，提交者无法抵 赖或者欺骗接收者。这就是承诺的绑定性。根据隐藏性的不同，串承诺协议可以 分为完美隐藏性，统计隐藏性和计算隐藏性三种，同理，也存在完美绑定型，统 计绑定性和计算绑定性三类。但是不存在同时完美绑定性和完美隐藏性的承诺 协议。形式化定义如下： 定义5 ( 串承诺协议) 当一对概率多式项式交互图灵机缈刀( sr ) 满足以下条 件时它们构成t 一个串承诺协议： 完备性肘所有安全参壹鼽，v s f o ，l 。似日犯= k ( n ) 代表某个多项 式k ) 以t 概率成立 p r ( ( n ，p ) + 一( s ( s ) ，r ) 0 4 ) ；( t ，( t ，t ，) ) 一( s ( 口) ，兄( 仂) ( 1 “) ：t ，= 8 】= 1 完美计算) 隐藏往对蕊有足够大n 任意p p t 攻击者r | 、 1 1 1 睨其中仉地 长度相等皆为k 。下面两个概率分布是完美r f g ) 不可区分： f 渔，p ) 一s ( 暂- ) ，牙) ( 1 “) ：翻a n d 【( ，) 一( s ( 耽) ，r ) ( 1 “) ：绷 计算绑定性对所有足够大的n 和任意p p t 攻击者s 。以t 概率可忽略。 p r p r f ( 口，p ) 一( s c b ) ，r ) ( 1 “) ；( t ，o ，t ，) ) 一( s ( 口) ，r ( p ) ) ( 1 “) ； ( ，( 7 ，t j ，) ) 一( s ( a ) ，r ) ) ( 1 ”) ：t ，口f o ，1 ) 。a v 川 由于在以后的章节中，位承诺协议也将涉及，故这里也给出位承诺协议的定 义及说明。 定义6 ( 位承诺协议) 当一对橱率多式项式交互图灵祝凹刀( s 兄) 满足以下条 锌对，它幻拉成7 一个位承塔协议： 完备性对所有安全参数n ，v b i t b 。吣以f 概率成立 p f l ( a ，所+ 一( s ( 6 ) ，r ) ( 1 ”) ；( t ，0 ，口) ) 一( s ( d ) ，兄( 卢) ) ( 1 “) ：t i = 6 】= 1 完美附算j 臆藏性黜所有足够大n 任意p p t 攻击者p ，vu 1 ，忱 0 ，1 ) ， 下面两个概率分布是完美( - - $ g ) 不可区分： 【( n ，p ) 一( s ( 口- ) ，r ) ( 1 “) ：纠a n d 【( a ，) 一侈池) ，彤) ( 1 “) ：】 第二章预备知识 ，- 一 。 一 - ，。一 - 4 图2 1 ：承诺值域分布图 计算绑定性对所有足够大的n 和任意p p t 攻击者9 以下概率可忽略，： p r 【p r 【( 口，) 一( s ( 6 ) ，固( 1 ”) ；( t ，( t ，口) ) + 一( s ( d ) ，r ( 仂) ( 1 “) ( ，( ，t ，) ) 一拶陋) ，r 够) ) ( 1 “) ：t ，t ， o ，l a t ，川 当绑定性定义中概率为零时，定义它为完美绑定性。为了方便，本文标记比 特b 的承诺为b c o m m i t ，其长度为p d y b 将0 一c o m m i t 和1 一c o m m i t 的值域统一 定义为( o ，1 9 其中p o l y = m a x p o l y o ，p o l y l ，为某个多项式。而0 一c o m m i t 在 该值域上的分布概率为d o ，1 一c o m m i t 为d 1 对于串承诺协议，在提交阶段，给定发送者一个串，发送者和接收者共同参与 运算，得到一个承诺值，该值蕴含着这个串，并被发送给接收者。在解提交阶段， 双方合作，发送者将解提交信息发送给接收者，接收者打开承诺并验证串值是否 满足其需要。承诺值分布在一个长度固定的空间中，这个空间的大小与串的大小 和安全参数都具有相关性，其空间大小的对数可能与串长度，安全参数具有线性 或其他联系，甚至可能是常数。对于某一个串值来说，其承诺值可以随着随机数 的不同而发生变化，但是对于某个承诺值空间的值来说，其对应的串值却是有限 个。在极端的情况下，可以所有的串都对应于同一个承诺值，或者该承诺值不对 应于任何串值。实际情况下，承诺空间可以分为三部分，第一部分是只能对应于 某个串值的承诺值的集合，第二部分是可以对应于多个串值的承诺值的集合，而 第三部分则是不对应于任何串值的承诺值的集合。如图2 1 所示。 承诺协议的主要性质是隐藏性和绑定性。隐藏性代表着一个具有现实计算能 力的接收者无法从承诺值中推导出串值。依据接收者能力的不同，隐藏性也分为 三个级别。最高的级别是完美隐藏性，即使接收者具有无限的运算能力，在多项 第二章预各知识 图2 2 ：承诺值的碰撞图 式时间内也无法推出承诺值所对应的串值。这是因为所比较的不同串的承诺值 的概率分布相同，故而无法区分。注意，这里提到承诺值首先得是有效的，即不 属于第三部分空间。次一些的级别则是统计隐藏性，即对拥有无限运算能力的接 收者，当限于取样多项式次时，无法分辨出不同串对应承诺值的概率分布，即这 两个概率分布之间的统计距离为可忽略。而最为常见的则是计算不可区分，即不 同串的承诺值的概率分布是计算不可区分，对于一个概率多项式的算法，无法在 多项式时间内区分得到结果 相应的，绑定性也分为三类。这里首先关注绑定性与值域空间分布之间微妙 的联系。正如前面提到，一个承诺值可以对应于不同的串值，当这个承诺值落在 第二部分空间时。当这部分空间大小为零，则不存在承诺值可以对应于多个串， 此时该协议可以称为完美绑定性，即任何计算设备，即使拥有无限能力，也无法 从一个承诺值中解提交出两个不同的串值。然而，实际情况中，确实可能存在该 部分空间，而且空间大小甚至可以是指数于安全参数及串长。根据发送者的能力 进行区分，当发送者拥有无限计算能力，并能进行多项式次采样时，只有可忽略 的承诺值能够被其解提交成两个不同的串值。此时称为统计绑定性。而发送者仅 限于概率多项式图灵机时，此时若只有可忽略的承诺值能够被其解提交成两个 不同的串值，称为计算绑定性。这里借用哈希函数中碰撞的定义，将两个不同的 串同时提交成一个承诺值的情况称作该两串构成了一个碰撞。统计与计算绑定 性的定义关键在于即使存在非常多的碰撞，发送者也无法在多项式时间内找到。 可以图2 2 中看到这一点。 为了精确的描述承诺值域的分布状况，本文定义了以下两个参数第一个是碰 撞空间比率，第二个是空闲空间比率前者刻画了承诺空间中多少比率的承诺值 可以被解提交成多个值，而后者则表示有多少比例的值是无法被解提交成任何值 第二章预备知识 1 3 的这里需要注意的是，这两个参数会根据协议的不同而发生变化 定义7 ( 碰撞比率) 假设( 只r ) 是一个串承诺协议且承诺值长度为称承诺 值c 是两义的向m 6 匆u d 伽，如果官能被解提交成多于一个串令代表( s ，兄) 中 两义韵承诺值的集合刹定义对应于峪鼬的碰撞比率c 为： 类似的有如下定义 ，凹i i 。2 可 定义8 ( 空闲比率) 假设( s ，固是一个事承诺协议且承诺值长度为七 令s f 代表l s ，r 中空闲空间集合刚定义对应于岱，黔的空闲比率f 为 f 鬯一i s f i 一 2 七 接着引入c r h f 和u o w h f 的定义。c m f 即抗碰撞哈希函数的缩写当一个 函数族满足抗强碰撞性和不可逆性时，称之为c r h f 不可逆性较容易理解，即 无法从哈希值逆推出原象，这有些类似于单向函数的性质，但并不完全相同。抗 强碰撞指的是对于所有概率多项式时间的算法，其发现一对碰撞的概率可忽略。 具体定义如下： 定义9 ( 抗碰撞哈希函数) 设d ，r ：n n 一族函 数 k ：t o ，1 ，一 o ，1 ) ) 。 。，l ，被称作抗碰撞哈希函数当存在一个概 率多项式算法i 使得下列条件成立： 存在多项式p 对所有足够大的n 以及任意存, 窿- t - z ( 1 “、值域的8 。ns p ( i s l ) 成立此外n 能够从8 以多项式对阃计算得出。 存在一个多项式算法使得给定8 和z 算法返回h s 。 称( z ，一) 构成了函舅娩下的一对碰擅当危( z ) = ( 一) 且z 一则尉任意概 率多项式算法a 。任意正多项式p 以及所有足够大的n p r a ( m “) i 8n 洲胁溉t 础r 吣) 1 丽1 这里韵概率考惑7 算法i 和a 所使用的内部随机串。 另一类看上去弱些的哈希函数族称为通用单向函数族( u n i v e r s a lo n ew a y h a s h i n gf a m i l y u o w h f ) 它同样满足不可逆性，但是不满足抗强碰撞性，即存 在某个算法可以攻破这个哈希函数，得到一对碰撞。但是它满足抗弱碰撞性，即 第二章预备知识 1 4 给定一个原象和其哈希值，无法找到对应原象的一个碰撞。实际使用的哈希函数 大多假定是这类函数，例如著名的s h a 系列函数。其具体定义给出如下： 定义1 0 ( 通用单向哈希函数) 设d ，r ：nn 一族函 数( 也： o ，l 一 o ，1 ) 7 ) 。e ( 。1 ，被称作通用单向哈希函效当存在一个概 率多项式算法i 使得t 列条件残立；： 存在多项j 妇，对所有足够大序，以及任意存在于了( 1 ”) 值域序拈，r s p ( i s l ) 成立此外，n 能够从s 以多项式时间计算得出。 存在一个多项式算法使得给定s 和z 算法返回h | 。 对任意确定多项式算法任意芷多项式q 。对任意概率多项式算法a | 任 意正多项式p 以及所有足够大弧。 p r h l c l n ) ( a ( i ( 1 “) ，( n ) ) ) = m n ) ( 山( ，( 1 ”) ，竹) ) ) 。毗州l ”) ，) ) 山( ) j 丽1 这里的概率考虑7 算法i 和a 所使甩韵内部随机串。 零知识证明系统在现代密码学中起着核心角色。一个协议称为零知识性质的， 当且仅当协议中的证明者拥有了某种知识，并向验证者证明了这一点，同时却不 泄漏该知识。零知识的这个性质在网络交易和信用卡安全支付上起着独特的作 用。同时零知识的性质应用到加密系统和签名上，也融生了新的加密协议和签名 协议。 定义1 l ( 零知识证明) 令( p ，n 为语言z p 的一个交互式证明系统，凡是关 于已的一个 正据似饥e 5 5 ，关系，即，对于b ，如果存在一个面咖满足( ，) r l ， 那么z l 。 锈l y i e w p v ( z ( z ) 表示一个随机变量，用于描述p 的随机带的_ 内容 和v 在协议执行时从p 处收到的消息协议执行时的公共输入为z v 有辅助输 入z 。称( p y ) 是交互式零知识证明系统，如果对每个概率多项式时同的交互式 机器v 存在一个概率多项式时间的o m c l e 祝器s 使得对所有足够长的z l 分布族 口钯t ，孑( z ) ) 。l 和 s p 忙) ) 。“是计算不可区分的。杌器s 称为( p ，v ) 的摸 拟器。如果上面两个分布族是统计上靠近的f 比如对f 任何一个芷多项式，这两 个分布族的方差距离都比杰要小) 刚称协议婶v 、是统计零知识的( s t a t i s t i c a l z e r ok n o w l e d g e ) 。如果上面两个分布族是完全一样的则称协议妒。v 1 是完美零 知识的( p e r f e c tz e r ok n o w l e d g e ) 。 第二章预备知识 1 5 非交互零知识是一类特殊的零知识协议。一般的零知识协议至少需要两到三 轮。在网络延迟存在时，对协议运行有较大影响而非交互零知识协议顾名思义， 只需要一轮。即发送者将信息在一轮中直接发送给接收者，接收者可以随后自行 验证。这样避免了网络延迟和多轮计算带来的影响。但是天下没有白吃的午餐， 非交互零知识协议只能在一定的模型中成立，常见的有公共引用串模型和时间 模型。本文将使用的是公共引用串模型。形式化定义如下。 定义1 2 ( 完美非交互式零知识n i z k ) 尸 y ) 为语言l 伊的一个交互式证明 系统，包括概率多项式的算法p ，v 和一个概率多项式的算法m 当满足一t 条件 时。称该系统具有完美非交互零知识性质。 完备性：对所有霉l 。 p r ( 。，州) ，p ( 毛删) = 1 】； 这里e 钿 ( 是均匀分布在 o ，1 p o “x 1 2 1 ) 的随机变量 玎靠性：对每个z 掣l 以及每个算法e p r 【y 扛，如( k i ) ，b ( z ，) ) = 1 】； 这里州是均匀分布在( o ，1 ) 9 删州 的随机变i 非交互零知识：存在一个概率多项式的算法m 和某个多项式p 使得集 合 ( z ，p ( z ，) ) ) 。e l 与集合 m ( z ) ) 。l 等概率分布，这里c 钿“ 是均匀分布在t o ，1 咖( 构随机变量 在其他定义中，通过多项式轮重复执行，可靠性错误和完备性错误都可以被 缩减到2 叫训z i ) 定义1 3 ( 协议) 一个三轮的公开随机串协议( p y ) 如果满足下面的条件，贝矿称 它为关于关系r 的协议： 完各性( g o m p l e t e n e s s ) ：如果户，y 按照协议去微，那么验证者崽会接受。 第二章预备知识 1 6 特殊的可靠性仰e d 耐s o u n d n e a s ) ：从任何长度为n 的公共输入z 以及任何 - 对输入为z 的可接受的会话( 口，z ，e ) 和( o ，e ，一) ，其中e 一，这就能很侠地 计算出叫，满足( z ，叻r 。这里a ，e ，z 2 别代表第一轮、第二轮和第三轮消 息，并且e 是一个从 o ，1 p 中均匀地选择出来的长度为七俾关于孔的某个多 项式) 的串。 完美的特殊诚实验证者零知识( p e q 鲥8 h v z k ) ：存在一个概率多项式 时间( p p t ) 的模拟器s - 它的输入为z ( 存在一令如r c c 足( x 。讪r ) 和一个 随机的质疑串，输出一个可接受的会话( a e ，2 ) 。这个会话的概率分布 和p 与v z 同在输入为霉时的真实会话b ，e ，痢的概率