（计算机应用技术专业论文）基于属性的加密体制研究.pdf

基于属性的加密体制研究麓要 论文题目：基于属性的加密体制研究 专业：计算机应用技术 硕士生：刘阳 指导教师：王常吉副教授 摘要 基于属性的加密体制是基于身份加密体制的延伸，也是基于模糊身份加密体 制的具体应用。在基于属性的加密体制中，身份用一系列描述性的属性表示，同 时添加了一个更具灵活性的访问结构。它最突出的优点就是非常适用于解密方不 固定的情况。发送方加密信息时不需要知道具体是谁解密，而接收方只需要符合 相应条件便可以解密。遗憾的是现有的基于属性的加密( a b e ) 方案安全水平远 达不到要求，仅处于选择明文安全的水平。因此，本文运用混合加密的思想构造 了一个抗适应性选择密文攻击( c c a 2 ) 安全的a b e 方案。 本文对基于属性的加密及其安全性进行了研究，主要研究成果如下： 1 ) 本文介绍了几个典型的a b e 方案，并从效率和安全性上作了详细地分 析。结果表明现有方案的安全性远达不到要求，迫切需要提出一个安全性较高的 a b e 方案。 2 ) 提出了密钥策略的基于属性的密钥封装( k p a b k e m ) 的概念，并对其 进行了形式化定义及安全模型设计；随后，给出了一个酣d c c a 2 安全的 k p a b k e m 方案和严格的安全证明，并将其扩展到l s s s 访问结构。 3 ) 在混合加密思想的启发下，将k e m + d e m 混合加密范例同基于属性的加 密体制相结合，提出一个i n d c c a 2 安全的基于属性的加密方案，并作了比较完 整的安全定义，然后对其进行形式化的安全性证明。 4 ) 以l a b e 作为基础方案，运用f o 变换方法构造出另一个i n d c c a 2 安全的基于属性的加密方案。最后，将上述两个方案同k p a b e ，c p a b e 从效率 和安全性上进行了分析对比。 关键词：基于属性的加密，密钥封装机制，混合加密，可证明安全 基于属性的加密体制研究 t i t l e ：r e s e a r c ho f 吐地a t t r i b u t cb 勰e de n c r y p t i o n m 旬o r ：c 0 l i l p u t 盯a p p l i c a t i o nt e c h n o l o g y n 锄e ：l i u y 抽g s u p e r v i s o f ：w a n gc h 锄西i a b s t r a c t a t t 曲u t c - b a s e d 饥c 哪t i o ns y s t 锄i s 锄强t e 邶i o no fi d 锄t i t y - b 硒e d 朗c 聊p t i o n 肌das p c c i 丘ca p p l i c 撕o no f 矗l z z ) ri d e n t i 啪弱e d 铋叩唧i o n h lm i ss y s t e m ，i 妇l t i t y i sas 甜锶o fd 豁c r i p t i v ea t t r i h n 骼锄dam o 他f l e x i b l ea 仪懋翳s 咖c t l l r ei sa d d e dt 0 “s s y s t e m t h em o s tp r o m i n 饥ta d v 觚t a g eo f 曲旧s y s t 锄i $ v e r ya p p l i c a ：b l et 0n l e d i s t r i b u t e de n v i r o n n l e f l tw h e r er e c e i v e ri sn o t 矗x e d s e n d e r d o e sn o tn e e dt ok n o w 廿l e s p c c i f i cr e c e i v 觚dr c c e i v c rw h 0o n l yn e c d st 0b ec 0 璐i s t c n tw i t hm ec o n c s p o n d i n g c o n d i t i o n sc 跹 d e c r y p tt h em c s s a g e舶ms e n d e lu n f o m m a t e l y ，m ee x i s t i n g a 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 ) s c h 锄e sa r ct o ow e a l ( h l 廿l i st l l 锱i s ，an e wa b e s c h e m ea g a i n s ta d a p t i v ec h o s e nc i p h e n e x ta t t a c k ( o c a 2 ) i sc o n s m l c t e du s i n g 玲i d e a o 仆y b r i d 饥c r y p t i o n i i lt l l i sp a p e r a t t r i b u t e - b 弱e de n c r y p t i o na 1 1 di t ss 谢t yh a v eb e e n 删e d ；圮 m a i nr c s e a r c b “笛u l t s 卸r ea sf b l l o w s ： f i r s to fa l l ，w ei n h o d u c e ds c v 啪lt y p i c a la b es h c e m 岱，t 1 1 廿1 ee 历c i 铋c y 觚d s e c u r i t yw e r e 锄a l y z e di nd e t a i l t h e 锄a l y z i n g 髑u l ts h o w st 1 1 a tn l es a f e t yo f 廿1 e mi s b e l o ws t a n d a r d ，s om e r ei s 觚瑚苫e n tn e e df 1 0 ras e c u r ea b es c h 锄e w h a t sm o r e ，w ep u tf o r w a r dt l l ec o n c e p to fk e y p o l i c y 删b u t e - b a s e dk e y e i l c 印s u l a t i o nm e c h a l l i s m ( k p - a b k e m ) ，锄dm a k ef o 蛐a 1d e f i n i t i o n 觚ds e c 嘶t ) ， m o d e ld e s i 印a r e rm a t ，锄k e y - p o l i c ya t t r i b u t e _ b a s e dk e y c a p s u l a t i o ns c h e m ew i t l l 嘶c ti n d c c a 2s e c u i i t y p r o o fi sp r o p o s e d f i n a l l m l i ss c h 锄ei sc x t 既d e dt 0 l s s s r e a l i za _ b l ea c c e s ss t i 。u c t i 】i 。e a d d i t i o n a l l m l r o u g l l 坞c o m b i n a t i o no fh y b r i d 铋c r y p t i o n ( k e m + d e m ) a n d a t t d b u t e b a s e d 铋c r ) ，p t i o 玛 w e p r o p o s e a n a d a p t i v ec _ h o s e n c i p h e r t e x ts e ( u 他 u 基于属性的加密体制研究 a b s t 腿c t 删b m i o n b a u s e d 饥c r y p t i o ns c h 锄e a n dt t l 饥ar e l a t i v e l yc o m p r e h e n s i v ed e f i n i t i o n 觚df o n i l a lp r o o fo ft h es c h e m e ss e c u r i 够w 觞p r e s e n t c d 。 l 弱t l y ，u s i n gk p - a b es c h e m e 嬲ab 弱i s ，w ec o n s t m c t 锄o n 埘a d a p t i v e c h o s e l l - c i p h 叭甑ts e c u 鹏a 嘶b u t e - b 勰e de i l c 唧t i o n 谢廿lf o 仃a 1 1 s 内加a t i o n f i n a l l 弘 w em a l ( ead e t a i l e d 锄a l y s i so nk p a b e ，c p a b e ，嬲w e l l 鹤m e 撕os c h e i l l e s p r o p o s c db yt l l i sp a p 粕d0 b t a i l lm e i rr e s p e c t i v ea d v a n t a g e s 锄dd i s a d v 锄t a g e s i ，e yw d r d s ：a 蛹b u 皓b 嬲e de n c 呻t i 鸭k e ye n c a p s u l a t i 彻m h 衄i 锄，h y 鲥de 蚴弹t i 佣， i n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：主j7 9 j ? 吼7 年f 月咖 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 ) 学位论文作者签名： & 订7 阳 眺口了年 月咨日 导师签名：啦彦眇( 铖) 嗍：叩眦日 基于属性的加密体制研究第1 章结论 第1 章绪论 1 1 研究背景与意义 在传统的公钥密码体制中，用户身份和他的公钥是通过证书来绑定的。不过 证书的管理问题却是非常复杂，它需要消耗大量的时间和空间来处理证书的存 储，验证和撤销。随后，基于身份的密码体制则很好地解决了这个问题。同时， 它也存在一个致命的缺陷，那就是密钥托管问题。基于模糊身份的密码体制是一 种新型的基于身份的密码体制，所谓模糊身份就是一个描述性的属性集合。就加 密而言，只有当解密方与加密方的属性集合的交集大于某个特定值时才能解密。 它所具有的容错性使得它在生物识别领域有着天然的优势，因为提取的生物信号 和特征会随着提取方法、提取环境以及人与提取仪器之间的接触的不同而发生变 化，而仪器的精度也会影响提取的结果。 基于属性的加密体制是基于身份加密的延伸，身份用一系列描述性的属性表 示；也是基于模糊身份加密体制的具体应用，同时添加了一个更具灵活性的访问 结构。它最突出的优点就是很适用于分布式环境下解密方不固定的情况。加密方 加密信息时不需要知道具体是谁解密，而解密方只需要符合相应条件便可以解 密。它的这种灵活性使得它在许多特定领域有比基于证书，甚至基于身份的密钥 体制更好的适用性。 1 1 1 加密体制的发展历程 从出现加密这一概念到现在，加密技术已经获得了长足的进步。总的来看， 加密技术的发展可以分为三个阶段【1 1 。 第一阶段：古典加密技术 1 9 4 9 年以前的加密技术比较简单，并且安全性较低，这个时期的密码被称 为古典密码。此时的密码算法只是针对字符，使用的手段大多是替代和置换。替 代就是用密文字母来代替明文字母，在隐藏明文的同时还可以保持明文字母的位 置不变，而置换则是通过重新排列明文中字母的顺序来达到隐藏真实信息的目 基于属性的加密体制研究第1 章绪论 的。 第二阶段：对称加密技术 对称加密又称单钥加密，即加密和解密使用的是同一个密钥。发送方将明文 和加密密钥一起经过加密算法处理变成复杂的加密密文发送出去。接收方收到密 文后，如果想解密密文，则需要使用加密时使用的密钥及相同算法的逆算法对密 文进行解密，才能使其恢复成可读明文。在对称加密算法中，使用的密钥只有一 个，发收双方都使用这个密钥对消息进行加解密，这就要求解密方事先必须知道 加密密钥。对称加密算法的特点是计算量小、加密速度快、算法公开、加密效率 高。不足之处就是，每对用户每次使用对称加密算法时，都需要使用其他人不知 道的惟一密钥。这会使得密钥数量成几何级数增长，密钥管理将成为用户的负担。 对称加密算法在分布式网络上使用较为困难，主要是因为密钥管理困难，使用成 本较高。 第三阶段：公钥加密技术 1 9 7 6 年，美国密码学专家迪菲( d i 伍e ) 和赫尔曼( h e l l m 锄) 提出公钥密码 体制的概念，将密码学引入了一个全新的方向。这类密码体制的安全强度取决于 它所依据困难问题的计算复杂度。基于公钥概念的加密算法就是非对称加密算 法，该加密算法使用两个不同的密钥：加密密钥和解密密钥。前者是公开的，又 称公开密钥，简称公钥。后者是保密的，又称私有密钥，简称私钥。这两个密钥 是数学相关的，用某个用户的公钥加密后所得的信息只能用该用户的私钥才能解 密。 随着计算机网络的发展，数据机密性要求的日益提高，非对称加密算法有着 对称密钥加密算法不可替代的优越性。近年来，非对称加密算法和p 、数字签 名、电子商务等技术相结合，保证了网上数据传输的机密性、完整性和不可否认 性，在网络与信息安全方面起着重大的作用。目前比较流行的非对称加密算法主 要有两类：一类是基于大整数因子分解问题的，其中最典型的代表是r s a 算法； 另一类是基于离散对数问题的，如e 1 g 锄a l 算法。虽然公钥密码体制是非常重要 的一种技术，但非对称加密算法并非十全十美的，它的不足之处就是算法复杂、 运行速度慢。 2 基于属性的加密体制研究第l 章绪论 1 1 2 混合加密 公钥加密不需要在收发消息的双方之间交换密钥，但是公钥加密与对称加密 相比速度较慢，而且消息空间也常常受到限制，不宜加密长消息。一般来讲，对 称加密比公钥加密速度快近千倍。所以，在实际应用中通常结合这两种加密，用 公钥加密体制传输对称加密体制的密钥，而由对称加密体制加密真j 下的消息，这 通常被称为混合加密。它是密码学中的一种重要工具，同时也是使公钥加密从低 安全水平上升到适应性选择密文攻击下不可区分( i n d c c a 2 ) 安全的一种有效 方法。 混合加密由对称加密和公钥加密两部分组成，因此对于混合加密的安全性不 仅要考虑对称加密和公钥加密的安全性，更要考虑混合后加密的安全性。混合加 密中对称加密和公钥加密部分及其安全性是完全独立的。一般情况下，安全性高 的对称加密和公钥加密混合后安全性水平也越高，但是需要付出的代价往往也越 高。 混合加密的最简单、最直接的实现方式就是：用一个公钥加密方案加密对称 密钥k ，再用一个对称加密方案用足加密真正的消息。人们也往往认为只需要对 称加密和公钥加密部分分别选择密文安全，那么就能获得混合加密的选择密文安 全性，事实也确实如此。 1 2 国内外研究状况 1 2 1 基于身份的密码体制 在传统的公钥密码体制中，用户的公钥是随机生成的比特串，用户与其公钥 之间的绑定是由可信的证书机构( c 耐i f i c a t i o n a u t h o r i 哆，简记为c a ) 通过向每 个用户发放证书的方式来实现的。证书包含用户的信息以及对应的公钥。在这样 的系统中，用户必须首先获取证书、验证证书的有效性，才能使用相应的公钥。 而c a 也需要花费大量的时间和空间来存储、发放证书。为了解决传统公钥密码 体制中的这些问题，s h 锄i r 在1 9 8 4 年提出了基于身份的密码体制( i d e n t 时b 硒c d c 聊t o s ) r s t 锄) 【1 】【2 】。在这种体制中，用户的公钥直接来源于他的公开身份或者可 以通过简单的算法由他的公开身份计算出来。而用户的私钥则通过一个可信第三 3 基于属性的加密体制研究 第l 章绪论 方，通常称为密钥生成中心( p r i v a t ek b yg 肌e r a t o r ，简称p k g ) 来生成。用户 和公钥之间的绑定不再需要证书来保证，因此p k g 也不再需要保存和发放证书， 甚至可以是离线的。p k g 唯一的任务就是为每个首次加入系统的用户分配一个 与其身份对应的私钥。 s h 锄i r 在文章【2 】中还利用大整数分解的困难性问题给出了第一个可行的基 于身份的数字签名方案( i d 咖时b a s e ds i 伊a t u 陀，简记为i b s ) 。之后，许多基 于身份的数字签名方案也陆续被提出。但是却在之后的很长一段时间未能提出一 个可行的基于身份的加密方案，直到双线性对的特性被发现并应用于密码学。 下面以加密为例，介绍一下基于身份的公钥加密体制的运作流程。假设a l i 要给b 0 b 发送一条加密消息，其中b o b 的身份信息为i d ，具体操作如下： 1 ) a l i c e 计算b 0 b 的公钥后，进行加密并将加密消息发送给b o b ； 彳j f j 毯舻b d 6 2 ) b o b 向p k g 索取私钥，其中p k g 的主私钥为s ； 户磊，g - _ 璺堕：丛! 堕肋6 3 ) b 0 b 获得私钥后，解密消息； 肋6 ：所= ( c ) 1 2 2 混合加密体制 2 0 0 3 年，c 例【l l e r 和s h o u p 第一次对混合加密作了形式化定义。c r 锄盯和 s h o u p 提出的混合加密范例3 1 是密钥封装机制( k e ye n c 叩叭l a t i o nm e c h a i l i s m 简 记为k e m ) 与数据封装机制( d a t ae n c a p s u l a t i o nm e c h a i l i s m 简记为d e m ) 进 行混合，简记k e m + d e m 混合加密范例。k e m 与公钥加密相似，只是任务变为 对随机生成的密钥k 进行加密。d e m 是一个一次对称加密方案，即每个密钥只 用于一条消息的加密。k e m 是混合加密的一个关键因素。当然，可以用一般的 公钥加密方案来加密随机生成的密钥k ，但是还有更有效的方式来实现，譬如基 于r s a 的密钥封装机制( r s a k e m ) 【4 】等。 另外，很多混合加密方案t 1 0 1 并不能简单地套用k e m + d e m 混合加密的模 4 基于属性的加密体制研究 第l 章绪论 式，它们大都是随机预言机模型下的，但是效率很高。为了设计一个更实用更有 效的混合加密模式，2 0 0 5 年a b e 等人提出了t a g k e m d e m 混合范例【6 】，它最 大的优势在于将d e m 部分的安全性要求降低到对被动攻击的安全性。这被认为 试更为合理的，因为既然d e m 是一次的，那么允许攻击者询问解密预言机实际 上是不现实的。t a l ，- k e m d e m 结构设计非常精巧，也很实用，它将d e m 的密 文作为t a g - k e m 的t a g ，确保了混合加密密文的不可延展性。 许多相关的文献都默认了混合加密的i n d c c a 2 安全性为它们作为公钥加 密的i n d c c a 2 安全性，简而言之，c c a 2 攻击者只有权限访问整个混合加密的 解密预言机。但是2 0 0 4 年的e u r o c 聊p t 上，b d l a r e 等【l l 】第一次给出了更强的安 全性定义。他们的安全性定义中允许敌手分别询问作为组成部分的对称加密和公 钥加密的解密预言机，虽然他们的定义是针对多消息的混合加密，即用公钥加密 的对称密钥k 可以用于加密多条消息。本文把b e l l a r e 等提出的混合加密范例简 记为u 江+ s k e 混合加密。i n d c c a 2 安全的a k e 与i n d c c a 2 安全的s k e 得 到的混合加密也是i n d c c a 2 安全的。 1 3 本文的主要工作 本论文对基于属性的加密体制进行研究，具体研究内容包括三个方面： 1 ) 本文对两个典型的基于属性加密方案作了描述，并从效率和安全性上作 了详细地分析。当前，基于属性的加密方案的最大不足就是安全性仍处于较低的 水平一抗选择明文攻击安全。 2 ) 介绍了混合加密的典型范例k e m + d e m 及其安全性定义，以及相关的 结论。并且对该范型是否能够应用与基于属性的密码体制作出了深入分析，最后 得出的结论是肯定的。 3 ) 提出了基于属性的密钥封装( k p a b k e m ) 的概念，并对其进行了形 式化定义及安全模型设计；随后，给出了一个i n d c c a 2 安全的k p a b k e m 方案和严格的安全证明，并将其扩展到l s s s 访问结构。 4 ) 在混合加密思想的启发下，将k e m + d e m 混合加密范例同基于属性的 加密体制相结合，提出一个烈d c c a 2 安全的基于属性的加密方案，并作了比 5 基于属性的加密体制研究第l 章绪论 较完整的安全定义，然后对其进行形式化的安全性证明。 5 ) 以l a b e 作为基础方案，运用f o 变换方法构造出另一个i n d - c c a 2 安全的基于属性的加密方案。最后，本文对l o a b e ，c p a b e 以及本文构造的 两个方案进行分析比较，得出其各自的优劣所在。 1 4 本文的章节安排 第l 章首先介绍了论文的背景、意义和加密体制的发展，接着回顾了混合加 密和基于身份的加密体制的研究现状，最后介绍了本论文的章节安排。 第2 章主要介绍研究论文所需基础知识和基础理论，包括双线性对及相关的 困难性假设、可证明安全性理论和秘密共享体制。随后本文介绍了公钥加密和混 合加密的形式化定义、安全模型以及各自具有代表性的方案等。 第3 章首先介绍了基于属性的加密体制的研究现状，接着详细介绍了两种类 型的基于属性加密方案，即k p a b e 和c p - a b e 。 第4 章首先介绍了密钥策略的基于属性的密钥封装的形式化定义和安全模 型，并提出了一个i n d c c a 2 安全的k p - a b k e m 方案；随后，在此基础上构 造了一个i n d c c a 2 安全的基于属性的加密方案，并对其进行严格的形式化安 全性证明。接着，本文基于f o 变换再次构造出一个i n d c a 屹安全的基于属性 的加密方案。最后，把本文构造的两个i n d c c a 2 安全的基于属性的加密方案 同先前的两种典型加密方案进行了比较分析。 第5 章是对本论文的一个总结及展望。 6 基于属性的加密体制研究 第2 章基础知识和基础理论 第2 章基础知识和基础理论 2 1 双线性对 设p ，g 是素数，g i 是阶为p 的乘法循环群，g 2 是阶为g 的乘法循环群假 设d l p 问题在g l 和g 2 中都是困难的。通常称映射p ：g l g l _ g 2 为一个双线性 对，如果g 满足下述性质： 双线性( b i l i n e a r ) ：对于任意口，6 z 叮和尺，s g i ，都有下列换算关系： p ( 尺口，s 6 ) = p ( r ，s ) 西。 非退化性( n o n - d e g e l l e r a t e ) ：存在r ，s g i ，使得p ( r ，s ) l g ：这里l g l 代表g 2 群的单位元。 可计算性( c o m p u t a b l e ) ：存在有效的算法对任意的尺，s g l ，计算 p ( j r ，s ) 的值。 双线性对还具有以下性质： 对于任意墨，尺2 ，s g l ，都有p ( 墨心，s ) = p ( 蜀，s ) p ( r ，s ) 。 对于任意足，墨，足g l ，都有“尺，墨岛) = “r ，s ) “尺，最) 。 在这样的群g l 上，有以下几个密码学困难问题： 定义2 1 离散对数问题( d i s c r e t el o g 撕t l 吼p r o b l 锄，简称d l 问题) ： 给定两个元素g g i 和】，g i ，计算口乏，使其y = 9 4 成立。 定义2 2 计算d i 伍e h e l l m a l l 问题( c o m p u t a t i o n a ld i 佑e - h e l l m a l lp m b l 锄， 简称c d h 问题) ：给定三元组( g ，旷，9 6 ) ，其中口，6 z ：且未知，g 为循环群的 一个生成元，计算g 柏的值。 定义2 3 判定d i m e - h e l l m 觚问题( d e c i s i o n a ld i 衢e h e l l m 肌p r o b l 锄，简 称d d h 问题) ：给定四元组( g ，矿，9 6 ，旷) ，其中口，6 ，c z g 且未知，g 为循环群 7 基于属性的加密体制研究第2 章基础知识和基础理论 的一个生成元，判定是否c = 口6 ( m o d g ) 。 上述三个问题通常被视为困难性问题，但它们的困难程度却是不一样的。显 然，如果能够解决d l 问题，那么便能够解决c d h 问题和d d h 问题。如果能够 解决c d h 问题，那么d d h 问题也就容易解决了，所以说d d h 问题的困难程度 不比c d h 问题更高；c d h 问题的困难程度不比d l 问题更高。它们之间的关系 可以表示为： d d h 专c d h d l 其中沿“一 方向表示问题的困难程度单调不减。 d l 问题的困难性是否一定能够保证c d h 问题的困难性目前还没有得到完 全的证明。但普遍认为这两个问题具有同等困难性，所以在讨论基于c d h 问题 的密码体制的安全性时，我们经常考虑d l 问题。 下面的讨论告诉我们尽管c d h 问题通常被认为和d l 问题一样困难，但 d d h 问题在某些场合下却是容易解决的。 设双线性对p ：g i g l g 2 ，因为双线性对具有非退化性，所以e ( 尸，尸) l g 2 假设群g 。上的d l 问题和c d h 问题是困难的，g 口，9 6 ，g 。g l 是群g l 中的任意 元素，根据双线性对的双线性可得： e ( g 口，9 6 ) = p ( g ，g ) 口一，e ( g ，g c ) = e ( g ，g ) c 所以， 口6 三c p ( g ，g ) 4 = p ( g ，g ) c p ( g 口，9 6 ) = p ( g ，g c ) 这样就把d d h 问题转化为判断两个双线性对的值是否相等的问题。所以， 借助于双线性对，群g l 上的d d h 问题变得容易起来。 定义2 4 1 2 。如果群g l 上的c d h 问题是困难的，而d d h 问题却是容易解决 的，则称群g i 为间隙d i 伍争h e l l m 觚群( g a p d i 伍争h e l l i i l 觚g m u p ) ，简称为g d h 群。 引入双线性对之后，c h e o n 等1 3 】讨论了一种新的类型的困难性问题，称之为 r 基于属性的加密体制研究 第2 章基础知识和基础理论 双线性d i 硒e - h e l l m 锄问题。 定义2 5 双线性d i 伍e h e l l m 锄问题( b i l i i l e 盯d i 衔e - h e l l m 锄p r o b l 锄，简称 b d h 问题) ：给定五元组( g ，g 口，9 6 ，旷) ，其中口，6 ，c 乙且未知，计算 e ( g ，g ) 如g 2 。 定义2 6 判定双线性d i m c - h e l l m 觚问题( d e c i s i o n a lb i l i n e a rd i 伍争h e l l m 锄 p r o b l 锄，简称d b d h 问题) ：给定五元组( g ，g i ，9 6 ，g f ，) ，其中口，6 ，c z 口且未 知，g 2 ，g 为循环群的一个生成元，判定是否，= p ( g ，g ) 咖。 首先，如果群g i 上的c d h 问题是可计算的，比如由g 口，9 6 可计算出y = g 曲 那么p ( y ，g ) = e ( g 曲，g ) = p ( g ，g ) 咖，这样就解决了b d h 问题，所以说b d h 问题不会比群g l 上的c d h 问题更难。其次，b d h 问题还依赖于g 2 上c d h 问题 的困难性，设e ( g ，g ) = r ，那么 p ( g ，g c ) = r c ，p ( g 口，9 6 ) = 丁n 6 如果由r c ，丁曲可计算出丁幽，那么丁出= p ( g ，g ) 口6 c 。 g l 和g 2 上c d h 问题的困难性能否保证b d h 问题的困难性? c h e o n 等1 3 1 指出：对任意的丁g 2 ，g l ，9 2 g i ，如果能够有效地计算出：p ( 蜀，9 2 ) = r ， 那么b d h 问题与g l 和g 2 上的c d h 问题具有同等的困难性。但是，目前还不知 道双线性对中是否存在计算蜀，的有效算法。所以目前还不知道b d h 问题是 否与g l 和g 2 上的c d h 问题的困难程度一样。既然还没有解决b d h 问题的有效 算法，所以，人们总是认为b d h 问题是一个困难问题。 9 基于属性的加密体制研究第2 章基础知识和基础理论 2 2 可证明安全理论 2 2 1 可证明安全的概念 在可证明安全的概念提出之前，人们通常是设计出方案后等待攻破来保障密 码体制的安全，一旦被攻破就加一些补丁或做一些修改得到新的方案，并不断反 复这样的过程。这种方法使我们总是处于被动的状态，对密码方案的使用总是心 有余悸。 2 0 世纪8 0 年代提出的可证明安全的概念改变了这一局面。可证明安全是用 归约方法来保障密码体制的安全，通过提前确定攻击模型并给出安全性证明，从 而有效地抵御许多未知的攻击。可证明安全的提出对密码学最大的贡献在于它创 造性地采用形式化的方式来审视公钥密码体制安全性，使公钥密码体制的可证明 安全性得到了广泛的研究。此外，许多关键性的概念和思想都是在这些研究中发 现和总结的，比如存在性伪造、自适应选择密文攻击等等。 对于一个待证明的密码学方案，可证明安全的典型过程如下【1 4 】： 1 ) 确定一个标准的安全模型和安全性定义； 2 ) 确定方案所基于的困难性问题，如大整数分解问题、离散对数问题等等； 3 ) 建立破坏方案安全性的复杂性与解决该难题的复杂性之间的联系，这一 过程称为安全性归约。 也就是说，我们不是直接去分析方案本身，而是关注于如何建立安全性归约。 一旦建立了安全性归约，我们就等于得到了以下保证：如果方案的安全性可以被 攻破，则相应的困难性问题也可以被解决。因为我们相信后者是不可解的，所以 也相信方案是安全的。 在建立安全性归约时，如果没有任何假设便可以将方案的安全性约化到困难 性问题上，则称为该归约是基于标准模型( s t a n d 砌m o d e l ) 的，也称方案具有 在标准模型下的可证明安全性。但是对于许多方案来说，在标准模型下建立安全 性归约是比较困难的。为了降低证明的难度，人们在建立安全性归约时常常对方 案进行了一些合理的假设。其中最常见的假设是针对h 础函数的随机预言机 ( r a n d o mo r a d e ) 假设。这种假设下得到的安全性也称为随机预言机模型 l o 基于属性的加密体制研究 第2 章基础知识和基础理论 ( r 锄d o mo r l em o d e l ) 下的可证明安全性。 2 2 2 随机预言机模型 在1 9 9 3 年，b e l l a r e 和r o g a w a y 提出了随机预言机模型。它是从h 勰h 函数 抽象出来的一种模型【1 5 1 ，是在可证明安全中被广泛使用的证明方法。 随机预言机是一种虚构的h 袖函数，它具有以下性质： 1 ) 一致性：对于相同的输入，其输出必然相同； 2 ) 可计算性：输出的计算可以在输入值长度的多项式时间内完成； 3 ) 均匀分布性：预言机的输出在取值空间内均匀分布。 在随机预言机模型中，假定敌手不会利用h 嬲h 函数的弱点来攻击密码学方 案。换句话说，即使将方案中的实际h 袖函数换成随机预言机，敌手仍然可以 成功。 人们对随机预言机模型下的安全性证明的有效性仍存在争议的。因为这种模 型下的证明是一种具有很强假设性的，即敌手不可以利用h 础函数的弱点。但 是在现实中，h 曲函数是确定的，其输出并不能保证是完全随机且均匀分布的。 所以，随机预言机模型下证明安全的一些方案，在用真实的h 袖函数代替随机 预言机后，就不再安全了。 但是也要看到，基于随机预言机模型的安全性证明也帮助避免了方案中可能 存在的许多缺陷，而且它还告诉了我们对于该方案而言，其最脆弱的环节是方案 中使用的h a s h 函数。因此，随机预言机模型仍然被认为是可证明安全理论中最 成功的实际应用。目前，几乎所有的国际安全标准都要求方案设计必须至少在随 机预言机模型可证明安全，而当前大多数可证明安全的方案也是基于随机预言机 模型的。 2 2 3 s h o u p 引理 对本文4 2 节中提出的方案的安全性证明，该节运用了s h o u p 提出的证明技 术1 6 1 。在这种技术里，定义了一系列从实际的攻击游戏g 口所开始不断修改的攻 击游戏彤聊q 、弘聊印等等。每一个游戏都在相同的基本概率空间p 上执行： 基于属性的加密体制研究第2 章基础知识和基础理论 包括密码学方案的的公私钥对，攻击者彳的随机抛币以及随机预言机等等。接下 来需要考虑的仅仅是两个游戏之间的差异计算。具体来讲，就是反复运用以下引 理( 称之为s h o u p 引理) ，以一个微小的分布概率差异从一个游戏过渡到另外一 个游戏。从而完成密码方案的最终安全性证明。 引理2 1 ( s h o u p 引理【1 6 】) ：在一个密码方案里，概率空间j p 的修改会影响 事件s 的成功概率占= 州s 】。即如果概率空间p 不变，那么事件s 成功概率也不 会改变p r 【si - 1 e 】= p r s l1 司。而当某一个b a d 事件e 发生时，概率空间p 发 生变化，事件s 的成功概率随之发生变化。此时， 1 ) 如果s 与e 无关，那么p r s 】p r 【s 】p r 卜t 司= 占p r 【1 e 】； 2 ) 如果s 与e 相关，那么ip r 【s 卜p r 【跚峰p r 【明。 2 3 秘密共享体制 秘密共享的概念和密钥共享体制是针对密钥管理中密钥的泄漏问题和遗失 问题提出的。自从1 9 7 9 年b l a l 【l e y 【”1 和s h 锄i i l l 8 】分别独立地提出了密钥共享的 概念以来，人们在密钥共享理论和密钥共享技术与应用方面取得了丰硕的成果。 而且，密钥共享理论与技术在密码学和信息安全理论与技术中已占有重要的地 位。b l a k l c y 和s h 枷r 提出了密钥共享体制分别是仿射的和线性的。其后，人们 提出的密钥共享体制大多是b l a l ( 1 e y 和s h 锄i r 体制的变型，不过它们有一个共同 的特点，就是主密钥的重构方法可通过求解线性方程组来实现【1 8 埘】。这自然促使 人们建立一般的线性密钥共享体制( 简记为l s s s ) 。肖亮亮和刘木兰【2 2 1 利用单 调张成方案构造了一批线性密钥共享体制【2 3 1 。下面详细介绍访问结构，秘密共享 体制中的一种特殊类型门限秘密共享，以及构造线性密钥共享体制的工具 单调张成方案。 2 3 1 访问结构 定义2 7 访问结构( a c c e s ss t n ：瓜u r e ) 【2 1 l ：一个实体集 毋，罡，只) ，对于 ，c ，如果当b 彳且曰c 时，则有c 彳，那么称集合彳2 毋忍 乓是单调 1 2 基于属性的加密体制研究第2 章基础知识和基础理论 的一个访问结构( 通常是指单调的访问结构) 是 暑，罡，) 的一个非空子集 合彳，即彳9 2 毋 恳一最 办。包含于彳中的集合称为授权集合，而不包含在彳中 的集合称为非授权集合。 在本文中，上述定义中的实体集中每个主体表示一个属性，访问结构彳包括 了授权属性集。同时，彳被严格限制为单调访问结构。 2 3 2 门限秘密共享 门限秘密共享( n r c s h o l ds e c r e ts h 耐n gs c h 锄e ) 是s h 锄i r 于1 9 7 9 年提出 的【1 羽。s h a m i r 的o ，一) 门限密钥共享体制是最简单、最有效、也是最实用的一类 密钥共享体制。一个o ，刀) 门限秘密共享方案可以将一个秘密s 分成n 个部分，使 得只要知道其中任意f 个部分都可以恢复出秘密s ，而任意，一1 个或少于卜1 个部 分的组合都无法恢复出秘密s 。共享的概念是指秘密的恢复需要，个部分的共同 作用。门限秘密共享方案的一个主要应用就是实现私钥的分散保存以降低私钥泄 露所带来的风险性。此外门限秘密共享方案还可以提供系统的健壮性，因为即使 有刀一f 个部分被破坏，秘密仍然能够通过剩下f 个部分的组合得到恢复。 s h 锄i r 的门限秘密共享机制基于多项式插值法，即一个f 一1 阶单变量多项 式y = 厂( 工) ，能够通过f 个不同点( 毛，y ，) 唯一确定。换句话说，设- 厂( x ) 为x 的一 个次数小于f 的函数，则给定f 个不同点( ，y j = 厂( ) ) ，可以求出任意一个x 所 对应的厂( x ) 值。利用拉格朗日( i a g r a n g e ) 插值公式有： m ，= 轨墨码硝暑 假设希望将秘密s 分为万个部分共享，则可以设口。= s ，并随机选择t - 1 个独 立系数q ，口2 ，口“，定义z 。上的随机多项式厂( x ) = 口；z 。再对每个f 刀， 计算厂( f ) ，每个片段所持有的信息就是( f ，厂( f ) ) 。 当需要恢复秘密时，只需选择任意t 个部分的集合s ，计算下列公式： s = 口o = 厂( o ) = 厂( 必嫡( o ) 基于属性的加密体制研究第2 章基础知识和基础理论 其中 嘣加，骢，哥j e 6 ，j 事l j 2 3 3 单调张成方案 定义2 8 【2 l 】线性秘密共享方案( l i n e 缸s e c r e t s h 撕n gs c h e m 髓简记为 l s s s ) ：一个基于成员集p 的秘密共享方案n 在z ，上是线性的需要满足以下两个 条件： 1 ) 每个成员所分得秘密的一部分构成一个z ，上的矩阵。 2 ) h 中存在一个，( 刀+ 1 ) 秘密分享矩阵m 。对于江l ，m 的第f 行表 示第f 个成员薯p 。设一个列向量y = ( s ，吒，呢，) ，其中s 乙是待分享的秘密， ，；，z ，是随机的，则m ，把秘密s 根据分成，个部分。( m ，) ，属于成员玉。 定义2 9 f 2 l 】线性重构( l i n c a rr e c o n s t m c t i o n ) ：n 是访问结构彳上的一个 l s s s 方案。设s 彳是任意一个授权集，= f ：五s c 1 ，2 ，) ，那么可以在多 项式时间内找出这样的常数集她乙埘，使得劬( m - y ) ，= s 。 i e j 单调张成方案( m o n o t o n es p 雒p r o g r a m ) 【2 4 1 最初用于布尔函数的计算，现 在用它作为构造l s s s 的工具。一个布尔函数，被称为单调的，对满足 厂( 五，毛) = 1 的所有( 五，) ，在它的任意输入比特中本来为。的改成l ， 其输出值仍为1 。 定义2 1 0 单调张成方案( m s p ) ：m 是一个二元组( m ，缈) ， 尸= 嘏，只) 是一个参与者集合，膨是有限域f 上的d ，矩阵，标号 缈： l ，d ) _ p = 暑，只) 是一个满射，代表将膨的一行指定给参与者集合p 中唯一的一个用户。 一个单调张成方案m 是接受还是拒绝一个输入根据以下标准。对于每个输 入集合7 ，定义m 的子向量m ，它只包含那些满足砸) 7 的行。m s pm 计算一 个布尔函数厶，如果厶( 7 ) = 1 ，那么m 接受，；否则拒绝。m 的大小就是矩阵m 的行数。 1 4 基于属性的加密体制研究第2 章基础知识和基础理论 性。 在本文中，由于参与者是一个属性集，所以矩阵m 的每行被标记为一个属 定理2 1 【2 5 1 ( f ，刀) 门限存取结构能被单调张成方案m ( m ，缈) 计算，这里的矩 阵m 为 五 恐 武 毫 _ 1 # 1 其中当lsf 一时而f o ) ；当l s s 疗且f 歹时五x ， 缈： l ，刀) 一尸= a ，见 是一个一一映射，其中矽( f ) = 只，l f 刀。 单调张成方案和线性密钥共享体制的关系如下： 定理2 2 【2 1 1 设p = 和i ，一，见) 是参与者集合，r 是p 上的存取结构，弄是r 的单