（计算机系统结构专业论文）随机预言机模型下可证明安全性关键问题研究.pdf

摘要 随着电子商务、政务等网络应用的蓬勃开展，设计安全并且高效的密码学方 案成为密码学的一个重要课题。可证明安全理论( p r o v a b l es e c u r i t y ) 是在预先精确 设定的安全模型下，用来验证一个设计好的密码学方案是否能抵御现实中自适应 攻击者的形式化分析方法。早期的可证明安全体制一般是基于标准模型( s t a n d a r d m o d e l ) 下，将攻击者成功破解方案的概率可转化为攻破某已知困难问题的优势。 但基于标准模型的密码学方案往往需要大量的计算，难以实用。随机预言机模型 ( r a n d o mo r a c l em o d e l ) 一经提出，便成为了平衡密码学方案的可证安全性和实用 性的重要途径。在随机预言机模型当中，基于一个公共可访问的随机预言机，攻击 者的能力仍然可以规约到某个困难问题，同时方案的计算开销也会因为随机预言机 模型下许多紧规约技巧而大大降低。实际中，广泛使用的密码学方案和标准大都是 基于随机预言机模型下可证安全的。 虽然基于随机预言机模型设计方案具有高效率优势，该模型自身的安全性问题 也不容忽视，许多负面例子说明现有广泛使用的伪随机函数、散列函数等并不能替 换方案证明中所使用的随机预言机，甚至有研究结果表明替换后的方案会失去可证 安全性。如何设计一个实际的，安全的散列函数，来替换模型中所使用的随机预言 1 ，成为了近年来该领域的研究热点问题。我们对随机预言机模型的已有成果及其 存在的安全性问题进行了总结和分析。首先我们针对基于分组密码的散列函数给出 了相应的与随机预言机的白盒不可区分性( 1 n d i f f e r e n t i a b i l i t y ) 。 1 我们给出了对基于分组密码的散列函数的白盒不可区分性的进一步分析， 并给出了一个更加精确的对应基于分组密码的散列函数的白盒不可区分性 攻击者的形式化定义。白盒不可区分性的优势对应于散列函数是_ 否k e y e d 的 情况加以了区分。我们指出t c h a n g 等人对于4 种p g v 和p b g v 方案给出可区 分性攻击存在缺陷，而且给出对应的形式化证明来表明4 种p g v 和p b g v 构 造实际上在使用p r e f i x f r e ep a d d i n g 、h m a c n m a c 和c h o pc o n s t r u c t i o n 等改进 型m d 构造后，并同样基于压缩函数满足限定长度的随机预言机的性质，那么 这些散列函数与随机预言机是满足白盒不可区分性的。 2 基于密钥长度是分组长度两倍情况的分组密码，我们更进一步地对速率 ( r a t e ) 为l 的双倍分组长度散列函数的构造方法和安全性加以研究。研究工 作可分为以下三个方面：首先，我们给出了针对h i r o s e 提m 的两个作为公开问 题的例子的攻击，该攻击证实h i r o s e 给出的例子并不能达到最优化抵抗原像和 二次原像攻击，同时给出三个反例证明h i r o s e 给出的最优化抗碰撞的两个必要 条件并不完善。其次，基于上述攻击和反例，我们形式化的分析了由s a t o h 等人 在文献中定义的速率为l 的双倍分组长度散列函数，来找寻是否存在速率为l 并 且达到最优化安全的双倍分组长度散列函数。在上述分析之后，我们进一步给 出了该类型下速率为l 的双倍分组长度散列函数达到最优化安全的必要条件。 特别地是，我们针对两个基于新的必要条件下的有代表性的例子给出了白盒不 可区分性的形式化证明。 其次，对于随机预言机模型下的可证明安全性，选择合适的紧致规约证明技巧 来达到安全性与效率的平衡，在方案设计中也是十分重要的。将协议中使用的散列 函数理想化为随机预言机，同时基于若干实用性签名方案的设计与规约证明，我们 通过这些签名方案的可证明安全来介绍随机预言机模型下最有效的几种证明技巧。 这些技巧都具有推广性和启发性，因而被广泛用在其他协议的设计、证明过程中。 1 我们首先介绍了部分盲签名的基本概念及其安全性定义，随后基于离散对 数问题给出了一种高效率的部分盲签名的方案( d l p p b s ) 的设计与安全性 分析，与以往若干方案相比，d l p p b s 方案的计算和存储开销均有降低。由 于l f s r 序列在替换表示有限域元素上的优势，我们基于n 阶l f s r 序列和d l p p b s 方案给出了另一种高效率的部分盲签名方案。我们所给出的两种部分盲签 名方案均是在随机预言机模型下证明了其安全性。与有限域上的方案相比，基 于l f s r 的部分盲签名长度有所减少。特别的是，两种方案证明中都使用分叉 引理作为安全性规约方法。 2 我们给出了两种无证书公钥体制下的聚集签名方案。两种方案具有不同的优 势，我们能根据实际应用场景的不同加以选择合适的方案。在随机预言机模型 下，两种无证书聚集签名方案都通过全域散列规约方法将方案的安全性规约到 了椭圆曲线上的计算d i f f i e h e l l e m a n 困难问题之上，没有使用分叉引理规约方 法。 关键词：密码学，可证明安全，随机预言机，散列函数，双倍分组长度，数字 签名，部分盲签名，聚集签名 a b s t r a c t w i t ht h eb r o a di m p l e m e n t a t i o n so ft h ee l e c t r o n i cb u s i n e s sa n dg o v e r n m e n ta p p l i c a t i o n s ， h o wt od e s i g nas e c u r ea n df e a s i b l ec r y p t o s y s t e mb e c o m e sm o r ea n dm o l ls i g n i f i c a n ti nt h e r e s e a r c ho fc r y p t o l o g y t h et h e o r yo fp r o v a b l es e c u r i t yi saf o r m a la n a l y s i st e c h n i q u ef o r w h i c ht h ed e s i g n e rd e f i n e sap r e c i s ea d v e r s a r ym o d e li na d v a n c e ，a n dt h e np r o v e sw h e t h e r a w e l l d e s i g n e dc r y p t o s y s t e m sc a nr e s i s tt h ea d v e r s a r y i nr e a l i t y t h ec l a s s i c a lp r o v a b l es e e r - r i t yi su s u a l l yb a s e do nt h es t a n d a r dm o d e l ，s u c ht h a tt h ep r o b a b i l i t yo fas u c c e s s f u la t t a c k c a l lb er e d u c e dt ot h ea d v a n t a g eo fr e s o l v i n gaw e l l - k n o w nc o m p u t a t i o n a l l yh a r dp r o b l e m c o m m o n l y ，t h es c h e m e s t h a ta l ep r o v e ns e c u r ei nt h es t a n d a r dm o d e la t el e s se f f i c i e n t ，w h i c h m a k e st h e ml e s sp r a c t i c a l t h ef o r m a la n a l y s i su n d e rt h er a n d o mo r a c l em o d e lb e c o m e s 卸 i m p o r t a n tw a yt ob a l a n c et h ep r o v a b l es e c u r i t ya n dt h ee f f i c i e n c y i nt h ed e s i g no fc r y p t o s y s - t e m s i nt h er a n d o mo r a c l em o d e l ，b yi m p l e m e n t i n gap u b l i c l ya c c e s s i b l er a n d o mo r a c l e ， t h ep r o b a b i l i t yo ft h es u c c e s s f u la t t a c kc a nb er e d u c e dt oac o m p u t a t i o n a l l yh a r dp r o b l e m a s w e l l s i m u l t a n e o u s l y ，b yu s i n gt h et i g h tr e d u c t i o nt e c h n i q u e si nt h er a n d o mo r a c l em o d e l ， t h es c h e m e s c o m p u t a t i o n a lc o s t sw i l la l s ob er e m a r k a b l yr e d u c e d i nf a c t ，m a n yw i d e l y a c c e p t e dc r y p t o g r a p h i cs c h e m e sa n ds t a n d a r d sh a db e e np r o v e ns e c u r eu n d e rt h er a n d o m o r a c l em o d e l a l t h o u g hw ee n j o yt h ee f f i c i e n c yo ft h es c h e m e st h a ta r ep r o v a b l ys e c u r e i nt h er a n d o m o r a c l em o d e l ，t h i sm o d e lh a ss e c u r i t yp r o b l e m si t s e l f m a n yn e g a t i v er e s u l t sd i s c l o s e dt h a t p s e u d o r a n d o mf u n c t i o n sa n dh a s hf u n c t i o n si nr e a l i t yc a n n o ti n s t a n t i a t et h er a n d o mo r a c l e m a n i p u l a t e di nt h es i m u l a t i o n s i tb e c o m e sar e d h o tt o p i ci nt h i sr e s e a r c hf i e l do nh o w t od e s i g nac r y p t o g r a p h i ch a s hf u n c t i o nt or e p l a c et h er a n d o mo r a c l ei nt h es c h e m e st h a t a r ep r o v e ns e c u r eu n d e rt h er a n d o mo r a c l em o d e l i nt h i st h e s i s ，w es u m m a r i z et h ek n o w n r e s u l t sa n dt r a c et h es e c u r i t yp r o b l e m si nt h er a n d o mo r a c l em o d e l ： 1 as y n t h e t i ci n d i f f e r e n t i a b i l i t ya n a l y s i so fs o m eb l o c k - c i p h e r b a s e dh a s hf u n c t i o n si s c o n s i d e r e d f i r s t ，am o r ep r e c i s ed e f i n i t i o ni sp r o p o s e do i lt h ei n d i f f e r e n t i a b i l i t ya d v e r - s a r yi nb l o c k c i p h e r - b a s e dh a s hf u n c t i o n s n e x t ，t h ea d v a n t a g eo fi n d i f f e r e n t i a b i l i t yi s s e p a r a t e l ya n a l y z e db yc o n s i d e r i n gw h e t h e rt h eh a s hf u n c t i o ni sk e y e d o rn o t f i n a l l y , al i m i t a t i o ni so b s e r v e di nc h a n ge ta 1 si n d i f f e r e n t i a b l ea t t a c k so nt h ef o u rp g va n d t h ep b g vh a s hf u n c t i o n s 。t h ef o r m a lp r o o f ss h o wt h ef a c tt h a tt h o s eh a s hf u n c t i o n s i v a r ei n d i f f e r e n t i a b l ef r o mar a n d o mo r a c l ei nt h ei d e a lc i p h e rm o d e lw i t ht h ep r e f i x f r e e p a d d i n g ，t h en m a c h m a ca n dt h ec h o pc o n s t r u c t i o n 2 t h es e c u r i t yo ft h er a t e 一1d o u b l eb l o c kl e n g t hh a s hf u n c t i o n s ，w h i c hb a s e do nab l o c k c i p h e rw i t hab l o c kl e n g t ho fn b i ta n dak e yl e n g t ho f2 n b i t ，i sr e c o n s i d e r e d p r e i m a g ea n ds e c o n dp r e i m a g ea t t a c k sa r ed e s i g n e dt ob r e a kh i r o s e st w oe x a m p l e sw h i c h w e r ei e ra sa no p e np r o b l e m c o u n t e r - e x a m p l e sa n dn e wa t t a c k sa r ep r e s e n t e do na g e n e r a lc l a s so fd o u b l eb l o c kl e n g t hh a s hf u n c t i o n sw i t hr a t e1 ，w h i c hd i s c l o s et h e r e e x i s tu n c o v e r e df l a w si nt h ef o r m e ra n a l y s i sb ys a t o he ta 1 a n dh i r o s e s o m er e f i n e d c o n d i t i o n sa r ep r o p o s e df o re n s u r i n gt h i sg e n e r a lc l a s so ft h er a t e 1h a s hf u n c t i o n st 0 b eo p t i m a l l ys e c u r ea g a i n s tt h ec o l l i s i o na t t a c k i np a r t i c u l a r , t w ot y p i c a le x a m p l e s ， w h i c hd e s i g n e du n d e rt h ep r o p o s e dc o n d i t i o n s 。a r ep r o v e nt ob ei n d i f f e r e n t i a b l e 劬m t h er a n d o mo r a c l ei nt h ei d e a lc i p h e rm o d e l f o rt h ep r o v a b l es e c u r i t yu n d e rt h er a n d o mo r a c l em o d e l ，t h eo t h e r k e yp r o b l e mi st o c h o o s eat i g h tr e d u c t i o nt e c h n i q u et ob a l a n c et h es e c u r i t ya n dt h ee f f i c i e n c yi np r a c t i c e b y s i m u l a t i n gt h eu n d e r l y i n gh a s hf u n c t i o na sar a n d o mo r a c l e ，w ep r e s e n ts o m ew e l l d e s i g n e d s z g n a t u r es c h e m e sw h i c ha r ee f f i c i e n t l yg i v e nt h er e d u c t i o np r o o f si nt h er a n d o mo r a c l e m o d e l a l lt h e s er e d u c t i o np r o o f sc a nb ee a s i l ye x t e n d e dt ot h ep r o v a b l es e c u r i t yo ns i m i l a r s i g n a t u r es c h e m e si nt h er a n d o mo r a c l em o d e l 1 b a s e do nt h ed i s c r e t el o g a r i t h mp r o b l e ma n dt h es c h n o r r sb l i n ds i g n a t u r es c h e m e ， w ep r o p o s ean e we f f i c i e n tp a r t i a l l yb l i n ds i g n a t u r es c h e m e t h ec o m p u t a t i o na n d c o m m u n i c a t i o nc o s t sa r eb o t hr e d u c e di no u rs c h e m e w ea l s o p r o v i d ean e wp a r t i a l l y b l i n ds i g n a t u r es c h e m ew h i c hi sb a s e do n 讫t ho r d e rc h a r a c t e r i s t i cs e q u e n c e sg e n e l - - a t e db yl f s r b yu s i n gt h ef o r k i n gl e m m ar e d u c t i o nt e c h n i q u e t h e i rs e c u r i t i e sa r e p r o v e ni nt h er a n d o mo r a c l em o d e l c o m p a r e sw i t ht h ef i n i t ef i e l db a s e ds c h e m e s ，o u r s c h e m es h o w sa d v a n t a g e so nt h ec o m p u t a t i o na n ds t o r a g es i n c et h e r e d u c e dr e p r e s e n t a t i o no ff i n i t ef i e l de l e m e n t sb yl f s r b o t ho ft h es c h e m e sc a nm a k e p f i v a c y o r i e n t e d a p p l i c a t i o n s ，w h i c ha r cb a s e do np a r t i a l l yb l i n ds i g n a t u r e s ，b e c o m em o r e p r a c t i c a lf o r h a r d w a r e l i m i t e de n v i r o n m e n t ，s u c ha ss m a r t p h o n e sa n dp d a s 2 w e p r o p o s et w oc e r t i f i c a t e l e s sa g g r e g a t es i g n a t u r es c h e m e s ，w h i c ha r et h ef i r s ta g g r e g a t es i g n a t u r es c h e m e si nt h ec e r t i f i c a t e l e s sc r y p t o s y s t e m s t h ef i r s ts c h e m er e d u c e s t h ec o s t so fc o m m u n i c a t i o na n ds i g n e r - s i d ec o m p u t a t i o nb u tl o s e so ns t o r a g e ，w h i l e t h es e c o n ds c h e m em i n i m i z e st h es t o r a g eb u ts a c r i f i c e st h ec o m m u n i c a t i o n w ec a l l v 一 卜海交通大学博上学位论文 c h o o s eo n eo ft h ea b o v es c h e m e sb yc o n s i d e r i n gt h ei m p l e m e n t a t i o nc i r c u m s t a n c e i na d v a n c e ，o u rs c h e m e sd on o tn e e dt h ep u b l i ck e yc e r t i f i c a t ea n y m o r ea n da c h i e v e t h et r u s tl e v e l3 w h i c hi st h es a m el e v e li nt h et r a d i f o n a lp k i b o t ho ft h es c h e m e s a r ep r o v a b l ys e c u r ei nt h er a n d o mo r a c l em o d e lb ya s s u m i n gt h ei n t r a c t a b i l i t yo ft h e c o m p u t a t i o n a ld i f f i e h e l l e m a np r o b l e mo v e rt h eg r o u p sw i t hb i l i n e a rm a p s k e yw o r d s ：c r y p t o l o g y , p r o v a b l es e c u r i t y , r a n d o mo r a c l e ，h a s hf u n c t i o n s ，d o u b l eb l o c k l e n g t h ，d i g i t a ls i g n a t u r e s ，p a r t i a l l yb l i n ds i g n a t u r e s ，a g g r e g a t es i g n a t u r e s 主要符号对照表 整数 实数 o ，1 ，n 一1 ) 自然对数，e 2 7 1 8 2 8 单位置换 全0 向量 g 元有限域 二元异或运算符 串连接符 求余运算符 元素a 属于集合a 集合a 是集合b 的子集 集合a 是集合b 的真子集 两集合求交集( i n t e r s e c t i o n ) 操作符 两集合求并集( u n i o n ) 操作符 表示消息m 的二进制长度 x 童b b z r e 1 o。i删一埏肛n u m 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 学位论文作者签名： 日期：泄年卫月日 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 第一章绪论 随着现代密码学理论的发展，在面向各种应用的密码方案设计中，可证明安全 性( p r o v a b l es e c u r i t y ) 受到越来越多的重视。某个方案没有通过形式化验证确认其 可证明安全性，是无法想象能被广泛接受而投入到现实应用当中来。古典密码学中 将某个方案的安全性简单归结为某种函数运算( 大整数分解，背包问题，离散对数 等) 的单向性上【l ，2 ，3 】，并没有充分考虑适应性攻击者和实际应用中复杂的环境条 件影响。单向函数只是作为方案的一个基础组成部分( a t o m i cp r i m i t i v e ) ，往往只 能作为方案安全性的必要而非充分条件。因而采用该思路而设计的方案往往很快被 发现其中可被适应性攻击者利用的漏洞，例如二次剩余加密方案可被适应性攻击者 利用【2 ，4 】，以不可忽略的概率对模数进行分解，大量方案被随后的研究证实存在安 全漏洞，如文献【5 ，6 ，7 ，8 ，9 】中提出的当时“认为”是安全的方案。将方案安全性证 明形式化，模型化成为了证明结论可信度的评判标准。基于某个充分仿真现实环境 的模型，如果方案在该模型中发现存在可被攻击者利用的漏洞，则证明其在现实环 境中也肯定是不安全的。 根据所基于的不同理论，可证明安全性可分为信息论安全( i n f o r m a t i o nt h e o r y s e c u r i t y ) 和计算复杂性安全( c o m p u t a t i o n a lc o m p l e x i t ys e c u r i t y ) 两大类【1 0 ，1 1 】。 信息论安全由c s h a n n o n 在其开创性的文献【1 2 】中给出定义，一个方案如果满足信息 论安全，那么无论攻击者具有什么样的计算能力都无法破解，所以信息论安全又被 称为无条件安全。虽然信息论安全在安全上是完美的，但却有着难以实用的缺点， 因而只是用在军事和外交等对信息保密极度敏感的领域。计算复杂性安全是基于复 杂性理论之上的一套模型，它将攻击者的能力限定为多项式时间，一个方案是否安 全取决于攻击者成功的优势能否规约到以不可忽略的概率解决某个已知困难问题， 例如大整数分解，二次剩余，离散对数等。计算复杂性安全虽然并不能保证无条件 安全( 例如在量子计算机中大数分解问题不再是困难的) ，并且对攻击者的能力加 以了限制，但在理论下的攻击者的计算能力实际上已远远超过现实当中存在的攻击 者，因而计算复杂性安全模型下的方案在实际应用中仍然是可以信赖的。因而在现 实环境当中。攻击者在计算能力上并无任何特别的优势可言。在本文以后的部分 巾，如果没有加以特殊说明，我们所列出的方案的可证明安全性均是基于计算复杂 性理论加以讨论的。 早期基于计算复杂性安全的密码方案一般是基于标准模型( s t a n d a r dm o d e l ) 下，该模型首先对方案中攻击者的能力加以定义，而且必须强调攻击者一定是自适 应性的。然后假设该攻击者成功的概率为某个多项式时问不可忽略的值，然后通过 卜海交通大学博上学位论文 一定的步骤利用该攻击者，将攻击者的能力转化为攻破某已知困难问题的优势。由 于该困难问题在多项式时间下无法求解，因而可以得出存在攻击者以不可忽略概率 攻破方案这一假设与事实相矛盾。不幸的是，基于标准模型的密码方案往往需要大 量的计算，难以实用。如现有最高效的标准模型下安全的公钥加密方案【1 3 】，数字 签名方案【1 4 】，仍然没有广泛加以使用。如何设计一个面向具体应用的密码方案， 同时平衡可证明安全性和实用性，成为了密码方案设计中首要考虑的问题。因为一 个低效率的方案与不安全的方案一样，都无法在实际当中被广大用户接受并广泛使 用。 1 1 基于随机预言机模型的可证明安全研究现状 虽然计算复杂性安全模型下的方案已经比信息论安全模型下的方案更加实用， 但仅从标准模型下的现有绝大部分方案来看，都无法在实际当中推广开来，造成 了密码学理论和实践中的一个鸿沟。其原因在于有许多广泛应用的方案虽然无法 给出标准模型下的证明，但在长期应用中抵御住了实际的攻击者，取得了大众的 信任【1 5 ，1 6 】。同时标准模型下设计一个安全的方案十分困难，没有形成一套方 法论，方案的设计成为一种科学艺术( a r t ) 而非工程( e n g i n e e r i n g ) 。这种状况 在1 9 9 3 年，b e l l a r e 和r o g a w a y 仓t j 造性地提出随机预言机模型后【1 7 】，取得了飞跃性的 进步。 1 1 1 随机预言机模型的定义 随机预言机( r a n d o mo r a c l e ) 的定义是一个确定性的公共可访问的随机均匀分 布函数( u n i f o r m l yd i s t r i b u t e d ) ，对于任意长度的输入，在输出域中均匀选择一个 确定性长度的值作为询问的回答。随机预言机模型是在标准模型的基础上增加了一 个公共可访问的随机预言机，将方案中所使用的散列函数( h a s hf u n c t i o n ) 理想化 为随机预言机，攻击者( a d v e r s a r y ) 只能通过询问随机预言机来获得所需要的散列 值( h a s hv a l u e ) 。然后仿真者( s i m u l a t o r ) 通过一定的步骤利用该攻击者，将攻 击者的能力转化为攻破某已知困难问题的优势( a d v a n t a g e ) 。在绝大部分方案的 实际应用中，用一个安全的散列函数( 如s h a 1 ，s h a 2 5 6 ，3 8 4 等) 来替代随机预言 机，方案的安全性便基于可证明安全的规约结果和散列函数本身与随机预言机的可 区分性之上。同时与标准模型下可证明安全的方案相比较，方案的计算开销也会因 为随机预言机模型下许多紧规约技巧( t i g h tr e d u c t i o n ) 而大大降低。虽然随机预 言机模型仍然是基于计算复杂性理论，但为了加以区分，我们将计算复杂性安全模 型中没有使用随机预言机的称之为标准模型( s t a n d a r dm o d e l ) 。随机预言机模型 一经提出，便成为了平衡密码方案可证安全性和实用性的重要途径。在随机预言机 一2 一 第一章绪论 模型下设计一个实用，高效并且安全的方案不再是不可平衡的矛盾。许多广泛应 用的密码方案都是基于随机预言机模型安全的，如数字签名( d i g i t a ls i g n a t u r e ) 方 案p s s 【1 8 】，公钥加密( p u b l i ck e ye n c r y p t i o n ) 方案r s a o a e p 【1 9 ，2 0 ，密钥分配协 议( k e ye x c h a n g ep r o t o c 0 1 ) 【1 7 1 。 1 1 2 随机预言机模型下可证明安全过程 在随机预言机模型下，我们将整个证明过程定义为一个仿真游戏( g a m e ) 。在 模型中除了随机预言机之外，还存在一个仿真者( s i m u l a t o r ，简称s i m o n ) ，该仿 真者对攻击者( a d v e r s a r y ，简称m a l i c e ) 所有定义的询问进行回答，这一过程 被称之为训练( t r a i n n i n g ) 。在仿真游戏的最后，仿真者s i m o n 给出事先确定的挑 战( c h a l l e n g e ) ，如果攻击者m a 三，c e 完成挑战，则仿真游戏成功。由于事先确 定的挑战包含有仿真者可用来解答方案所基于的困难问题的知识( k n o w l e d g e ) ， 如果仿真游戏成功的概率为不可忽略的值，那么必然方案所基于的困难问题在给 定攻击者的环境下不再是困难的，这与现实环境中该已知困难问题的不可计算性 ( c o m p u t a t i o n a li n t r a c t a b l e ) 相矛盾，因而该攻击者实际是不存在的，方案在模型下 是安全的。图1 1 【4 】给出了仿真游戏的描述。 e n c r y p t i o ns c h e a n e & p u b l i ck e y 1 1 1 c r y p t a n a l y s i s ：t r a i a n 8 m 。 a - ，7 吩， l ，一c c e - c r y p t a a a l y s i s t r a i t t m g _ _ _ _ _ _ _ _ 。e d u c a t e dg u e s s e n c r y p t i o ns c h e m e & p u b l i ck e y m a l l c e s i m u l a t e d c t t p t a ：m l y s i s 仃a m 噼 p 一 s j 1r s a f。 ar a i l n 吼 ，np o i n t o ，1 f 叫佃 l 、 一7 。晴。l c r e d u c e ”a na t t a c kt os o l v i n gah a r dp r o b l e m 图1 1随机预言机模艰下的仿真游戏过程 n k o b l i t z 和j m e n e z e s 在文献【l o ，1 1 】中总结了可证明安全理论的发展和近况。 他们通过总结近年来关于可证明安全性一些分析性文献【2 l ，2 2 ，2 3 ，2 4 ，1 6 】，得出的结 一3 一 卜海交通大学博上学位论文 论是对于随机预言机模型而言，对于现有的方案设计来说是积极而有帮助的。散列 函数与随机预言机相似的性质( 快速，确定，单向，均匀分布) 使其在密码方案设 计中扮演了非常重要的角色。实际上，对某个消息进行散列运算之后再处理可以增 加该消息的冗余度，从信息论安全的角度来看是十分有益的。 1 1 3 随机预言机的类型 在基于随机预言机模型下的密码方案的证明当中，使用随机预言机的方法也有 不同，从仿真者对随机预言机加以控制的程度不同可以分为以下三种类型： 1 无控制型 此类型下，仿真者无法截取攻击者提出的询问，也不能控制随机预言机的输 出信息，该模式下的随机预言机与现实中密码学散列函数( c r y p t o g r a p h i ch a s h f u n c t i o n ) 最为接近。 2 部分控制型 在一些方案中，仿真者可以知道攻击者提出的询问，但不能控制随机预言机的 输出，该模式相当于仿真者可以窃听攻击者，在现实中需要仿真者对攻击者的 通信完全可知，在大多数的内网环境或存在木马、后门程序的情况下，具有合 理性。 3 完全控制型 在大多数的方案中，要求仿真者对随机预言机完全控制，对于每一个询问，仿 真者可以按照一定规则返回输出值给攻击者。该模式下的随机预言机实际上已 无法直接由实际中的任何散列函数加以替换。 1 2 随机预言机模型下可证明安全规约方法 与标准模型相比，除了提高效率之外，随机预言机模型另外一个显著优势就在 于方案的安全性证明成为了一套可以重复使用的方法论。安全性证明的规约方法集 中存了将方案中的散列函数替换为随机预言机，然后按照一定的规则返回询问请 求。对于询问回答的要求是确定性，并且在攻击者看来是输出域均匀分布的。所以 在随机预言机模型下的密码方案往往可以规约到比较著名的困难问题( 例如离散对 数，计算d i f f i e h e i l e m a n 问题) ，而在标准模型下的方案一般都需要些特殊的困难 问题假设( 例如s t r o n gr s a 假设【2 5 ，b d h 假设【2 6 ，2 7 等) 。下面我们将会介绍随机 预言机模型下最具代表性、最有效的儿种证明方法，这些方法都具有启发性，因而 被广泛用在密码学方案的设计、证明过程中。 一4 一 第一章绪论 1 2 1 分叉引理规约方法 在一段相当长的时期里，e 1 g a m a l 【2 8 1 及其各种类似的数字签名方案( 例 如s c h n o r r 签名 2 9 】，d s s 签名 3 0 】) 都没有形式化的证明方法，将方案的安全性 规约到某个已知并充分研究过的困难问题。人们只是相信攻破e i g a m a l 类数字 签名与解决大素数有限域上某个个密码学子群的离散对数问题是等价的。直 至u 1 9 9 6 年，p o i n t c h e v a l 和s t e r n 在文献【3 1 中给出了形式化的证明方法，将e i g a m a l 类 数字签名方案的安全性规约到离散对数问题上。他们给出的证明方法是基于随机预 言机模型的，并且该证明方法具有很好的移植性，对于所有e i g a m a l _ _ = 元组性质的 数字签名方案都可以采用此证明方法。由于在证明过程中使用到了随机预言机回答 分叉规约技术( f o r k i n gr e d u c t i o nt e c h n i q u e ) ，所以该证明方法又被广泛称之为分 叉引理( f o r k i n gl e m m a ) 。在2 0 0 0 年，p o i n t c h e v a l 和s t e r n 在文献【3 2 中进步完善 了e i g a m a l 类数字签名方案的分叉引理，并将该证明方法扩展到盲签名方案上。 对于e i g a m a l 类数字签名来说，我们假定p 是一个大素数，夕是p 上一个q 阶子群的 生成元。系统私钥s k = z ，公钥p k = 旷( m o dp ) = 可。一个完整的对应任意消息m 的 签名由三元组( ，e ，s ) 构成。 r 为每生成一个签名时所需要的承诺( c o m m i t m e n t ) 。r 的值由每次签名都独立 且互不相同的一个值f 来决定。通常选用的方式是r = g ( m o d p ) 。 e = n ( m ，r ) ，日( ) ： o ，1 ) _ o ，1 ) 。定义为一个密码学散列函数1 3 3 1 。在随机 预言机模型下的方案用到散列函数时，往往假定散列函数为密码学散列函数， 保证其与随机预言机的可替换性。在后面的章节中，我们会对密码学散列函数 的定义加以介绍。在本文中，如上下文无特殊说明，散列函数均指密码学散列 函数。 s 是对应消息m 和承诺r 的签名，它是由私钥x ，消息m ，承诺r 所确定的一个线 性值。通常选用的方式为s = - 1 1 ( 7 z e ) ( m o dq ) 。 根据以上定义，