基于属性的加密体制研究与实现-计算机应用硕士论文

分类号：T P 3 0 9 密级： 单位代码：1 0 4 2 2 学号：2 0 1 0 1 2 9 7 6 硕士学位论文 论文题目：基于属性的加密体制研究与实现 R E S E A R C HA N DlM P L E B E N T A T10 N0 N A T T RIB L r r EB A S E DE N C R Y P Tl0 N 作者姓名余敏达 学院 专业 指导 合作 名称 名称 教师 导师 计算机科学与技术学院 计算机应用技术 徐秋亮教授 2 0 13 年4 月5 日 山东大学硕士学位论文 目录 摘要I A B S T R A C T 第1 章绪论1 1 1 引言1 1 2 研究现状2 1 3 本文的工作3 1 4 本文的组织3 第2 章基础知识4 2 1 双线性映射4 2 1 1 判定性B D H 假设4 2 1 2 判定性q - B D H E 假设4 2 2 秘密共享5 2 2 1 访问结构的定义5 2 2 2 门限秘密共享方案一6 2 2 3 线性秘密共享方案7 2 2 4 访问结构的表示方法7 第3 章经典A B E 方案介绍1 0 3 1G P S W 的K P A B E 方案1 0 3 1 1 安全模型1 0 3 1 2 方案构造1 1 3 1 3 安全性证明1 3 3 2W a t e r s 的C P A B E 方案1 5 3 2 1 安全模型15 3 2 2 方案构造1 6 3 2 3 安全性证明1 7 3 3 讨 仑1 9 3 3 1 策略类型1 9 i 山东大学硕士学位论文 3 3 2 访问结构2 0 3 3 3 方案开销2 1 第4 章A B E 方案的构造2 2 4 1 一种简单有效的C P A B E 方案2 2 4 1 1 方案构造2 2 4 1 2 安全性证明2 3 4 1 3 讨论。2 4 4 2K P A B E 与C P A B E 的相互转换2 5 4 2 1 修改G P S W 的K P A B E 为C P A B E 方案2 5 4 2 2 修改W a t e r s 的C P A B E 为K P A B E 方案2 6 4 2 3j 时j 沧2 7 第5 章A B E 方案的实现2 9 5 1 数值属性整数比较的实现2 9 5 1 1 访问树的数值属性整数比较2 9 5 1 2L S S S 访问结构的数值属性整数比较3 5 5 2 基于对的密码程序库3 8 5 3 本文A B E 方案的性能测量3 9 5 4A B E 工具包介绍4 2 第6 章总结与展望4 5 参考文献一4 6 致谢一4 9 攻读学位期间发表的学术论文5 0 山东大学硕士学位论文 T A B L EO F C O N T E N T S A b s t r a c ti nC h i n e s e I A b s t r a c ti nE n g l i sh I I C h a p t e r1 I n t r o d u c t i o n 1 1 。1B a c k g r o u n d 1 1 2R e l a t e dW O r k 2 1 3R e s e a r c hc o n t e n t s ，3 1 4T h e s i sS t r u c t u r e 3 C h a p t e r2 P r e l i m i n a r i e s 4 2 1B i l i n e a rM a p s 4 2 1 1D e c i s i o n a lB i l i n e a rD i 衔e H e l l m a nA s s u m p t i o n 4 2 1 2D e c i s i o n a lq - P a r a l l e lB i l i n e a rD i 伍e - H e l l m a nE x p o n e n tA s s u m p t i o n 4 2 2S e c r e ts h a r i n g 5 2 2 1D e f r u i t i o no f a c c e s ss t r u c t u r e 5 2 2 2T h r e s h o l dS e c r e t S h a r i n gS c h e r m s 6 2 2 3L i n e a rS e c r e t S h a r i n gS c h e m e s 7 2 2 4E x p r e s s i o no f a c c e s ss t r u c t u r e 7 C h a p t e r 3 C l a s s i cs c h e m e so f A B E 1 0 3 1G P S W SK P A B ES C h e m e 1 0 3 1 1S e c u r i t ym o d e l 1 0 3 1 2C o m t r u c t i o n 1 1 ：；1 3S e c u r i t yp r o o f 1 3 3 2W a t e r s SC P A B ES C h e m e 1 5 3 2 1S e c u r i t ym o d e l 1 5 3 2 2C o m t r u c t i o n 1 6 3 2 3S e c u r i t yp r o o f 1 7 ：；：；D i s c u s s i o n 1 9 3 3 1P o l i c y 一1 9 诵 L f 东大学硕士学位论文 3 3 2A c c e s ss t r u c t u r e 2 0 3 3 3O v e r h e a d 2 1 C h a p t e r4 O u rc o n s t r u e t i o m 2 2 4 1A S i m p l ea n dE f f e c t i v eS c h e m eo f C P A B E 2 2 4 1 1C o n s t r u c t i o n 。2 2 4 1 2S e c u r i t yp r o o f 2 3 4 1 3D i s c u s s i o n 。2 4 4 2T r a n s f o r m a t i o nb e t w e e nK P A B Ea n dC P A B E 2 5 4 2 1C o n v e r tG P S W sK P A B Et oC P A B E 。2 5 4 2 2C o n v e r tW r a t e r s sC P A B Et oK P A B E 2 6 4 ：! 3D i s c u s s i o n 2 7 C h a p t e r5 O u ri m p l e m e n t a t i o n 2 9 5 1I n t e g e rc o m p a r i s o no f n u m e r i c a la t t r 而u t e s 2 9 5 1 1A c c e s st r e ei m p l e m e n t i n gt h ei n t e g e rc o m p a r i s o n 2 9 5 1 2L S S Sa c c e s ss t r u c t u r ei m p l e m e n t i n gt h ei n t e g e rc o m p a r i s o n 3 5 1 ；2P a i r i n g - B a s e dC r y p t o g r a p h yL i b r a r y ：3 8 5 3P e r f o r m a n c em e a s u r e m e n t s 3 9 5 4T h eA B Et o o l k i t 4 2 C h a p t e r6 C o n c l u s i o na n df u t u r ew o r k 4 5 R e f e r e n c e s 4 6 A c k n o w l e d g e m e n t s 4 9 P a p e rP u l i sh e df o r t h em a s t e r sd e g r e e 5 0 山东大学硕士学位论文 摘要 随着互联网的高速发展与不断普及，越来越多的敏感信息在互联网第三方 站点上存储与共享，例如云存储和云共享。通常情况下，这些敏感信息并不是 以加密的形式进行存储，对敏感信息的访问控制是由服务器完成的。如果服务 器不可信或者遭受黑客入侵，敏感信息将面I 临泄露的危险，因此在共享之前对 敏感信息进行加密是必要的。 基于属性的加密( A B E ) 就是针对这类问题提出的。A B E 是一种一对多的 加密模式，能够对加密后的信息进行细粒度的访问控制。A B E 有两大基本类型， 密钥策略A B E ( K P A B E ) 和密文策略A B E ( C P A B E ) 。K P A B E 中，密文与 属性集合关联，私钥与访问结构关联；C P A B E 中，密文与访问结构关联，私 钥与属性集合关联。两种策略的A B E ，当且仅当属性集合满足访问结构时，才 能正确解密。 本文研究的主要内容是A B E 方案的构造与实现。我们以两个经典的A B E 方案为例，对K P A B E 和C P A B E 进行了比较，分析了访问树和线性秘密共享 方案( L s S S ) 访问结构，讨论了A B E 方案的空间和时间开销。通过修改现有 方案，提出了一种标准模型下可证明安全的C P A B E 方案，新方案比原方案在 空间和时间开销上有所改进。讨论了K P A B E 和C P A B E 之间的相互转换，并 分别构造了一个具体的方案。讨论了数值属性和整数比较在访问树和L S S S 访 问结构中的实现，设计了访问树中实现数值属性整数比较的算法，对现有的一 个L S S S 访问结构算法做了扩展，新算法增加了数值属性整数比较功能。利用 基于对的密码程序库对本文提出的C P A B E 方案进行了性能测量，并和其他 C P A B E 方案做了比较。此外，我们还实现了一个可扩展的图形用户界面A B E 工具包。 关键词：属性加密；访问控制；秘密共享 山东大学硕士学位论文 A B S T R A C T W i t ht h er a p i dd e v e l o p m e n ta n ds t e a d yp o p u l a r i z a t i o no f t h eI n t e r n e t , m o r ea n d n 1 0 r es e n s i t i v ed a t ai ss t o r e da n ds h a r e do nt h et h i r dw e b s i t e s ，s u c ha st h ec b u d s t o r a g ea n dc l o u ds h a r i n gT h es e n s i t i v ed a t ai su s u a l l yn o te n c r y p t e da n ds t o r e di n t h es e r v e rw h i l et h ea c c e s sc o n t r o li sd o n eb yt h es e r v e r I ft h es e r v e ri su n t r u s t e do r t h es e r v e ri sa t t a c k e db yah a c k e r , t h e nt h es e n s i t i v e d a t ai sa tt h er i s ko f c o m p r o m i s i n g S oi t sq u i t en e c e s s a r ys t o r et h ee n c r y p t e dd a t ab e f o r es h a r i n gi t i n c o n s i d e r a t i o no fs e c u r i t y T h eA t t r i b u t e B a s e dE n c r y p t i o n ( A B E ) i sp r e s e n t e dt os o l v et h i s i s s u e A B E e n a b l e sa na c c e s sc o n t r o lm e c h a n i s mo v e re n c r y p t e dd a t au s i n ga c c e s ss t r u c t u r e s a n da s c r i b e da t t r i b u t e sa m o n gp r i v a t ek e y sa n dc i p h e r t e x t s A B Ec o n i e si nt w o f l a v o r sc a l i e dK e y - P o l i c yA B E ( K P A B E ) a n dCi p h e r t e x t - P o l i c yA B E ( C P - A B E ) I n K P A B E , c i p h e r t e x t sa r ea s s o c i a t e dw i t hs e t so fa t t r i b u t e s a n dp r i v a t ek e y sa r e a s s o c i a t e dw i t ha c c e s ss t r u c t u r e st h a tc o n t r o lw h i c hc i p h e r t e x t sau s e r i sa b l et o d e c r y p t I nC P A B E , t h e r o l e so f s e t so f a t t r i b u t e sa n da c c e s ss t r u c t u r e sa r es w a p p e d f i o mK P A B E T h i sp a p e rc a r r i e so u td e e pr e s e a r c hi nt h ec o n s t r u c t i o na n di m p l e m e n t a t i o no f A B E T a k i n gt w oc l a s s i cA B Es c h e m e sa se x a m p l e s ，w ec o m p a r eK P - A B Ew i t h C P A B E , a n a l y z ea c c e s st r e ea n dL S S Sa c c e s ss t r u c t u r e ，a n dd i s c u s st h es p a c ea n d t i m ec o s to fA B Es c h e m e s As i m p l e ra n dm o r ee f f e c t i v eC P A B Es c h e m eb y m o d i f y i n ga ne x i s t i n gs c h e m ei sp r e s e n t e d O u rn e ws c h e m ec o s t sl e s ss p a c ea n d t i m et h a nt h eo r i g i n a ls c h e m e ，a n dc a nb ep r o v e ds e c u r ei nt h es t a n d a r dm o d e LW e d i s c u s sh o wt oc o n v e r tb e t w e e nK P A B Ea n dC P A B E ，a n dc o n s t r u c tas p e c i f i c e x a m p l es c h e m er e s p e c t i v e l y A na l g o r i t h mi sd e s i g n e d t Oi m p l e m e n tt h ei n t eg e r c o m p a r i s o no fn u m e r i c a la t t r i b u t e f o ra c c e s st r e e ，a n da ne x i s t i n gL S S Sa c c e s s s t r u c t u r ea l g o r i t h mi se x p a n d e d t o s u p p o r t n u m e r i c a la t t r 而u t e sa n di n t e g e r c o m p a r i s o n s T h ep e r f o r r m n c ee v a l u a t i o n o fo u rC P - A B Es c h e m ei sd o n eb y P a i r i n g - B a s e dC r y p t o g r a p h yL 击r a r ya n da l s o t h ec o m p a r i s o nw i t ho t h e rC P - A B E I I 山东大学硕士学位论文 s c h e m e si sm a d e I na d d i t i o n , w em a k ea ne x t e n s i b l eA B Et o o l k i tw i t hg r a p h i c a l u s e ri n t e r f a c e K e yW o r d s ：A t t r i b u t e - B a s e dE n c r y p t i o n ；A c c e s sC o n t r o l ；S e c r e tS h a r i n g I I I 山东大学硕士学位论文 山东大学硕士学位论文 1 1 引言 第1 章绪论 传统的加密技术在加密消息后，通常都会有一个或多个明确的接收解密者。 但在实际中往往存在这样的情况：人们并不关心具体的接收者有哪些，而是希望 某些满足条件或者符合策略的接收者能够解密加密后的消息。这里包含了两个关 键的问题，即一对多通信和灵活的访问控制。显然，传统的加密体制不能很好地 同时解决这两个问题。公钥基础设施( P u b l i cK e yI n f r a s t r u c t u r e ，P K I ) 技术既无 法实现有效的一对多通信，也不能灵活地进行访问控制。发布者需要事先获得每 一名接收者的公钥证书，然后分别对敏感信息进行加密、传输和存储，每个环节 的开销与接收者的数量都是线性关系。广播加密技术虽然能够实现有效的一对多 通信，但是发布者通常需要事先指定具体的接收者集合，访问控制缺乏灵活性。 如果接收者集合过于庞大，获取大量接收者的身份信息会产生不菲的开销，同时 这些身份信息也可能存在被泄露的问题，因此广播加密技术也是不可行的。 基于属性的加密( A t t r i b u t e B a s e dE n c r y p t i o r t , A B E ) 能够很好解决上述两个 问题。A B E 可以看作是基于身份的加密( I d e n t i t y - B a s e dE n c r y p t i o n , I B E ) 的扩展 与延伸。I B E 用一个唯一的描述性字符串表示用户的身份，如 r n d y u m a i l s d t t e d u c n ，而A B E 用一组描述性的属性字符串表示用户的身份，如 ( 山东大学，信息安全实验室，学生) 。A B E 是一种一对多的加密模式，能够对 加密后的信息进行细粒度的访问控制。它用一个属性集合或访问结构对信息进行 加密，可以被多个访问结构或属性集合解密，当且仅当属性集合满足访问结构。 例如，用户的身份用一组属性集合( 计算机学院，学生，硕士) 描述，信息用访 问结构 老师O R ( 学生A N D 博士) ) 进行加密，当且仅当属性集合满足访 问结构，能够正确解密，而不需要关心具体有哪些老师或博士生。 A B E 具有广泛的应用前景，例如云共享、付费电视等等，是近些年来密码学 的研究热点之一。 山东大学硕士学位论文 1 2 研究现状 S a h a i 和W a t e r s 1 在2 0 0 5 年提出了A B E 的概念并构造了具体方案。方案采 用门限访问结构，接收者能够解密发布者加密的消息，当且仅当两者相同的属性 个数大于或等于系统设置的门限值。方案可以应用于生物密码学等领域，例如指 纹，每次采集的时候都会有细微的差别，门限值可以理解为生物特征的容错参数， 如果两次采集相同的部分大于或等于容错参数，则可以认为是同一个人的指纹 G o y a l 2 等在2 0 0 6 年提出了密钥策略基于属性的加密( K e y - P o l i c yA B E ， K P A B E ) 并构造了具体方案。方案采用访问树表示访问结构，能够表示属性之 间的“与”、“或”和“门限”三种关系。密钥策略是指私钥与访问结构关联，密 文与属性集合关联，即用属性集合加密，用访问结构解密。K P - A B E 可以应用于 审计日志，付费电视等。 B e t h e n c o u r t 3 等在2 0 0 7 年提出了密文策略基于属性的加密 ( C i p h e r t e x t - P o l i c yA B E C P A B E ) 并构造了具体方案。密文策略是指私钥与属 性集合关联，密文与访问结构关联，即用访问结构加密，用属性集合解密。C P A B E 可以应用于云共享，安全邮件列表等。 O s t r o v s k y 4 等在2 0 0 7 年提出了非单调访问结构A B E 方案。方案利用线性秘 密共享方案( L i n e a rS e c r e tS h a r i n gS c h e m e s ，L S S S ) 构造非单调访问结构，除了 能够表示属性之间的“与”、“或”和“门限”三种关系外，还可以表示“非”关 系。该方案可以应用于同行审核评估，用户无法查看自己的评估信息，但是可以 查看其他用户的评估信息。 C h a s e 5 在2 0 0 7 年提出了多权威中心A B E 方案。系统中存在一个中心权威 和多个相互独立的属性权威，中心权威为属性权威颁发密钥，属性权威为各自属 性域内的属性颁发密钥。用户的属性集合分属若干个属性域，监管这些属性域的 属性权威负责为该用户颁发密钥。该方案中，多个属性权威可以看作是多个独立 运行的A B E 方案。 A t t r a p a d u n g 6 等在2 0 0 9 年提出了双策略A B E 方案。双策略可以看作是密钥 策略和密文策略的结合，用户私钥与一个访问结构和一个属性集合关联，密文与 一个访问结构和一个属性集合关联。用户能够解密，当且仅当私钥的属性集合满 足密文的访问结构，密文的属性集合满足私钥的访问结构。 山东大学硕士学位论文 G r e e n 7 等在2 0 11 年提出了外包密文解密A B E 的概念并构造了具体方案。 外包密文解密可以看作是在原有A B E 方案的基础上添加外包解密功能。主要思 想为：取一个随机数Z 作为新方案的私钥，对原方案的私钥做1 z 指数运算，结 果作为新方案的转换密钥。新方案增加了一个转换算法，首先用转换密钥对密文 进行第一步解密。然后用z 对第一步解密结果做指数运算，最后计算得到明文消 息。例如，A B E 密文存储在云服务器上，受权用户向云提供一个单向的转换密 钥，云对A B E 密文做第一步解密。受权用户从云端接收转换后的密文，再用私 钥还原出明文。外包密文解密能够减少用户存储密文和解密操作的开销。第一步 解密主要是对运算，时间开销较大，可以外包给代理完成，同时将密文尺寸变小。 第二步解密是指数运算，开销小，由用户完成。K P A B E 和C P A B E 均可以添加 外包密文解密功能。 1 3 本文的工作 本文对K P A B E 和C P A B E 做了比较，分析了访问树和L S S S 访问结构，讨 论了A B E 方案的空间和时间开销。通过修改现有方案，提出了一种标准模型下 可证明安全的C P A B E 方案，新方案比原方案在空间和时间开销上有所改进。讨 论了K P A B E 和C P A B E 之间的相互转换，分别给出了一个具体的转换构造。 讨论了数值属性整数比较在访问树和L S S S 访问结构中的实现，设计了访问树中 实现数值属性整数比较的算法，对现有的一个L S S S 访问结构算法做了扩展，新 算法增加了数值属性整数比较功能。对本文提出的C P A B E 方案进行了性能测量 并和其他C P A B E 方案做了比较。此外，实现了一个可扩展的图形用户界面A B E 工具包。 1 4 本文的组织 第1 章介绍了A B E 的研究背景和研究现状。第2 章介绍了A B E 的相关基础 知识。第3 章介绍了两个经典的A B E 方案。第4 章介绍了我们修改后的三个A B E 方案。第5 章讨论了A B E 方案的实现方法，给出了本文C P A B E 方案的性能测 试结果，介绍了本文实现的A B E 工具包。第6 章对本文工作做了总结和展望。 山东大学硕士学位论文 2 1 双线性映射 第2 章基础知识 设G ，和G 。是两个乘法循环群，它们的阶均为素数p 。设夕为G ，的生成元， e ：G 。G ，_ G 。表示双线性映射，如果e 满足下面三个条件： 双线性：任取锃，秽G ，和口，b z 。，等式e ( 扩，v b ) = e ( 钍，曲成立。 非退化性：e ( g ，g ) 1 。 可计算性：任取乱，钉G ，双线性映射e ( 乱，V ) 能够进行有效计算。 则称G ，是一个双线性群，又因为e ( 扩，9 6 ) = e ( 纺夕) 赫= e ( 矿，9 8 ) ，所以双线性映射 P 是对称的。 2 1 1 判定性B I l l 假设 设G ，是一个阶为素数p 的双线性群，9 是G ，生成元，e ：G ，G ，_ G 2 表示 双线性映射，随机选取o ，b ，c ，Z Z 。，判定性B D H 假设( D e c i s i o n a lB i l i n e a r D i f f i e H e l l m a nA s s u m p t i o n ) 为：不存在概率多项式时间算法笤，以不可忽略的 优势区分( A = 夕，B = 以C = g C , e ( 夕，夕) 曲) 和( A = 夕“，B = g b , C = 矿e ( g ，夕) 。) 。算 法君的优势定义为： l P r 零( A B ，C , e ( 9 ，夕) 8 k ) = 0 】一P r 【零( A B ，C ，e ( 9 ，夕) ：) = o l 2 1 2 判定性q - B i b l E 假设 设G ，是一个阶为素数p 的双线性群，9 是G ，生成元，e ：G ，G 。_ G 。表示 双线性映射，随机选取o ，s ，6 1 ，6 9 z ，判定性q - B D H E 假设( D e c i s i o n a l q - p a r a l l e lB i l i n e a rD i f f i e H e l l r m nE x p o n e n tA s s u m p t i o n ) 是指给定敌手 4 山东大学硕士学位论文 夕，夕5 ，9 8 ，夕( 扩) ，9 ( q “j ，g ( 。”) ：V l = ! ；J 曼口 9 9 。，g 。j 。，夕( 口9 。) ，夕( d 。+ 。吩，9 n 2 9 。 V lsj I 曼口女；，g 。1 5 ? l ，g 。5 埔 j t j 不存在概率多项式时间算法B ，以不可忽略的优势区分e ( g ，9 ) 8 ”。G 。和随机元 素R G 。算法笤的优势定义为： i P r 零( 可，丁= e ( 阢9 ) 扩1 8 ) = 0 】一P r 笤( y ，丁= R ) = o l 2 。2 秘密共享 1 9 7 9 年，S h a m i r S 和B l a k l e y 9 分别独立地提出了秘密共享的概念并设计了 实现算法。秘密共享可以解决核心秘密的安全保存和管理问题。例如，导弹发射 程序的密钥该如何保存和管理。多人保管虽然可以防止密钥的意外丢失，但多保 存一份就多一分泄密的危险。单人保管也是不安全的，因为密钥可能意外丢失， 造成导弹无法正常发射，除此之外，一旦保管人的忠诚度出现问题，后果将不堪 设想。 秘密共享是指把秘密分成若干份，每份称作是一个分享份额。某些分享份额 组合起来可以重构恢复出秘密，称这些份额是授权集合；反之，某些分享份额即 便组合起来也无法恢复出秘密，称为非授权集合。秘密共享可以解决核心秘密的 安全保存和管理问题问题。首先，核心秘密被分成了若干个分享份额交给多人保 管，因此避免了单人保管可能造成的忠诚度问题。其次，每个分享份额并不会泄 露核心秘密的相关信息，从而大大降低了多人保管可能泄密的风险。最后，存在 多个授权集合可以恢复出核心秘密，故而个别分享份额的丢失不会造成核心秘密 的无法挽回。 2 2 1 访问结构的定义 设P = 只，足，P ) 是由n 个参与者组成的集合，A 2 P 是2 P 的一个非空子 集。其中2 P 表示P 的所有子集组成的集合，即A 是由P 的若干子集组成的非空 山东大学硕士学位论文 集合。如果集合A 是单调的，即对任意的由若干个参与者组成的集合B 和C ， 如果B 企BcC 则有C A ，那么我们称A 是参与者集合P 上的一个访问结 构。设A 是参与者集合P 上的一个访问结构，如果D A ，则称D 是一个授权 集合，否则D 是一个非授权集合。 2 2 2 门限秘密共享方案 S h a m i r 和B l a k l e y 提出的秘密共享方案都是门限秘密共享方案，S h a m i r 用多 项式插值的方法设计算法，而B h k l e y 用几何方法设计算法。S h a m i r 的门限秘密 共享最简单、最有效，并且最易于实现，是设计安全方案或协议时常用的基础构 件。 设k 和扎是两个正整数，且k 佗，一个( 忌，礼) 门限秘密共享方案是指，将秘 密D 分成礼个分享份额D l ，D 。进行共享，并且满足以下两个条件： 已知任意k 个或更多的分享份额D 。，可以很容易地计算出秘密D 。 已知任意k 一1 个或更少的分享份额D i ，无法恢复出秘密D 。 S h a r r f i r 的( 包佗) 门限秘密共享方案基于多项式插值：给定二维平面上七个互不 相同的点( x IY 。) ，( ，Y k ) ，存在一个并且只有一个度为k 一1 的多项式g ( z ) ，满 足g ( z i ) = Y ；，其中i = l ，jk 。设秘密D 是一个数，被分为n 份q ，或，我们 随机取一个度为k 一1 的多项式g ( z ) = + a l z + + a k _ l x “1 ，令a o = D 。然后 计算：q = g ( 1 ) ，D ，= q ( n ) 。给定任意露个皿的值，通过插值可以得到多项式 q ( x ) 的各个系数，从而恢复秘密D = q ( O ) 。在实际应用中，上述运算都是模素数 运算，以确保能够插值。 设e 是一个有限域，p 是素数，并且p 佗。设秘密D 是一个整数，P D ， S h a r r f r 的( 尼，n ) 门限秘密共享方案定义如下。 秘密地随机选取0 1 ) ，n 。一。 o ，p ) ，设g ( z ) = D + o ，z + + a k 一。z 卜1 ，对 6 山东大学硕士学位论文 于i = 1 ，礼，计算D 。= q ( i ) m o dp 。秘密D 的第i 个分享份额用( i ，皿) 表 示。 不失一般性，假设现有七个分享份额( 1 ，q ) ，( 七，巩) ，利用插值法得到： 如瑚篇格藉等+ 吣暑糖黼 最后计算获得秘密D = q ( O ) m o d p 。 2 2 3 线性秘密共享方案 一个关于参与者集合的秘密共享方案在Z p 上是线性的，则它满足： 所有参与者的分享份额构成Z 上的一个向量。 P 存在一个e 行礼列的矩阵M ，称作n 的分享生成矩阵，对于i = L ，C ， 函数J D ( i ) 表示M 第i 行所标记的参与者。设列向量钉= ( s ，t ，r ) ，其中 s Z ，是需要共享的秘密，r Z I , 是随机选取的，则向量胁表示 n 对秘密8 的个分享份额，( M y ) i 是第i 个分享份额，它属于参与者p ( ) 。 由文献【1 0 】可知，L S S S 具有线性重构特性。设n 是一个关于访问结构A 的 线性秘密共享方案，S A 是一个授权集合，I = i ：p ( i ) S ) c 1 ，q ，则可 以在多项式时间内找到一组常数 哆z ，) 斛，如果 磊) 是n 对秘密s 的有效分 享，则等式甜i 乃= s 成立。 2 2 4 访问结构的表示方法 访问树是用来表示访问结构的常用方法之一。设T 是一棵访问树，丁上的任 一非叶节点为一个阈门( T h r e s h o l dG a t e ) ，由该非叶节点的所有子节点和某个阈 值( T h r e s h o l d V a l u e ) 进行描述。设z 是T 上的任一节点，n u m 。表示z 的子节点 数量，吃表示z 的门限值，则有o ，其中z 为叶子节点，i = a 乇t ( 功。 D e c r y p t i o n ( E ，D ) ：算法输入密文E = ( 7 ，E 7 = M Y 8 ， E = 巧5 ) 晒) 和解密密 钥D ，若解密成功输出G 。上的一个元素，否则输出上。设。为访问树中的任一 节点，定义一个递归函数艺= D e c r y p t N o d e ( E ，D ，z ) 。 如果z 是叶子节点，设i = a t t ( x ) ，计算： c = 笠三乙，E ) = e ( 9 f f l J f ：夕9 ) = e ( 夕，9 ) ”以“1 j 2 1 o t h e r w i s e 如果z 是非叶结点，则对z 的所有子节点名计算e = D e c r y p t N o d e ( E ，D ，z ) ， 若Z 上的数量小于z 的门限值吃，则返回F = 上。若满足只上的z 节点数量 大于等于z 的门限值吃，设i = i n d e x ( z ) ，& 为任意吃个满足Z 上的子节点集 合，彰= i n d e x ( z ) ：z 瓯) ，计算： F 。= 兀矿 = 兀( e ( 伽。) 龟 = n ( e ( 夕夕) 9 铀“础叱甲1 m = n e ( g ，9 ) 9 “弘i 2 乓 ： e ( 9 ，9 ) 9 o 当且仅当密文满足解密密钥相关联的访问结构时，解密算法从根节点r 开始， 计算D e c r y p t N o d e ( E ，D ，7 1 ) = e ( g ，夕) 扩= y 8 ，又因为已知E I = 朋y ，因此算法从 密文中还原并返回明文消息M 。 山东大学硕士学位论文 3 1 3 安全性证明 定理3 2 在3 1 1 定义的基于属性的选择集合安全模型中，如果一个敌手能 够攻破3 1 2 构造的K P A B E 方案，则可以构造一个模拟