（基础数学专业论文）基于图形随机路径的线性多密钥共享体制.pdf

中文摘要 摘要 本文首先介绍了单调张成方案和布朗函数，再介绍了存取结构和密钥共享体制 的概念而本文主要是要介绍多密钥共享体制的情形，多密钥共享体制是在参与成 员的集合p 中分享任意的仇个秘密，是单个密钥共享体制的扩张，有许多秘密被 分享，而每个秘密只有p 中被授权的子集才能恢复它，而非授权子集得不到这个秘 密的任何信息本文共定义了两类存取结构，类是基于图形连接的存取结构，另一 类是基于图形随机路径上的存取结构通过单调张成方案和实现存取结构的密钥共 享体制之间的对应关系，我们构造出相应的单调张成方案来实现前类存取结构 本文的重点是讨论后类存取结构，通过分析讨论，我们知道存在多密钥共享体制 来实现后类存取结构 关键词：张成方案；存取结构；秘密共享 英文摘要 a b s t r a c t i nt h i sa r t i c l ew ei n t r o d u c et h em o n o t o n es p a np r o g r a m sa n db u l lf u n c t i o n f i r s t l y t h e nw ei n t r o d u c ea c c e s ss t r u c t u r e sa n ds e c r e ts h a r i n gs c h e m e s o u r n m a i np o s i t i o ni st oi n t r o d u c em u l t i - s e c r e ts h a r i n gs c h e m e s m u l t i - s e c r e ts h a r i n g s c h e m e si st h a tp a r t i c i p a n t sps h a r ea r b i t r a r ym k e y sa n do n l yq u a l i f i e ds u b s e t s o fpa r ea b l et or e c o n s t r u c tt h es e c r e tv a l u e ，w h i l en o n q u a i i f i e ds u b s e t sc a nn o t o b t a i na n yi n f o r m a t i o na b o u tt h ev a l u eo ft h es e c r e t t h e nw ed e f i n et w oc l a s s e s o fa c c e s ss t r u c t u r e s o n ei st h a ta c c e s ss t r u c t u r e sb a s e do nc o n n e c t i v i t yo f 妒a p l 培。 o t h e ri st h a ta c c e s ss t r u c t u r eb a s e do nr a n d o mw a l k so ng r a p h s w ec o n s t r u c t m o n o t o n es p a np r o g r a m st or e a l i z ep r e v i e wa c c e s ss t r u c t u r ef r o mt h er e l a t i o n b e t w e e nm o n o t o n es p a np r o g r a m sa n ds e c r e ts h a r i n gs c h e m e s b u tt h i sp a p e r a n a l y z e sa c c e s ss t r u c t u r eb a s e do nr a n d o mw a l k so ng r a p h sm a i n l y a n dw e k n o wt h e r ee x i s t sm u l t i - s e c r e ts h a r i n gs c h e m e sr e a l i z i n gt h e s ec l a s s e so fa c c e s s s t r u c t u r e k e y w o r d s ：s p a np r o g r a m s ；a c c e s ss t r u c t u r e ；s e c r e ts h a r i n gs c h e m e s 厦门大学学位论文原刨性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研 究成果。本人在论文写作中参考的其它个人或集体的研究成 果，均在文中以明确方式标明。本人依法享有和承担由此论 文而产生的权利和责任。 声明人( 签名) ：奄施刚 印净舌月箩日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。 厦门大学有权保留并向国家主管部门或其指定机构送交论文 的纸质版和电子版，有权将学位论文用于非赢利目的的少量 复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘 要汇编出版。保密的学位论文在解密后适用本规定。 本学位论文属于 i 、保密() ，在年解密后适用本授权书。 2 、不保密() 。 ( 请在以上相应括号内打 ”) 作者签名童彘鼬 导师签名：导议 日期：2 。吵年舌月亨日 日期：年月 日 基于图形随机路径的线性多密钥共享体制 第- - 节引言 为了多毪生，个没计者有时需要籽个密钥分成一些碎片( 或称为子密钥) 秘 密地发送给若干个参与者，使之分开保护，当这些参与者之中的某些人出示他们所 拥有的碎片时，他们就有可能计算出密钥的值以恢复密钥这种保存密钥的方案称 为密钥共享体制密钥共享体制在安全保密和密码技术方面有着广泛的应用 密钥共享首先由著名密码学家s 蛐【1 】和b l a k l e y 2 提出他们提出种最 基本的秘密共享技术一( ，纷) 门限密钥共享方案，其基本思想是将秘密分割为n 个 份额，只要任何t 个( t 他) 份额即可还原原始的秘密，而任何少于t 个的份额则 无法获得任何原始秘密的信息后来在此基础上，人们又逐步提出了许多基于通用 存取结构的秘密共享方案这些方案中，仅有授权子集中的所有份额才可恢复原始 秘密，而所有非授权子集合中的份额均无法获取有关原始秘密的任何信息显然， ( t ，礼) 门限方案是通用存取结构的种特殊情况 因此密钥共享( s e c r e ts h a r i n g ) 是一种分发、保存、恢复秘密密钥( 或其他秘密 信息) 的方法：密钥管理者将秘密密钥拆分成一系列相互关联的秘密信息( 也称为子 密钥) ，然后将子密钥分发给某群体中的各个成员；使得某些小组( 授权集) 中的备成 员拿出他们的子密钥后，就可以利用既定的方法恢复该秘密密钥，而其他小组( 非授 权集) 则无法恢复该密钥所有的授权子集的集合叫做个存取结构 密钥共享也称为密钥分存、秘密共享或秘密分存在现实环境下的信息系统中 使用密钥共享，可以防止系统密钥的遗失、损坏和来自敌方的攻击，减小密钥持有 者( 个人或服务器) 的责任，同时还可以降低敌手破译密钥的成功率 多密钥共享体制是在参与成员的集合中分享任意的m 个秘密，是单个密钥共享 体制的扩张，有许多秘密被分享，而每个秘密又只有授权集才能恢复它，而非授权子 集得不到这个秘密的任何信息由于在现在生活中许多网络环境下的问题可以用图 基于图形随机路径的线性多密钥共享体常j 2 形来模拟解决，这使得我们研究图形随机路径上的多密钥共享体制在文献【3 】， 【4 】，【5 】，【6 】中的作品中研究了一些图形上特殊性质的密钥共享体制，但还很少 有作品研究到图形上的多密钥共享体制在这篇文章中，从基于图形随机路径上的 统计多方计算的思想，我们研究了图形随机路径上的多密钥共享体制因为图形上 不同的路径我们能够定义不同的存取结构，所以我们能够构造实现这些存取结构的 多密钥共享体制 在本文中安排如下：在第二节，我们回顾一些基本的概念，如单调张成方案f 7 】， 8 】，密钥共享体制【9 】及多密钥共享体制【a o ，【ii 】，【1 2 1 在第三节中，我们先 定义类基于图形连接的存取结构，然后构造单调张成方案知道有密钥共享体制来 实现这些存取结构 b e i m e l 1 3 】证明了关于存取结构的线性密钥共享体制( l s s s ) 和单调张成方案之间的等价性通过分析我们知道对于基于图形随机路径的存取结 构，同样可以由构造单调张成方案的方法知道有多密钥共享体制来实现这些存取结 构 基于图形随机路径的线性多密钥共享体幸i 3 第二节预备知识和基本概念 通篇文章中我们记k 是个有限域，p = p 1 ，r ) 是n 个用户的集合 记r ( r 2 尹) 是p 中子集组成的集合，如果r 内每个集合中的用户能够恢复密 钥，则r 称为存取结构，所以a r ，acb 兮b f 此时r 内的每个能够恢 复密钥的集合称为授权集合由最少的用户组成的授权集合记为r m 不能恢复密 钥的用户集合称为非授权集合，由非授权集合组成的集合记为( 2 p ) ，此时 有a a ，a ) b 令b a 由最多的用户组成的非授权集合记为m 显然有 rna = 0 如果r 和的并集等于2 p ，即r 等于的补集，我们就称这个存 取结构是完善的 2 1 单调张成方案 对任意的子集a ，a p ，我们记对应的特征向量为砍，以= ( 6 1 ，以) o ，1 ) 竹，使得当且仅当只a 时蠡= 1 ，1 i 他另方面，对任意的6 o ，1 ) n ，总会有懒a p ，使得“= 因为 o ，1 p 中的向量和p 中子集的对应关系，接下来我们记 o ，1 住中的向量为尹中某些子集的特征向量 k a r c h m e ra n dw i g d e r s o n 7 首先提出了单调张成方案，作为计算单调布朗函 数的线性) 溪型通常我们把单调张成方案( m s p ) 记为m ( k ，m ，妒，才) ，这 里m 是域k 上的个dx ：矩阵，x l ，z n ) 是标号集，映射砂： 1 ，d ) 一 z 1 ，z n ) 将矩阵m 的行用写1 ，z n 作上标记d 称为m s p 的规模 才称为目标向量如果目标向量为单位向量，则m s p 记为m ( k ，m ，矽) 对任何k 上矩阵m ，s p a n ( m ) 表示由矩阵m 的行向量生成的线性空间设_ y = ( y l ，y n ) o ，1 ) n ，定义m - g 为m 的部分行组成的矩阵，当且仅当犰= 1 时 标记为戤的行在m - g 中出现， 1 i n 基于图形随机路径的线性多密钥共享体制 4 我们知道布朗函数，； o ，l n _ o ，1 ) ，它满足单调性的意思是：对任意 的子集a p 和b a ，当“石) = 1 时总有“瓦) = l 成立我们说m s p m ( k ，m ，矽，才) 关于目标向量才尉( 0 ，0 ) 能计算单调布朗函数，如果它满 足。当且仅当f ( 五) = 1 时才s p a n ) 言s p a n ) 意味着存在叶 向量岔使得才= 玄坛b e i m e l 1 3 证明了关于存黼r 的线性密钥共享体 制( l s s s ) 和m s p 之间的等价性，此时m s p 是能计算单调布朗函数，的，并且 满足：当且仅当a r 时 f ( 酝) = 1 定义l ：f 8 】如果r i 和n 分别是定义在r 和兄上的存取结构，乃和 是两个不同的用户集合，那么我们可以定义在乃u 岛上的存取结构r 1 + f 2 和 f 1 n 若a 冬乃u 伤， a i 、l + n 铮an 只r 1 或an 伤f 2 ， a f 1 f 2 = 夸anr r 1 且an 死i 、2 推广定义t 如果r 1 ，r 2 ，r 分别定义在死，砀，r 上的存取结构， 乃，乃，r 是不同的用户集合那么可以定义在ru 岛u r 上的存蝴 r l + r 2 + + n 和f 1 r 2 r n 。若4 9ru 砘u u 及， a r l + r 2 + + r 错a nr r l 或anr n 或或anr l a r l r 2 f n 锚anr f 1 且an 砘r 2 且且anr f n 基于图形随机路径的线性多密钥共享体翻 5 2 2 密钥共享体制和多密钥共享体制 我们先来了解密钥共享体制和多密钥共享体制的基本概念现假设s 是密钥 空间，冗是随机输入值的集合，& 是用户b 密钥份额的分享空间，1 t n 定义2 ： 1 0 】关于存取结构r 的密钥共享体制是由分布函数n 和重构函数 觑组成： 分布函数1 - i ：s r _ & & ， 1 - i ( s ，r ) = ( 兀。( s ，r ) ，n n ( 3 ，r ) ) 重构函数r e ：对任意的集合a er ，r ei a ：( s l x & ) l a _ s ，并且满足以下 两个条件： 1 正确性 对任意的集合a f ，s s 和r r ，总有皿i a ( 1 - i ( s ，r ) l a ) = s 成立 2 安全性 对任意的集合b ，h ( sl ( s ，r ) i b ) 日( s ) ，这里日( ) 是熵函数如果 h ( si ( 只r ) i b ) = 日( s ) ，我们称这个密钥共享体制为个完善的密钥共享体制 而且，如果个完善的密钥共享体制是线性的( 简记为l s s s ) ，又需要满足以下两 个条依 3 假设密钥空间s = k ，密钥份额的分享空间& ( 1 t 佗) 和随机输入值 的集合r 是k 上的有限维线性子空间，那么，存在正整数d i ( 1 i 1 2 ) 和f 使得 最= k 武和r = k z 4 重构函数必须是线陛的也就是说，对任意的集合a f ，存在着_ 组常数 吼k 只a ，1 k 死) 使得对任意的8 k 和广r = k z ， 基于图形随机路径的线性多密钥共享体牵j 6 有s = 最a o l ki i k ( s ，7 ) 定义3 ：【1 1 】假设k 是个有限域，r l ，r 2 ，r m 是定义在p 上的存取结 构，密钥份额的分享空间& ( 1 i n ) 和随机输入值的集合兄是k 上的有限 维线性子空间，关于存取结构f 1 ，f 2 ，k 的线性多密钥共享体制由分布函数n 和重构函数组成，其中分布函数为 1 - i ：k mxr _ s x x & ， 1 - i ( s 1 ，s m ，r ) = ( 兀。( s 1 ，s m ，r ) ，i f n ( s 1 ，s m ，r ) ) 此时需要满足以下两个条件； ( 1 ) 重构函数必须是线性的，也就是说，对任意的a ef i ，l ism ，存在组常数 q l kl1 k n ，p k a ) ，使得 s i = p h aq i k ( s 1 ，s m ，r ) = r aq ：后( s 1 ，s m ，l l ，n ) ， 这里t - - - ( 7 1 ，n ) ，r t ( 1 ， 岛，p 4 1 ， 忍，r ) ， b ，p 2 ，p d ， 马，p 3 ，r ) ， 恳，p 4 ，p d ， p l ，p 4 ，b ) ) 对于图形上任意的两个顶点让和，0 i ， ( r 如睨) m = ( r ) ， p a ，只) ， p 1 ，马) ， p l ，p 3 ，p 5 ) ， p 2 ，p 4 ，p 5 ) ) ， ( r 如珊) m = ( 只) ， b ，屁) ， b ，r ， p 1 ，p 2 ，尼) ， 岛，忍，r ) ) 3 2 实现存取结构的密钥共享体制 首先我们令密钥空间s = k = f 2 对于更大的密钥空间，我们可以放大到 f 2 t 匕来考虑，其中k 为正整数显然s = k = f 2 时密钥共享体制的正确性和 安全性仍然是满足的我们记顶点让为向量寄= ( o ，o ，1 ，o ，o ) ( 第i 个位置匕 的分量为1 ) e 曰，其中0 i m 一1 ，并且寄= 0 对于1 i 佗，如果 ，( 只) 之让。优：，我f f 伶向量宿= 磊+ 赢，其中0 t l i 2 m 一1 基于图形随机路径的线性多密钥共享体制 9 例3 ( 续例1 ) 记顶点伽为( 0 , 0 ，o ) ，顶点t ，1 为( 1 , 0 ，o ) ，顶点v 2 为( 0 , 1 ，o ) ，顶 点钝为( o ，o ，1 ) 那么宿= ( 1 ，0 ，o ) ，r p 2 、- - ( 1 ，1 ，o ) ，r p 3 = ( 0 , 1 ，1 ) ，r _ p 4 = ( 0 , 0 ，1 ) ，试= ( 1 , 0 ，1 ) ，赢= ( 0 ，1 ，o ) 构造个单调张成方案m s pm ( 易，m ，砂) 如下：m 由行向量东组成，l i 视，并且砂将行向量宿映射到用户只显然，m 是个在岛上的礼 ( m 一1 ) 矩阵而且m ( 玛，m ，妒) 关于目标向量亩能够计算布朗函数舟叼粕，其 中l i ，1si m 一1 也就是证明顶点v o 和顶点仇在子图形g ( ve i a ) 匕是连接的首先，如 果a r 如眦，那么在g w , e t ) 上存在_ 条从顶点v o 到仇的路径，记为耽。一娥。 一讧k ，其中饥。= v o ，v i = 且0 i i ，如m 一1 由i - i ( 仇j 忱仆1 ) = 只j ，0 歹k 一1 ，有只，a 且司= 玄+ 东因此哥= 赢+ = 基于图形随机路径的线性多密钥共享体制1 0 ( 磊+ 磊) + ( 赢+ 兹) + + ( 宏+ 甚) = 芪+ 磊+ + 厄= ，也就是说， _ e i 踟礼 吆) 另方面，如果一e i s p n n 吻) 不失般性，假设哥2 瓦 + 历专+ + 历：，其中0 i o ，旗一l m 一1 且只j a ，0 歹k 一1 记，( 只，) = v h j ，那么 一e l = ( 东- 4 - e t o ) + + ( 历= + 瓦= ) ， ( 1 ) 其中葡，e t j e 寄，亩，e r a - l ，0 歹七一1 因为苟，石磊是线性无关 的，蕾和昂分别在( 1 ) 式的右边出现奇数次，而对于j i ，0 歹m 一1 ， 寄则出现偶数次因而( 1 ) 式确定了条从到v i 的路径所以a r 如佻 例4 ( 续例3 ) 由e 所述， m = 1 0 l1 01 0 0 l o 01 易验证朋( 局，m ，砂) 关于耳标向量_ e i 能够计算布朗函数歹粕，其中1 i m 一1 我们来验证m ( 而，m ，妒) 关于目标向量才能够黼朗函数，r 掣。，不 防在r k v 。中取个用户子集a = 忍，r ) ，此时 = 10 ) 显然存在个向量亩= ( 1 ，1 ) 使得贯= 葡，因此有一e lq s p a n m 不 o o 1 1 1 0 基于图形随枫路径的线性多密钥共享体制 l l 由于实现存取结构的线性密钥共享体制( l s s s ) 和m s p 之间的等价性，我们知道 此时存在密钥共享体制来实现r 如”选取s 是主密钥，a ，b 是k 上随机输入的 值，令茹= ( s ，a ，b ) ，计算计算m 蠡7 ，得到的是( 8 ，8 + a ，a + b ，b ，8 + b ，口) 7 ， 分别是用户只，岛，恳，只，恳，r 分享到的份额，显然p 1 能够直接恢复密钥，马和 r 起能够恢复密钥，r 和r 起能够恢复密钥，岛、b 和r 起能够恢 复密钥，恳、r 和r 在起能够恢复密钥，这与我们在例2 中给出的( r 如。) m 授权集合相对应 3 3 基于图形随机路径上的线性多密钥共享体制 引理；【1 2 】若r l ，如，r m 是p 上的存取结构，f r ，舟：，丸是与之相 对应的单调布朗函数，如果在域k 上有计算布朗函数，r 。，舟：，厅。的单调张成方 案，那么存在实现这些存取结构r l ，r 2 ，r i m 的线性多密钥共享体制 证明；不失般性，令向量苟= ( 1 ，0 ，0 ) ，弓= ( o ，o ，1 ，o ，o ) ( 第i 个 位置匕的分量为1 ) ，赢= ( o ，o ，1 ，u ，0 一，0 ) 是m + l 维的向量，1 冬i m ， 假设朋是关于向量有，赢计算舟。，舟：，舟。的单调张成方案m 是公开 的矩阵，选择主密钥向量( s 6 ，s 孑) k m ，随机输入的向量( 7 0 1 ，r 0 1 ) k 2 令 珈 5 0 1 ，s 孑，r o l ，m ) ，计算m ，蠡丁，将必；蠡丁作为用户只的子密钥，其 中 心。是m 中标记为x i 的那些行向量组成的，1 i 礼现在我们只验证下 这个体制的正确性，它的安全性证明可在文献f 1 2 】中找到 正确性：同样不失般性，假设g f 1n f 2 n f k ，那么一e i s p a n ( m 宏) ，1 i k ，不妨设喙是有t 个行向量组成，那么亩= ( 玩，k ) 所以磊= 寄舻= ( ( b i l ，6 i t ) 锄) 蠡丁= ( 阢1 ，玩t ) ( 镑蠡丁) 基于图形随机路径的线性多密钥共享体制 1 2 为简单起见。我们说单调张成方案计算布朗函数直接说成是计算与之对应的存 取结构 引理2 ；【8 1 令r x 和f 2 分别是定义在用户集7 1 和伤上的存取结构，与之对 应的矩阵令矩阵m l = ( u l m ( 1 ) 和m 2 = ( u 2 m ( 2 ) ) ，其中u l ，乱2 分别是m i 和m 2 m = 叫 能计算存取结构r 1 十r 2 并且m 是个( 仇l + m 2 ) ( d 1 + d 2 1 ) 矩阵 下面我们证明这个单调张成方案是能够计算r 1 + r 2 的令r = 1 1 + r 2 且 a = r c ，f c 为r 的补集相应地1 = f i c 且2 = r 2 c 我们有 b 镑bnr 1 且bn 伤a 2 如果bnr a x 且bn 伤2 ，那么捌向量( 1 ，蠡) k d l 和 ( 1 ，最) k a 2 使得m 圳0 ) a ( 1 ，友) = 0 ，m 鼎仡( 1 ，最) = 0 构造列向量( 1 ，k ) = ( 1 ，立，正) k ( d - + d 2 1 1 由b = ( bn7 1 ) u ( bn 伤) 很容易，蚍m b ( 1 ，k ) = 0 ， 因此b a 另方面，如果b a ，那么存在列向量( 1 ，k ) k ( d ，+ 屯1 ) 使得m b ( 1 ，k ) = 0 又记( 1 ，k ) = ( 1 ，良，k 。) ，其中立k ( d ，一、盂k ( 如一1 ) 且良，最都是列向量 基于图形随祝路径的线性多密钥共享体制 1 3 同样很容易验证m 斟r ( 1 ，文) = 0 和肜鼎伤( 1 ，莨) = 0 因此我们有b nr l 且bn 乃a 2 所以m 黻博r 定理1 ：如果r l ，r 2 都是定义在用户集p 上且基于图形随机路径上的存取结 构，那么存在能实现这两个存取结构的线性多密钥共享体制 证明s 由引理2 我们知道，存在单调张成方案a 4 能计算r l + f 2 ，则存在密 钥共享钵制实现存取结构r l + r 2 由于r ：，n 都是定义在用户集p 上的存取结 构，对任意的acp ，a r 1 + r 2 等价于a r l 或a r 2 ，自然地m 能够分 别计算r l 和岛由上述引理l 我们知道，如果单调张成方案4 4 能够计算r l 和 r 2 ，那么存在能实现这两个存取结构的线性多密钥共享体制 定理2 ：如果r 1 ，r r 是分别定义在用户集r ，辟上的存取 结构，与之对应的单调张成方案分别是规模为m l 的m l ，规模为m r 的 朋r 那么存在规模为m 1 + m 2 + + m r 的单调张成方案m 能够计算存取结构 r 1 + r 2 + + 1 1 ， 证明；假设舰，尬，。坼是单调张成_ 噤m 1 。m 2 ，m ，对 应的矩阵，m 是州对应的矩阵令尬= ( u 1 ，硝1 ) ，= ( 乱2 ，磁1 ) ， m r = ( t t r ，a 舔 ) ，其中铭l ，分别是矩阵的第列那么单调张成方案 m = 牡l 叫1 0 u 2 0 趔1 ) 仳，0 0 0 0 膨1 ) 能计算r 1 + r 2 + + r r 并且m 鬼m ( 7 y t l + m 2 + + m r ) ( d 1 + d 2 + + 基于图形随机路径的线性多密钥共享体制 1 4 d r r + 1 ) 矩阵 推论：如果i 、1 ，r r 都是定义在用户集p 匕目基于图形随机路径上的存取结 构，那么存在能实现这些存取结构的线性多密钥共享体制 证明；由定理2 ，有单调张成方案朋能计算r 1 + r 2 + + r r ，又前述的推 广定义我们知道，若a c _ p ， a f 1 + f 2 + + f r = 争a f 1 或a r 2 或或a f ， 自然地m 能够分别计算r l ，r r 由引理1 ，如果单调张成方案m 能够计算 r 1 ，r r ，那么存在能实现这些存取结构的线性多密钥共享体制 基于图形随祝路径的线性多密钥共享体翻 1 5 在本文中，我们首次将图形的随机路径和线性多密钥共享体制结合起来，证明 了确实存在线性多密钥共享体制可以实现基于图形随机路径的存取结构随着信息 网络越来越复杂化，我们可以把复杂的事情用图形来简单化由于我们在图形上对 不同的路径可以定义不同的存取结构，这样我们能够构造实现这些存取结构的多密 钥共享体制，效率比单个的密钥共享体制大大提高了事实上，我们还可以把图形 的顶点作为用户来考虑_ 竖问题，已经有人把它和门限密钥联系起来，其实可以类 似来研究些多密钥的问题 参考文献 参考文献 【1 】a s h a m i r ，h o wt os h a r eas e c r e t ，c o m n a c m 2 2 ( 1 9 7 9 ) ，6 1 2 6 1 3 【2 jb l a c l d e ygr ，s a f e g u a x d i n gc r y p t o g r a p h i ck e y s p r o eo ft h e1 9 7 9a f i p sn a t i o n a lc o r n - p u r e rc o n f e r e n c e ，1 9 7 9 ，4 8 ：3 1 33 1 7 1 6 【3 1 m u s t a f aa tc ，i n f o m a t i o na n da v e r a g ei n f o r m a t i o nr a t e so fag r a p h i c a l 幽。e 鹄s t r u c t u r eo n s i xv e r t i c e s ，t u r kje l e ce n g i n ，v 0 1 8 ，n o 12 0 0 0 【4 】k a m i lk u l e s z a ，z b i g n i e wk o t u l s k i ，o ns e c r e ts h a r i n gf o rg r a p h s ，c r 0 3 1 0 0 5 2 f 5 jl a s z l oc s i r m a z 7s e c r e ts h a r i n gs c h e m e so i lg r a p h s ，2 0 0 5 。 【6 】l i a n g l i a n gx i a o ，m u l a nl i u ，z h i f a n gz h a n g ，m u l t i p a r t yc o m p u t a t i o nb a s e do nc o n n e c - t i v i t yo fg r a p h s ，2 0 0 5 f 7 】m k a r c h m e r ，a w i g d e r s o n ，o ns p a np r o g r a m s ，p r o c 8 - t ha n n u a ls t r u c t u r ei nc o m p l e x - i t yt h e r o yc o n f e r e n c e ，s a nd i e g o ，c a l i f o r n i a ，1 8 - 2 1m a y1 9 9 3 ，i e e ec o m p u t e rs o c i e t y p r e s s ，p p 1 0 2 1 1 1 【8 】v n i k o v ，8 n i k o v a ，n e wm o n o t o n es p a np r o g r a mf r o mo l d c r y r t o l o g ye p r i n t a r c h i v e ：r e p o r t2 0 0 4 2 8 2 【9 】g j s i m m o n s h o wt o ( r e a l l y ) s h a r eas e c r e t i ns g o l d w a s s e r ，e d i t o r ，a d v a n c e si n c r y p t