（概率论与数理统计专业论文）秘密分享方案及其在数字签名中的应用.pdf

摘要 秘密分享是一种分发、保存和恢复秘密信息的方法，是信息安全和数据保密的重要 手段之一它在门限密码学、安全多方计算、电子商务、电子选举、密钥托管等诸多方面 有着广泛的应用本文对秘密分享方案的构造作了一些研究，并将秘密分享应用于数字 签名，构造出新的门限共享验证签名方案 本文主要工作如下： 首先，对秘密分享体制进行研究，构造了一种新的广义多重秘密分享方案该方案 中，参与者持有的秘密份额可以重复使用，接入结构中合法子集的动态增加以及秘密信 息集合中新的秘密信息的动态加入都不会影响参与者原有的秘密份额，只需要相应地变 更公告板公开的信息分析表明，该方案具有较好的安全性能 其次，构造了一个新的m u l t i - d e a l e r 秘密分享方案方案中引入了m u l t i _ d e a l e r 的概 念，进一步避免了分发者的欺骗和秘密信息的泄漏，从而提高了秘密分享方案的安全性 m u l t i d e a l e r 秘密分享方案是s i n g l e d e a l e r 秘密分享方案的有效拓展本文给出了在已有 s i n g l e d e a l e r 秘密分享方案基础上构造m u n d e a l l e r 秘密分享方案的方法 最后，本文研究了秘密分享在数字签名中的应用将秘密分享方案应用于数字签名， 构造出一种门限共享验证签名方案分析表明，该方案不仅具有较好的安全性和较低的 计算复杂度，而且还具有如下特点： ( 1 ) 签名者的私钥可以重复使用，签名不可伪造； ( 2 ) 进行多次验证签名而不会暴露验证者的秘密份额； ( 3 ) 验证者之间不能相互伪造验证信息，从而验证者可以使用相同秘密份额对多个签名 进行验证 这些特点使得方案中的签名私钥和秘密份额都具有可重复使用性 关键词秘密分享，接入结构，可验证秘密分享，广义多重秘密分享，m u l t i d e a l e r 秘密 分享，数字签名，门限共享验证签名 a b s t ra c t s e c r e ts h 盯i n gi sam e t h 。d 。fd i s t r i b u t i o n ，s a v ea n dr e 删y 硝s 弛也a n d 幽( ：1 8 ：他r y i m p 。r t a j l tt e c h n i q u ei n i n f o r m a t i 。ns e c u r i 够a n dd a t ae n c r y p t 沁n s e c r e t8 ：a r i n ：，h b r 。a d a p 三l i c a t i o ni nt h r e s h 。l dc r y p t 0 1 。g y ，e 1 e c t r o n i cc 。n 脚c e ，e l e c 乞r o n i ce 1 e ：t i ? n ，e y ? 8 兰0 w 茹s 。n ar e s e a r c h 。ns e c r e ts h a r i n gs c h 咖ea n d i t sa p p l i c a t 沁i l shd i g 托a 1 甑g n a t u r e l 8d o n e i nt h i sp a p e r t h em a i nc o n t r i b u 七i o n si nt h ep a p e r a r e1 i s 七e da sf o l l o 、s ： f i r s t l y ，an e wg e n e r a li n u l t i s e c r e ts h a r i n gs c h e i n ew a sp r o p o s e d b a s e do nc u r r e n t8 e e r e t s h 盯i n gs c h e m e s i nt k ss e h e m e ，t h es e e r e ts h 砒e sh e l db yp a r t i c i p a n t 8 c a nb eu s e dr e ? e a t e d l y j b e s i d e s ，t h ed y n a m i cp a 甙i c i p a n c eo ft h ea u t h o r i t a t i v e s u b s e to fa c c e s ss t r u c t u r ea n dt h es e c ：e t i n f o r m a t i o nn e e d n ，tt oc h a n g et h e8 e c r e 乞s h a r e sb u ta l t e rt h ei n f o r 鼍a i o n p u b l i 8 h e do nn o 1 c e b o a r d t h ea n da n a l y s i sd e m o n s t r a t e dt h a tt h ep r o p o s e ds c h e m ep 。o m l 8 e db e 。e 。8 e c u r l y ， s e e o n d l y ，an e wm u h i 。d e 妇s e e r e t 妇主n gs c h e m e 哪p r o p o s e d ac o n c e p t 0 1 舢上t i - d e a 攀 w a si n 乞r o d u c e di no r d e rt or e d u c et h ep o s s i b i l i t yo fi n f o r m a t i o nl e a k a g eb y d e 以e rf u 。t h e 。，w h l c h i m d r o v e dt h es e e u r i t yo fs e c r e ts h a r i n gs c h e m e c o m p 甜e dt ot h ep r e v i o u sm e t h o d s ，1 i m m d e a l e rd r o v i d e dam o r er e a l i s t i cs o l u t i o nt os e c r e ts h 盯i n g b a s e do n t h ea 1 1 a l y s i so fs l n g l e - d e 龇e r m e e h a n i s m ，a 龇1 t i - d e 8 l e ro n ew a sp r o p o s e d f i n 出1 v ，b a s e do nr e s e 盯c ho ft h e 印p l i c a t i o n so fs e c r e ts h 缸i n g i nd i 酉t a ls i g n a t u r e ，an e w t h r e s h o l ds h 孤e dv e r 逾c a t i o ns i g n a t m es c h e m ew a sp r o p o s e d a c c o r d i n gt oa n a 坶s 1 8 ，o no n e h a n d ，t h ep r o p o s e ds c h e m ei nt h ep a p e r h a sb e t t e rs e c w i t ya n d l e s sc o m p u t a t i o nc o m p i e x l t y o nt h eo t h e rh a n d ，t h es c h e m eh a sf 色a t u r e sa sf d l o w s ： t h ep r i v a t ek e y 。fs i g n e rc a l lb eu s e dr e p e a t e d l ya n d i t i sv e r yd i 伍c u l t 乞of o r g eas i g n a t u 。e ( 2 ) s i g n a 乞u r ec a nb ev e r i f i e df o rm a i l yt i m e sw i t h 。u te x p 。s i n g v e r i f l e r s s e c r e 。s h 跗e s ； ( 3 1t h e r ei sl i t t l ep o s s i b i l i t yt h a ti n f o r m a t i o n o fv e r i a c a t i o nc a nb ef g e da 扛m n gv e n 髓。8 t h e r e f o r ev e r i f l e r sc a nd e dw i t hd o z e n so fs i g i l a t u r e sw i t ht h e s a i n es e e r e ts h 缸e s t h ef e a t u r e sp r o m i s et h a tp r i v a t ek e y 。fs i g n e ra n d s e c r e ts h 缸e sc a nb eu s e dr e p e a t e d l y k e yw 。r d s s e c r e ts h 盯i n g ，a c c e s ss t r u c 乞u r e ，v e r i f l a b l es e c r e ts h 盯i n g ，g e n e r a l n m l t i 5 e c r e t 8 h 盯i n g ，m u l t i d e a l e rs e c r e ts h a r i n g ，d i 西t a _ ls i g n a t u r e ，t l l r e s h o l ds h a r e d v e r i f l c a t i o n8 i g n a t u 。e j 口 致谢 本论文是在尊敬的导师陈鲁生教授指导下完成的陈老师渊博的知识，严谨的作风 和谦逊的为人，使我在这三年的求学中获益颇深他对科学研究一丝不苟、精益求精的 精神，深深感染了我，使我懂得了如何才能作一名合格的科研工作者在这三年的学习 和生活中，我的每一点进步都是和陈老师的严格要求与悉心培养联系在一起从论文的 选题开始到论文的成功完成，无处不凝结着陈老师的心血在此谨向陈老师表示衷心的 感谢 我还要感谢尊敬的沈世镒老师、阮吉寿老师、梁朴老师、吴忠华老师以及信息论方向 其他老师，感谢他们对我的指导老师们正直的为人和一丝不苟的科研作风，对我影响 甚深，值得我永远尊重和学习 在学习期间，我的很多想法得益于和同学之间的交流，从他们的身上我学到了许多 东西，也得到了许多帮助，在此谨向他们表示诚挚的谢意感谢已经毕业的陈艳玲师姐， 在读的师兄岳廷海、张鹏程、王立鹏、张青坡，师姐李楹，师弟曹雷、桑盛虎、许晋、鄢 德俊、杨敏、郭勇，师妹宋爱荣等 三年的学习生活，离不开父母亲人和朋友的支持，没有他们的鼓励和鼎力支持，我 就不能顺利完成学业愿本文的完成能作为对他们的一点回报 第一章引言 网络技术的飞速发展，在给人们生活和工作方式带来巨大变化的同时，也带来了安 全隐患大量的敏感信息如病例、法庭记录、资金转移、私人财产等常常通过公共通信设 施或计算机网络进行交换，人们迫切需要保证这些信息的保密性和真实性社会信息化 使得信息安全与数据保密问题成为几乎每个人都不可忽视的问题而现代密码学可以用 于解决信息的保密性、完整性、可用性、可控性和不可抵赖性，能够为信息安全提供关 键理论和技术，是保护信息安全最有效的手段近年来，密码学得到长足的发展，其应 用已经渗透了社会生活的各个方面，比如数据加密、信息认证、网络安全、电子选举、电 子现金等 密码学中的一个重要课题就是密钥管理技术，它包括密钥的产生、保存、装入、分 配、保护、丢失、销毁、保密以及合法的恢复等在k e r c h h o f r 假设下，一个密码系统的 安全性应取决于对密钥的保护，而不是对系统或硬件本身的保护，所以密钥的安全保密 是密码系统安全的重要保证，也是密钥管理技术的核心解决密钥保护问题的所有方法 都应该保证以下三个条件成立：密钥不会丢失、密钥不会被破坏和密钥不会被非法授权 者获得。作为密码技术之一的秘密分享技术就是解决这类问题的有效方法，是信息安全 和数据保密中重要的手段之一 1 1 秘密分享的基本概念 秘密分享( s e c r e ts h 盯i n g ，也称为密钥分享或密钥共享) 是一种分发、保存和恢复秘密 信息的方法，其概念最早由s h 锄i r 【l 】和b 1 a k l e y 阁分别提出它是指将秘密信息s 分割成 若干份额( s h 缸e ，也称为碎片p i e c e ，或影子s h a d o w ) 在一组参与者p = p 1 ，p 2 ，p 钆 中 进行分配，使得每一个参与者都得到关于该秘密的一个份额，并只有p 的一些特定子集 ( a u t h o r i z e ds u b s e t ，称为授权子集或合格子集) 能有效的恢复s ，而p 的其他子集不能有效 的恢复s ，甚至不能得到关于s 的任何有用信息 通常，一个秘密分享方案由一个秘密分发者( d e a l e r ) d 、参与者( s h a r e h o l d e r s 或p 盯一 t i c i p a n t s 或p l a 弘r s ) 集合p 、接入结构( a c c e s ss t r u c t u r e ) r 、秘密空间s 、份额空间t 、 分配算法、恢复算法等几个方面构成其中参与者集合是参与秘密分享的成员集合；接 入结构r 指出哪些参与者集合可恢复秘密信息，即r 是合格子集的集合显然r 具有单 调性( 即，若4 r 且a b ，那么b r ) f 中极小元称为最小合格子集这些最小合 格子集的集合r o 完全决定了r ，称为f 的基秘密空间指秘密信息的取值范围；份额空 间指秘密份额的取值范围；分配算法是一个以秘密信息为输入，多个秘密份额为输出的 多项式时间算法；恢复算法是一个以多个秘密份额为输入，秘密信息为输出的多项式时 间算法构造一个秘密分享方案就是在一定的接入结构基础上，设计相应的份额分配算 法和秘密恢复算法，使得接入结构中的所有合法子集都能利用秘密恢复算法获得秘密信 息，而所有非合法子集均得不到被分享秘密的任何信息如果在一个秘密分享方案中， 所有非合法子集都得不到关于被分享的秘密的任何信息，则称该方案是完备的( p e r f e c t ) 一个秘密分享方案的信息率( i n f o r m a t i o nr a t e ) 定义为p = l o gl t i l o g 蚓如果一个秘密分 享方案的信息率为1 ，则称其为理想的( i d e a l ) 1 2 秘密分享的研究现状 目前，许多学者都对秘密分享方案进行了研究，其中最常见的是门限体制( 即接入 结构为门限接入结构) ，比较有代表性的方案有s h a m i r 的l a g r a n g e 插值多项式体制 1 1 、 b l a k l e y 的矢量体制 】、a s n m t h 等人的基于中国剩余定理的同余类体制阁等目前提 出的基于广义接入结构( 即非门限接入结构) 的秘密分享方案为数不多，但这类方案更切 合实际应用正如文献【4 】所指出，把秘密分享的概念推广到广义接入结构上去有着重要 的理论和实用价值在对秘密分享体制研究深化过程中，一个比较重要的概念是可验证 秘密分享( v e r i f i a b l es e c r e ts h 盯i n g ，简记为v s s ) 它是由c h o r 等人于1 9 8 5 年在文献f 5 中 提出，主要目的是为了解决分发者的欺骗问题v s s 是在秘密分享的基础上增加了一个 验证算法而形成的v s s 概念一经提出，许多安全、高效的v s s 方案相继出现以文 献 6 】和 7 】中方案为代表的v s s 方案具有较好的安全性和较高的效率另一个重要的概 念是可公开验证秘密分享( p u b l i c l yv e r i f i a b l es e c r e ts h 耻i n g ，简记为p v s s ) ，它用来解决分 发者和分享者相互欺骗的问题 1 9 9 6 年，s t a d l e r 于文献【8 中在v s s 基础上进一步提 出p v s s 的概念，使得不仅验证者( 不必是分享者) 可以验证秘密分发过程的正确性，分 享者也可以验证自己所持有的份额的正确性f i s a k i 和o l 【a l m o t o 于9 8 年在文献f 9 1 中 提出了一个效率相对较高的p v s s 方案后来，s c h o e n m a k e r s 在文献【1 0 1 中对s t a d l e r 和 f q i s a k i 等人的p v s s 模型做了简单的改进 1 3 秘密分享的主要应用 随着研究的日益深入和成熟，秘密分享方案的安全性以及效率都得到了很大的提高， 这使得秘密分享在很多领域得到了广泛的应用以下简单介绍其几个主要应用 1 在门限密码学中的应用 几乎所有实用的门限密码体制都用到了秘密分享方法，主要体现在以下两个方面： 2 ( 1 ) 分布式密钥生成( d i s t r i b u t e dk e yg e n e r a t i o n ，简称d k g ) ，是门限密码系统以及分布式 密码计算的重要组成部分它允许多个参与者共同合作以生成一个密码系统的公钥 和私钥，其中公钥以公开形式输出，私钥被参与者按照某一秘密分享方案所分享主 要的d k g 方案可参考文献【1 1 、【1 2 】等 ( 2 ) 门限签名，是门限密码学的重要组成部分它通过分散签名的权利，使得一个群体的 多个子集具有产生合法签名的权利，并增加攻击者获取签名私钥从而伪造签名的困 难性在已有的大多数门限签名方案中，无论是密钥的分布式生成，还是部分签名的 生成，都频繁地使用秘密分享技术 2 在电子商务中的应用 秘密分享在电子现金、电子拍卖、公平交换等方面有着重要的应用p v s s 不仅可以 应用于可撤销匿名性的电子现金系统的设计中，还可以用来以可信机构的公钥可验证地 加密用户的跟踪信息这样，如果用户利用系统的匿名性进行非法交易或者犯罪活动， 系统就可以借助于可信机构找到该用户的真实身份已提出的电子拍卖方案中很多方案 都采用了秘密分享技术，比如文献 1 3 】此外，n a l l l ( 1 i n 等人在文献【1 4 】中应用秘密分享 技术设计了一种公平交换协议 3 在多方安全计算中的应用 多方安全计算( s e c l 】r e 眦l t i p 盯t yc o m p u t a t i o n ，简称m p c ) 的概念是在文献【15 中提 出的它是用来实现多个参与者计算他们各自的秘密份额的一个函数，要求在即使有恶 意攻击者的情况下也要保证输出的正确性和各自份额的保密性秘密分享是进行多方安 全计算的基本工具 此外，秘密分享还在密钥托管、电子选举等方面有重要的应用可见，对秘密分享 的研究不仅具有重要的理论意义，而且具有不可低估的实用价值 1 4 本文的主要内容 本文研究的主要问题是： ( 1 ) 秘密分享方案的构造研究，主要是对广义多重秘密分享方案和m l l l t o d e a l l e r 秘密分享 方案的研究； ( 2 ) 将秘密分享应用于数字签名方案，构造门限共享验证签名方案 本文各章内容安排如下： 第二章提出一种新的广义多重秘密分享方案，较门限方案有更广泛的现实意义该 方案中，参与者所持有的秘密份额是可以重复使用的接入结构中的合法子集的动态增 3 加以及秘密信息集合中新的秘密信息的动态加入都不会影响参与者原有的秘密份额，只 需要相应的变更公告板公开的信息分析表明，该方案具有较好的安全性能 第三章构造了一个新的m u l 协d e a l e r 秘密分享方案该方案引入了m u l t i d e a l e r 的概 念，进一步避免了分发者的欺骗和秘密信息的泄漏，从而提高了秘密分享方案的安全性 m u l t i _ d e a l e r 秘密分享方案是s i n g l e d e a l e r 秘密分享方案的有效拓展，相比较而言更具有 现实意义本章给出了在已有s i n g l e d e a l e r 秘密分享方案的基础上，构造m u l t i _ d e a l e r 秘 密分享方案的方法 第四章将秘密分享方案与e l g 眦a l 数字签名方案结合起来构造出一种新的门限共享 验证签名方案该方案的n 个验证者中任意t 个可以验证签名的有效性，而少于t 个验 证者不能验证签名的有效性分析表明，该方案不仅具有较好的安全性和较低的计算复 杂度，而且还具有如下特点： ( 1 ) 签名者的私钥可以重复使用，签名不可伪造； ( 2 ) 进行多次验证签名而不会暴露验证者的秘密份额； ( 3 ) 验证者之间不能相互伪造验证信息，从而验证者可以使用相同秘密份额对多个签名 进行验证 这些特点使得方案中的签名私钥和秘密份额都具有可重复使用性 4 第二章一种新的广义多重秘密分享方案 目前，大多数已知的秘密分享方案中，参与者拥有的秘密份额都是针对某一秘密信 息分发的，从而只能使用这些秘密份额来恢复这一特定秘密信息然而，现实生活中存 在具有多个秘密信息的情形在这种情况下，如果使用这些方案来分发秘密份额，那么 秘密分发者就要进行多次秘密信息分发，每个参与者也要相应持有多个秘密份额这显 然需要很大的计算量、通信量和存储量，不切合实际多重秘密分享则可以解决这一问 题多重秘密分享是指参与者可以重复使用他们所拥有的秘密份额来恢复多个秘密信息 的秘密分享体制也就是说，秘密分发者只需要进行一次秘密份额分发过程，参与者也 只需要持有一个秘密份额就可以对多个秘密信息进行恢复显然，多重秘密分享的使用 可以大大减少计算量、通信量和存储量目前虽然已有一些有效的门限多重秘密分享方 案【1 6 川l 醐，但这些方案不能完全消除分发者的欺骗1 9 9 5 年，h 盯n 基于离散对数难 解性问题在文献 1 9 中成功地开发了一种计算上安全的( t ，佗) 门限多重可验证秘密分享 方案，该方案能够解决分发者和参与者的欺骗问题此外，文献【2 0 】提出一种基于离散 对数问题和因子分解问题的门限多重秘密分享方案文献 2 1 提出一种基于杂凑函数的 在线秘密分享机制然而，上述这些方案均为门限方案，而对于广义多重秘密分享方案 ( 即非门限、适合于任意接入结构的多重秘密分享方案) 的研究却很少实际上，基于门 限的多重秘密分享体制仅是多重秘密分享体制的一个特殊情形，它是以所有参与者具有 同等安全性和可靠性假设为基础的咄】在现实生活中这种假设往往是不成立的，因而对 广义多重秘密分享方案的研究具有重要的现实意义由此，本章提出一种广义多重秘密 分享方案 2 1 广义多重秘密分享方案描述 本节所给出的方案构造分成系统设置、秘密份额生成、秘密凭证信息生成和秘密恢 复四个阶段其中前三个阶段由秘密分发者执行，第四个阶段由想恢复秘密信息的参与 者合法子集完成。 2 1 1 系统设置 主要参数：p 和g 为两个大素数，满足9 1 0 1 ) 夕是巧的一个口阶元 是一安 全h a l s h 函数 5 系统参与者：d 为秘密分发者n b 为公告板( n o t i c eb o a r d ) ，用于存储d 公布的公 开参数系统中的所有参与者均能取得n b 中的内容，但只有d 才能修改或更新n b 的内 容k = 尼1 ，南2 ，) 是一个秘密信息集合1 1 为一任意广义单调接入结构( m o n o t o n e 北e e s ss t r u c t u r e ) ，r o = q l ，q 2 ，q2 ) 为r 的基。 p = p 1 ，p 2 ，p n 是分享者集合 p 中任一参与者p i 都具有唯一标识符i d i 为方便起见，引入虚拟参与者p 。+ l ( 实际上它并 不存在) 及其标识符i d n + l ，并假设+ 1 p 且p n + 1 不属于任一q t 2 1 2 秘密份额生成 首先，d 选取上的任意一个n 一1 次非零多项式 ，( z ) = o o + 0 1 z + + o n 一1 z “一1 ， 计算检查向量 y = ( o ，u 1 ，u n 一1 ) ， 其中仇= 9 口tm o d p ，i = o ，1 ，礼1 ，并将y 放入n b 其次，d 为p 中任一参与者巧，计算秘密份额 = ，( i 功) 可1m o d q ， 其中 = ( p 。熟句c 一卟- ) m o 地川忍，np k p ，七j 最后，d 将秘密传送给已 p j 可通过下式验证d 传送给他的秘密信息的可靠性： 如果上式不成立，则可知d 存在欺骗 下面在假定d 是诚实的条件下，验证上式的正确性 证明 严q 三严。州d j ) 叮1 ( m o d p ) 三夕，( i 功) ( m o d p ) 三9 驴。；( m o d p )三9 。o( m o d p ) 6 p dom d 口 f l ：l 三 z q g n 一1 三9 a t l d ；( m o d p ) i = o 三赁口甄删p ) = o 可见验证等式是正确的。 2 1 3 秘密凭证信息的生成 首先，d 在乙中分别随机选择m 个不同的b 1 ，b 2 ，b 。和r l ，r m ，其中m 为 k 中秘密信息个数，并计算 m i = 9 n m o d p ，i = 1 ，2 ，m 其次，对于k ，q j r 0 ，d 根据点集 ( i d 岛，( i d k ) ) lp 蠡嗡) 以及点( o ，玩) ，按照 拉格朗日插值公式生成一个多项式 以z 卜p 赢，加( 耻g 嗍去) 名舶p 盟，苫 岳c m o ， 并计算 铲触队1 ) p 臻( 矗) ( m o d q ) ， p r q 。十1 7 d 订= m ( m o d p ) 再次，d 计算卫= 一毳( m m o d 彩和悬( ) 。 最后，d 把 正，m ， ( ) ，奶，歹= 1 ，2 ，2 ) 放入n b 作为秘密信息的凭证信息 如果d 在今后某时要在k 中动态增加一个新的秘密信息七n 。，则他只需为删生 成新的凭证信息 。，m 。 ( 恐。) ，d 。，j ，j = 1 ，2 ，2 _ ，而不会影响k 中其它秘密信 息的恢复同样，如果要在f o 中动态增加个新的合法子集q 仳留，则d 只需在趣的凭 证信息中增加一也m 叫，i = l ，2 ，m ，而不会影响其它合法子集对秘密信息的恢复 2 1 4 秘密的恢复 设q j 为要恢复秘密的合法子集，其中k 秘密恢复步骤如下： ( 1 ) 中参与者从n b 中得到对应的凭证信息 互，m t ，九( ) ，奶) ( 2 ) p 缸计算关于的恢复信息 z 兽= m ；u 仃m 。d p 7 和数字签名s p 。= s i g p 。( z 兽l i 吗i | m t ) ，其中 ( 一i d ，) ( i d 惫一i d r ) m o d g ( 3 ) p 将z 兽和s p 。传送给的其他参与者p r ，p r 验证从p 砖得到的数字签名s p * ，然 斥亏计算 七：死+ ( 。p 盟，z 兽d 巧，m 。d p ) 喇= 死+ ( z 髯d 巧) m o d p p k q j 下面证明在假设中参与者和d 均为诚实的条件下，上式恢复出来的磋即为 秘密信息 证明显然，只需证明 即可而 所以只要证明 nz 留 p 知q j 奶( m o d p ) m ；扩吼。m ( m o d p ) p k q j n - ( z k - 9 蝌+ 岛j ) ( m o d p ) ， 即可由多项式南( z ) 的构造可知，点集 ( i d 惫，( i d 船) ) ip k ) 和点( i d 叶l ，向( i d 。+ 1 ) ) 均为向( z ) 上的点，又有6 t = 岛( o ) ，所以可利用拉格朗日插值公式计算6 ： ；三，( i d 划。珏。志 p 凫q jp r q ，u p n + 1 ) ，r 岛一5 一7 州- 酬p 恶，痞( 酬 p 乏，陟( i 阢) 睢叫乳_ 珥) p ，娶。毒去 p k q jp r n j u p n + 1 ) ，r 耙 p r p ，r 一尤 一r n ( i d k i d ，) 】+ c 巧( m o d 口) p r p q j u p n + 1 ) ) 8 ! p 乏，卜划p ，基。d 商) ( ( 一i d ，) ( i d 舟一i d r ) p r “o u p 住+ l ，昆 p r p 52 j u p n + l + c 巧( m o dg ) 三 z 忌盯幻+ 叼( m o d g ) 由此可知，结论成立 ( 4 ) 为验证恢复的秘密是否正确，p 可计算允) 并将其与n b 上公布的 ( ) 进行 比较如果 ( 联) = ( ) ，则认为磁= ；反之，则认为恢复过程中存在参与者欺骗 2 2 所提方案性能分析 以下从安全性和计算复杂性两方面着手分析本文方案的性能 2 2 1 安全性分析 以下分析是以离散对数问题难解性为基础，并假设f o 的任一合法子集中至少有一个 参与者是诚实的从方案的构造可以看出，该方案可以抵抗以下几种攻击： 攻击1 ：在秘密份额分发阶段d 企图给参与者p ，发放假的秘密份额是不可行的假的 秘密份额可被耳通过验证方程检测出 攻击2 ：参与者p 七在秘密恢复期间企图获得其他参与者p r 所持有的秘密信息z ，是不 可行的在秘密恢复过程中， p 仅获得由p ，传送过来的z 搿以及数字签名s p 。( 因 为签名信息只能用于验证，所以在此不予考虑，下同) 由z 搿的构造以及离散对数难 解性假设可知，p k 不能从z 搿中获得z ，的任何信息同样分析可知，即使在p 恢 复了k 中部分信息后仍不能获得的任何信息另有，即使q j 中不合法参与者合 谋也不能获得z ，的任何信息 攻击3 ：p 在恢复了k 中部分秘密信息后，企图在不借助中其它诚实参与者的帮助 下自行获得k 中剩余信息是不可行的由攻击2 不可行可知，p 企图获得中 其它参与者的秘密信息从而自行恢复k 中剩余信息是不可行的那么，p 惫为得到 k 中剩余信息就只能利用那些在完成的恢复过程中获得的信息，来伪造新的恢复过 程中其它成员输入的信息具体分析如下假设已恢复信息南o ，在其恢复过程中，耳 9 向p 砖传送的恢复信息有z 黑现在p 要恢复秘密南1 ，p 向希望能利用已知的信息z 粤 伪造p ，的新的恢复信息z 訾而 z 曼) = m ：4 r jm o d p ， z ；f 72m o 。m o d p ， z ! ：仃z ：9 jm o d p ， z ； 7 = 仃z 】 。m o q p ， 显然，只有在m 。= m 。的条件下( 否则需要求解离散对数) 才能伪造伪造z 浮但由于 m o 和m 1 是d 在中随机选取不同的r o ，r 1 ，然后计算以9 为底的模指数得出的， 这保证了m o 和m 1 的随机性，所以仇1 = m o 的概率很小，进而这种攻击不可行同 样分析可知，即使在恢复了多个秘密信息后，参与者之间仍然不能相互伪造他人新 的恢复信息 攻击4 ：在假设d 是诚实的条件下，p 企图在恢复过程中公布假的恢复信息是不可行 的如果p 忌存在欺骗，那么通过磁计算得到的 ( 联) 值必与危( ) 不一致这时，d 可根据值z 凫计算z 兽，然后利用相应的数字签名s p 。找出该不诚实参与者 以上分析表明，该方案不仅可以保证多个秘密信息恢复后参与者持有的秘密份额的 保密性，而且可以抵御伪造他人新的恢复信息等多种攻击可见，该方案具有较好的安 全性 2 2 2 计算复杂性分析 在秘密份额生成阶段每个参与者为验证收到的秘密份额正确性需要进行他+ 1 次模 指数运算和n 一1 次模乘运算对于每一个秘密信息，d 为其计算凭证信息需要进行2 次 拉格朗日插值操作、2 + c 次模指数运算和2 次h a s h 运算由于秘密份额生成阶段和凭 证信息生成阶段只执行一次，故对整个方案的影响不大动态增加一个新的秘密信息需 要公开3 + j 个参数，动态增加一个新的合法子集需要公开m 个参数另外，合法子集 q j 为恢复一个秘密信息需要作i q j l 次模指数运算、i 屿卜1 次模乘运算、i q ，1 次签名与 验证和1 次h a s h 操作为验证恢复信息正确性需进行1 次h a s h 操作 1 0 第三章m u l t i d e a l e r 秘密分享方案的构造 通常的秘密分享方案在安全性方面大都附加了d e a l e r 是诚实的假设，然而这样的假 设在现实生活中往往是不成立的就目前的诸多方案来说，秘密分享系统都只含有单个 d e a l e r ，这就不可避免地存在d e “e r 欺骗和泄漏秘密信息的可能在现实生活中，有时可 能并不希望d e a l e r 知道所要分享秘密的值，因为d e a l e r 也存在泄漏秘密的可能比如在密 钥托管中，秘密持有者可能并不希望可信中心知道具体的密钥值这时，s i n g l e d e 越e r 方 案的这个缺点就明显的表现出来就此，本章提出m u l t i d e a l e r 的概念，即存在一个d e a l e r 集合d = d l ，d 2 ，d m ，使得被分享的秘密s 由d 中成员联合生成并分发给参与者 d 中任意单个成员、任意不诚实成员集合均不知道s 的具体的值这就避免了d e a l e r 欺 骗和泄漏秘密信息 本章将给出基于已有s i n 百e d e a l e r 秘密分享方案构造m u l t i - d e a l e r 秘密共享方案的具 体方法该方法不但增加了系统的安全性、实用性，而且继承了原s i n 斟e d e a l e r 方案的全 部优点( 安全性以及效率等) 3 1 相关工作 这里首先给出文献 2 3 中的s i n g l e d e 猷e r 秘密分享方案 3 1 1 系统的参与者及主要参数 d 是一个d e a l e r ，p = p 1 ，p 2 ，p n ) 是参与者集合，v 是一个验证者( 不必是分享 者) p ，q 为大素数，满足g 旧一1 g 为零上的g 阶生成元，使得在召中计算以夕为底的 离散对数是不可行的秘密空间为刃接入结构r 2 p ，是一个( t ，n ) 门限接入结构，即 r = bl b l t ) r r o = bi i b l = t 是r 的基 3 1 2 秘密份额的产生和验证算法 设d 要分享的秘密为s ，步骤如下： ( 1 ) d 首先选取z g 上的t 维非零向量o = ( o l ，0 2 ，o t ) t 及乙上的t 佗矩阵c ：( g j ) ， 满足：c 的任意t 列线性无关，任意z 一1 列不能表示o ( 2 ) d 在 u ( s ) = ( 6 1 ，b 2 ， 中随机选一维向量( 6 1 ，6 2 ，巩) ，计算 ( s l ，s 2 ，s 。) = ( 6 1 ，6 2 ，b t ) c y = 9 8 ( m o d p ) ， 札i = 矿( m o d p ) ，l i t ， = 9 8 j ( m o d p ) ，1 j 佗 ( 3 ) 发送s t 给参与者p t ，s i 就是d 分发给参与者p i 的秘密份额，同时公布 o ，c ，秽，u 1 ，u t ，u 1 ，u n 任意验证者v 可根据d 公布的公开信息验证以下等式是否成立： 参与者p t 可通过等式 验证d 是否存在欺骗如果上式不等，那么参与者p t 向d 广播一个抱怨d 对于接收 到的一个来自p t 的抱怨，公布相应的满足上式的s t 设拒绝条件为： ( 1 ) d 得到的抱怨是来自于合法子集； ( 2 ) d 答复抱怨的值s t 不满足p t 的验证等式； ( 3 ) v 断定d 在分发过程中存在欺骗 如果d 满足拒绝条件中的任一点，则d 被拒绝，否则d 被接受 在假设计算以9 为底的离散对数是困难的条件下，文献 2 3 证明了此p v s s 方案在 计算上是安全的 1 2 、， 8 1 1 b 0 。触 p do m 口 。芦 = 耖 佗 一 一 ， p do m k u 。随 i | 口 n 一 一 l p dm 尼 u 。h 随 i | 钞 i 氏 9 3 2 m u l t i d e 出e r 秘密分享方案的构造 本节将在第3 1 节所提出的s i n g l e d e a l e r 秘密分享方案的基础上构造m u l t i - d e a l e r 秘 密分享方案 3 2 1 系统的参与者及主要参数 设d = d 1 ，d 2 ，d m ) 为d e a l e r 集合，并假设d 中至少存在一个诚实的d e a l e r n = ( n l ，0 2 ，o t ) t 为召上的t 维非零向量。c = ( g j ) 是召上的t n 矩阵，满足： c 的任意t 列线性无关，任意t 一1 列不能表示o p ，g 为大素数，满足q | p 一1 9 为玩上 的q 阶生成元，使得在召中计算以g 为底的离散对数是不可行的秘密空间为露，接入 结构i 、2 p ，是一个( ，耗) 门限接入结构，即r = bb 2 p 且l b l 吼r o = bb 2 p 且吲= t ) 是r 的基 3 2 2 秘密的生成、秘密份额的产生及验证算法 ( 1 ) d 中任一成员耽执行3 1 中的秘密分享方案，即在 汐( ) = ( 玩1 ，玩2 ，6 讫) 露l 中随机选一t 维向量b t = ( 玩1 ，b 仍，b ) ，其中为也在名上取得的随机数计算 ( s n ，s t 2 ，s 讯) = 6 t c ， 玑= 夕( m o d p ) ， u 巧= 9 6 幻( m o d p ) ，1 t ， = 夕5 蚶( m o d p ) ，1 j n 然后发送s 玎给参与者巧，s 巧就是域分发给参与者p j 的秘密份额，同时公布 ( 2 ) 公布o ，c 参与者p j 可通过等式 验证耽是否存在欺骗任意验证者v 可根据功公布的公开信息验证以下等式是否 成立： 1 3 、， i | 一叼 6 吁 。触 m 一 一 l p dom 派 珏 。柑 i | i i 乳 9 p dom 町巧 仳 。触 l | y 设 f = id i 未被拒绝( 根据拒绝条件) ) 显然，在假设d 中至少存在一个诚实秘密分发者的条件下f 非空 ( 3 ) 定义要分享的秘密为s2 ，参与者巧的秘密份额为勺2 s 诊 3 2 3 秘密的恢复 由3 2 2 知 勺= s 巧= 阮勺= ( 6 t ) c j = 6 勺， t ft ft f 其中 6 = ( b ( ，6 ( ，6 ( 。) ) ， 6 ( m ) = 6 t m ，l m t ， i f 岛为矩阵c 的第列向量 对任意b = p 1 ，p 2 ，p t ) r o ，可设存在乙中元d 1 ，d 2 ，也使得 ( c 1 ，c b ，g ) ( d 1 ，d 2 ，一，d t ) t = o 从而可通过以下计算恢复秘密信息s s j 奶 j = 1 = 6 ( fc j d 订 、z j jj7 j = 1 =6 o = 6 ( ”) o m ”l = 1 1 4 n ，那么他可获得的信息除了公布的信息 外，还有 m e s l = 6 t ，( 龟1 ，s 饥) ，i = 1 ，h 一1 显然，为获得s ，a 需要从这些已知信息中计算得出或者直接猜测得出s 而这些 信息都与无关，无法计算得到，所以获得s 的概率只相当于在露中随机猜测s 获得成功的概率，即1 ( q 一1 ) 口 可见，由于s 是在方案执行过程中由d 联合生成，这使得任意d 中单个成员( 包 括诚实成员) 、任意不诚实成员合谋均不知道s 的具体值另外，方案中拒绝条件的 使用，使得部分不诚实的d e a l e r 在秘密分发之前被排除，增强了s 保密性 ( 2 ) p 方安全性： 引理3 2 在假设对手a 至多可以收买p 中t 1 个参与者条件下，a 得不到关 于s 的任何信息 证明： 如a 收买了 p 1 ，p 2 ，p c 一1 】，那么他可获得的信