（计算机软件与理论专业论文）基于双线性配对的加密方案及密钥协商协议.pdf

基于双线性配对的加密方案及密钥协商协议 摘要 2 0 0 0 年，s a k a i 等学者，以及j o u x 分别开创性地利用双线性配对构 造出静态( 非交互式) 身份基密钥共享方案和一轮三方密钥协商协议， 解决了公钥密码学界的两个著名难题。从那以后，双线性配对作为一种 基本工具在设计崭新密码方案方面的有效作用不断被挖掘出来，出现了 大量新颖而又实用的密码方案。例如，身份基加密方案、无证书加密方 案、短签名方案、双方及多方身份基密钥协商协议等等。 利用双线性配对构造各种新型密码方案的研究，是当前公钥密码学 研究领域的一个热点。另外，基于计算复杂性理论的可证安全技术也已 成为分析这些新提出方案安全性的一种必要手段。本文工作围绕基于双 线性配对的新型密码方案的设计与可证安全展开，主要研究内容分为两 大部分：( 1 ) 公钥加密方案，包括身份基加密方案和可托管公钥加密方 案；( 2 ) 双方身份基认证密钥协商协议，分别包括随机预言模型下和标准 模型下安全的协议。主要研究成果如下： 一、高效身份基加密方案的设计与分析。深入探讨了身份基加密方 案的实际应用场景，即多管理域环境。基于s a k a i o h g i s h i k a s a h a r a 身份 基密钥抽取方法，我们提出了一个新的身份基加密方案。在我们的新方 案中，加密者可以在获得意定解密者所属域的主公钥之前离线预先加密 明文，因此它比著名的b o n e h f r a n e i n 方案在多域环境下更为实用和高 效，且与后者具有相同的安全级别，即它们的安全性都基于标准双线性 d i f f i e h e l l m a n ( b d h ) 假设。我们还详细讨论了该身份基加密方案的多种 应用，包括：全局托管e 1 g a m a l 加密、多接收者身份基加密以及身份基 代理重加密等。其中，我们提出的多接收者身份基加密方案比b a e k 等 学者的方案在多域环境下具有更好的扩展性。并且，我们提出的身份基 代理重加密方案成功解决了g r e e n a t e n i e s e 方案不能抵抗合谋攻击的问 题。它同时也是第一个能够抵抗合谋攻击的基于密钥分割策略的代理重 加密方案。 卜海交通大学博士学位论文 二、可托管公钥加密方案的设计与分析。提出了两个高效的可托管 公钥加密方案( 即带有两个解密密钥的公钥加密方案) 。其中，我们提出 的第二个方案是现有文献中所有同类方案中最为高效的一个，它使得用 户的密钥存储空间已经公钥长度降到最低，且去除了加密过程中的配对 运算，并能对明文进行离线预先加密。除此之外，它也是第一个可证安 全的可托管公钥加密方案，它的安全性基于标准双线性d i f f i e h e l l m a n ( b d h ) 假设。 三、随机预言模型下身份基认证密钥协商协议的设计与分析。首次 建立了认证d i f f i e h e l l m a n 协议和身份基认证密钥协商协议之间的对应 关系，提出了一种有效的协议平行设计方法。系统研究了身份基认证密 钥协商协议的前向安全属性，继而提出了一个在托管模式下( 即无p k g 前向安全) 达到完美前向安全的身份基认证密钥协商协议。在考虑预先 计算的情形下，所提新协议比w a n g 的协议更为高效。并且，我们利用 模块化证明方法，严格证明了所提新协议的基本安全属性及完美前向安 全性。 四、标准模型下身份基认证密钥协商协议的设计与分析。利用 g e n t r y 身份基加密方案，提出了第一个在标准模型下可证安全的身份基 认证密钥协商协议。并且，我们还给出了所提基本协议在无托管模式下 的扩展。 关键词：公钥密码学，双线性配对，身份基密码学，加密方案，可托管 公钥加密，认证密钥协商协议，可证安全 一一 r e s e a r c ho nc r y p t o s y s t e m sa n dk e ya g r e e m e n tp r o t o c o l s f r o mb i l i n e a rp a i r i n g s a bs t r a c t i n2 0 0 0 ，s a k a ie ta 1 a n dj o u xi n d e p e n d e n t l yf o u n dt h a tb i l i n e a lp a i r i n g sc o u l db eu s e d i nc o n s t r u c t i v ew a y st ob u i l dn e wc r y p t o g r a p h i cs c h e m e s ，b yp r e s e n t i n ga l li d e m i t y - b a s e d k e ys h a r i n gs c h e m ea n dao n e - r o u n dt r i p a r t i t ek e ya g r e e m e n tp r o t o c o l ，r e s p e c t i v e l y f r o m t h e no n ，n u m e r o u sn o v e la n dp r a c t i c a ls c h e m e sh a sb e e np r o p o s e du s i n gb i l i n e a rp a i r i n g s ， s u c ha si d e n t i t y - b a s e de n c r y p t i o n ( i b e ) s c h e m e s ，s h o r ts i g n a t u r es c h e m e sa n dt w o - p a r t y i d e n d t y b a s e dk e ya g r e e m e n tp r o t o c o l s b i l i n e a rp a i r i n g sh a v eb e e nu s e di n t e n s i v e l ya sa ni m p o r t a n tt o o lt od e s i g nn e w c r y p t o - g r a p h i cs c h e m e s ，a n dr e c e n d yt h i sa r e ah a sb e c o m ea h o ts p o ti np u b l i ck e yc r y p t o g r a p h y b e s i d e s ，p r o v a b l es e c u r i t yb a s e do nc o m p l e x i t yt h e o r yh a sb e c o m eap r e v a i l i n gm e t h o dt o e v a l u a t et h es e c u r i t yo ft h o s en e w l yp r o p o s e ds c h e m e s t h i st h e s i sf o c u s e so nt h ed e s i g n a n da n a l y s i so fn e w p a i r i n g b a s e dc r y p t o g r a p h i cs c h e m e s ，w h i c hi sd i v i d e di n t ot w o d i s t i n c t p a a s t h ef i r s tp a r ts t u d i e sp u b li ck e ye n c r y p t i o ns c h e m e s ，i n c l u d i n gi d e n t i t y b a s e de n c r y p t i o ns c h e m e sa n dp u b l i ce n c r y p t i o ns c h e m e sw i t ht w o p r i v a t ek e y s t h es e c o n dp a r te x p l o r e s t h ed e s i g na n da n a l y s i so fi d e n t i t y - b a s e da u t h e n t i c a t e dk e ya g r e e m e n tp r o t o c o l s ，i n c l u d i n g p r o t o c o l ss e c u r ei nt h er a n d o mo r a c l em o d e la n d t h es t a n d a r dm o d e l ，r e s p e c t i v e l y t h em a i n c o n t r i b u t i o n so ft h et h e s i sa l ea sf o l l o w s ： i 1 t h ed e s i g na n da n a l y s i so fe f f i c i e n ti d e n t i t y b a s e de n c r y p t i o ns c h e m e s f i r s t l y , w ei n v e s t i g a t et h er e a l - w o r l da p p l i c a t i o ns e t t i n gf o ri d e n t i t y - b a s e de n c r y p t i o ns c h e m e s ，i e ， t h em u l t i p l ea d m i n i s t r a t o rd o m a i ne n v i r o n m e n t ，a n dt h e nw ep r o p o s ean e wp r o v a b l y s e c u r es c h e m eb a s e do nt h es a k a i - o h g i s h i k a s a h a r ap r i v a t e - k e ye x t r a c t i o na l g o r i t h m i nt h en e ws c h e m e ，t h ee n c r y p t o rc a nh a v et h ep a i r i n gc o m p u t a t i o np r e c o m p u t e d o f f - l i n ea n dh e n c ei sm o r ep r a c t i c a lt h a nt h ef a m o u sb o n e h f r a n k l i ns c h e m ei nt h e m u l t i d o m a i ne n v i r o n m e n t w ea l s od i s c u s si t sa p p l i c a t i o n si ng l o b a le s c r o we 1 g a m a l e n c r y p t i o n ，m u l t i r e c e i v e ri d e n t i t y b a s e de n c r y p t i o na n dp r o x yr e e n c r y p t i o ns e t t i n g s n o t a b l y , o u ri d e n t i t y b a s e dp r o x yr e e n c r y p t i o ns c h e m es o l v e st h ec o l l u s i o na t t a c k p r o b l e mi nt h eg r e e n a t e n i e s es c h e m e ，a n d t ot h eb e s to u rk n o w l e d g e ，o u r si st h ef i r s t s u c hs c h e m et h a te m p l o y st h es o c a l l e dk e ys h a r i n gs t r a t e g y 2 t h ed e s i g na n da n a l y s i so fe s c r o w a b l ep u b l i ck e ye n c r y p t i o ns c h e m e s ( i e p u b l i c - k e ye n c r y p t i o ns c h e m e sw i t ht w od e c r y p t i o nk e y s ) w ep r o p o s et w o e f f i c i e n ts u c h s c h e m e s a n d 。o u rs e c o n ds c h e m ei st h em o s te f f i c i e n to n ea m o n ga l lt h ee x i s t i n g c o n s t r u c t i o n si nt h el i t e r a t u r e i te l i m i n a t e sp a i r i n ge v a l u a t i o ni nt h ee n c r y p f i o np r o - c e d u r ea n da tt h es a m et i m ee n a b l e so f f - l i n ep r e e n c r y p t i o n b e s i d e s ，i ti st h ef i r s t p r o v a b l y s e c u r ee s c r o w a b l ep u b h ck e ye n c r y p t i o ns c h e m ea n d i t ss e c u r i t yi sb a s e do n t h es t a n d a r db i l i n e a rd i f f i e h e l l m a n ( b d h ) a s s u m p t i o n 3 t h ed e s i g na n da n a l y s i so fi d e n t i t y b a s e da u t h e n t i c a t e dk e ya g r e e m e n tp r o t o c o l st h a t a les e c u r ei nt h er a n d o mo r a c l em o d e l f o rt h ef i r s tt i m e ，w ee s t a b l i s hac l o s er e l a - t i o n sb e t w e e na u t h e n t i c a t e dd i f f i e h e l l m a np r o t o c o l sa n di d e n t i t y - b a s e da u t h e n t i c a t e d k e ya g r e e m e n tp r o t o c o l s w ep u tf o r w a r d ap a r a l l e ld e s i g nm e t h o d o l o g yf o ri d e n t i t y b a s e da u t h e n t i c a t e dk e ya g r e e m e n tp r o t o c o l s w ei n v e s t i g a t et h ef o r w a r ds e c r e c yo f t h ei d e n t i t y - b a s e da u t h e n t i c a t e dk e ya g r e e m e n tp r o t o c o l sa n dp r o p o s ean e we f f i c i e n t p r o t o c o lw h i c ha c h i e v e sp e r f e c tf o r w a r ds e c r e c yi nt h ee s c r o w e dm o d e w h e n p r e - c o r e p u t a t i o ni sp o s s i b l e ，o u rn e wp r o t o c o li sm o r ee f f i c i e n tt h a tt h a to fw a n g l a s t l y ， w es t r i c t l yp r o v e dt h es e c u r i t yo ft h en e wp r o t o c o lb ya d o p t i n gt h em o d u l a rp r o o f t e c h n i q u e 4 t h ed e s i g na n da n a l y s i so fi d e n t i t y b a s e da u t h e n t i c a t e dk e ya g r e e m e n tp r o t o c o l st h a t a r es e c u r ei nt h es t a n d a r dm o d e l w ep r o p o s et h ef i r s ti d e n t i t y - b a s e da u t h e n t i c a t e d k e ya g r e e m e n tp r o t o c o lt h a tc a l lb ep r o v e ns e c u r ei nt h es t a n d a r dm o d e l b e s i d e s w e a l s oe x t e n do u rb a s i cp r o t o c o lt ot h ee s c r o w l e s sm o d e la n dt h ea c r o s s - d o m a i ns e t t i n g ， r e s p e c t i v e l y k e yw o r d s ：p u b l i c k e yc r y p t o g r a p h y , b i h n e a rp a i r i n g ，i d e n t i t y b a s e dc r y p t o g r a p h y , e n c r y p t i o ns c h e m e e s c r o w a b l ep u b l i c - k e ye n c r y p t i o n ，a u t h e n t i c a t e dk e ya g r e e m e n tp r o t o c o l ，p r o v a b l ys e c u r i t y 一一 i 木i a ra o ，1 ) + | o ，1 ) n 磊 z a | ib aob - 1 e e uf ef 、f ecf p r e 】 p r ej 卅 主要符号对照表 字符串木的比特长度 a 均匀随机地取自集合a 所有任意长度比特串组成的集合 所有长度为n 的比特串组成的集合 以死为模的剩余类环z n z 磊中所有对模乘可逆元构成的集合 表示比特串a 和b 的连接 表示相同长度的比特串a 和b 按位求异或 事件e 的补事件 事件e 和f 的和事件，即或者事件e 发生，或者事件f 发生 事件e 和f 的积事件，即事件e 和事件f 都发生 事件f 包含事件e ，即事件f 的发生蕴含事件f 的发生 事件e 发生的概率 事件f 发生的条件下，事件e 发生的条件概率 v i i i 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中己经注明引用的内容外，本论文不包含任何他个人或集体 已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 殆复 型星年4 月阜e t 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 学位论文作者签名：旦盟 日期：型年阜月4 日 指导教师签名： 日期：之竺缉二l 月l 日 第一章绪论 本章我们介绍论文的总体研究背景和主要研究内容，给出论文主要研究成果以 及总体结构安排。 1 1 研究背景 1 1 1 公钥密码学简介 密码学( c r y p t o g r a p h y ) 有着非常悠久的历史【6 】，早在2 0 0 0 多年以前的古罗马凯 撒大帝0 u l i u sc a e s a r ：公元前1 0 0 年一4 4 年) 时期，就被用于保密通信。当时，古 罗马军队根据一定的移位规则，打乱他们信件中的字母顺序( “加密”) ，以达到防 止敌方中途截获并读懂消息的目的。而只有知道这种字母移位规则的接收方，才能 恢复( “解密 ) 消息。在第二次世界大战期间，盟军成功地截获并破译了德军的 e n i g a m a 密码，被许多历史学家认为大大推动了盟军胜利的进程，在二战史上具 有重要意义。 1 9 4 9 年，信息论创始人s h a n n o n 发表了题为保密系统的通信理论1 8 7 1 的著名 论文，它被广泛认为是第一篇正式公开发表的密码学文献。该文把信息论引入密码 学，用统计的观点对信源、密码源和接收到的密文进行数学描述和定量分析，从而 将密码学置于坚实的数学基础之上，标志着密码学正式由一门艺术发展为一门科 学。 当前，信息化浪潮席卷全球，互联网i n t e m e t 的应用已经遍及世界的每个角落。 政府、企业以及个人都越来越多地利用计算机网络来存储和传递消息。然而，计算 机网络在给人们带来极大方便的同时，也带来了信息安全方面的严峻挑战：在开放 的互联网i n t e r n e t 和其它公共通信设施上进行的信息处理过程，容易遭受到恶意方的 窃听、篡改、伪造以及重放等攻击。而密码学成为保障网络时代信息安全的核心技 术，为用户提供以下四种不同服务【7 7 ，6 ，7 4 】： 机密性( c o n f i d e n t i a l i t y ) 确保传输的消息只有合法用户才能读懂。为了达到这 一目的，通常利用加密( e n c r y p t i o n ) 算法对消息进行加密，使得非授权用户( 被 称为敌手，或攻击者) 即使截获了密文，也不能解密获得明文。 数据完整性( d a t ai n t e g r i t y ) ：确保传输的消息不能被敌手以不被合法用户察觉 的方式篡改。为了达到这一目的，通常同时使用哈希函数( h a s hf u n c t i o n ) 和加 密算法，或者使用消息认证码( m a c ：m e s s a g ea u t h e n t i c a t i o nc o d e ) ，来检测对数 据的插入、删除和替换等篡改行为。 卜海交通大学博士学位论文 实体认证或身份识别( e n t i t ya u t h e n t i c a t i o no ri d e n t i f i c a t i o n ) 这一服务用以验证 特定用户的身份，确保身份不被冒充。 数据源认证( d a t ao r i g i na u t h e n t i c a t i o n ) 确保传输的消息来自特定的消息发送 方。数据源认证隐含着数据完整性，因为对数据的不合法篡改即意味着数据源 的改变。也就是说，只有在数据没有被篡改时，才有可能达到数据源认证。通 常，通过同时采用加密和m a c 码的方式能够达成这一安全服务。 密码系统分为两大类：私钥密码系统( 亦称对称密码系统) 和公钥密码系统( 亦称 非对称密码系统) 。在1 9 7 6 年之前，人们通常认为通信的两方( 一般用a l i c e 和b o b 来代表) 必须首先共享一些密码数据( 称为密钥) ，才有可能实现保密通信。这样的密 码系统之所以被称为对称密码系统，是因为通信双方必须握有相同的密钥。此类密 码系统的优点是计算效率高，但是它不可避免地存在以下问题：每一对用户之间都 必须共享一个密钥，当系统内用户数目增加时，必然带来密钥量的( 平方) 指数级增 长。在计算机网络通信中，大量密钥的产生、存储和分发的开销是十分巨大的。 1 9 7 6 年，针对私钥密码系统中密钥管理非常复杂这一难题，d i f f i e 和 h e l l m a n t 4 0 ) 在密码学的新方向一文中首次提出了“公钥密码学的概念，成 为密码学历史上的一次重大突破。在公钥密码系统中，用于加密消息的密钥( 称为 公钥) 和用于解密消息的密钥( 称为私钥) 是不同的。并且，从加密密钥推出解密密 钥在计算上不可行，因此加密密钥完全可以公开出去【2 2 i 。相比私钥密码系统，公钥 密码系统的最大优点在于，处在计算机网络两端的两个用户可以不必在事先共享一 个相同密钥的情况下，达成保密通信：消息的发送方只要获得了接收方的真实公钥 之后，即可实现对消息的加密。他们的这一开创性论文中还提出了数字签名的概 念：任何获得某个用户公钥的签名验证方，都可以利用这一公钥验证该用户利用她 的私钥产生的数字签名。文中虽然没有提出任何具体公钥加密和数字签名方案，但 却给出了第一个公钥协议：著名的d i f f i e h e l l m a n 密钥协商协测4 0 1 。这一协议使得 a l i c e 和b o b 可以通过在公开信道上传递消息的方式，协商达成一个共享密钥。1 9 7 8 年，r i v e s t ，s h a m i r 和a d l e m a n 给出了第一个实用公钥密码方案一r s a t 8 4 1 。二十多 年以来，r s a 方案仍然是应用最广泛的密码体制。此后，人们基于不同的计算问 题，提出了大量的公钥密码算法。其中具有代表意义的有基于整数分解问题的r a b i n 算法1 8 习以及基于有限域上离散对数相关难题的e 1 g a m a l 算法m 1 。 公钥密码系统虽然较好地解决了私钥密码系统中存在的密钥分发问题，但在传 统公钥密码系统中，对公钥的管理却不是一件轻松的事情：这种公钥密码系统中， 用户的公钥是某个集合上的一个随机比特串，如何才能将公钥比特串与公钥所对应 用户的身份关联起来? 为了解决这问题，k o h n f e l d e r t 6 3 】于1 9 7 8 年提出了“公钥证 书”的概念。公钥证书通常包含的内容有：公钥持有者的身份信息、公钥参数等信 一2 一 第一章绪论 息组成的消息，以及由可信第三方( 称为证书权威中心，或c a 中心) 对该消息的一 个数字签名。在此基础上，人们提出了基于公钥证书的公钥认证框架一公钥基础 设施( p k i ：p u b l i c k e yi n f r a s t r u c t u r e ) 。在p k i 系统中，人们在使用一个用户的公钥之 前，必须首先其公钥证书是否正确、合法和有效。由此可见，在基于公钥证书的密 码系统中，需要较大的存储空间用于存储众多用户的公钥证书。并且，验证众多用 户的公钥证书，带来了较大的计算开销。 为了进一步简化公钥密码系统中的密钥管理过程，s h a m i r l 8 6 于1 9 8 4 年首次提出 了身份基密码学( i b c ：i d e n t i t y b a s e dc r y p t o g r a p h y ) 的概念。在身份基密码系统中，用 户的公开身份信息( 例如电子邮件地址、地址、住址等等) 即可作为公钥。或者等 价的，可以利用这些身份信息，通过一个公开的算法直接计算出该用户的公钥。与 身份基公钥对应的私钥则必须由一个被称为私钥生成中心( p k g ：p r i v a t ek e yg e n e r a t o r ) 的可信第三方生成，并通过安全信道分发给用户。既然某个用户的身份信息就是她 的公钥，那么就根本不需要公钥证书来绑定公钥及其所有者身份。终端用户在欲使 用某个用户的公钥前，也不必查询获取公钥证书。唯一需要认证的仅是该用户所处 管理域的私钥生成中心p k g 的公钥( 本文将之称为域p k g 公钥) 。从这一点看，在 实际应用中身份基密码学并没有完全消除对公钥证书( 或者公钥目录) 的依赖。但 是，由于隶属于同一管理域的多个用户从同一个域p k g 处获得私钥，因此整个系统 对证书或目录的依赖程度被显著降低了f 6 9 】。 s h a m i r 在文献 8 6 中提出了一个基于整数分解的身份基数字签名方案，但是 如何找到一个安全实用的身份基加密( i b e ：i d e n t i t y b a s e de n c r y p t i o n ) 方案的问题， 直到2 0 0 1 年才被成功解决。虽然在此之前也有一些相关方案被提出，例如文献 4 3 ，9 6 ，9 7 ，7 9 ，5 8 ，但这些方案不是需要用到特殊硬件，就是需要p k g 拥有巨大的 计算能力，甚至要求终端用户不合谋从而计算获得p k g 的私钥。显然，这些方案 是无法付诸实际应用的。2 0 0 1 年，b o n e h 和f r a n k l i n 利用椭圆曲线上的双线性配对 首次提出了一个实用身份基加密方案，即著名的b o n e h f r a n k i ni b e 方案【| 0 】。同样在 2 0 0 1 年，c o c k s t 3 4 1 利用二次剩余理论构造了一个安全的i b e 方案，但是这一方案中 的密文扩张十分巨大，从而限制了它的实用性。b o n e h 和f r a n k l i n 的杰出工作不仅解 决了身份基密码学中构造实用加密方案的这一难题，还极大地推动了双线性配对在 密码学中的应用。 1 1 2 双线性配对密码学 19 9 3 年，当m e n e z e s ，o k a m o t o 和v a n s t o n e 7 6 l 将双线性配对( b i l i n e a rp a i r i n g ) 引 入密码学，并把它作为针对超奇异椭圆曲线( s u p e r s i n g u l a re l l i p t i cc u r v e ) 上离散对 数问题的攻击工具时，双线性配对的存在对于密码学来说似乎仅具有消极作用。 一3 一 卜海交通人学博上学位论文 人们对双线性配对的这种片面认识一直持续了七年之久，直到s a k a i ，o h g i s h i 和 k a s a h a r a t 1 ，以及j o u x 61 】的开创性工作为止。在2 0 0 0 年，他们分别利用双线性配 构造了身份基密钥共享方案和一轮三方密钥协商协议，解决了密码学界的两个著名 难题。紧接着，v e r h e u l 9 8 1 利用双线性配对，提出了一个所谓“可托管公钥加密”方 案的e 1 g a m a l 方案的变体。在这一方案中，每个用户的唯一公钥对应于两个解密密 钥：主解密密钥和托管解密密钥。其中，托管解密密钥由主解密密钥计算得出，而 从后者试图得到前者则在计算上不可行。这样，用户即使在将托管解密密钥交给可 信托管机构之后，她仍然可以利用主解密密钥进行解密和签名。也就是说，可托管 公钥加密方案仅利用一个公钥，同时达成了加密和不可否认两项安全服务。显然， 这在公私钥一一对应的普通加密方案中是不可能的，因为当唯一的私钥被托管之 后，它不能再被用于签名以提供不可否认服务。 我们注意到，上述三项利用双线性配对构造密码方案的开创性工作都早于b o n e h 和f r a n k l i n 【1 0 l 在身份基加密方面的工作。而正是基于与文献 9 3 】中完全相同的私钥 抽取算法( 我们称之为s o k 私钥抽取) ，b o n e h 和f r a n k l i n “j 】利用双线性配对成功地 设计出他们的身份基加密方案。这些杰出工作表明，双线性配对在构造密码方案方 面具有十分独特的作用：一方面，利用它能够解决利用其它工具无法解决的问题， 比如j o u x 的一轮三方密钥协商协议【6 1 】；另一方面，它还可以被用来构造一些具有 特殊性质的新型密码方案，比如v e r h e u l 的可托管公钥加密方案【堋1 。2 0 0 1 年以后， 双线性配对在设计崭新密码方案方面的独特作用被人们不断挖掘出来，出现了大量 新颖而又实用的密码方案，从而诞生了所谓双线性配对密码学( p b c ：p a i r i n g b a s e d c r y p t o g r a p h y ) 4 1 。顾名思义，它是研究双线性配对在密码学中应用，特别是构造公钥 密码方案的一个密码学分支，是目前公钥密码研究领域的一个重要方向。 同其它公钥密码学分支一样，双线性配对密码学的主要研究内容包括三个方 面，分别为加密方案、数字签名方案和密钥协商协议的设计与分析。特别地，双 线性配对在设计身份基密码方案和协议方面的应用，更是双线性配对密码学的主 要内容。另外，基于计算复杂性理论的可证安全( p r o v a b l es e c u r i t y ) 技术( 详见本文 第2 4 节) ，越来越受到密码学界的重视，几乎成为分析和评估所有公钥密码方案安 全性的标准程序。因此，可证安全技术也是双线性配对密码学中的重要内容。除此 之外，如何进一步提高基于双线性配对方案的计算效率，特别是减少方案或协议中 所需配对运算的数目( 总体运算数目或在线运算数目) ，是双线性配对密码学研究的 一个重要方向。关于双线性配对密码学的发展及现有方案的详细综述，可参见文献 【3 8 ，l ，5 3 ，4 】等。 一4 一 第一章绪论 1 2 研究内容和主要成果 本文全部工作围绕基于双线性配对的密码方案和协议的设计与分析展开，内容 涵盖双线性配对密码学三项基本内容中的两项：加密方案和密钥协商协议的设计与 分析。研究的主要目标是设计更加高效和实用的可证安全身份基加密方案、可托管 公钥加密方案和身份基认证密钥协商协议。 本文主要研究内容和成果概括如下： 1 在深入分析身份基加密方案的实际应用场景一多域环境( m u l t i d o m a i ne n v i r o n m e n t ) 的基础上，提出了一个高效身份基加密方案。我们给出了多域环境下身 份基加密方案的形式化定义，并严格证明了所提方案的安全性。通过与著名的 b o n e h f r a n k l i n 身份基加密方案【1 0 1 比较表明，新提出的方案在多域环境下更加 实用。特别是在多接收者身份基加密情形下，新提出方案显著减少了所需配对 计算的数目，因此在计算效率方面明显高于后者。 2 深入研究了可托管公钥加密，基于双线性配对提出了两个主动式可托管公 钥加密方案。通过与v e r h e u l 方案【9 8 1 及b o n e h f r a n k l i n 全局可托管e 1 g a m a l 方 案【l o ，lj 】的比较表明，所提新方案在计算上更加高效。我们的新方案也是目前 现有文献中第一个可证安全的可托管公钥加密方案。 3 在双方身份基认证密钥协商协议的设计与分析方面，本文首次建立身份基认证 密钥协商协议与认证d i f f i e h e l l m a n 协议【4 0 】之间的紧密联系，提出了一种十分 有效的协议设计方法。首先，在s o k 静态( s t a t i c ) 密钥共享协议1 9 3 】的基础上， 提出了半静态( s e m i s t a t i c ) 和动态( d y n a m i c ) s o k 密钥协商的概念，并将其分 别与静态、半静态和动态d i f f i e h e l l m a n 协议一一对应。根据这一巧妙对应关 系，我们提出了一种十分有效的身份基认证密钥协商协议的平行设计方法。特 别地，我们深入考察身份基认证密钥协商协议的前向安全属性，设计了一个在 托管模式下( 即无p k g 前向安全) 达到完美前向安全的身份基认证密钥协商协 议。在随机预言模型( r o m ：r a n d o mo r a c l em o d e ) 下，我们分别证明了所提协 议的基本安全属性和完美前向安全性。在考虑预先计算( p r e c o m p u t a t i o n ) 的情 形下，所提新协议比w a n g 】的协议更加高效。 4 首次研究了标准模型( s t a n d a r dm o d e l ) 下可证安全的身份基认证密钥协商协 议。利用g e n t r y 身份基加密方案【5 1 ，设计了一个托管模式下的身份基认证密 钥协商协议，并给出其在无托管下模式的一个扩展版本。我们在标准模型下 ( 即不利用随机预言假设) 严格证明了所提托管模式下基本协议的安全性。 一5 一 卜海交通人学博上学位论文 1 3 论文结构 本文后续章节结构安排如下： 第二章主要介绍了本文所需的基础理论和预备知识。主要包括双线性配对的定 义、相关复杂性假设、可证安全技术，以及本文所涉及密码方案及协议的形式化定 义和安全模型。 第三章给出一个多域环境下的高效身份基加密方案。我们首先深入考察多域环 境下身份基加密方案的系统需求，紧接着在b o n e h f r a n k l i n 单域环境下身份基加密 方案定义【0 ，1 的基础上，给出多域环境下方案的形式化定义。其次，我们详细描述 新提出方案，并将其与b o n e h f r a n k l i n 方案进行详细比较。然后，我们在随机预言 模型下将其安全性规约到标准双线性d i f f i e h e l l m a n 问题。最后，我们给出新提出方 案的扩展应用，包括：被动式可托管加密、多接收者身份基加密以及身份基代理重 加密。 第四章研究可托管公钥加密。我们提出两个新的主动式可托管公钥加密方案， 并将它们与目前现有文献中的同类方案进行比较，然后严格证明了我们所提第一个 方案的安全性。 第五章研究随机预言模型下可证安全的双方身份基认证密钥协商协议。首先简 要给出了一种平行协议设计方法，设计了一个在托管模式下达到完美前向安全的身 份基认证密钥协商协议，并详细证明了它的基本安全属性以及完美前向安全性。 第六章首先简要回顾了g e n t r y 的身份基加密方案瞰1 ，紧接着在此方案的基础 上。提出一个身份基认证密钥协商协议，并给出该协议在托管和无托管模式下的两 个版本。最后，我们在标准模型下，严格证明了所提托管模式下协议的安全性。 第七章对全文进行总结，并提出若干需要进一步研究的问题。 一6 一 第二章预备知识 本章我们首先介绍论文所需基础理论和背景材料，主要包括本文所有方案和协 议都用到的基本工具一双线性配对的定义、相关复杂性假设、可证安全技术，以及 本文所涉及密码方案及协议的基础知识。 2 1 计算复杂性基础 计算复杂性理论的目的是提供一种根据解决计算问题所需资源来对其进行分类 的机制。这些所需资源一般用时间，或者存储空间的形式来度量。我们首先介绍一 些必要的术语【6 8 1 ： 算法：算法是一个以某个变量为输入的计算过程，它在结束时会返回计算结 果。若一个算法对于某个固定的输入，它每次执行的步骤是固定的，那么我们 称它为确定性算法。与此对应，一个随机算法对于某个固定的输入，它每次执 行的步骤都是不同的。 算法运行时间：对于一个特定输入，算法的运行时间指它在终止前它所执行的 步数或者原子操作的个数。 最差情形运行时间：指算法对应于任何输入的运行时间的上界。它通常用输入 规模的一个函数来表示。 期望运行时间：指算法对应于具有某个特定规模的所有输入的平均运行时间。 它通常用输入规模的一个函数来表示。 一个算法的确切运行时间一般很难得到，通常的作法是采用近似记法。特别 地，我们通常采用0 ( ) 记号来表示一个算法运行时间的渐进上界的阶。 定义2 1 ：对于两个函数厂( f ) 和夕( z ) ，若存在一个正常数c 和一个正整数f 。，满足对 于所有z f 。，都有0 f ( 1 ) c 夕( z ) ，则我们说厂( f ) = d ( 夕( f ) ) 。 密码学中常用到可忽略函数、不可忽略函数和多项式时间算法的概念，它们的 定义如下： 定义2 2 ( 可忽略函数( n e g l i g i b l e ) ) ：称函数f ( t ) 是可忽略的，则对于任意多项式 p ( ) ，总存在一个自然数，使得对于所有f n ， 7 ，( f ) 0 ) 为输入的随机算法z 9 ，在以k 的多项式时间内运行，输出关 于两个群g 1 和g 2 的描述、它们共同的素数阶p ，以及一个可容许的双线性配对 芭：g 。g 1 _ g 2 的描述，则我们称这个算法为一个b d h 参数生成器。 定义2 1 4 ( 双线性d i f f i e h e l l m a n ( b d h ) 问题) ：假设群g 1 、g 2 、生成元p 及芭的为 上面所定义的参数。( g 1 ，g 2 ，邑) 中的b d h 问题定义如下：给定( p ，a p , b p , c p ) ( 其 中，随机元素o ，b ，c