（计算机软件与理论专业论文）基于辫群的密码方案的设计与分析.pdf

基于辫群的密码方案的设计与分析 摘要 公钥密码学已经发展了三十余年，许多优秀的公钥密码系统被不断 地提出并逐渐完善。但是，量子计算的最新研究成果对许多基于数论难 题假设的公钥密码系统形成了潜在威胁。于是，人们开始积极探索那些 可以抵抗已知量子分析的公钥密码系统。基于辫群的公钥密码系统正是 其中之一。自从k o 等人于2 0 0 0 年提出基于辫群的公钥密码系统以来，基 r 辫群的公钥密码系统的发展虽然经历了不少曲折，但目前仍然是公钥 j 码学研究领域中十分活跃的主题之一。近年来，算法研究方面的进展 对辫群密码系统的基础假设一共轭搜索问题( c s p ) 困难性假设提出了 质疑，但是并未形成任何定论。另外，已经发表的基于辫群的公钥密码 方案，具有可证明安全模型者甚少；即使那些底层难题最终被证明是困 难的，现有的基于辫群的密码方案也不具备人们所期望的安全属性。因 此，本文研究的重点是：( 1 ) 分析目前已经发表的典型的求解c s p 问题 的方法的计算复杂度；( 2 ) 研究基于辫群的数字签名体制，设计可证明 具有e u f c m a 安全性( 即在自适应选择消息攻击下存在性不可伪造) 的 新的签名体制；( 3 ) 研究并设计基于自分配系统的密码方案。 主要研究成果如下： 1 为求解c s p 问题的各个典型方法提供了具体的算法描述和详细的 复杂性分析，指出了s s s 集合、u s s 集合和u 轨道之间的关系，并 对u s s 方法所宣称的高效性提出质疑。我们的结论是：目前发表的 求解c s p 问题的方法还没有一个能够被证明是可以在多项式时间内 完成的。另外，澄清了一些人关于c s p 难解性和群的小消去条件之 间的关系的一个误解。 2 基于c s p 困难性假设，设计了两个基于辫群的比特承诺方案：一个 是标准的比特承诺方案；另一个是推广的非平衡的比特承诺方案。 基于辫群实现比特承诺协议有着计算效率和安全性级别两方面的优 势。 3 提出了辫群上的密码学新问题一“多一”匹配共轭问题，并且基于 该问题的困难性假设，对k o 等人提出的基于辫群的签名体制给出 上海交通大学博士学位论文 了新的安全性规约。这是首次证明了一个基于辫群的签名体制具 有e u f c m a 安全性。 4 提出了辫群上的另外一个密码学新问题一共轭连接问题，并且基于 该问题的困难性假设，设计了新的基于辫群的数字签名体制。新体 制也被证明具有e u f c m a 安全性。 5 设计了多个基于自分配系统的密码体制。这是首次系统地从密码设 计的角度对自分配系统进行的考察，取得了较为丰富的结果： ( a ) 设计了基于1 型左自分配系统( l d l ) 的数字签名方案。 ( b ) 设计了基于1 。型中自分配系统( c d l ) 的数字签名方案和具有 部分变色龙属性的哈希函数。 ( c ) 提出了其它1 4 种形式的自分配系统。 ( d ) 设计了基于2 型中自分配系统( c d 2 ) 的数字签名方案。 ( e ) 设计了基于1 。型右自分配系统( r d l ) 的数字签名方案和认证 方案。 关键词：辫群，公钥密码学，可证明安全，共轭搜索问题，小消去条 件，数字签名，自分配系统 一一 d e s i g na n da n a l y s i so fc r y p t o g r a p h i cs c h e m e s b a s e do nb r a i dg r o u p s a b s t r a c t s i n c et h ei n v e n t i o no ft h ec o n c e p to fp u b l i ck e yc r y p t o g r a p h y ( p k c ) ，p k ch a sb e e n d e v e l o p e df o ra b o u tt h i r t yy e a r s m a n ye x c e l l e n tp u b l i ck e yc r y p t o s y s t e m sh a v eb e e np r o - p o s e da n di m p r o v e d b u t ，t h er e c e n td e v e l o p m e n to fq u a n t u mc o m p u t a t i o nc r e a t e sp o t e n t i a l m e n a c et ot h es e c u r i t yo fc u r r e n tp u b l i ck e yc r y p t o s y s t e r n s i no r d e rt oe n r i c hc r y p t o g r a p h y a sw e l la sn o tt op u ta l le g g si no n eb a s k e t ，p e o p l eh a v em a d el o t so fe f f o r to i ld e v e l o p i n ga l t e r n a t i v ep k c b a s e do nd i f f e r e n tm a t h e m a t i c a lf o u n d a t i o n b r a i dg r o u p - b a s e dp k ci s j u s to n eo ft h ee g g so u t s i d et h eb a s k e t f r o mt h ep u b l i c a t i o no ft h ef i r s tb r a i d b a s e dp k c s c h e m ed u et ok oe ta 1 i n2 0 0 0 ，t h er e s e a r c ho nb r a i d b a s e dp k ch a sb e e nu n d e r g o i n g s o m es i n a a f i o na n dk e e p i n ga c t i v e r e c e n t l y , p r o g r e s so na l g o r i t h m sc a s t sd i s t r u s to nt h e b a s i ca s s u m p t i o no fb r a i d b a s e dp k c ，i e ，t h ei n t r a c t a b i l i t yo fc o n j u g a t o rs e a r c hp r o b l e m ( c s p ) 一b u tp e o p l eh a v en o tr e a c h e da n yd e f i n i t ec o n c l u s i o na ss of a r i na d d i t i o n ，m a n y p u b l i s h e db r a i d - b a s e dp k c s c h e m e sl a c ko fp r o v a b l ys e c u r em o d e l s ，r e s u l t i n gi nt h a te v e ni f t h o s eu n d e r l y i n ga s s u m p t i o n sw e r es o u n d ，t h e s es c h e m e sh a df a i l e dt om e e tt h em o s td e s i r e d s e c u r ep r o p e r t i e s t h e r e f o r e ，i nt h i sp a p e r , w ef o c u so i l r n c o m p l e x i t yo fp u b l i s h e dm e t h o d s f o rs o l v i n gc s p ； b r a i d b a s e ds i g n a t u r e sw h i c hc a nr e a c he u f c m as e c u r i t y ； s e l f - d i s t r i b u t i v es y s t e m s t h eo r i g i n a l i t yo ft h i sp a p e ri ss t a t e di nt h ef o l l o w i n g ： 1 w ep r o v i d ed e t a i l e da l g o r i t h m i cd e s c r i p t i o n sf o rp u b l i s h e da l g o r i t h m sf o rs o l v i n gc s p , g i v ec o m p l e x i t ya n a l y s i so nt h e s ea l g o r i t h m s ，a n dc l a r i f yt h er e l a t i o n s h i pa m o n gt h e s u p e rs u m m i ts e t ( s s s ) ，t h eu l t r as u m m i ts e t ( u s s ) a n dt h eu o r b i t b a s e do nt h e s e w o r k , w ep r o m p to u rd o u b to nt h ec l a i m e de f f i c i e n c yo fu s sm e t h o da n dd r a wa c o n c l u s i o n ：t h ec o m p l e x i t i e so fa l lp u b l i s h e dm e t h o d sf o rs o l v i n gc s ph a v en op o l y n o m i a lb o u n d ，w i t hr e s p e c tt ot h es c a l eo fi n p u tp a r a m e t e r so fc s pi n s t a n c e s ；a sa 上海交通大学博士学位论文 r e s u l t ，t h ec s pi n t r a c t a b i l i t ya s s u m p t i o ni ss o u n da tp r e s e n t i na d d i t i o n 。w ep o i n t o u ta f a l s ei d e ao nt h er e l a t i o n s h i pb e t w e e nt h es m a l lc a n c e l l a t i o nc o n d i t i o n so fb r a i d g r o u p sa n d t h ei n t r a c t a b i l i t yo fc s e 2 b a s e do nt h ec s p i n t r a c t a b i l i t ya s s u m p t i o n ，w ed e s i g nt w ob r a i d b a s e db i tc o m m i t m e n tp r o t o c o l s ：t h eo n ei st h es t a n d a r db i tc o m m i t m e m ；t h eo t h e ri sc a l l e db i a s e d b i tc o m m i t m e n t , w h i c hi san o n t r i v i a lg e n e r a l i z a t i o n t h ep e r f o r m a n c ea n ds e c u r i t y a n a l y s i so no u rp r o t o c o l ss u g g e s tt h a tb r a i d b a s e db i tc o m m i t m e n t sh a v ea d v a n t a g e s o v e rt h o s eb a s e do nn u m b e rt h e o r y 3 w ep r o p o s ean e wb r a i d b a s e dc r y p t o g r a p h i cp r o b l e m o n em o r em a t c h i n gc o n j u g a t ep r o b l e m ( o m - m c p ) ，a n dp r o v et h a ti nt h er a n d o mo r a c l em o d e l ( r o m ) ，k oe t a 1 sb r a i d - b a s e ds i g n a t u r es c h e m e sa r ee u f - c m as e c u r eu n d e rt h ea s s u m p t i o no ft h e i n t r a c t a b i l i t yo fo m - m c p a sf a ra sw ek n o w , t h i si st h ef i r s tt i m et oc o n c l u d et h a t s o m eb r a i d b a s e ds i g n a t u r e sw h i c hc a nr e a c he u f - c m as e c u r i t y 4 w ep r o p o s ea n o t h e rn e wb r a i d b a s e dc r y p t o g r a p h i cp r o b l e m c o n j u g a t ea d j o i n p r o b l e m ( c a p ) ，a n dd e s i g nan e wb r a i d - b a s e ds i g n a t u r es c h e m ew h i c hi sa l s op r o v e d t 0b ee u f - c m as e c u r eu n d e rt h ea s s u m p t i o n so fr o ma n dt h ei n t r a c t a b i l i t yo fc a p 5 w ed e s i g ns e v e r a lc r y p t o g r a p h i cs c h e m e sb a s e do ns e l f - d i s t r i b u t i v es y s t e m s t h i si s t h ef i r s tt i m et oc o n d u c ts y s t e m a t i c a l l ys t u d yo ns e l f - d i s t r i b u t i v es y s t e m s a n dw e o b t a i ns o m ei n t e r e s t i n gr e s u l t s ： ( a ) as i g n a t u r es c h e m eb a s e do nt h ef i r s tt y p eo fl e f ts e l f - d i s t r i b u t i v es y s t e m ( l di ) ( b ) as i g n a t u r es c h e m ea n dah a s hf u n c t i o nw i t hp a r t i a lc h a m e l e o np r o p e r t yb a s e d t h ef i r s tt y p eo fc e n 仃a ls e l f - d i s t r i b u t i v es y s t e m ( c d1 ) ( c ) s e l f - d i s t r i b u t i v es y s t e m st a k i n go t h e r f o u r t e e nf o r m s ( d ) as i g n a t u r es c h e m eb a s e do nt h es e c o n dt y p eo fc e n t r a ls e l f - d i s t r i b u t i v es y s t e m ( c d 2 ) ( e ) as i g n a t u r es c h e m ea n d a na u t h e n t i c a t i o ns c h e m eb a s e do nt h ef i r s tt y p eo ff i g h t s e l f - d i s t r i b u t i v es y s t e m ( r d 1 ) k e yw o r d s ：b r a i dg r o u p s ，p u b l i ck e yc r y p t o g r a p h y , p r o v a b l es e c u r i t y , c o n j u g a t o r s e a r c hp r o b l e m , s m a l lc a n c e l a t i o nc o n d i t i o n s ，d i g i t a ls i g n a t u r e ，s e l f - d i s t r i b u t i v es y s t e m 一一 z ，n ，q ，r z r i z ： o ，1 ) o ，1 ) n 1 n i s l ，蚓 n s ，a 硭s o 尺s ，a 卜s n i | 6 aob p ( n ) 住! q ) e x p ( 1 ) ，e - 1 e euf enf e c f 0 ，伽，o ( n ) p r e 1 p r 旧l 用 主要符号对照表 分别表示整数、正整数、有理数和实数的集合 以佗为模的剩余类环z n z 中所有对模乘可逆元构成的集合 任意长度的比特字符串集合 长度为n 的比特字符串集合 正整数n 的1 元表示 分别表示字符串8 的长度、集合5 的规模 元素a 属于( 不属于) 集合5 均匀随机地在集合s 中选取元素a a 和b 的连接 表示相同长度的a 和b 按位求异或 表示死的一个多项式 n 的阶乘( = n ( n 一1 ) 一2 ) 1 ，o ! = 1 ) 竹个对象中取南个的取法个数( = 志) 表示自然对数的底( e x p ( 1 ) = e 2 7 1 8 2 6 ) 事件e 的补事件 事件e 和f 的和事件，即或者事件e 发生，或者事件 f 发生 事件e 和f 的积事件，即事件e 和事件f 都发生 事件，包含事件e ，即事件e 的发生蕴含事件f 的 发生 分别表示随机预言机，名为n a m e 的随机预言机，和计 算复杂度( 可根据上下文区分) 事件e 发生的概率 事件f 发生的条件下，事件e 发生的条件概率 v 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何他个人或集体 已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日 期： 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定，同意 学校保留并向困家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索。可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 1 1 公钥密码学 第一章绪论 1 1 1 里程碑 如果说s h a n n o n 于1 9 4 9 年发表的“c o m m u n i c a t i o nt h e o r yo fs e c r e c ys y s t e m s 一 文【1 3 2 1 标志着现代密码学的开端，那么d i f f i e 和h e l l m a n 于1 9 7 6 年发表的“n e wd i r e c t i o n s i nc r y p t o g r a p h y ”一文【5 1 1 则标志着公钥密码学的开端。在公钥密码系统里，用于加密 信息的密钥( 公钥) 与用于解密信息的密钥( 私钥) 是完全不同的。而且要从公钥 分析求解出对应的私钥，在计算上也是不可行的。 虽然d i f f i e 和h e l l m a n 在当时并未构造出具体的公钥密码系统，但是他们宣布了 一个信念：只要找到合适的单向陷门函数，就可以构造出公钥密码系统来。随后。 他们的工作引起了密码学界的广泛关注。很快，到了1 9 7 8 年，r i v e s t 、s h a r n i r 和 a d l e m a n l l 2 5 1 就给出了第一个实用的公钥密码体制一即大家最为熟悉的r s a 体制。近 三十多年来，r s a 不断接受实践的考验，目前仍然是应用最为广泛的密码体制之 一。除r s a 密码体制之外，其他学者基于另外的计算问题提出了大量的公钥密码算 法。其中具有代表意义的密码体制有：基于整数分解的改进的r s a 算法【3 2 l 和r a b i n 算 法【1 2 2 1 ，基于有限域上离散对数相关难题的e 1 g a r n a l 算法【5 5 】以及目前被普遍看好的基 于椭圆曲线的方案 9 3 ，1 0 7 ，l 嗍。 d i f f i e 与h e l l m a n 甚至在正式发表“n e wd i r e c t i o n si nc r y p t o g r a p h y ”一文之前，就 发明了数字签名的概念1 0 4 1 。在一个数字签名系统中，公钥与私钥的运作顺序正好 与公钥密码系统相反，发送者首先通过自己的私钥对消息进行数字签名，随后，当 接收者收到消息及其对应的数字签名之后，利用发送者的公钥来证实这个数字签名 的正确性。数字签名可以确保信息的鉴别性、完整性及不可否认性。所谓数字签名 的不可否认性是指：签名的接收者能够证实发送者的身份，发送者不能否认其曾签 署过的签名，其他任何人不能伪造和篡改签名【1 0 4 2 7 1 。 第一个数字签名方案也是由r i v e s t 、s h a m i r 和a d l e m a n 三位密码学家【1 2 5 1 首先提 出。之后，数字签名的理论与技术在密码学界受到了广泛的重视。具有代表意义 的数字签名体制有基于整数分解问题的改进的r s a 签名【3 2 】和r a b i n 签名【1 2 、基于有 限域上离散对数相关难题的e i g a m a l 签名方案t 5 5 】及两个著名的变形- - s c h n o 碰名方 案【i 勰，1 2 9 】以及美国国家数字签名标准d s s t l l 4 - i s l 。 在公钥密码体制的密钥生成过程中，通常先随机产生私钥，之后通过私钥产生 对应的公钥，这样产生的公钥将是一段随机的乱码，因此如何将公钥与其对应的实 上海交通大学博士学位论文 体的身份进行绑定就成为一个棘手的问题。为了解决这个问题，k o h n f e l d e r 在1 9 7 9 年 提出了“公钥证书的概念 1 0 4 1 。公钥证书通常包含这样的一些内容：由公钥持有实 体的身份信息、公钥参数信息，以及由可信第三方( 称为证书权威，或c a ) 对该 ( 证书) 消息的一个数字签名。目前最为流行的基于目录的公钥认证框架为x 5 0 9 证 书框架【8 7 1 。然而，它的建立和维护异常复杂，且成本昂贵。 1 9 8 4 年，s h a m i # 1 3 1 】突破基于目录的公钥认证框架的束缚，提出了基于身份 的( i d e n t i t y b a s e d ) 公钥密码系统的思想。在这种公钥密码系统的密钥生成过程中， 公钥直接为公钥拥有实体的身份信息，因此基于身份的公钥密码系统可以很自然的 解决公钥与实体身份的绑定问题。基于身份的密码系统之所以可直接将身份信息作 为公钥，是因为在其密钥产生过程中，先由实体的身份信息产生公钥，然后再由公 钥产生对应的私钥。在文献【1 3 1 3 】中，s h a m i r 基于r s a 假设【1 2 5 1 给出了一个基于身份的 签名方案。在随后的几年里，其他学者又提出了一些优秀的基于身份的数字签名体 制【5 9 6 0 , 7 9 1 1 6 1 。但是基于身份的加密方案却在很长时间内没有人提出。 s h a m i r 基于身份的公钥密码系统的思想发表1 7 年之后，即到了2 0 0 1 年，b o n e h 和f r a n k l i n 两位学者1 2 6 】基于双线性配对技术提出了第一个实用的基于身份的密码 方案。同年，c o c k s t 4 3 也基于二次剩余理论提出了另外一个基于身份的加密方案。 这两个密码方案都完全符合s h a m i r f l 3 l 】基于身份密码系统的设想。此后，双线性配 对技术b o 成为构造基于身份密码体制的主流，这方面也已经发表了很多优秀的成 果【1 3 2 4 ，3 0 地7 7 6 9 8 2 i o t l 。 1 1 2 安全性模型 人们对公钥密码系统安全性的研究，是随着对攻击方式理解的逐渐加深而日趋 严谨的。最初，人们认识到的攻击手段只有被动攻击，即攻击者只能窃听密文，不 能运用自己掌握的数据操纵或修改密文【3 1 1 0 4 1 。而且对密码方案的破解方式的认识 也仅限于密码体制的完全破解，即已知密码算法及其输出的密文，攻击者的攻击目 标是恢复密文对应的完整明文信息：或者攻击者通过对自己选择的明文密文对的分 析，来达到获取密钥的目标。事实上，真实世界中的攻击者不可能那么被动，他们 完全有可能对密文进行修改、替换或伪造。至于用“对密码方案的完全攻击”来描 述攻击者的行为，在现实世界中更是不可想象的：现实中的攻击者不一定要完全破 译窃听到的密文或攻破密钥，也许只要推知密文中的部分信息就可以获得很大的利 益。 1 9 8 2 年，g o l d w a s s e r 和m i c a l i t 7 2 1 提出了比特安全性的概念：公钥密码系统的安全 性应该使得密文在遭受被动攻击时不能泄露一个比特。他们的想法可形式化描述 为f - 5 7 】：假设攻击者已知两条等长的明文消息和尬，又已知c 是这两条明文消息之 一2 一 第一章绪论 一的密文，那么该攻击者利用任何概率多项式时间算法来判断c 是由哪一条明文对应 的密文，与同“抛币”的方法猜测相比较，其正确的概率“几乎”一样，或者用他 们论文中的说法就是其获得的优势是多项式不可区分的。这个概念又被他们称为语 义安全性，或称为不可区分选择明文攻击( i n d c p a ) 安全。在他们的论文中还有一个 非常重要的成果就是引入了“概率加密”的技术，使得相同的明文每次加密后的结 果是不一样的，这就有效抵抗了存储密文攻击。 g o l d w a s s e r 和m i c a l i 的成果更正了人们对公钥密码安全性方面的一个错误观念， 即攻击者对密码方案的破解方式不仅仅限于完全攻击，因而密码系统安全必须做到 比特级别的安全。用语义安全的概念来审视以前的一些公钥密码体制【1 2 2 ，1 2 5 ，1 s o l 就会 发现，这些体制不是语义安全的。幸运的是，关于r s a j i i 密函数有一条非常有用的 性质：如果一条r s a 密文是对事先不可猜测的信息进行加密，那么从密文中提取一 比特的明文信息就同提取整个明文组一样团难 4 1 , 7 3 - 0 4 1 。因此，只要采用合适的概率 加密技术，那么这些方案都可以改造为语义安全的方案【7 3 1 0 0 1 。 语义安全虽然使人们对公钥密码系统安全性的认识进了一步，但是，在这个概 念中，还是只将攻击者定位在被动攻击的行为上。1 9 9 0 年，n a o r 和y u n g t l l 3 】引入了 不可区分选择密文攻击( i n d c c a ) 安全的概念。在这个概念中，攻击者可以选择自 己需要的密文，并得到解密服务，产生相应的明文，即攻击者可以实施选择密文 攻击。n a o r 和y u n g 还在他们的论文中提到，原本语义安全的一些密码体制f 2 3 引，7 2 j 不 是i n d c c a 安全的。 1 9 9 1 年jr a c k o f f , i s i m o n t n 4 提出了一种更强的安全性概念一不可区分适应性选 择密文攻击( i n d c c a 2 ) 安全。在这个概念中，攻击者在得到他感兴趣的密文c 后， 还可以继续获得除c 之外的解密服务。r a c k o f f 和s i m o n 的成果彻底更正了语义安全概 念中所认为的攻击者的被动攻击行为。 2 0 0 1 年，b o n e h 和f r a n k l i n 2 6 1 在基于身份的密码系统环境中给出了基于身份的不 可区分选择明文攻击( d 心i d c p a ) 安全性的概念和基于身份的不可区分适应性选择 密文攻击( d i n d c c a 2 ) 安全性的概念，在这些概念中，攻击者除了可以拥有对应的 攻击手段，还可以获得针对除攻击目标用户之外的其它用户的私钥提取询问服务。 人们对数字签名体制安全性的认识也是逐渐完善起来的。人们对伪造者的攻击 手段的认识经历了这样几个过程【7 4 ，1 叫： 1 已知公钥攻击。伪造者在攻击的整个过程只知道签名人的公钥。 2 已知消息攻击。伪造者在整个攻击过程中可以利用一些已经存在的由被攻击的 签名人产生的消息签名对。 3 适应性选择消息攻击。在整个攻击过程中，伪造者随时可以得到签名人对由伪 造者所选择消息的签名。 一3 上海交通大学博士学位论文 同样，人们对签名体制的破解方式的认识也经历过如下几个阶 段【3 ，2 5 ，5 5 7 4 , 1 0 2 1 2 2 i s o ： 1 完全破解。伪造者经过整个攻击过程后得到签名人的私钥。 2 通用性伪造。发现一个算法，这个算法和签名人的签名算法是等价的。 3 选择性伪造。在攻击过程开始之前，伪造者选择了一个目标消息，在攻击过程 结束以后，伪造者能够伪造出这个消息的签名。 4 存在性伪造。经过整个攻击过程之后，伪造者至少可以伪造出一个消息签 名对( m ，口) 。当然在整个攻击过程中，伪造者没有就消息m 向签名人询问过签 名，而且消息m 也许是伪造者预先无法知道的，也许是随机的、无意义的，伪 造的后果也许对签名人不会构成一点点伤害。 5 强存在性伪造。经过整个攻击过程之后，伪造者至少可以伪造出一个消息签 名对( m ，盯) 。而且消息m 也许是攻击者预先无法知道的，也许是随机的、无意 义的，伪造的后果也许对签名人不会构成一点点伤害。与存在性伪造不同之处 在于，攻击者在攻击过程中可以就消息m 向签名人询问过签名，但是签名o r 不 能包含在关于m 的询问结果中。 可以看出，从完全破解到强不可伪造性，对破解的要求是逐渐降低的。人 们当然希望数字签名体制在拥有最强攻击手段的攻击者面前也不会以最容易的 破解方式遭到攻击。对于数字签名体制，最基本也最常用的安全性概念是由 g o l d w a s s e r 、m i c a l i 和r i v e s t 7 4 1 于1 9 8 8 年提出的：适应性选择消息攻击下的存在性 不可伪造( e x i s t e n t i a lu n f o r g e a b l ea g a i n s ta 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 ，e u f - c m a ) 。 这个概念非常适合于现实世界的情况b o a 。此后，a n t 3 1 等人提出了一个更强的数字签 名概念，即适应性选择消息攻击下的不可强存在性伪造的数字签名的概念。 2 0 0 3 年，c h a 等人f 蚓和d o d i s 等人【5 3 】分别在g o l d w a s s e r 、m i c a l i 和r i v e s t 的工作基 础上，提出基于身份的适应性选择密文攻击下的不可存在性伪造的数字签名的安全 性概念，在这些概念中，攻击者除了具有适应性选择密文攻击的手段外，还可以获 得针对除攻击目标用户之外的其它用户的私钥提取询问服务。 1 1 3 典型的方案构造技术和安全性证明方法 早期的i n i ) 一c c a 2 安全的公钥密码方案1 5 4 ，1 1 3 ，1 堋都普遍依赖于非交互零知 识( n i z k ) 技术，这些方案效率很低，不实用。1 9 9 1 年，d a m g a r d t 4 6 摒弃 n i z k 技 术，提出了一个重要的设计方法：为了防止攻击者对密文的篡改，保证密文数据的 注：一些攻击手段弓破解方式在概念上是有矛盾的。比如适应性选择消息攻击和选择性伪造就 不能搭配起来【7 4 j 。 4 第一章绪论 完整性，可在一般的公钥密码方案中加入验证方程。虽然d a m g a r d 当时利用这种方法 设计的方案只能达到n d c c a 安全而不是i n d c c a 2 安全的 1 5 3 】，但是他的这种设计 思想却成为以后设计i n c c a 2 安全的密码方案的主流思想。随后，许多基于这种思 想的密码方案被设计出来，其中z h e n g 和s e b e r r y 1 5 3 m 1 提出采用了哈希函数来进行密 文的完整性保护的方法，从效率上对d a m g a r d 的方法进行了非常有意义的改进。 1 9 9 3 年，b e l l a r e 和r o g a w a y 在z h e n g s e b e r r y 方法的基础上，结合f a i t s h a m i r 的预 言机1 6 0 1 的思想，提出了在随机预言模型( r a n d o mo r a c l em o d e l ，r o m ) 下证明i n d c c a 2 安全性的方法【1 4 1 。他们的工作开辟了密码学可证安全的一个方向，即基于随机 预言模型的可证明安全性。 随后，b e l l a r e 和r o g a w a y 又在随机预言模型中提出了明文感知( p l a i n t e x ta w a r e - b e s s ，p a ) 的概念【1 5 1 。他们的思想是：如果一个公钥密码方案是明文感知的，则攻 击者得到一个密文蕴涵着此攻击者预先知道这个密文对应的明文。换句话说，如 果一个公钥密码方案是p a 的，那么攻击者得到的解密服务对他的破译工作没有任 何帮助，因此如果一个公钥密码方案是i n d c p a 安全的，而且是p a 的，那么该密 码方案就是i n d c c a 2 安全的。p a 的思想丰富了基于r o m 的可证明安全性的方法 和内容。做为p a 概念应用的例子，他们在这篇文章中，给出了一个著名的公钥密 码方案r s a c 恤p 。这个方案的安全性证明路线就是i n d c p ! a + p i a 专i n d c c a 2 。 然而，他们在当时提出的p a 的概念并不完善，此证明后来也被s h o u p t l 3 5 1 找出了漏 洞。在1 9 9 8 年，他们对p a 的概念进行了修正【1 1 】。2 0 0 1 年，f u j i s a k i 等人 6 4 1 采用修正后 的p a 概念证明了r s a o a e p 方案确实是i n d c c a 2 安全的。 1 9 9 8 年，c r a m e r 和s h o u p m 】给出了实用的公钥密码方案，并在标准模型下证明了 该方案是i n d c c a 2 安全的。所谓标准模型是指安全性的形式化证明只依赖于方案所 依赖的单向陷门函数的困难性和单向哈希函数的不可逆性，以及哈希函数的一些其 它在真实世界中可以实现的特性。当然，在c r a m e v s h o u p 方案提出以前，也有一些 基于标准模型下可证i n d ，c c a 2 安全的方案【5 4 1 2 4 】，但是这些方案都是基于n i z k 实现 的，正如前文所讨论的，这些方案不实用。c r a m e v s h o u p 方案是第一个实用的基于 标准模型的可证明具有i n d c c a 2 安全性的密码方案。此后，s h o u p 还提出了这个密 码方案的变形【1 3 4 l 。 1 9 9 9 年和2 0 0 0 年，f u j i s a k i 和o k a m o t o 先后发表了两篇文章 6 2 ，6 3 1 ，给出了通用的 而且是比较高效的方法，使得我们可以在r o m 假设下，对一个i n d c p a 安全的密码 方案进行适当改造，使其具有i n d c c a 2 安全性。2 0 0 1 年，b o n e h 和f r a l l k l i n 【硐在提 出他们的基于身份的密码方案的时候，其实就使用丁 f u j i s a k i o k a m o t o 转换方法。 最近，s h o u p t l 3 6 】、b e l l a r e 和r o g a w a y 1 7 】等人都对可证明安全的方法进行了系统 的总结，尤其对证明过程中所普遍采用的“挑战者模拟器一攻击者”之间通过玩 一5 一 上海交通犬学博士学位论文 游戏( g a m ep l a y i n g ) 来进行规约的思路进行了深入分析，总结了游戏序列( g a m e s e q u e n c e ) 定义的一些技巧和原则，使人们对可证明安全的方法和思路有更加系统 的认识。 1 2 量子计算的发展及其对公钥密码学的启示 目前，许多未被攻破的公钥密码体制的安全性假设均依赖于某个特定的计算难 题。迄今为止，最典型的两类安全性假设仍然是整数分解难题和离散对数难题，以 及它们的某些变种和推广。例如， 基于整数分解问题困难性假设的体制。包括r s a 1 2 5 1 、r a b i n w i l l i 锄s c i 钇1 5 1 1 、 l u c 1 4 3 1 、c o c k s 基于二次剩余的i b e 3 2 1 ，等等： 基于离散对数计算困难性假设的体制。包括e l g a m a l e 5 5 1 、椭圆曲线密码系 统e c c 9 3 1 0 9 、二次域理想类群上的密码系统 2 7 ，1 1 0 】、b o n e h 和f r a n k l i n 基于配对 的i b e 2 6 1 ，等等。 然而，量子计算的快速发展，使得这些目前仍然活跃的公钥密码体制面l 隘威 胁。1 9 9 4 年，s h o r f l 3 3 提出了大整数分解和离散对数计算的概率量子算法。1 9 9 5 年， l 【i t a e v 【8 9 】给出了另外一种大整数分解的量子算法。2 0 0 3 年，p r o o s 和z a l k a 1 2 0 1 将s h o r 的 量子算法推广到了椭圆曲线上，得到了求解椭圆曲线上的离散对数问题( e c d l p ) 的 量子算法。这些算法都具有多项式复杂度t 。因此，在量子计算环境下，上述许多现 存的未被攻破的公钥密码体制都将土崩瓦解。虽然许多专家预测量子计算机离我们 至少还有2 0 年的距离，但是这已经足以使我们产生紧迫感：现存的许多密码体制不 再固若金汤了。 能否发展新的公钥密码系统，使其可以抵抗已有的量子攻击呢? 根据目前的量 子计算复杂性理论，人们确实找到了一些计算难题，它们即使到了量子计算时代， 也仍然是困难的。人们也基于这些难题，设计了新的公钥密码系统，例如基于格的 公钥密码系统【2 】，等。 基于配对的各类密码体制的安全性也依赖予离散对数计算困难性假设。 t 对于量子计算而言，由于量子比特的制备十分昂贵，所以，算法的量子宅问复杂度( u p 所需要的量子 比特的数量) 是首先耍考虑的问题。而量子时间复杂度主要是指量子操作( 即对量子寄存器执行测量) 的 次数。另外。目i j 的景了算法都是一种混合机制：即少量的量予操作附加一定的经典计算和推导。因 此，说一个量子算法具有多项式复杂度的含义是： 1 算法所需的量子比特数以输入问题规模的某个多项式为界。典型地，s h o r 算法所需要的量子比 特数为o ( 1 0 9 ) 。 2 算法所需要的量子操作次数也以输入问题规模的某个多项式为界。典型地，s h o r 算法需要的量 子操作次数为o ( 0 0 9 ) 2 ( 1 0 9 l o g n ) 0 0 9 l o g l o g ) ) 。 3 ，算法所需的附加经典计算的空间复杂度和时阃复杂度以问题的输入规模的某个多项式为界。 一6 一 第一章绪论 2 0 0 4 年，k 【9 5 1 提出建议：我们不要把所有的“鸡蛋”都放到一个“篮子”里， 而是应该努力寻找新的不同的公钥密码系统的实现平台。现存的公钥密码系统，它 们更多地是以某个特定的有限交换群( 或环、或域) 为基础，尤其是更多地依赖于 数论上的某些计算难题。而目前发展起来的几个典型的量子算法，恰恰是专门针对 这几个数论问题而设计的。因此，为了抵抗已知的量子算法的攻