（计算机系统结构专业论文）基于双线性对的签名体制及紧安全规约研究.pdf

基于双线性对的签名体制及紧安全规约研究 摘要 双线性映射和可证安全技术正在当前的密码学界、代数学界甚至业界全面展 开，这正是需要密码学作出回答的前沿课题，具有相当深刻的实践意义。在此背景 下，本文专注于这两个方面的研究，就紧安全性规约问题、基于双线性对技术的密 码构件设计展开论述，提出了新颖有效的密码算法。本文的主要贡献及创新点为： ( 1 ) 详细梳理了双线性对技术的研究与发展，给出了可证安全知识概述。 本文不仅概述了数字签名的形式化定义以及密码学中的可证安全思想，还 认真梳理了国内外代数学界和密码学界的主要论文和相关专著；在代数学和计 算复杂度理论的框架中，厘清了椭圆曲线、双线性映射以及椭圆曲线密码的概 念和应用；从局限性和可行性两个角度对密码学中的超奇异椭圆曲线进行综合 分析；给出了基于身份的密码系统的定义、数字签名算法的可证安全性研究现 状、紧安全性规约的意义以及代理签名的安全性和特殊代理签名适用范围等方 面的一般性表述。 ( 2 ) 提出了一个著名短签名方案和相应环签名体制的新的安全性证明，新的结论具 有紧规约的特点。 长度比较小的数字签名在现实中有许多应用，尤其是在低带宽通讯环境 下。在一个环签名体制中，任意一个人都可以选取任意一群人作为可能的签名 者，然后使用自己的私钥和其他所有人的公钥对任意消息产生环签名，而不需 要征得这些人的同意或是帮助。本文首先回顾了著名的b l s 短签名体制和在 此基础上设计的环签名方案，然后给出了这两个体制的新的安全性证明，新的 证明具有紧安全性规约这一良好性质。新的结论一方面加强了我们对b l s 体 制和相应的环签名方案的安全性所持有的信心度，另一方面也可以较好地划分 c d h 假设与1 ”p c d h 假设之间的强弱对比。 ( 3 ) 提出了基于双线性对技术的可验证加密签名体制并给出了形式化的安全性分 析，提供了标准模型下具有紧安全性规约的不可伪造性证明。 可验证加密签名在乐观的合同签署协议中用于实现最优公平交易。因此讨 论可验证加密签名算法具有很强的理论意义和潜在的应用价值。本文对可验证 加密签名及其安全性进行了严格定义，设计了两个可证安全的可验证加密签名 方案，并给出了它们的紧安全性规约的证明，引人注意的是安全性规约都是在 标准模型下给出的。 上海交通大学博士学位论文 ( 4 ) 基于双线性对技术设计了新颖有效的多代理签名、代理多签名、多代理多签名 以及代理签密体制。 在代理签名基本知识的基础上，本文全面阐述了多代理签名、代理多签 名、多代理多签名等体制的使用环境、概念以及相应的安全性需求，并首次使 用双线性对技术设计了多代理签名、代理多签名体制和基于身份的多代理多签 名方案，同时对各个算法的安全性有效性进行了分析。这样设计的一个优点 是方案的安全性不再依赖于较强的判定性d i x i e h e l l m a n 假设，从而具有更强 的安全性。 在一个签密方案中，消息加密和消息签名可以在一个逻辑步骤中同时实 现。与传统的先签名再加密相比，签密需要计算代价更小、通讯带宽更少，效 率显著提高。本文首先从形式化角度给出签密的定义及其安全模型，然后针对 代理签名只能提供授权认证而不能提供保密性这一问题，设计了一个基于身份 的代理签密算法，该算法在基于身份的环境中，能够组合代理签名和加密技术 的功能从而扩展了代理签名的概念，解决了代理签名不能提供保密性的问题。 本文最后简要总结全文，并给出了笔者对可证安全和双线性对技术发展前景的 思考以及笔者今后可能展开的研究方向和思路。 关键词：可验证加密签名，短签名，代理签密，多代理签名，代理多签名，多代理 多签名，基于身份的密码算法，双线性对，紧安全性规约 一i i r e s e a r c ho ns o m ep a i r i n g b a s e dd i g l l - a l s l g n a l - u r e sa n dt i g h ts e c u r i t yr e d u c t i o n s a b s t r a c t b i l i n e a rm a p s ，p r o v a b l es e c u r i t ya n d t i g h tr e d u c t i o nh a v eb c c o m ef a s h i o n a b l ei s s u e si n e r y p t o g r a p h i ec o m m u n i t y n u m e r o u sp a i r i n g - b a s e dp r i m i t i v e sw i t hp r o v a b l es e c u r i t yh a v e b e e nc o n s t r u c t e d ，s u c ha ss h o r ts i g n a t u r e sa n di d e n t i t y - b a s e ds y s t e m s ，e r e t h ed i s s e r t a t i o n w i l lf o c u so nt h ed i s c u s s i o n so f p a i r i n g - b a s e de r y p t o g r a p h i ca l g o r i t h m sa n d o f t i g h ts e c u r i t y r e d u c t i o n o u rc o n t r i b u t i o n sa n dm a i nc r e a t i v ep o i n t sc a nb ec l a s s i f i e di n t of o u rp a r t sa s d e p i c t e db e l o w ( 1 ) w e n a r r a t ed c t a j l e d l yt h ep r o g r e s so f b i l i n e a rp a i r i n g sa n d p r o v a b l es e c u r i t y t h ed i s s e r t a t i o nb r i e f l yi n t r o d u c e ss o m ep r e l i m i n a r i e si n c l u d i n gp r o v a b l es e c u n t ya n dd i g i t a ls i g n a t u r e s i na d d i t i o n ，w ed e s c r i b eb a s i cn o t i o n sa n da p p l i c a t i o n si n c r y p t o g r a p h ya n da l g e b r ac o m m u n i t y , s u c ha se l l i p t i cc r r v e s ，s u p e r s i n g u l a rc u r v e s ，b i - l i n e a r p a i r i n g s ，a n d i d - b a s e d c r y p t o g r a p h y , e t e b e s i d e s ，w es u m m a r i z er e c e n t r e s e a r c h p r o g r e s so fp r o v a b l ys e c u r es i g n a t u r e s ，s i g n i f i c a n c eo ft i g h tr e d u c t i o n s ，a n ds e c u r i t y r e q u i r e m e n t so f p r o x ys i g n a t u r e s ( 2 ) w ep r e s e n tn e ws e c u r i t ya r g u m e n t so f k n o w ns h o r ts i g n a t u r e sa n dr i n gs i g n a t u r e sw i t h t i g h tr e d u c t i o n s d i g i t a ls i g n a t u r e sw i t hs m a l ls i z e sa r eu s e f u li ns o m es i t u a t i o n s ，e s p e c i a l l yi n b a n d - l i m i t e ds e t t i n g s r i n gs i g n a t u r ea l l o w sau s e rt op r o v et h a ta m e s s a g ei ss i g n e d b yo n eo fp o s s i b l es i g n e r sw i t h o u tr e v e a l i n gt h ei d e n t i t yo ft h ea c t u a ls i g n e r w e f i r s tr e v i e wb l ss h o r ts i g n a t u r e sa n dc o r r e s p o n d i n gr i n gs i g n a t u r e s ，t h e np r e s e n tn e w s e c u r i t yp r o o f sf o rt h e m , w h i c hs h o wt h a to p t i m a lr e d u c t i o n se x i s tf r o mt h el m - c d h a s s u m p t i o n t h en e wr e s u l t si n c r e a s eo u rc o n f i d e n c ei nt h es e c u r i t yl e v e l so f t h et w o s c h e m e s ( 3 ) n e wp a i r i n g - b a s e dv 面a a b l ye n c r y p t e ds i g n a t u r e sa r ep r o p o s e d t h e s ea c h e m e sa r c s u p p o r t e dw i t hf o m m ls e c u r i t yp r o o f sa n dt i g h tr e d u c t i o n si nt h es t a n d a r dm o d e l v e a f i a b l ye n c r y p t e ds i g n a t u r e s ( v e s s ) a r ee m p l o y e di no p t i m i s t i cc o n t r a c ts i g n - h a gp r o t o c o l st oa c h i e v ef a i re x c h a n g e w ef o r m a l l yd e f i n et h en o t i o n so fv e s sa n d 上海交通大学博士学位论文 s e c u l ev e s s ，d e v i s et w o p a i r i n g - b a s e dv e ss c h e m e s ，a n de x h i b i tc o r r e s p o n d i n gs e - c u r i t ya r g u m e n t sw i t ht i g h ts e c u r i t yr e d u c t i o n 丘o mq - s d ha s s u m p t i o ni nt h es t a n d a r d m o d e l b o t hl m - c d ha n dq - s d ha s s u m p t i o n sa r es o m e w h a ts t r o n g ，a n di ti si n t e r e s t i n g t od e v i s er i n gs i g n a t u r e sa n dv e s sb a s e do nw e a k e ra s s u m p t i o n sw i t ht i g h ts e c u r i t y p r o o f s ( 4 ) w es y s t e m a t i c a l l yd e s i g nm u l t i p r o x ys i g n a t u r e ，p r o x ym u l t i s i g n a t u r e ，m u l t i p r o x y m u l t i - s i g n a t u r ea n dp r o x y - s i g n c r y p t i o ns c h e m e s w ef i r s te x h i b i tt h es c e n a r i o sa n dn o t i o n so f m u l t i - p r o x ys i g n a t u r e s ， p r o x y ( s t r u c t u r e d ) m u l t i s i g n a t u r e s ，m u l t i p r o x ym u l t i s i g n a t u r e s ，t h e nd e v i s ec o i l e - s p o n d i n ga l g o r i t h m sf r o mb i l i n e a rp a i r i n g sa n ds u p p o r tt h e s es c h e m e sw i t he f f i c i e n c y a n ds e c u r i t ya n a l y s i s a s i g n c r y p t i o ns c h e m ei sac r y p t o g r a p h i cm e t h o dt h a tf u l f i l l sb o t l lt h ef u n c t i o n s o fs e c u r ee n c r y p t i o na n dd i g i m ls i g n a t u r e ，b u tw i t hac o s ts m a l l e rt h a nt h a tr e q u i r e d b ys i g n a t u r e - t h e n - e n c r y p t i o n w ef i r s tf o r m a l l yd e f i n et h ep r i m i t i v es i g n c r y p t i o na n d s o c l l r es i g n c r y p t i o n , t h e nc o n s t r u c ta ni d e n t i t yb a s e dp r o x ys i g n e r y p t i o ns c h e m et o p r o v i d ec o n f i d e n t i a l i t ya sw e l la sa u t h e n t i c a t i o n l a s t l y , w ec o n c l u d et h ew h o l ed i s s e r t a t i o na n dd e s c r i b ep o s s i b l er e s e a r c hl i n e si nt h e n e a rf u t u r e k e yw o r d s ： v e r i f i a b l ye n c r y p t e ds i g n a t u r e s ，s h o r ts i g n a t u r e s ，p r o x ys i g n c r y p t i o n , m u l t i - p r o x ym g n a t u r e s ，p r o x ym u l t i - s i g n a t u r e s ，m u l t i - p r o x ym u l t i s i g n a t u r e s ，i d e n t i t yb a s e d p r i m i t i v e s ，b i l i n e a rp a i r i n g s ，t i g h ts e c u r i t yr e d u c t i o n i v i x 主要图表索引 2 1 椭圆曲线上的加法运算 2 2 安全性等级与相应的安全参数长度( 6 豇订 2 3 各系统计算开销的大致比较( 计算单元) 2 4 密钥长度、签名长度、密丈长度比较 2 5 超奇异椭圆曲线安全乘子。 2 6 密码学中感兴趣的部分超奇异椭圆曲线。 2 7 1 个t a t e 配对执行时问( ” ) 2 8 不同算法的签名、验证执行时间比- m m s ) ( p l l l1g h z ) 2 9 基于双线性对的系统中的复杂度假设之间的关系。 2 i o 基于身份酌体制中的私钥请求。 2 1 l 基于身份的体制中的私钥发放。 2 1 2 基于身份的加密与解密 2 1 3 基于身份的签名与验证 2 1 4 预言机回放攻击 3 1 可验证加密签名方案， 3 2 可验证加密签名方案， 4 1 系统初始化 4 2 多代理签名生成。 4 3 子代理与代理生成。 4 4 串行并行图 4 5 签名验证。 4 6 代理证书生成 4 7 多代理多签名生成。 4 8 多代理多签名验证 m也屹坦m垮垮：2托体悸憾悖扒 铝鲐 们甜田n弭” l i s to ff i g u r e s f i g 2 1a d d i t i o ni ne l l i p t i cc u r v cg r o u p ， 1 0 f i g 2 1 0p r i v a t ek e yq u e r y i n gi ni d b a s e d s y s t e m s ，1 8 f i g 2 11 p r i v a t ek e yd i s t r i b u t i o ni ni d - b a s e ds y s t e m s 1 8 f i g 2 1 2e n c r y p t i o na n dd e c r y p t i o ni ni d - b a s e ds y s t e m s ，1 8 f i g 2 1 3s i g n i n ga n dv e i l f y i n gi ni d - b a s e ds y s l e m s ，1 9 f i g 2 1 4o r a c l er e p l a ya t t a c k s ，2 1 f i g 2 2s e c u r i t yl e v e l sa n dc o r r e s p o n d i n g p a r a m e t e r s ，1 2 f i g 2 3c o m p a r i s o n o f c o m p u t a t i o n c o s t s ( u n i 0 ，1 2 f i g 2 4c o m p a r i s o no fs i z e so fk e y s ，s i g n a t u r e sa n dc i p h e r t e x t s ，1 2 f i g 2 5s e c u r i t ym u l t i p l i e ro f s u p e r s i n g u - l a re l l i p t i cc u r v e s ，1 4 f i g 2 6s o m ei n t e r e s t i n gs u p e r s i n g u l a re l - l i p t i co l i v e s ，1 5 f i g 2 7c o m p u t a t i o nc o s to f1t a t ep a i r - i n g ，1 5 f i g 2 8c o m p a r i s o no f c o m p u t a t i o nc o s t s o f s i g n i n ga n dv e r i f i c a t i o n , 1 5 f i g 2 9r e l a t i o n so fc o m p l e x i t ya s s a m p - t i o n so f p a i r i n g b a s e ds y s t e m s ，16 f i g 3 1v e r i f i a b l ye n c r y p t e ds i g n a t u r e s c h e m e 4 8 f i g 3 2v e n f i a b l ye n c r y p t e ds i g n a t u r e s c h e m e , 5 5 f i g 4 1s y s t e ms e t u p ，6 0 f i g 4 2m u l t i p r o x ys i g n a t u r eg e n e r a t i o n , x i 6 l f i g 4 3s u b p r o x ya n dp r o x yg e n e r a t i o n , 6 6 f i g 4 4s e r i e s - p a r a l l e lg r a p h , 6 9 f i g 4 5s i g n a t u r ev e r i f i c a t i o n , 7 1 f i g 4 6p r o x yc e r t i f i c a t eg e n e r a t i o n , 7 4 f i g 4 7m u l t i p r o x ym u l t i s i g n a t u r eg e n - e r a t i o n ，7 5 f i g 4 8m u l t i p r o x ym u l t i - s i g n a t u r ev e d f i c a t i o n ，7 6 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名：查叠篁 日 期：逊年望月 垄e t 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 日期：碰年月鱼日 日期：山挥手月卫日 1 1 背景介绍 第一章绪论 信息安全是涉及我国经济发展、社会发展和国家安全的重大问题。在信息化社 会里，没有信息安全的保障，国家就没有安全的屏障。研究计算机网络中任一用户 都可以和其中的一个用户进行秘密交换信息就是一项重要课题。1 9 7 6 年，美国斯坦 福大学的d i f i i e 与h e l l m a n 在“密码学的新方向”一文中提出了公钥密码体制的新概 念【5 6 】，可用于解决此问题，从而开创了现代密码学的新领域。后来在此领域内提出 了一系列的公钥密码体制及新的应用与概念【5 l ，5 2 ，2 4 ，例如数字签名【7 3 】、概率加 密体制【7 2 】、门限方案【8 】等，形成了较为系统的公钥密码学 3 8 ，1 4 7 】。 事实上，在实际应用中大多数情况下的安全需求不是为了数据的保密，而是为 了保证数据的可靠性及数据源的不可否认性，满足这种要求的方法就是使用数字签 名。数字签名是密码学中的重要问题之一，它是传统手写签名的模拟，能够实现用 户对电子形式存放消息的认证。数字签名的目的有：使接收方能够确认发送方的签 名，但不能伪造；发送方发出签了名的消息给接收方后，就不能否认它所签发的消 息；一旦收发双方就消息的内容和来源发生争执时，可由仲裁者解决收发双方的争 端。另外，和手写签名一样，数字签名也可以带有时间戳，从而可以获得前向安全 性，即当前的密钥泄漏不会影响到以前签名的有效性。 数字签名方案一般包括三个过程：系统的初始化过程、签名产生过程和签名验 证过程。系统初始化过程产生数字签名方案中用到的一切参数，有公开的，也有秘 密的。在签名产生的过程中用户利用给定的算法对消息t t 产生签名s i g n ( m ) ，这种签 名过程可以公开也可以不公开。在签名验证过程中，验证者利用公开验证算法对给 定的消息的签名进行验证，得出签名的有效性。 下面给出数字签名的形式化定义： 系统的初始化 系统的初始化产生签名方案中的基本参数( m ，s ，k ，s g ，w r ) ，其中：m 为消 息集合；s 为签名集合：k 为密钥集合，包含公钥和私钥；s g 为签名算法集 合；r 为签名验证算法集合。 签名产生过程 密钥集合k ，k k ，相应的签名算法为s i g n k s g ，s i g n ：m s 。对任 意的消息t o , m ，有s = s i g n ，且s s ，那么s s 为消息m 的签名，将签名 消息组( m ，s ) 发送给签名验证者。 上海交通大学媳士学位论文 签名验证过程 对应密钥集合k ，k ，有签名验证算法 v e r f y k ：m s _ o c c e 讲，r e j e 以 ( 或 1 ，o ) 或 v a l i d ，i n v a l i d ) ，v e r i f y k v e r ， 且： ， verifyk沪：?爹s-signk(一x),e3ect y 5 l g n k ( x )l r 尹 签名验证者收到( m ，s ) 后，计算v e r i f y k ( m ，s ) ，若v e r i f y k ( m ，8 ) = a c c e p t ，签名 有效：否则，签名无效。 这里，前两个算法是概率性的，三个算法均应在期望的多项式时间内运行。 对于密钥集合k ，签名函数s i g n k 和签名验证函数v e r i f y 是容易计算的。一般情况 下，s i g n 。可以公开也可以不公开，而函数v e r i f y k 是公开的。同时还要求对任意的消 息m ，从集合s 中计算8 使得v e r i f y k ( m ，s ) = a c c e p t 是困难的，也就是说，攻击者在不 知道密钥的情况下要对消息m 产生有效的签名8 是不可能的。 目前人们已经设计出许许多多不同种类的数字签名方案。根据不同的标准将这 些数字签名方案进行不同的分类： 基于数学难题的分类 根据数字签名方案所基于的数学难题，数字签名方案可分为基于离散对数问题 的签名方案 6 i 】、基于因子分解问题( 包括二次剩余问题) 的签名方案 3 3 ，1 4 3 、 基于椭圆曲线 7 6 】的数字签名方案、基于有限自动机理论 1 5 9 的数字签名方案 等。比如e 1 g a m a l 数字签名方案和d s a 签名方案都是基于离散对数问题的数 字签名方案。将离散对数问题和因子分解问题结合起来，又可以产生同时基于 离散对数问题和因子分解问题的数字签名方案，也就是说，只有离散对数问题 和因子分解问题同时可解时，这种数字签名方案才是不安全的，而在离散对数 问题和因子分解问题只有一个可解时这个方案就仍是安全的。最近几年中也出 现了众多由椭圆曲线延伸而来的基于双线性对技术的数字签名方案 9 0 】。 基于签名用户的分类 根据签名用户的情况，可将数字签名方案分为单个用户签名的数字签名方案和 多个用户签名的数字签名方案。一般的数字签名是单个用户签名方案。而多个 用户的签名方案又称为多重数字签名方案【1 2 l 】。根据签名过程的不同，多重数 字签名可分为有序多重数字签名方案【3 5 和广播多重数字签名方案 2 4 】。 基于数字签名特性的分类 根据数字签名方案是否具有消息自动恢复特性，可将数字签名方案分为两类： 一类不具有消息自动恢复特性；另一类具有消息自动恢复特性【2 】。一般的数字 一2 一 第一章绪论 签名是不具有消息自动恢复特性的。1 9 9 4 年，n y b e r g 和r u e p p l e 1 2 4 】首次提 出一类基于离散对数问题的具有消息自动恢复特性的数字签名方案。 数字签名的批验证协议 数字签名方案主要包含两个过程：签名产生过程和签名验证过程。为了提高数 字签名方案的效率，一方面要设计出高效的数字签名方案，减少存储空间，缩 小通信带宽：另一方面要提高签名产生和签名验证的效率。批验证协议是提高 数字签名方案效率，加快签名验证速度的有效方法，因此对数字签名方案设计 一种可靠的批验证协议具有重要意义 1 6 ，4 4 。当然，批验证协议的产生亦为签 名方案的安全性提出了新的挑战。 另外还有其他一些数字签名方案，比如由c h a u m 和h e y s t 4 2 1 在1 9 9 1 年首次提 出的群签名、c h a u r f l 在1 9 8 2 年提出的盲签名【4 0 】、不可否认签名 4 l ，5 5 ，8 7 1 、r i v e s t 等人提出的环签名 1 4 4 】、多重数字签名【8 6 】、代理签名 1 1 2 ，1 1 3 】、指定验证者签 名 8 8 1 等等。 1 2 随机预言机模型 密码学中的哈希函数是一个确定的函数， 定长比特串的哈希值。设h 表示一个哈希函数， 望h 具有性质 1 5 6 】： 它的输出是将任意长的比特串映射为 其固定的输出长度j 矸| j l h l 表示。我们希 混合变换：对于任意的输入z ，输出的哈希值 ( z ) 应该和区间【o ，2 陋l i c e 均匀的二 进制串在计算上是不可区分的。 抗碰撞攻击：要计算两个值z ，y ，且石y ，使得h ( z ) = ( ) ，在计算上应 该是不可行的。为使这个性质成立，要求h 的输出空间应该足够大。一般 地，川最小应该为1 2 8 ，而典型的值为1 6 0 。 抗原像攻击：已知一个哈希值h ，计算一个输入串z ，使得h ( x ) = h ，在计算上 是不可行的。这个性质同样也要求h 的输出空间足够大。 有效性：给定一个输入串z ，危 ) 的计算可以在川的低阶多项式( 理想情况下是 线性的) 时间内完成。 哈希函数广泛应用于密码学中。比如在数字签名体制中，哈希函数一般用来产 生消息摘要。这种做法是为将要签署的消息增加一个可以验证的冗余，以便这个哈 希消息包含可以识别的信息。这时可以依赖包含在签名消息中的可识别冗余信息来 实现数字签名体制的安全性，如p s s 【2 l 】方案。在公钥密码系统中，哈希函数被用 于实现密文正确性验证机制。对于要获得可证安全的抗主动攻击的加密体制来说， 这个机制是必不可少的，如r s a - o a e p 【2 0 以及c r a m e r - s h o u p 【5 l 】方案。 一3 一 上海交通大学博士学位论文 如果将哈希函数的“混合变换”性质中的“与均匀分布在计算上不可区分”换成“是 均匀的”，则就将该哈希函数变成是一种很强的，虚构的函数，称之为随机预言 机 1 9 ，1 1 4 1 。之所以将随机预言机称为是虚构的函数，是因为就我们所知道的计 算模型中还没有如此强大的计算机器或机制。在随机预言机假设下仅允许预言 机访问函数h ，求出函数h 在点z 的值是得到h c x ) 的唯一有效的方法，甚至当其他的 值h ( x 1 ) ，h ( z 2 ) ，已经计算出来，这仍然是正确的，即计算 ( z ) 的唯一方法就是访问 预言机。这可以想象为在一本巨大的关于随机数的书中查询丘( z ) 的值，对于每个z ， 有一个完全随机的值 ( o ) 与之对应。 随机预言机这种强大的虚构函数组合了以下三种性质：确定性、有效性和均匀 输出。该模型是一种探索性分析一个密码学殿型和协议的方法，它为密码学理论和 实践提供了一座桥梁。在基于随机预言机模型( r a n d o m o r a c l e m o d e l ，r o m ) 的安全 性证明技术中，不仅假设随机预言机存在，而且使用了一个特殊的代理一s i m o n 仿 真器。当某人想对某个值应用随机预言机时，譬如对a 应用g ，他就必须对s i m o n 做 一个随机预言机询问：他将。提交给s i m o n ，然后从s i m o n 那里收到询问结果g ( a ) 。 s i m o n 仿真预言机的行为如下：对于预言机g ，s i m o n 要维护一个g 表，它包含所有 的( n ，g ( o ) ) 对，o 是在g 的整个历史中被询问过的值。对每一个询问o ，s i m o n 检查n 是 否已经在表中，如果是，他就将g ) 作为结果返回( 确定性) ；否则他在g 的值域范围 内随机选取一个新值作为g ( a ) ，将这个新值作为结果返回( 均匀性) ，并将( 口，g ( n ) ) 添 加在表中。表开始为空，随着提问的增加而增加。s i m o n 可以将他的表以第一个元 素排序。对于每一个询问，在个排序的元素中查找可以在l o gn 时间内完成( 有效 性) 。 因密码学意义上的哈希函数可以很好地仿真随机预言机的行为，所以随机预言 机模型下的可证安全技术( 参见1 3 节) 在现实世界中确实提供了一种令人信服的启发 式见解。尽管c a n e t t i 、g o l d r e i c h 和h a l e v i 【3 7 】证明存在签名和加密方案，在r o m 下 是可证安全的，但在实际中不会有任何安全的实现，g o l d r e i e h 本人仍认为基于r o m 技术的安全性证明是一个有用的试验台；在该试验台上性能不好的密码体制( 即不能 通过这个合乎情理的检查) 应该被丢弃。目前，大多密码学研究者认为，设计一个密 码学方案，使其在r o m 中可证安全是一个很好的工程准则。 基于这一方法，b e l l a r e 2 0 首次分析并提出了可证明安全的r s a 加密算法 o a e p 。相继s c h n o r r 【1 4 8 数字签名算法 1 3 7 - 1 4 0 ，r s a 签名算法等的安全性 2 l ，4 7 ， 4 8 都得到了严格的证明。 与随机预言机模型相对应的是标准模型 6 9 ，7 7 ，1 6 1 1 。这是一个不需要随机预言 机假设的模型，因此，理想情况下我们更希望得到一个在标准模型下的可证安全的 实用算法，这不会带来随机预言机模型下所面临的批评。 一4 一 第一章绪论 1 3 可证明安全思想概述 当前，公钥密码的安全性概念已经被大大扩展了。像著名的r s a 公钥密码算 法 1 4 3 、r a b i n 公钥密码算法 1 4 2 和e i g a m a l 公钥密码算法 6 1 1 都已经得到了广泛应 用。我们要求公钥密码算法不仅在理论上而且在具体的实际应用中都是安全的。比 如，公钥加密算法根据不同的应用，需要考虑选择明文安全、非适应性选择密文安 全和适应性选择密文安全三类 5 1 ，2 9 1 。数字签名根据需要也要求考虑抵抗非适应 性选择消息攻击和适应性选择消息攻击等 7 3 ，3 1 ，3 4 ，6 0 。近年来，公钥密码学研 究中的一个重要内容一可证安全密码 1 9 ，1 4 ，1 5 4 ，1 5 2 及安全性证明的紧安全性规 约 2 1 ，9 3 ，1 6 2 ，6 6 ，9 7 】正是致力于这方面的研究。 一般地，为了给一个系统提供可信任的安全属性，我们需要对该系统的安全指 标进行量化，即给它提供可证明安全性。简单来说，就是借用形式化的手段，以数 学定理的形式，通过多项式时间规约，把一个系统的安全性转换成复杂度理论中的 众所周知的困难问题。 要达到这一目标，首先需要建立攻击者m a l i c e 的模型，即对攻击者的攻击能力 作出适当的建模。一般采用d o l e v - y a o 的主动攻击者模型1 5 8 ，把m a l i c e 抽象为一预 言图灵机。 其次，定义攻击者m a l i c e 的目标。比如关于加密算法，定义攻击者m a l i c e 的目 标是不可区分性或者不可延展性 1 5 ，1 2 3 ，1 2 8 t ；对于数字签名算法，攻击者m a l i c e 的目标是存在不可伪造性 7 3 ，6 4 ；对于密钥交换协议 2 3 ，1 5 3 ，攻击者m a l i c e 的目 标是通过攻击获得的会话密钥和随机数的不可区分性。 把这二者结合起来，就构成了对密码系统的安全性定义，如对于加密算法来说 有i n d - c p a ，i n d c c a ，n m c p a ，n m c c a 安全 1 5 】，以及数字签名的u f - c m a 安全 5 2 】。 定义好了攻击者m a l i c e 的模型和目标之后，接下来要做的就是通过一系列的游 戏来模拟攻击者m a l i c e 。这些游戏在挑战者和m a l i c e 之间进行，挑战者掌握了所有 的预言机的回答，m a l i c e 以自适应的方式向挑战者查询任意预言机对任意输入的回 答。这个过程中，挑战者调用m a l i c e 作为一个子例程来解决某个复杂度理论中的困 难问题，如果m a l i c e 能够以不可忽略的概率在多项式时间内达到了它的目标，那么 挑战者就能够以不可忽略的概率在多项式时间内解决这个困难问题。这个模拟能够 进行的必要条件是所研究的系统必须是可模拟的。 在这一方法论中，有f 再个规约的基础：其一是基于随机预言机的规约，这是一 种启发式的规约方法( 见1 2 节) ；由于对杂凑函数攻击的成功性，尤其是目前对m d 5 攻击 1 6 0 的成功，基于随机预言机的规约方法正逐渐向基于一般复杂度理论假设的 方法转变。后面这种规约方法是一种非常难的形式化规约【3 6 】，它要求系统具有良 一5 一 上海交通大学博士学位论文 好的可模拟性，目前就公钥加密来说，c r a m e r 5 l 】首先在1 9 9 8 年提出了第一个具有 i n d c c a 安全且其安全证明是基于一般复杂度理论假设( d d h 问题) 的加密算法。 1 4 本文贡献及章节安排 由上述讨论可以看出，近年来公钥密码学研究中的一个重大热点问题就是研究 可证安全密码及安全性证明的紧安全性规约。 另一方面，六年前，j o u x 【8 9 和s a k a i 、o h g i s h i 、k a s a h a r a 【1 4 5 分别创造性地发 现双线性对技术可以被用于密码体制的设计。从那以后，使用双线性对技术构造各 种各样的密码算法成为最近几年密码学研究最热门的研究方向之一( 详见2 2 ，2 3 节) ， 并出现了一批有重大影响的成果，比如利用双线性对构造以前没有或是不实用的方 案( 基于身份的密码体制【2 7 】、短签名【3 0 等) 。 双线性对技术和可证安全尤其是安全性证明的紧安全性规约研究正在当前的密 码学界( 以及代数学界甚至业界) 全面展开，这正是需要密码学作出回答的前沿课题， 具有相当深刻的实践意义。在此背景下，本文致力于双线性对技术和可证安全密码 以及安全性证明的紧安全性规约等方面的研究。全文可归结为四个部分。 第一部分，即为本文第二章。本章认真梳理了国内外代数学界和密码学界的主 要论著和学术论文；在代数学、计算复杂度理论的框架中，厘清了椭圆曲线、双线 性映射、超奇异椭圆曲线以及椭圆曲线密码的概念和应用：从有效性和安全性的层 面上对因子分解系统、离散对数系统、椭圆曲线离散对数系统进行了科学的比较； 从局限性和可行性两个角度对密码学中的超奇异椭圆曲线进行综合分析。另外，本 章还给出了