（计算机应用技术专业论文）基于模糊身份的门限体制的研究.pdf

堆丁模糊身份的f j i 艇体制的研究摘要 论文题目： 专 业： 硕士生： 指导教师： 基于模糊身份的门限体制的研究 计算机应用技术 黄立 王常吉副教授 摘要 随着网络应用技术的不断发展，门限密码体制以其面向群体的优势得到广 泛的应用。在门限密码体制中，签名者和解密者都不是指单个实体，而是一个 群体。门限密码体制主要包括门限数字签名和门限解密。在基于证书的公钥密 码体制和基于身份的公钥密码体制下，密码学研究者对门限签名以及门限解密 展开了深入的研究，取得了不少的研究成果。2 0 0 5 年，s a h a i 和w a t e r s 结合基 于身份的公钥加密和生物测度的思想，在欧密会上发表了一篇基于模糊身份的 公钥加密的论文，丌创了一个新的密码学研究方向，立即引起了密码学研究者 对基于模糊身份的公钥密码体制的高度关注。 本文将基于生物测度信息的模糊身份引入到门限密码体制领域，提出了基 于模糊身份的门限解密概念，并分别提出了可证明安全的基于模糊身份的门限 签名方案和基于模糊身份的门限解密方案。本文的主要研究内容包括： ( 1 ) 给出了基于模糊身份门限签名完整的形式化定义以及安全定义。其相当 于是基于身份的门限签名向属性方向的扩展。 ( 2 ) 提出了第一个可行的基于模糊身份的门限签名的方案，并证明了该签名 方案的安全性。 ( 3 ) 提出了基于模糊身份的门限解密概念，并给出了完整的形式化定义以及 安全定义。其相当于是基于身份的门限解密向属性方向的扩展。 ( 4 ) 提出了第一个可行的基于模糊身份的门限解密的方案，并证明了该方案 的安全性。 关键词：门限密码体制，基于模糊身份的数字签名，基于模糊身份的解密，可 证明安全 n j i ；丁模糊身份的fj 限体制的研究 t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： r e s e a r c ho nf u z z yi d e n t i t y - b a s e dt h r e s h o l dc r y p t o s y s t e m c o m p u t e ra p p l i c a t i o nt e c h n ol o g y h u a n gl i w a n gc h a n g j i a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g y , t h r e s h o l dc r y p t o s y s t e mi sw i d e l y u s e df o ri t sg r o u p - o r i e n t e da d v a n t a g e i nat h r e s h o l dc r y p t o s y s t e m , t h es i g n e ro rt h e d e c r y p t e ri sn ol o n g e ras i n g l ee n ti t y , b u tag r o u p t h r e s h o l dc r y p t o s y s t e mm a i n l y i n c l u d e st h r e s h o l ds i g n a t u r ea n dt h r e s h o l dd e c r y p t i o n t h r e s h o l dc r y p t o s y s t e mh a s b e e nw e l ls t u d i e da n dr e s e a r c h e di nt h ec e r t i f i c a t e - b a s e dp u b l i c - k e yc r y p t o s y s t e mb y t h ec r y p t o l o g yr e s e a r c h e r sr e c e n t l y t h e n , t h e yh a v em a d el o t so fa c h i e v e m e n t si n t h i sf i e l d i n2 0 0 5 ，s a h a ia n dw a t e r sp r o p o s e dap a p e rw h i c hi sa b o u tt h ef u z z y i d e n t i t y b a s e de n c r y p t i o nw i t ht h ec o m b i n a t i o no fi d e n t i t y - b a s e de n c r y p t i o na n d b i o l o g i c a l m e a s u r ei n e u r o c r y p t2 0 0 5 t h i sp a p e ri m m e d i a t e l y a t t r a c t e dt h e c r y p t o g r a p h yr e s e a r c h e r s a t t e n t i o no nf u z z yi d e n t i t yb a s e dp u b l i c - k e yc r y p t o s y s t e m a n dt h e nc r e a t ean e wc r y p t o g r a p h yr e s e a r c hd i r e c t i o n t h i sp a p e ri m r o d u c e st h ec o n c e p to fb i o m e t r i c - b a s e df u z z yi d e n t i t yi n t ot h e t h r e s h o l dc r y p t o s y s t e mf i e l d s a f t e rt h a t ，t h i sp a p e rp u t sf o r w a r dt h ec o n c e p to f f u z z yi d e n t i t y - b a s e dt h r e s h o l dd e c r y p t i o n f i n a l l y , t h i sp a p e rp u t sf o r w a r daf u z z y i d e n t i t y - b a s e dt h r e s h o l ds i g n a t u r es c h e m ea n daf u z z yi d e n t i t y - b a s e dt h r e s h o l d d e c r y p t i o ns c h e m ew i t ht h e i rs e c u r i t yp r o v e s t h em a i nr e s e a r c hr e s u l t sa l ea s 内1 1 0 w s ： ( 1 ) g i v e sa ni n t e g r i t ya n ds e c u r i t yf o r m a ld e f i n i t i o no ff u z z yi d e n t i t y - b a s e d t h r e s h o l ds i g n a t u r e i ti sj u s ta sa ne x t e n s i o no fi d e n t i t y b a s e dt h r e s h o l ds i g n a t u r ei n t h ea t t r i b u t e b a s e dd i r e c t i o n ( 2 ) p u t sf o r w a r daf e a s i b l ef u z z yi d e n t i t y - b a s e dt h r e s h o l ds i g n a t u r es c h e m ea n d p r o v e si t ss e c u r i t y ( 3 ) p r o p o s e st h ec o n c e p to ff u z z yi d e n t i t y b a s e dt h r e s h o l dd e c r y p t i o na n dg i v e s 锄i n t e g r i t ya n ds e c u r i t yf o r m a ld e f i n i t i o no f i t ( 4 ) p u t sf o r w a r daf e a s i b l ea n ds e c u r ef u z z yi d e m i t y - b a s e dt h r e s h o l dd e c r y p t i o n i v 幕丁模糊身份的fj 限体制的研究 s c h e m e k e yw o r d s ：t h r e s h o l dc r y p t o s y s t e m , f u z z yi d e n t i t y b a s e ds i g n a t u r e ，f u z z y i d e n t i t y - b a s e dd e c r y p t i o n ，p r o v a b l es e c u r i t y v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：型墓趁 日期：础。笸。主 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即： 学校有权保留学位论文并向国家主管部门或其指定机构送交论文的 电子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆、院系资料室被查阅，有权将学位论文的内 容编入有关数据库进行检索，可以采用复印、缩印或其他方法保存 学位论文。 学位论文作者签名：缮，么 日期：知p 年6 月e t 专 节，壬钿孙孵 签 o ，1， 师嶷导日 堆丁丰萸糊身份的f j m 体制的研究 第i 章引卉 1 1 研究背景与意义 第1 章引言 门限是指把一个秘密分拆成很多分秘密，只有超过一定数目的分秘密合到 一起，才能够恢复出原来的秘密。而如果分秘密的数量没有达到这个数目的话， 就不能够恢复出原始的秘密。能够恢复出秘密所需要的分秘密的最小数量我们 称为门限值。使用门限的原因是为了防止单个秘密比较容易泄露和丢失的问题。 门限体制主要有门限解密、门限签名等等。随着人们安全意识的不断提高 以及计算机安全技术的不断发展，门限技术以其面向群体的特征得到了越来越 多的应用。 在人们同常的生活和工作中，很多事情的处理需要当事人进行签名。签名 是一个人在社会、法律、条文契约等一切关系中，代表个人资信及个人审美情 趣的视觉标志，签名起到了认证、核准、有效和负责等作用。而数字签名继承 了书面签名的优点，特别适用于电子文件普遍使用的今天。传统的数字签名特 别类似于普通的纸质的签名，对于一份电子文件起到认证的作用，防止了电子 文件的非法伪造和篡改。例如，如果a l i c e 打算通过网络发送一份电子邮件给 b o b 。由于电子邮件在网络中的传输大多数是公开的。因此，a l i c e 的电子邮件 很有可能在传输的过程中被其他不怀好意的人截获。如果a l i c e 没有对这封电 子邮件做出任何保护措施的话，那么任何截获这封电子邮件的人都可以对这封 电子邮件进行非法的修改，或者干脆自己伪造一份电子邮件，冒充是a l i c e 的 原邮件并发送给b o b 。b o b 在这种情况下是无法辨别电子邮件的真伪的。但是 如果a l i c e 在这封电子邮件中使用了数字签名的话，b o b 就能够通过a l i c e 的数 字签名非常方便地识别出这封电子邮件是不是a l i c e 所发送的。 随着计算机技术的不断发展以及互联网使用的普及，数字签名在网络安全 中的作用越来越重要。数字签名以其信息安全、身份认证、数据完整性、不可 否认以及匿名性等特性，在商业、金融、军事等领域，特别是电子贸易、电子 耩丁模糊身份的fj 敝体制的研究 第i 章引卉 支票等方面都有着广泛的应用。 与数字签名一样，对于消息的加密与解密也是密码学里面的一个重要的研 究方向。随着1 9 8 7 年d e s m e d t 提出了密钥共享的概念之后，门限解密的概念 也随之诞生了。门限解密的主要思想也与秘密共享的思想一致，就是要把解密 者解密的权利进行分化。当一条密文只能够由一个掌握着解密密钥的人来解密 的时候，这个解密的人所具有的权力就非常巨大了。换句话说，如果这条消息 的解密者由于某种原因没有对密文进行解密的话，那么这条密文所隐藏的明文 消息将永远不会被任何其他人知道。门限解密的出现就是为了解决这个问题而 设想出来的。在一个门限解密方案中，解密私钥将会被拆分成很多份并分别交 给不同的解密服务器。只有当超过一定数量的解密服务器对密文进行解密并生 成各自的分消息之后，原消息才能够被成功地恢复出来。 基于身份的密码体制是由s h a m i r 比1 在1 9 8 4 年提出来的一种密码体制。在基 于身份的密码体制中，用户的公钥被描述成用户的身份信息( 例如用户的电子 邮箱地址、身份证信息、执照信息等等) 。例如，如果某个用户对一条消息进行 了基于身份密码体制的签名。那么，其他验证者只需要使用这个用户的身份信 息作为公钥就能够对这条消息进行验证。基于身份的密码体制与传统的基于公 钥证书的密码体制相比最大的优点是，基于身份的密码体制免除了基于公钥证 书的密码体制中冗长的用户身份与公钥的对照表，使得加密与签名的效率大大 提高了。 基于属性的密码体制是最新提出的一个密码体制。在基于属性的密码体制 中，用户进行消息解密或者消息签名时使用的是用户的属性。只有具有特定属 性集合的用户才能够解密或者签名一条消息。相比基于身份的密码体制，基于 属性的密码体制更方便、更实用。例如，a l i c e 给一个公司发送了一封加密的电 子邮件，并且只想让该公司的总经理级别的人才能够解密这封电子邮件。如果 使用传统的基于身份的密码体制，a l i c e 需要先找到这个公司具有总公司级别的 人的l d 信息，并使用这些i d 信息生成私钥对要发送的电子邮件分别加密。最 后，a l i c e 把这些加密过的电子邮件发送给不同的总经理。如果使用了基于属性 的密码体制，a l i c e 只需要使用该公司总经理这个属性生成私钥并对这封电子邮 件进行加密就可以了。 2 牡丁模糊身份的fj 限体制的研究 第1 章引矗 基于模糊身份的密码体制是基于属性密码体制的一个分支。对于基于属性 的密码体制来说，存在着不同的控制结构。这些控制结构包括有门限型的控制 结构、访问树性的控制结构，等等。基于模糊身份的密码体制就相当于是基于 属性的密码体制中的门限型的控制结构。在一个模糊身份的密码体制中，只有 当加密者与解密者或者签名者与验证者之间的属性存在某种程度的交集时候， 解密者力能够成功地解密出一条消息，验证者才能够成功地验证一个签名。可 以这么说，基于模糊身份的密码体制是基于身份的密码体制的细粒度化。基于 模糊身份的密码体制把基于身份的密码体制中的单个身份分解成了更细粒度化 的多个属性，使得用户在签名或者加密消息时能够进行更细粒度化地操作。 由此我们也可以看到，细粒度化已经成为密码体制今后发展的一个重要方 向。因此，门限体制作为密码学中细粒度化的重要分支，把门限体制与基于模 糊身份的密码体制结合起来具有很高的现实意义与理论意义。本文的重点就是 对基于模糊身份的门限体制进行研究，试图能够得到可行的基于模糊身份的门 限体制方案。 1 2 国内外研究现状 1 2 1 基于模糊身份的密码体制 基于属性的密码体制是从基于身份的密码体制衍生而来的。在1 9 8 4 年， s h a m i r 心1 首先提出了使用身份信息作为一个加密机制里的公钥的概念。s h a m i r 提出这个概念正是为了简化传统的公钥证书体制里面繁杂的证书管理机制。其 中，这个机制中用户的公钥直接来源于他的公开信息，而用户的私钥则由个 可信第三方( p k g ) 生成。使用基于身份的密码机制可以让p k g 不需要存储每 一个认证过的成员的公钥信息。用户和公钥之间的绑定不再需要证书来保证。 但是，s h a m i r 在这篇文章里面并没有提出一个切实可行的基于身份的加密方案。 在2 0 0 1 年，d a nb o n e h 和m a t t h e wf r a n k l i n n l 首次使用双线性对构造出了 一个实用和安全的基于身份( i d e n t i t y - b a s e d ) 的加密方案。这个方案是利用双 线性对中的b d h 难题( b i l i n e a rd i f f i e h e l l m a np r o b l e m ) 来构造的。并且经过 安全性证明，这个方案在i n d i d c c a ( 不可区分基于身份的选择密文攻击) 3 毖丁模糊身份的fj 限体制的研究第l 章引卉 下是安全的。这个方案的提出，为基于身份的密码体制的成熟和完善奠定了曝 实的基础。之后的许多基于身份的加密机制和基于身份的签名机制都是在双线 性对难题的基础上构造的。 如果使用生物属性( 例如指纹、虹膜扫描) 作为身份信息，提取的生物信 息很可能会存在噪音。因此，我们不能直接把生物属性信息使用于传统的基于 身份的密码体制。为了解决这个问题，s a h a i 和w a t e r s 于2 0 0 5 年在他们的方 案中首次引入了模糊身份( f u z z yi d e n t i t y ) 的概念。在这个方案中，对用户身 份信息的描述是使用一组属性值而不是一条代表用户身份的字符串来完成的。 在一个模糊身份的加密方案中，当且仅当加密者与解密者的属性集的交集大于 某一个门限值时，解密者能够成功地解密出加密者加密所尘成的密文。他们的 方案将广大密码学研究者关注的目光由身份转移到了属性的方向。之后，b a e k ” 又对模糊身份的加密进行了改进。模糊身份允许用户的身份信息存在一定限度 的误差，而不需要百分之百的相同。同时，模糊身份中第一次引入了属性的概 念，这是基于身份的密码体制向基于属性的密码体制自仃进中的重要的一步。 在2 0 0 8 年，y a n g 8 】等人第一次提出了模糊身份签名( f u z z yi b s ) 的概念。 在文章中，他们在s a h a i 和w a t e r s l 4 1 的模糊身份加密方案以及b o y e n 和w a t e r s 3 0 】 的两层结构签名方案的基础上构造了第一个基于模糊身份的签名方案。同时， 他们证明了这个方案在标准模型下是对于选择消息攻击以及模糊身份攻击具有 存在性的不可伪造。该方案能够规约到c d h 难题。在2 0 0 9 年，w a n g 3 1 】等人提 出了两个效率更高的模糊身份签名方案。与y a n g 的方案相比，该方案在公私钥 长度以及签名验证的效率上都有所改进。 相比于模糊身份的加密与签名而言，对于模糊身份密钥交换的研究则要相 对滞后一些。在2 0 0 2 年，s m a r t 9 1 提出了一个基于身份的密钥交换方案。但是 之后，s h i m 1 0 1 和c h e n k u d l a 】分别独立地指出s m a r t 的方案并不满足前向安全 性这个不足，并提出了自己的基于身份的密钥交换方案。之后c h o i e l l 2 】根据s m a r t 的方案提出了一个新的密钥交换方案。在2 0 0 7 年，a t e l l i e s e 【b 】等人在他们的文 章中第一次把模糊身份的概念引入密钥交换领域，提出了一个基于模糊身份的 密钥交换方案并对其进行了效率上的分析。 4 螭丁模糊身份的i j 瞅体制的研究第l 章引卉 1 2 2 基于属性密码体制 2 0 0 6 年，g o y a l 。p a n d e y ，s a h a i ，w a t e r s t 刚一起提出了第一个基于属性的加 密方案( 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 st r e e ) 来表示。访问树能够支持“与” 和“或 的关系。对于一棵访问树，访问结构的中问结点代表门限，叶子结点 与属性相关联，而加密的消息则与属性集合相关联。用户能否成功解密一条消 息，取决于用户的属性集是不是能够满足访问控制结构。例如，用户所拥有的 访问控制结构是( aa n db ) o r ( ca n dd ) ，那么，该用户就能够解密使用属性 集 a ，b ) 或者属性集 c ，d ) 加密生成的密文，但不能够解密使用属性集合 b ，c ) 加密锁生成的密文。这种使用属性集对消息进行加密，使用访问控制树生成私 钥的基于属性的加密方案称作密钥策略的基于属性的加密方案( k e y - p o l i c y a b e ，简称k p a b e ) 。 2 0 0 7 年，b e t h e n c o u r t 1 等人提出了密文策略的基于属性的加密方案 ( c i p h e n e x t p o l i c ya b e ，简称c p - a b e ) ，在这个加密方案中，用户所加密的 消息是与访问控制结构相关联的。而这个消息的解密者是拥有他自己的属性集 合的。当且仅当该解密者的属性集满足加密所使用的访问控制结构的时候，解 密者才能够成功地解密该消息并恢复出相应明文。 在这些方案中，作者都是使用了拉格朗同的插值多项式来构造多层门限， 从而与访问控制中的相应结构相对应。 基于属性的数字签名是由基于模糊身份的门限签名发展而来的。在2 0 0 6 年，y a n g 睛1 首次提出了模糊身份签名的概念。类似于模糊身份的加密，在模糊 身份的签名中，签名者是使用自身的属性集进行签名的。只有签名者与验证者 的属性集之间的交集达到或者超过某个临界值时，验证者才能够验证这个签名 的正确性。 h e m a n t a n 钉于2 0 0 7 年发表的论文中，对基于属性的签名有了更详细的描述， 这篇文章提出了基于属性的签名应该满足以下几个条件： 5 綦丁模糊身份的fj 限体制的研究第l 章引 1 ) 不可伪造性。对于一个签名，如果一个个体不满足签名者所要求的属性， 那么他将无法伪造出此签名。 2 ) 隐私保护。这旱的隐私保护是指对用户的属性进行隐私保护。 3 ) 抗合谋攻击。抗合谋攻击是指不同的签名者即使合谋也不能伪造出一个 他们各自之前都不能生成的签名。 1 2 3 基于模糊身份的门限签名的发展 门限签名的概念是d e s m e d t 在1 9 8 7 年第一次提出来的。在他的文章中， 他第一次提出了如何把一个秘密分拆成多份以避免把一个秘密存放在单个地方 所造成的危险。同时，把秘密分拆之后，能够降低每个签名人的能力，使得只 有超过一定数量的签名人组在一起才能够对一条消息进行签名。 2 0 0 4 年，b a e k 和z h e n g 引首次提出利用分拆用户私钥的方法来构造基于 身份的门限签名方案。在他们的( ，n ) f - j 限签名方案中，p k g 首先根据自己的身 份信息生成一个主密钥s 。在分配密钥阶段，p k g 使用拉格朗同插值多项式对 这个主密钥j 进行拆分，生成力个分密钥s 又l g 勤) 并分发给这刀个用户。每个 用户分别把分密钥s ，作为自己的私钥并对消息进行签名。在这篇文章中，作者 还提出了一般基于身份签名机制的模型以及安全性证明模型。在最后，作者自 己构造了一个能够把他的基于身份的门限签名方案规约到基于身份的签名方案 的安全性证明。 在2 0 0 9 年，c a i 和z h a n g 2 1 首次提出了模糊身份门限签名的概念，把属性 集与门限结合在了一起。他们还试图通过转化s a h a i 和w a t e r h l 的模糊身份加密 方案到一个新的签名方案，从而构造出一个新的基于模糊身份的门限签名的方 案。 可以说，模糊身份与门限签名还没有真正意义地结合起来。随着密码体制 向着细粒度的不断发展，基于模糊身份的门限签名是很有研究的必要性的。因 此，本文的重点就是试图构造出新的基于模糊身份的门限体制方案，并对这些 方案进行安全性的证明。 6 耩丁模糊身份的fj 瞅体制的研究 第l 晕 引 1 2 4 基于模糊身份的门限解密的发展 在1 9 9 8 年，s h o u p 和g e n n a r o 州提出了一个具有代表性的门限解密体制。 这是一个自适应选择密文安全性的门限解密方案，能够舰约到基于素数域中的 d i f f i e - h e l l m a n 难题。 在2 0 0 1 年，f o u q u e 和p o i n t c h e v a l 力在他们的文章中利用n a o r 和y u n g 町 的工作，对同一条明文用两组公钥进行加密，再在密文后加入零知识证明“隶属 关系”，证明两条密文是对同一条明文加密的结果。 之后，b a e k 和z h e n g n 础在他们的文章中提出了第一个基于身份的门限解密 方案。在这篇文章中，他们首次对基于身份的门限解密进行了形式化定义和安 全模型的定义。此外，他们还对他们提出的基于身份的门限解密方案进行了安 全性证明。该方案可以成功地归约到d b d h 难题( 下一章将会介绍d b d h 难 题) 1 3 本文的主要工作 本文的研究工作围绕基于属性的门限签名展丌，具体内容包括： 1 ) 介绍了基于模糊身份的门限体制的应用背景，说明了研究基于模糊身份 的门限体制的现实意义。 2 ) 给出了基于模糊身份门限解密完整的形式化定义以及安全定义。其相当 于是基于身份的门限签名向属性方向的扩展。 3 ) 提出了第一个可行的基于模糊身份的门限签名的方案，并证明了该签名 方案的安全性。 4 ) 提出了基于模糊身份的门限解密概念，并给出了完整的形式化定义以及 安全定义。其相当于是基于身份的门限解密向属性方向的扩展。 5 ) 提出了第一个可行的基于模糊身份的门限解密的方案，并证明了该方案 的安全性。 7 毖丁模糊身份的门限体制的研究 第1 章引 1 4 本文的章节安排 第1 章是引言，介绍了基于模糊身份的密码体制以及门限密码体制的研究 意义和发展现状。 第2 章主要介绍本文所用到的一些基础理论和预备知识，包括双线性对的 概念、相应的困难性问题、可证明安全性理论以及访问控制结构等。 第3 章的内容包括：给出了基于模糊身份的门限签名的相应的形式化定义 和安全模型；给出了一个基于模糊身份的门限签名方案，并分析了方案的安全 性。 第4 章的内容包括：提出了基于模糊身份的门限解密概念以及相应的形式 化定义和安全模型；给出了一个基于模糊身份的门限解密方案，并分析了方案 的安全性。 第5 章是结语部分，对本文的研究工作进行了总结并对基于模糊身份门限 体制的发展前景进行了展望。 8 坫丁模糊身份的fj 戳体制的研究第2 章堆础知识和腿础理论 第2 章基础知识和理论 2 1 双线性对与困难性问题 大多数的基于身份以及基于属性的密码机制都是构建在双线性对困难性问 题之上的。自从d a nb o n e h 提出了第一个使用双线性对构造的基于身份的加密 方案以来，众多学者都比较倾向于利用双线性对的与众不同的特殊性质来构造 自己的方案。 2 1 1 双线性对 设q 是一个素数，( g l ，+ ) 和( g 2 ，) 均是阶为q 的循环群。映射e ：g lx g i 专g 2 就是一个双线性对。e 满足以下性质： 1 ) 双线性：对于任意a ，b z q 和p ，q g i ，都有e ( a p ，6 q ) = e ( e ，q ) 曲。 2 ) 非退化性：如果p 是g l 的生成元，那么e ( p ，尸) 就是g ：的生成元。换句 话说，不存在一个生成f r _ , p 使得e ( e ，p ) l g 。 3 ) 可计算性：存在一个有效的算法使得对任意的尸，o g l ，都能够计算 e ( p ，9 ) 的值。 通常来说，双线性映射e 能够从一个对于有限域的椭圆曲线w e i l 对或者 t a t e 对中获得。 2 1 2 困难性问题 假设g l 是一个由阶为q 的生成元p 生成的循环加法群，并且对于群g l 来说， 群里面的任何一个元素的乘法以及逆运算都是可以计算的。那么，我们将可以 围绕这个循环加法群g 1 构造下面的困难性问题。 1 ) 离散对数问题 离散对数问题( d i s c r e t el o g a r i t h mp r o b l e m ，简称d l 问题) 是指：不存 9 耩丁模糊身价的f j 限体制的研究第2 章尽础知识和埔础理沦 在这么一个有效地算法，该算法能够在多项式时间内以不可忽略的概率内找到 一个整数”z 口，使得9 = n p 。其中，p ，q g l 是随机选择的。 2 ) 计算性o i f f i e - h e l l m a n 问题刚 计算性d i f f i e h e l l m a n 问题( c o m p u t a t i o n a ld i f f i e h e l l m a np r o b l e m ，简称 c d h 问题) 是指：不存在这么一个有效地算法，该算法能够在多项式时间内以 不可忽略的概率从三元组( p ，a p ，b p ) 中计算出a b p 。其中，口，b z , i 是随机选择 的，尸是群g i 罩面的一个生成元。 3 ) 判定o i f f i e h e l l m a n 问题 判定d i f f i e h e l l m a n 问题( d e c i s i o n a ld i f f i e - h e l l m a np r o b l e m ，简称d d h 问题) 是指：不存在这么一个有效地算法，该算法能够在多项式时间内以不可 忽略的概率区分两个四元组( p ，a p ，b p ，a b p ) 和( p ，a p ，b p ，c p ) 。其中，口，b ，f 乙 是随机选择的，尸是群g l 罩面的一个生成元。 我们称群g l 是一个g a pd i f f i e h e l l m a n 群当且仅当在这个群中存在一个算 法，使得d d h 问题能够在这个群中以多项式时间解决。但是在这个群中不存 在一个算法能够在多项式时间内以不可忽略的概率解决c d h 问题。这样的群能 够在超单一椭圆曲线或者超椭圆曲线的有限域罩面找到。j o u x 心0 1 等构造出一类 椭圆曲线，在这类椭圆曲线上的某些子群上，c d h 问题和d l 问题是可证明等 价的，而d d h 问题又是容易解决的。也就是说，这类子群是理想的g d h 群。 4 ) 判定双线性d i f f i e h e l l m a n 问题 2 1 判定双线性d i f f i e h e l l m a n 问题( d e c i s i o n a lb i l i n e a rd i f f i e - h e l l m a n p r o b l e m ，简称d b d h 问题) 是指：不存在这么一个有效的算法，该算法能够 在多项式时间内以不可忽略的概率从四元组( p ，妒，妒，护) 中计算出 e ( p ，p ) 琊g 2 。其中，x ，y ，z z q 是随机选择的，p 是群g 1 里面的一个生成元。 5 ) 修改的判定双线性d i f f i e h e l l m a n 问题 修改的判定双线性d i f f i e - h e l l m a n 问题( d e c i s i o n a lm o d i f i e db i l i n e a r d i f f i e h e l l m a np r o b l e m ，简称d m b d h 问题) 是指：不存在这么一个有效的算 法，该算法能够在多项式时间内以不可忽略的概率分辨两个五元组 l o 摧丁模糊身份的fj 瞅体制的研究第2 章艇础知识和桀础理论 ( 尸，a p ，b p ，c p ，) 和( 尸，a p ，b p ，c p ，e ( e ，p ) 圳。) 。其中，t , b ，c 乞是随机选择的， ，g 2 ，p 是群g l 里面的一个生成元。 2 2 可证明安全 2 2 1 基本概念 1 9 8 2 年，g o l d w a s s e r 和m i c a l i 口习第一次提出了可证明安全性的概念。从而 解决了过去的密码学系统中不断出现新问题，不断修复问题的被动密码学设计 方法。 可证明安全1 是以归约方法来保障密码体制的安全。使用可证明安全的方 法，密码学家必须要先把他所做的方案规约到某个已知并公认的数学难题上来 ( 例如大数分解问题、离散对数问题、d b d h 问题等) 。然后，密码学家构造出 一些对这个方案进行攻击的手段( 例如通过公钥可以查询私钥，通过消息可以 查询签名等等) 来对这个方案进行攻击。如果在最后的证明中，对于该方案的 攻破肯定会规约到某个数学难题上( 也就是说，如果成功地攻破了这个方案的 话，那么，这个方案所规约到的数学难题也会被成功地攻破。) ，那么，我们就 可以说这个方案是可证明安全的，它能够成功地规约到某个数学难题上来。 在这篇文章中，他们还开创了通过形式化的方法去定义一个密码方案。许 多对于公钥密码的新思想和概念都是由于有了形式化定义彳会在之后产生的。 比如存在性伪造、选择明文攻击等等，都是在形式化定义的基础上出现的。 通过形式化的方法去证明一个密码方案，具体的过程如下： 1 ) 给出密码方案的一个形式化定义。 2 ) 为这个密码方案确定一个安全模型。也就是在这个安全模型下，攻击者 能够拥有的攻击手段以及最后能够达到的攻击效果。 3 ) 确定方案所需要规约到的困难问题。 4 ) 建立攻击方案安全性的复杂度与求解困难问题的复杂度之间的联系，这 个过程也称作安全性规约。 在建立安全性规约的时候，如果一个方案没有经过任何假设便能够成功地 祭丁模糊身份的门限体制的研究第2 章坫础知识和坫础理沦 规约到一个数学难题上来。我们就称这个方案是基于标准模型( s t a n d a r dm o d e l ) 下的，并称这个方案在标准模型下可证明安全。瞳2 1 但是，对于大多数方案而言， 在标准模型下的规约是有很大难度的。为了降低证明难度，人们在建立安全性 规约的时候，往往在证明中加入一些合理的假设。其中最常见的就是使用随机 预言机( r a n d o m o r a c l e ) 进行帮助证明。在随机预言机下可证明安全的方案也 成为随机预言机模型( r a n d o mo r a c l em o d e l ) 下的可证明安全。 可以认为，可证明安全的提出使得密码学家不需要在费尽心力地去研究一 个密码方案可能存在的各种漏洞，而只需要把这个密码方案规约到目前已知的 各种数学难题上来就可以了。这大大增加了密码方案的研究效率。 2 2 2 随机预言机模型 随机预言机模型( r a n d o mo r a c l em o d e l ) 是在1 9 9 3 年b e l l a r e 和r o g a w a y 第一次提出来的。在之后的可证明安全中，随机预言机模型得到了广泛的应用 晒1 。大多数的密码方案都是先在随机预言机模型下可证明安全，并在之后经过 改进再在标准模型下可证明安全。 随机预言机可以说是一种理想化的h a s h 函数。当输入不同的值的时候，这 个理想的h a s h 函数能够在一个均匀分布的值空问内取值并返回。当输入相同的 值的时候，这个h a s h 函数也能够得到相同的值并返回。随机预言机具有以下性 质： 1 ) 一致性：如果输入的值相同的话，输出的值也一定相同 2 ) 可计算性：输出的值的计算应该是在输入值长度的多项式时间内完成。 3 ) 均匀分布性：随机预言机的输出值必须在值空间内均匀分布。 在随机预言机模型下的可证明安全，是假定敌手不会利用充当随机预言机 模型的h a s h 函数的弱点来进行的。也就是说，在敌手的眼中，这个h a s h 函数 就是一个随机预言机模型，是不能被攻破的。 实际上，随机预言机的模型是具有很强的假设性的。在实际的应用中人们 发现，这么理想的h a s h 函数是很难找到的，或者说是根本不能找到的。在可证 明安全里面证明出的在随机预言机模型下安全的密码方案一旦到了实际应用中 就会发生问题。也就是说，在实际情况下，一旦使用真实的h a s h 函数来代替随 1 2 耩丁模糊身份的| 、j 限体制的研究第2 章垠础知以和肚础理论 机预言。机以后，在随机预言机下可证明安全的密码方案就变得不安全了。 但是，迄今为止，随机预言机的应用应该说是可证明安全性理论罩面最成 功的实际应用。几乎所有国际安全标准体系都要求提供至少随机预言机以上的 可证明安全设计。 2 2 3 数字签名攻击 对于数字签名的攻击通常包括两种： 唯密钥攻击( k e yo n l ya t t a c k ) ：也称无消息攻击( n om e s s a g ea t t a c k ) 。 在唯密钥攻击中，敌手仅知道签名者的公钥，是比较弱的一种攻击。 消息攻击( m e s s a g ea t t a c k ) ：在消息攻击中，敌手除了知道签名者的公钥， 还可以获得一些消息签名对。 根据敌手的攻击能力，还可以将消息攻击分成以下三类： 1 ) 已知消息攻击( k n o w nm e s s a g ea t t a c k ) 。挑战者可以为敌手提供有限 多对的( 消息，签名) 元组。敌手通过这些元组对签名系统进行攻击。但是这 些元组是由挑战者提供的，敌手不能自由选择。 2 ) 选择消息攻击( c h o s e nm e s s a g ea t t a c k ) 。在选定挑战者选定指定的消 息之前，敌手可以选择有限多条的消息让挑战者进行签名并返回。当挑战者选 定指定的消息之后，敌手将不能再对任何消息进行查询。 3 ) 自适应选择消息攻击( a d a p t i v e l yc h o s e nm e s s a g ea t t a c k ) 。敌手可以 在任何时候让挑战者对特定的消息进行签名并返回( 不包括挑战者指定让挑战 者猜的消息) 。也就是说，敌手可以根据以前所进行过的签名查询自适应地调整 签名查询。 可以看到，以上的攻击能力是越来越强的。总的来说，一个有效地签名方 案至少要求必须达到选择消息攻击( c m a ) 以上。 而按照数字签名方案被攻克的程度，可以分为以下三种： 1 ) 完全破译：攻击者经过整个攻击后破解了签名者的私钥； 2 ) 通用伪造：能够得到一个以比较高的成功率伪造出签名的算法； 3 ) 选择性伪造：在攻击过程结束后，敌手能够通过攻击过程伪造出一条攻 堆丁模糊身份的i j 瞅体制的研究第2 章肚础知以和坫础理论 击之前选择的消息的签名。 4 ) 存在性伪造：在攻击过程结束后，攻击者至少可以伪造出一个消息签 名对( m ，盯) 。而且消息m 在攻击过程中并没有被拿来做过签名生成查询。存在 性伪造一般并不危及安全。 2 2 4 公钥加密的安全模型 对于公钥加密的安全目标一般包括下面几种： 1 ) 语义安全性( s e m a n t i cs e c u r i t y ，简称s s ) ：敌手不能够从一条密文中 知道出了明文长度之外的其他关于原始明文的信息。 2 ) 不可区分性( 1 n d i s t i n g u i s h a b l “y ，简称i n d ) ：敌手选择两个明文交给挑 战者，挑战者随机选择一个明文加密并返回该明文所对应的密文。敌手从得到 的密文中不能够以明显超过1 2 的概率猜出挑战者所选择的明文是哪一个。 3 ) 不可扩展性( n o n m a l l e a b l e ，简称n m ) ：敌手在知道一条明文的条件 下，不能通过计算获得另一条密文，并且这两条密文之间存在着某种联系。 4 ) 明文可意识性( p l a i n t e x ta w a r e n e s s ，简称p a ) ：敌手在不知道明文的 情况下，不能够以不可忽略的概率构造一个合法的对应密文。 对于公钥加密的攻击类型主要包括下面几个： 1 ) 选择明文攻击( c p a ) ：敌手可以选择任何明文让挑战者加密并返回。 2 ) 非自适应性选择密文攻击( c c a l ) ：敌手在得知目标密文之前能够选择 任何密文让挑战者解密并返回，只是不能够选择目标密文进行查询。 3 ) 自适应性选择密文攻击( c c a 2 ) ：敌手在得知目标密文前后都更够选择 任何密文让挑战者解密并返回，只是不能够选择目标密文进行查询。 2 3 秘密共享 在1 9 7 9 年，s h a m i r 首先提出了秘密共享的概念以及一个秘密共享的方案。 其中，他们使用了拉格朗同插值多项式作为一个秘密的分拆方法。在之后的许 多秘密共享方案中，人们提出的秘密共享体制大多数是在s h a m i r 的秘密共享机 制之上提出来的。 1 4 旗丁模糊身份的fj 限体制的研究第2 章堆础知识和肚础理论 定义2 1 访问