（概率论与数理统计专业论文）秘密分享方案的构造.pdf

摘要 秘密分享是一种分发、保存和恢复秘密信息的方法，也是信息安全和数据保 密的重要手段之一。它在门限密码学、安全多方计算、电子商务、电子选举、密 钥托管等诸多方面有着广泛的应用前景。本文对秘密分享方案的构造作了一些研 究，主要是对多分发者秘密分享方案和广义多重秘密分享方案的研究本文主要 工作如下： 首先，基于多分发者的思想以及现实中需要分享多个秘密的情形，构造了多 分发者多秘密分享方案方案避免了分发者泄漏秘密信息，提高了秘密分享方案 的安全性，与以往的单分发者秘密分享方案相比，多分发者方案为秘密分享提供了 更现实的解决办法。另外，本文中的新方案假设分发者诚实的概率大于二分之一， 显然这一假设条件比假设至少有一个分发者对所有的参与者诚实更贴近现实同 时达到了与已有方案同等的安全性。 其次，基于离散对数的难解性，构造了一个广义多重秘密分享方案该方案 中，参与者持有的秘密份额可以重复使用，接入结构中合法子集的动态增加以及 秘密信息集合中新的秘密信息的动态加入都不会影响参与者原有的秘密份额， 只需要相应地变更公告板上公开的信息；同时，新方案中避免了分发者和参与者 的欺骗问题；而且在计算量上有一定的改进；方案的安全性基于离散对数的难解 性。分析表明，方案具有较好的安全性能。 关键词秘密分享可验证秘密分享动态秘密分享多分发者秘密分享 广 义多重秘密分享 a b s t r a c t s e c r e ts h a r i n gi sam e t h o do fd i s t r i b u i o n ，s a v ea n dr e c o v e r yo fs e c r e t ，a n d a 王s oi sav e r yi m p o r t 8 越tt e c h n i q u ei ni b f o r r n a e i o ns e c u “镑a n ( 量d 8 主8e n c r y p t i o n 。 s e c r e ts h a r i n gh a sb r o a da p p l i c a t i o ni nt h r e s h o l dc r y p t o l o g y ，e l e c t r o n i cc o m - m e r e e ，e l e c t r o 珏i ce l e c 七i o 珏，壬( e ye s e r 孵躲鑫o n ，ar 韶e 氇r 盘o nt h ee o n s t r u e 专i 掘 o fs e c r e ts h a r i n g8 c h e m e si sd o n ei nt h i sp a p e r ：a n dn e ws e c r e ts h a r i n gs c h e m e sa r e p r o p o s e do nt 量l eb 8 s 括o fr e 越s i t u a i o 毽si bo u rl i 凳。 t h em a i nc o n t r i b u t i o n si nt h ep a p e ra r el i s t e da sf o l l o w s ： f i r s t 孔am u l t i d e a l e rm u l i s e e 掩t 矗a r 赫gs c h e m eb a s e do nt h ee o n c e p to f m u l t i d e a l e ra n dt h er e a ls i t u a 七i o no fs h a r i n gm u l t i s e c r e tw a sp r o p o s e d i tr e d u c e s t 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 b g eb yt h ed e a l e r f l l r t h e r m o r e ，i tj m p r o v et h e s e c u “t yo fs e c r e t8 h a r i n gs e h e m e 。c o m p a r e dw i t ht h ep r e v i o u sm e t h o d s ，s c h e m e s o fm u l t i d e a l e rp r o v i d e 8am o 】er e a l i s t i cs o l u 廿o nt os e c r e ts h a r i n gi nt h en e w l y p r o p o s e ds c h e m e ，w es t l p p o s e 糠a t 如el o y a lp r o b a b m t y e v e r yd e a l e rw a s 掇o r e t h a nf i 托yp e r c e n t c l e a r l y ，t h es u p p o s i t i o ni sm o r ep r o p e rt h a nt h es u p p o s i t i o n 也瓣8 圭l e 稿to 珏ed e a l 潍w a sl 娜a l 协啦lt h ep 艇毯e i p 8 h t s b u 毛强es 馥e m e 拯& s s e c u r ea st h ef o r m e r l 弘p r o p o s e ds c h e m e s e e o 轻d 堍8g e 珏e r 蠢壬壬l 醢l 髓s e c r e t 豳a r 殛；s c l l e m ew 鑫sp f 。p 稍e db a s e do nt h e d i 微c u l t y0 fc o m p u t i n gd i s c r e t el o g a r i t h m s i n 堋i ss c h e m e ，t h es e c r e ts h 艄e s 圭l e l db yp a r i e i p a h t sc a nb eu s e dr e p e a t e d i y ；b e s i i e s ，t h ed y n a r n i cp a r t i c i p a n c e o ft h ea u t h o r i t a t i v es u b s e to fa c e e s ss t r u c t u r ea n dt h es e c r e ti n f o r m a t i o nn e e d n t t oc h a n g et h es e c r e ts h a r e sb u ta l t e rt h ei n f o r m a i o np u b l i s h e do nn o t i c eb o a r d i nt 1 1 en e w l p p r o p o s e ds c h e m e - t h ed e c e p t i o n d e a l e r sa n dp a r t i c i p a n t si sa v o i d - 8 b l ef u r t h e r m o r e ，t h ec o m p u t a t i o nt 黼ki sr e l i e v e d f i n a l ly j t h es e c u r i t yo ft h ep r o _ p o s e ds c b e m ei sb a s e d t h ed i 蠡e 越乞yo fe o 孤p u e i 】罐t h ed i s c r e t el o g a r i t h m s 。t h e 丘n a la n a l y s i sd e m o n s t r 砒e dt h 批t h ep r o p o s e ds c h e m ep r o m i s e db e t t e rs e c u r i 吣r _ k e yw o r 幽s e c 糟t 惑a r i 珏g v r 遗西ks e e r e ts 歉凝i n g 由珏鑫黻l es e 嚣蘸蠢默i 珏g m u l t i d e a l e rs e c r e ts h a r i n g g e n e r mm u l t i s e c r e ts h a r i n g i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和窀子版 本；举校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫播、数字诧或其它手段保存论文；学梭有权提供甏录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按脊关规定向国家有 关部门或者规构送交论文兹簸印件翻电子叛；在不以赢利为国熬懿蓠 提下，学校可以邋当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：繁爱筚 御6 年芎月；o 目 经指导教籁阉意，本学位论文属予保密，在年解密瑶适用 本授权书。 指导教雾器签名：学位论文作者签名： 荤爱肇 解密时间：年月日 各寮缀豹最长镶密年鞭及书写貉式焱定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：午睡荤 6 年岁月；d 日 第一章引言 网络与通信技术的迅猛发展，给人们生活和工作带来巨大的便利，但同时也 带来了很多安全隐患。大量的敏感信息如病例、资金转移、私人财产等常常通过 计算机网络或公共通信设施进行传输，人们迫切需要保证这些信息的保密性和真 实性。社会信息化使得信息安全与数据保密问题成为几乎每个人都不可忽视的问 题，而现代密码学可以用于解决信息的保密性、完整性、可用性、可控性和不可 抵赖性。能够为信息安全提供关键理论和技术，是保护信息安全最有效的手段 近年来，密码学得到长足的发展，其应用已经渗透了社会生活的各个方面，比如 数据加密、信息认证、网络安全、电子选举、电子现金等。 为了实现信息的安全保密，人们主要采用密钥加密信息，从而使不拥有密钥 的非法用户无法窃取信息，这使得信息的安全保密主要维系于密钥的安全在 k e r c k h o 丘假设下，一个密码系统的安全性应取决于对密钥的保护，而不是对系统 或硬件本身的保护，所以密钥的安全保密是密码系统安全的重要保证，也是密钥 管理技术的核心。解决密钥保护问题的所有方法都应该保证以下三个条件成立： 密钥不会丢失、密钥不会被破坏和密钥不会被非法授权者获得作为密码技术之 一的秘密分享技术就是解决这类问题的有效方法，是信息安全和数据保密中重要 的手段之一。 1 1 秘密分享的基本概念 1 9 7 9 年s h a m 州l 】和b l a u e y 各自独立地提出了秘密分享( s e c r e ts h a r i n g ， 也称为密钥分享或密钥共享) 的概念，它是指将秘密信息s 分割成若干份额( s h a r 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 a r t i c i p a n t s 或p l a y e r s ) 集合p 、接入结构( a c c e s ss t r u c t u r e ) r 、秘密空间s 、 份额空间t 、分配算法、恢复算法等几个方面构成。其中参与者集合是参与秘密 1 第一章引言 分享的成员集合；接入结构r 指出哪些参与者集合可恢复秘密信息，即r 是合格 子集的集合。显然r 具有单调性，即若a r 且a b ，那b r 。r 中极小元 称为最小合格子集。这些最小合格子集的集合r o 完全决定了r ，称为r 的基秘 密空间指秘密信息的取值范围；份额空间指秘密份额的取值范围；分配算法是一 个以秘密信息为输入，多个秘密份额为输出的多项式时间算法；恢复算法是一个 以多个秘密份额为输入，秘密信息为输出的多项式时间算法构造一个秘密分享 方案就是在一定的接入结构基础上，设计相应的份额分配算法和秘密恢复算法， 使得接入结构中的所有合法子集都能利用秘密恢复算法获得秘密信息，而所有非 合法子集均得不到被分享秘密的任何信息如果在一个秘密分享方案中，所有非 合法子集都得不到关于被分享的秘密的任何信息，则称该方案是完备的( p e r f e c t ) 一个秘密分享方案的信息率( i n f o r m a t i o nr a t e ) 定义为p = 1 0 9i t i 1 0 9l s i 如果 一个秘密分享方案的信息率为1 ，则称其为理想的( i d e a l ) 1 2 秘密分享的研究现状 秘密分享的思想一经提出，便得到了许多学者的关注并对其进行了大量的研 究。 最早的秘密分享体制都是门限体制( 即接入结构为门限接入结构) ，最有代表 性的方案有s h a m i r 的l a g r a n g e 插值多项式体制1 1 1 、b 1 a l d e y 的矢量体制、 a s m u t h 等人的基于中国剩定理的同余类体制等。 后来人们发现这种门限体制在现实应用中有一定的局限性，正如文献4 1 所 指出把秘密分享的概念推广到广义接入结构上去，有着重要的理论和实用价值， 出现了广义接入结构上的秘密分享方案刚纠，这类方案更切合实际情形 由于早期提出的秘密分享方案中存在以下问题：当要更新秘密时系统必须为 每位参与者重新分配新的秘密份额，即每个秘密份额至多只能使用一次；当某一 个参与者的秘密份额泄漏时，系统不能做到只为该成员重新分配秘密份额而不影 响其他参与者的秘密份额；当有新的参与者加入时，系统也必须重新为每一位参 与者分配秘密份额。为了克服上述不足，提出了动态秘密分享方案刚。 由于参与者拥有的秘密份额是针对某一秘密分发的，从而只能使用这些秘 密份额恢复特定的秘密，而现实中存在多个秘密的情形，如果仍然使用以往的 方案来分享秘密，那么需要进行多次秘密的分发且每一位分享者要持有多个秘 密份额，这需要很大的计算量、通信量和存储量。于是提出了多重秘密分享方案 【1 0 】【1 1 】【1 2 】【1 3 】【1 4 】 1 同，很好地解决了这一问题。 2 第一章引言 由于早期的秘密分享方案都附加了分发者和参与者是诚实的假设，因而在实 际中并不实用，为了解决分发者欺骗由c h o r 等人于1 9 8 5 年在文献1 6 1 中提出 可验证秘密分享( v e r m a b ks e c r e ts h a r i n g ，简记为v s s ) ，v s s 是在秘密分享的 基础上增加了一个验证算法而形成的。v s s 概念一经提出，许多安全、高效的 v s s 方案相继出现，以文献 1 7 】和 1 8 】中方案为代表的v s s 方案具有较好的安 全性和较高的效率。1 9 9 6 年，s t a d l e r 于文献f 1 9 1 中在v s s 基础上进一步提出 了一个效率相对较高的可公开验证秘密分享( p u b l i c l yv e r i 矗a b l e s e c r e ts h 壮i n g ，简 记为p v s s ) ，它用来解决分发者和参与者欺骗的问题，使得不仅验证者( 不必是 参与者) 可以验证秘密分发过程的正确性，参与者也可以验证自己所持有的份额 的正确性f u j i s a k i 和0 l ( a m o t o 于9 8 年在文献f 2 0 1 中提出了一个效率相对较 高的p v s s 方案。后来，s c h o e n m a k e r s 在文献 2 1 1 中对s t a d l e r 和f u j i s a k i 等 人的p v s s 模型做了简单的改进 为了避免单个分发者泄漏秘密的情形李云华在其毕业论文f 1 4 1 中研究了多 分发者秘密分享方案的构造 1 3 秘密分享的主要应用 随着研究的日益深入和成熟，秘密分享方案的安全性以及效率都得到了很大 的提高，这使得秘密分享在很多领域得到了广泛的应用以下简单介绍其几个主 要应用 1 在门限密码学中的应用 几乎所有实用的门限密码体制都用到了秘密分享方法，主要体现在以下两个 方面： ( 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 方案可参考文献 2 2 、 2 3 等 ( 2 ) 门限签名，是门限密码学的重要组成部分它通过分散签名的权利，使得一 个群体的多个子集具有产生合法签名的权利，并增加攻击者获取签名私钥从 而伪造签名的困难性在已有的大多数门限签名方案中，无论是密钥的分布 式生成，还是部分签名的生成，都频繁地使用秘密分享技术 2 在电子商务中的应用 3 第一章引言 秘密分享在电子现金、电子拍卖、公平交换等方面有着重要的应用 p v s s 不仅可以应用于可撤销匿名性的电子现金系统的设计中，还可以用来以可信机 构的公钥可验证地加密用户的跟踪信息这样，如果用户利用系统的匿名性进行 非法交易或者犯罪活动，系统就可以借助于可信机构找到该用户的真实身份已 提出的电子拍卖方案中很多方案都采用了秘密分享技术，比如文献f 2 4 1 _ 此外， f r a n k l i n 等人在文献f 2 5 1 中应用秘密分享技术设计了一种公平交换协议， 3 在多方安全计算中的应用 多方安全计算( s e c u r em u l t i - p a r t yc o m p u t a t i o n ，简称m p c ) 的概念是在文献 f 2 6 1 中提出的它是用来实现多个参与者计算他们各自的秘密份额的一个函数， 要求在即使有恶意攻击者的情况下也要保证输出的正确性和各自份额的保密性 秘密分享是进行多方安全计算的基本工具 此外，秘密分享还在密钥托管、电子选举等方面有重要的应用可见，对秘 密分享的研究不仅具有重要的理论意义，而且具有不可低估的实用价值 1 4 本文的内容与结构 本文研究的主要问题是秘密分享方案的构造，主要是对多分发者多秘密分享 方案和广义多重秘密分享方案的研究 本文各章内容安排如下： 第二章是对已有的两类方案的简单回顾。 第三章是对新提出的方案的描述和分析。其中，第一节基于多分发者的思想 以及现实中需要分享多个秘密的情形，构造了一个多分发者多秘密分享方案，避 免了分发者泄露秘密信息，提高了秘密分享方案的安全性，与以往的单分发者秘 密分享方案相比，多分发者方案为秘密分享提供了更现实的解决办法。另外，新 提出的方案假设每一位分发者诚实的概率大于二分之一，假设条件降低了，更贴 近现实，同时达到了与已有方案同等的安全性；第二节提出一个基于离散对数的 广义多重秘密分享方案，较门限方案有更广泛的现实意义。该方案中，参与者所 持有的秘密份额是可以重复使用的；接入结构中的合法子集的动态增加以及秘密 信息集合中新的秘密信息的动态加入都不会影响参与者原有的秘密份额，只需要 相应地变更公告板上公开的信息；在秘密份额分发阶段避免了分发者欺骗参与者 的问题，同时在秘密恢复过程中又避免了参与者之问的欺骗，这一点要优于其他 的方案；而且在计算量上较之已有的方案有一定的改进；方案的设计原理简单， 其安全性是基于离散对数的难解性。分析表明，该方案具有较好的安全性能。 4 第二章预备知识 由于本文的方案是在原有方案的基础上进行的研究与改进，所以首先简单地 回顾一下本文中涉及到的两类方案及它们的结论。 2 1 多分发者秘密分享方案的构造 通常的秘密分享方案在安全性方面大都附加了分发者是诚实的假设，然而 这样的假设在现实生活中往往是不成立的。就目前的诸多方案来说，秘密分享 系统都只含有单个分发者，这就不可避免地存在分发者欺骗和泄漏秘密信息的 可能。在现实生活中，有时可能并不希望分发者知道所要分享秘密的值，因为分 发者也存在泄漏秘密的可能就此，李云华在其毕业论文1 4 1 中研究了多分发 者( m u l t i - d e a j e r ) 秘密分享方案的构造。所谓多分发者即存在一个分发者集合 d = d - ，d 。，d 。) ，使得被分享的秘密s 由d 中成员联合生成并分发给参与 者。d 中任意单个成员、任意不诚实成员集合均不知道s 的具体的值，这就避免 了分发者欺骗和泄漏秘密信息。 2 1 _ l 方案的描述 下面就给出李云华在其毕业论文 14 的第三章中给出的多分发者秘密分享 方案，该方案是在文献 2 7 中的秘密分享方案的基础上构造出来的。 ( 一) 系统的参与者及主要参数 设d = d ，d 2 ，d 。) 为分发者集合，并假设d 中至少存在一个诚实 的分发者p = p 1 ，p 2 ，p 。) 为参与者集合。n = ( 0 1 ，0 2 ，o 。) ，为刃 上的t 维非零向量g = ( a ，) 是露上的t n 矩阵，满足：g 的任意t 列 线性无关，任意t 一1 列不能表示o p ，q 为大素数，满足q l ( p 一1 ) 9 为忍 上的q 阶生成元，使得在环中计算以9 为底的离散对数是不可行的秘密空 间为彩：接入结构r 2 p ，是一个( ，佗) 门限接入结构，即r = b1 日2 p 且i b i 出r o = bb 2 尸且l b i = t ) 是r 的基 ( 二) 秘密的生成、秘密份额的产生及验证算法 5 第二章预备知识 ( 1 ) d 中任一成员d 。执行文献 2 7 中秘密分享方案，即在 u ( t ) = ( 6 m6 协：6 。t ) 召i 6 ：j = 。) j = l 中随机选一t 维向量b 。= ( 6 m6 幽，b 。) ，其中。为画在乙上取得的 随机数计算 ( s m3 一，s 。) = 6 g ， 玑= 9 。( m o d p ) ， u = 夕6 ”( m o d p ) ，1 j t ， u ”= 9 5 1 ，( m o d p ) ：1 n 然后发送给参与者p ，s 。就是d 。分发给参与者p ，的秘密份额，同 时公布 ( 2 ) 公布n ，c 参与者p ，可通过等式 验证d 。是否存在欺骗，任意验证者v 可根据d ，公布的公开信息验证以 下等式是否成立： 设 f = ( id 。未被拒绝( 根据拒绝条件) ) 显然，在假设d 中至少存在一个诚实秘密分发者的条件下f 非空 ( 3 ) 定义要分享的秘密为s = 。孚2 z ，参与者p ，的秘密份额为s j2 。善8 ” ( 三) 秘密的恢复 由( 二) 知 勺= = 6 。 l f 4 f 6 勺= ( 堍) l f l 三 一 一 1 p d0 俯 。随 p don 扛 町玎 。m _ f n 一 ， 一 l p dom j 拖 u 。 = j 第二章预备知识 其中 6 = ( 6 ( 1 ) ，6 ( 2 ) ，一) ， 6 = 6 。，1s m t ， i f g 为矩阵c 的第j 列向量 对任意b = p ，：p 2 ， ，p d r o ，可设存在乙中元d 1 ，d 2 ，也使得 ( c 1 ：c 2 ：，c ) ( d 1 ，d 2 ，：d t ) 丁= o 从而可通过以下计算恢复秘密信息s s ，d ， j = 1 c j ) d j = 6 ( c j d j ) 6 n = b ( ”) n 。 = s t f 2 1 2 方案的结论 在假设d 中至少存在一个诚实的分发者即f 非空，且对手至多可以收买f 中h 一1 个成员，其中h 为f 中成员的个数，以及对手至多可以收买p 中t 一1 个参与者条件下，李证明了其方案的安全性 2 。2 基于单向函数的广义秘密共享方案 目前，大多数已知的秘密分享方案中，参与者拥有的秘密份额都是针对某一秘 密信息分发的，从而只能使用这些秘密份额来恢复这一特定的秘密信息。然而，现 实中具有多个秘密信息的情形，在这种情况下，如果使用这些方案来分享多个秘 密，那么秘密的分发者就需要进行多次秘密份额的分发，每一个参与者相应地也要 持有多个秘密份额。这显然需要很大的计算量，通信量和存储量，不切合实际。多 重秘密分享方案的提出解决了这一问题。多重秘密分享方案中秘密分发者只需要 进行一次秘密份额的分发，参与者也只需要持有一个秘密份额就可以对多个秘密 进行恢复。人们相继提出了很多多重秘密分享方案【1 0 】【1 l 】【1 2 】【1 3 】 1 4 1 5 】 2 8 【2 蜘。 7 o b 。一 时 o6 肼 。一 第二章预备知识 其中【2 8 】 2 9 】是门限多秘密分享方案，它是以所有参与者具有同等安全性和可靠 性假设为基础的 3 皿，在现实中这种假设往往不成立，因而对于广义多重秘密分 享方案的研究具有重要的现实意义。 2 2 1 方案的描述 现实中存在这样的问题：某公司的财务部门有a ，b ，c ：d ：e 5 位会计人员，该 公司在银行开设了甲，乙，丙三个账户。出于某种业务上的需要，要求必须有a ，b 两人同时在场或者b ，c ，d 三人同时在场时才能恢复出甲帐户的密码；必须 有a ，c ，d 三人同时在场或者a ，c ，e 三人同时在场时才能恢复出乙帐 户的密码；必须有a ，d ，e 三人同时在场或者b ，e ，d 三人同时在场时 才能恢复出丙帐户的密码。其他不满足要求的任何组合都无法恢复出任何帐户的 密码。针对这一问题，文献f 1 5 给出了如下的解决方案： f 一) 系统初始化 p 是一个大素数，d 是分发者，p = p 1 ，p 2 ，p 。) 为分享者集合， s = s ，s 2 ，s k ) 为要分享的秘密的集合，系统要求有一块公告板，每一 个成员均可读到公告板上的内容，但无权向公告板上写内容，只有d 可以在 公告板上写内容。 ，2 ，： 是有限域g f ( p ) 上的个不同的单向函数， 公开在公告板上碍是接入结构r 的基，其中r 。是集合p 上的能够恢复 秘密s ，的单调接入结构，i = 1 ，2 ， ( 二) 秘密份额的分发及凭证信息的生成 首先，分发者d 随机地选取礼个元素z 。，z z ，：z 。：并将z ，秘密地发 送给p ，j = 1 ，2 ，n 其次，对每一个r 0 以及每一个a 碑，其中i = 1 ，2 ，d 随机选取 r g f ( 口) ，计算 t = s i 一 ( r a + 码) d i p j a ) 并在公告板上公开h = ( r 以，t i ) l a r 0 ) ，i = 1 ，2 ， ( 三) 秘密的恢复 设y r ：是一个合法子集，有权恢复秘密s ，那么其成员可以通过以 下过程来恢复秘密s 。 ( a ) 取出包含在y 中的一个极小合法子集，不妨设其为a = p ，p z ，：r ) 8 第二章预备知识 ( b ) 每个成员b ，j = 1 ，2 ，t ，在公告板上读出( r a ，t 。a ) 以及五，计算 ( c ) 汇聚这些，再根据从公告板上读到的t ，就可以恢复出秘密 2 2 2 方案的结论 s 。= t ；a + 川p j ) 该方案简单可行，其安全性主要基于单向函数的求逆难解性方案中每个成 员无论属于多少个合法子集，只需要保存一个秘密份额，而且该秘密份额可以重 复多次使用并且在需要更新授权子集时无需更改每个成员的秘密份额。 9 第三章本文提出的新方案 针对2 1 节和2 2 节的方案中存在的问题与不足，分别构造了一个改进的方 3 1 多分发者多秘密分享方案 由于2l 中的方案假设d 中至少存在一个诚实的d e a l e r ，是指至少存在一个 对所有参与者均诚实的d e a l e r 这一假设在现实中并不合理，因为诚实与否并不 是绝对的现在我们就从概率的角度出发，假设分发者是经过精心挑选的，每一 个分发者( 对参与者及整个系统) 诚实的的概率都大于二分之一，且参与者拥有 的秘密份额并不是对所有参与者均诚实的分发者发送的秘密信息的模加，而是对 参与者诚实的所有分发者发送的秘密信息的模加( 也就是说，只要分发者对某参 与者是诚实的，那么该参与者就接受他发送的秘密信息) ，正是基于这样的假设， 构造了如下方案： 3 1 1 新方案的描述 ( 一) 系统参与者及主要参数 p ，q 为大素数，满足口f p 一1 ) ，9 为召上的q 阶生成元，使得在刃 中计算以9 为底的离散对数是不可行的 d = d ，d z ，d 。 为分发者集 合，他们的身份对参与者是公开的，但彼此不公开p = p ，p 2 ，p 。 是 参与者的集合，p 中任一参与者p 。都具有惟一身份标识符i d 。刃，r o = q 1 n 2 ，q ) 为p 上的单调广义接入结构r 的基。k = 1 ，2 ， 是要分享的秘密的集合。其中n 。是能恢复秘密。的极小合法子集 ( 二) 秘密信息的分发及秘密份额的生成 ( 1 ) 分发者耽在巧中随机选取瓤及。n 。n 2 ) ，n 。构造多项式 ( z ) = 丑+ 啦! z + n ：2 2 2 + + 血m z “( m o d g ) 且公开 玑= g “，= g 。”，j = 1 ，2 ，n 1 n 第三章本文提出的新方案 ( 2 ) d 。为p 中任一参与者p ，计算秘密信息z ：，= ( i d ，) ，将其秘密地发送 给p j ，且公开y 巧59 啊( m o d p ) ( 3 ) p ，验证同余式 y 萨g 响三n 玑( m o d p ) k = 1 是否成立，若上面的两个同余式均成立，则p j 接受d 。发送的秘密信息 z 。且认为d ：是诚实的，否则不接受z i j 且向其他的参与者公开d 。的身 份。当p ，验证完所有分发者发送给他的秘密信息后，计算 s j = ( m o d 口) 引t b ) 作为p ，拥有的秘密份额，其中f ，= rl 对p ，诚实的分发者d ，) 被所有 参与者知道，相应的巧即为对p 不诚实的分发者的集合 ( 4 ) 定义要分享的秘密为 耻川暑 i 静t m k ，i 盎c m o a a ， 引p j n t )州2 f j ) l h n ，) 1 u j 1 “8 ( 5 ) 蹴明1 在假设每一个分发者对参与者诚实的概率都大于1 2 的条件下 p ( b 非空) = p ( 至少有一个分发者对马诚实) = 1 一p ( 所有分发者都对马不诚实) 1 一( 扣 当m 取到1 5 2 0 之间的整数时，“f ，非空”的概率接近于1 ，则认为 d 非空。若小概率事件“b 是空的”的确发生了，即没有分发者对p ， 诚实，这个时候我们认为p ，不是一个合法的参与者，被排除在参与者集 合之外，实际上只剩下( n 一1 ) 位参与者。 又因为 p ( 分发者d 。至少对一个参与者诚实) = 1 一p ( 分发者d 。对所有的参与者均不诚实) 1 一( ；) n 第三章本文提出的新方案 当n 取到1 0 0 左右的整数时，这一概率几乎为1 。若“分发者d 。对所有 的参与者均不诚实”这一小概率事件发生了，则取消该分发者，认为分 发者的集合只剩下( m 一1 ) 位成员。 所以在再，再，巧对所有参与者公开之后，系统根据以上说明 重新定位分发者和参与者的集合，重新定位后，我们不妨仍然假设d = d 1 ，d 2 ，d 。 ，p = p 1 ，p 2 、，p 。) 就确保了每一个集合d ：j = 1 ，2 ，n 是非空的。每一个分发者对至少一个参与者发送了正确的秘密 信息，每一个参与者至少收到一个分发者发送的秘密信息 ( 三) 秘密的恢复 假设】，是能恢复秘密k 。的合法子集，那么取出包含在】厂中的极小合法 子集n 。，由q 。中成员p ，向f 2 。中其他成员p 女发送自己的秘密份额勺以及 签名s g p ，( s j i l p ，l n 。) ，p k 验证p ，的签名且验证是否有 若同余式不成立，则产生对巧的抱怨，并要求其重新发送8 j ，直到通过验 证为止当所有成员都收到了n 。中其他成员诚实的秘密份额后，汇聚这些秘 密份额( ( i d ，：勺) i p ，n 。) ，根据拉格朗日插值公式，恢复秘密 耻捌群，州艘蚴盎c 酬“l p ，n t 】 叫j ，p k n t 1 j 3 1 2 新方案的性能分析与结论 1 本方案中只要分发者发送给参与者的秘密信息通过了参与者的验证，就会被 参与者采用，作为秘密份额生成的有效部分，这样一来对分发者的诚实性要 求降低，不同于21 中的方案，2 1 的方案中假设至少有一个分发者( 对所有 参与者) 是诚实的，秘密的恢复采用的是对所有参与者都诚实的分发者所发 送的秘密信息。 2 单个分发者以及合法子集中不诚实的分发者的联合均不知道最后的秘密。 因为要分享的秘密k 是由分发者如此联合生成的： 耻。妻。，( 。乏，) 、盏( m o 捌p j n t )冲巧) 川k j ，p k n 。) 8 1 2 d k 。n ! 蓍 三 旷 第三章本文提出的新方案 在秘密信息的分发和秘密份额的生成阶段之前，分发者并不知道要分享的秘 密k 。，因为他们不知道其他分发者的身份，更不知道其他分发者会对q ：中 哪些参与者诚实及诚实的分发者发送给此参与者的具体秘密信息。即使知道 了f ，j = 1 ，2 ，n ，也只能知道对q 。中成员诚实的分发者的身份，仍然不 知道这些诚实的分发者发送给q ：中参与者的具体秘密信息，也无法知道最终 每个参与者拥有的秘密份额。因而单个分发者并不知道最后的秘密，由拉格 朗日插值公式合法子集中不诚实的参与者联合也无法得到要分享的秘密。 以下分析以秘密k 。为例，假设f 2 。= f p l ，p 2 ，一，p 。扎p 。) ，对q 。中参 与者诚实的的分发者的集合为f d ，d z ，d 。乩d 。1 3 p 方安全性( 假设每一位参与者被收买的概率小于1 2 ) 假设攻击者最多收买n 。中 q 。卜1 个参与者，那么他得不到关于该秘密的任何 信息。不妨假设p ，p t ，p 。，被收买，攻击者掌握了( s 1 ，f ) ，( s 。，f 2 ) ， ( s 。一，f 。一1 ) 以及 z n i i f 1 ) ， z 。2 i i f 2 ) ， z 。一1j i f 。一1 ) 为了得至0 k 。，攻击击者需要从已知的信息中计算得到或直接猜测出s ，( =z 。) 引。n 现在不妨假设只有d 。对p 。诚实( 需要得到的信息最少的情况下) ，要想得 到s 。只需得到z 。而z 。= 厶( i d 。) ，从已知的信息是无法恢复多项式丘( z ) 因而无法计算得到z 只能随机猜测，猜测成功的概率为1 q 与直接猜测 k 。或s 。获得成功的概率是相同的。因此在假设攻击者最多收买q ：中i 晚i 一1 个参与者的条件下，攻击成功的概率至多为1 q 4 d 方安全性 假设攻击者最多收买了对n 。中成员诚实的n 位分发者中的。一1 位，那么他 得不到关于该秘密的任何信息。首先，攻击者并不知道分发者的身份，更不 知道对n 。中参与者诚实的分发者的身份，增加了攻击的难度其次， k = ( ) 引p j n ；) z l t f j )川凛蚴志( m o d q ) 如果攻击者最多收买了对n 。中成员诚实的n 位分发者中的n 一1 位，不妨 假设d 。未被收买，那么攻击者便得不到该分发者对参与者发送的秘密信息 z 。( 假设d 。只对p 。诚实，此时攻击者需要得到的信息最少) ，从而无法根据 上面的等式计算得到k 。，要想得到它，只能随机猜测z 。或k 。，获得成功 的概率都为1 q 。因此在假设攻击者最多收买了对哦中成员诚实的n 位分 发者中的n 一1 位的条件下攻击成功的概率至多为1 q 1 3 第三章本文提出的新方案 5 联合安全性 攻击者最多收买n 中l n j 1 个参与者，同时，最多收买对p ，诚实的的分 发者集合f 。中的l f 。l 一1 位分发者，即使这样，仍然无法得到关于该秘密的 任何信息。要得到k 。，只能是随机猜测，猜测成功的概率为1 q 。 可见，该方案达到了2 1 中方案所具有的安全性，但是本方案的假设条件降 低了，更贴近现实1 3 1 3 可能的攻击与相应措施 1 ) 合法子集中全部成员被收买。因此必须限定合法子集中成员数量，使全部成 员被收买的概率趋近于零。 2 ) 对合法子集中成员诚实的分发者全部被收买。因此必须有一定数量的诚实的 分发者，且使得对每一位参与者诚实的分发者尽可能得多。这样，对合法子 集中成员诚实的分发者全部被收买的概率就会趋近于零 基于以上两点， “攻击者收买了合法子集中部分成员，同时又收买了对合法 子集中剩余成员诚实的分发者”是一个小概率事件，认为此类攻击不可行1 3 2 基于离散对数的广义多重秘密分享方案 由于2 2 的方案中在秘密份额的分发阶段不可避免地存在分发者欺骗分享 者，以及在秘密的恢复阶段不可避免地存在分享者之间的欺骗，本节给出的新方 案避免了这两点漏洞。 3 2 1 新方案的描述 本节的方案分为四个阶段：系统参与者及主要参数，秘密份额的分发，秘密 凭证信息的生成以及秘密的恢复。其中前三个阶段由秘密分发者执行，第四阶段 由能够恢复秘密的合法子集完成。 ( 一) 系统参与者及主要参数 p 和q 为大素数且满足2 7 sp 曼2 8 0 0 ，q1 一1 ) ，q 21 ( p 一1 ) ：2 ”9sg 2 1 6 0 ，吼；丸：”1 ) 佃( m o 印) 为召中的q 阶生成元，其中为z 中的随机数 且 p “9 ( m o d p ) 1 ，i = o ，1 ，d 为秘密的分发者，n b 为公告板，用 来存储d 公布的公开参数。p = p l ，p z ，凡) 为秘密分享者集合，p 中 任一分享者p 。都具有惟一的身份标识符i d 。环，他们均可以读取公告板上 1 4 第三章本文提出的新方案 的信息，但只有d 能修改或更新n b 上的信息s = s 1 ，s 2 ，s k ) 为要分 享的秘密的集合；r 为秘密s ：的任一广义单调接入结构，r 0 为r 的基， 其中t = 1 ，2 ，七 ( 二) 秘密份额的分发 首先，d 选取z 上的任意一个n 次多项式，扛) = 口o + 0 1 z + 0 2 茁2 + + o 。z ”( m o d q ) ，计算v o = ( v o o ，v 0 1 ，v o 。) ，其中”= 9 ( m o d p ) ，j = 0 ，1 ：礼将v o 放入公告板n b 其次，d 为p 中任一分享煮p ，计算秘密份额q = ，( i d ，) 并将巧秘密 地发送给已，同时计算y 。，= 毋：i = 1 ：2 ，j = 1 ，2 ，：n 并将y 。j 公 开在公告板上。p ，可以验证是否有9 ；，；疗 ：警( m o d p ) 成立，若成立，则 认为z ，有效 ( 三) 秘密凭证信息的生成 对于s 。s ，v a r ? ：d 在召中随机选取r a ，并计算 r + qn 芒 t 。 = s 。一吼 p 忙忙列1 “ 。f m o 将 ( 乩，t 。一) i a r 0 ) 作为s 。的凭证信息放入公告板如果今后某时d 要 在s 中动态增加一个新的秘密信息s 则只需为s 。生成新的凭证信息 “乩，t 。一) i a r ：。) ：这一过程需要进行l r ：。1 次拉格朗日操作和j 1 1 ：。f 次模指数运算如果需要在r 0 中动态增加一个新的合法子集b ，则只需在s 。 的凭证信息中增加一( r b ，t m ) ，这个过程只需进行一次拉格朗日操作和一次 模指数运算这两种情况都不会影响其他合法子集对秘密信息的恢复! ( 四) 秘密的恢复 设x 是要恢复秘密s 。的合法子集，取出包含在x 中的极小合法子集 a ，由a 中成员b 计算关于s 。的恢复信息。= 9 i ( m o d p ) ，并将其发送给 以中其他成员，其他成员验证是否有y 。，；g ( m o d p ) 并计算 净。暴剧，i 6 恙( m o d q )( 酬k p 女a ) 1 一j 1 一” 当a 中成员都收到并验证了关于s 。的恢复信息之后，各自计算n z ， j b a ) “ 并从公告板上读取( r a ，t 。a ) ，最后计算s 。= t 。a +兀z 字9 ，( m o d p ) 例p j 这样秘密s 。便被恢复出来了。 1 5 第三章本文提出的新方案 3 2 2 新方案的性能分析与结论 ( ) 安全