（计算机软件与理论专业论文）无密钥泄露的变色龙hash函数及其应用.pdf

题目：无密钥泄漏的变色龙h a s h 函数及其应用 专业：计算机软件与理论 硕士生：伍春晖 指导教师：陈晓峰副教授 摘要 变色龙h a s h 函数，首先由k r a w c z y k 和r a b i n 提出，它是一种带陷门的单向 h a s h 函数，掌握陷门信息的人可以容易地计算出一个随机输入的碰撞，而没有陷 门信息的人则无法计算碰撞。 变色龙h a s h 函数最初用于设计变色龙签名。变色龙签名可以看成是特殊的 不可否认签名，可以有效地解决不可抵赖性和控制可验证性之间的矛盾。它比不 可否认签名更简单，采用非交互式证明、计算量小，所以更为有效。早期的变色 龙签名存在密钥泄露的缺陷，从而削弱了变色龙签名的不可传递性。c h e n 等提 出了第一个无密钥泄露变色龙h a s h 函数的完全构造。变色龙h a s h 的另一个重要 应用是设计在线离线签名。在线离线签名利用离线阶段的预计算信息来加快在 线阶段的签名过程。s h a m i r 和t a u m a n 首先提出“h a s h s i g n s w i t c h ”机制，用于 设计一般的在线离线签名方案。然而，目前存在的所有基于s h a m i r - t a u m a n 机 制的在线离线签名方案都存在效率不高的问题，这也是由于变色龙h a s h 的密钥 泄露引起的。即在离线阶段，签名者需要预计算和存储大量不同的变色龙h a s h 值及对应的签名。 本文主要研究无密钥泄漏的变色龙h a s h 函数的性质及其应用。首先，基于 b l s 签名本文提出了一种新的变色龙聚合签名和变色龙多签名方案，并证明了其 安全性。其次，利用双陷门的变色龙h a s h 函数族，本文提出了一个新的有效的 在线离线门限签名方案，同时证明了方案的安全性。 关键词：变色龙h a s h ，密钥泄露，变色龙签名，聚合签名，多签名，不可否认签 名，在线离线签名，门限签名 t i t l e ：k e ye x p o s u r ef r e ec h a m e l e o nh a s ha n di t sa p p l i c a t i o n s m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：w uc h u n h u i s u p e r v i s o r ：a p r o f c h e r tx i a o f e n g c h a m e l e o nh a s hf u n c t i o n s , f i r s ti n t r o d u c e db yk r a w c z y ka n dr a b i n ，a l e t r a p d o o ro n e - w a yh a s hf u n c t i o n sw h i c hp r e v e n te v e r y o n ee x c e p tt h eh o l d e ro ft h e t r a p d o o ri n f o r m a t i o nf r o mc o m p u t i n gc o l l i s i o n sf o rar a n d o mg i v e ni n p u t c h a m e l e o nh a s hf u n c t i o n sw e r e0 r i g i n a yu s e dt od e s i g nc h a m e l e o ns i g n a t u r e s c h a m e l e o ns i g n a t u r e sc a nb es e e m e da ss p e c i a lu n d e n i a b l es i g n a t u r e s , w h i c hs o l v e t h ec o n f l i c tb e t w e e nn o n - r e p u d i a t i o na n dc o n t r o l l e dv e r i f i a b i l i t ys i m p l e ra n dm o r e e f f i c i e n t p r e c i s e l y , c h a m e l e o ns i g n a t u r e sa r en o n - i n t e r a c t i v ea n dd on o ti n v o l v et h e d e s i g na n dc o m p l e x i t yo fz e r o - k n o w l e d g ep r o o f s w h i c ht r a d i t i o n a lu n d e n i a b l e s i g n a t u r e sa r cb a s e d h o w e v e r , t h ei n i t i a lc h a m e l e o ns i g n a t u r es u f f e rf r o mt h ek e y e x p o s u r ep r o b l e m ，w h i c hu n d e r m i n i n gt h ec o n c e p to fn o n - t r a n s f e r a b i l i t y c h e ne ta l p r o p o s e dt h ef i r s tf u l lc o n s t r u c t i o no fc h a m e l e o nh a s hw i t h o u tk e ye x p o s u r e a n o t h e r i m p o r t a n tu s eo fc h a m e l e o nh a s hj si no n - l i n e o f f - l i n es i g n a t u r e s o n - l i n e o f f - f i n e s i g n a t u r e su s ct h ep r e - c o m p u t e di n f o r m a t i o ni no f f - l i n ep h r a s et oi m p r o v et h e p e r f o r m a n c eo fs i g n i n g , s h a m i ra n dt a u m a nf i r s tp r o p o s e dt h e “h a s h - s i g n - s w i t c h ” p a r a d i g mt od e s i g nag e n e r i co n - l i n e o f f - l i n es i g n a t u r es c h e m e h o w e v e r , w ea r g u e t h a ta l le x i s t i n go n - l i n e o f f - l i n e s i g n a t u r e s c h e m e sb a s e do ns h a m i r - t a u m a n s p a r a d i g ms u f f e rf r o mt h ek e ye x p o s u r ep r o b l e mo fc h a m e l e o nh a s h , 巴。t h es i g n e r s s h o u l dp r e - c o m p u t ea n ds t o r ep l e n t yo fd i f f e r e n tc h a m e l e o nh a s hv a l u e sa n dt h e c o r r e s p o n d i n gs i g n a t u r e so nt h eh a s hv a l u e si nt h eo f f - l i n ep h a s e h e n c e , t h e c o m p u t a t i o na n ds t o r a g ec o s t si nt h e s es i g n a t u r es c h e m e sa r cs t i l lal i t t l em o r e o v e r l o a d t h i st h e s i sf o c u s e so nt h ep r o p e r t i e sa n da p p l i c a t i o n so fk e ye x p o s u r ef r e e c h a m e l e o nh a s hf u n c t i o n s f i r s t l y , w cp r o p o s e dan o wc h a m e l e o na g g r e g a t es i g n a t u r e s c h e m ea n dan e wc h a m e l e o nm u l t i - s i g n a t u r es c h e m eb a s e do i lb l ss h o r ts i g n a t u r e s a n dp r o v e dt h e i rs e c u f i t y s e c o n d l y , w ep r o p o s e dan e we f f i c i e n to n - l i n e o f f - l i n e t h r e s h o l ds i g n a t u r es c h e m ed u et oc h e ne ta 1 ss p e c i a ld o u b l e - t r a p d o o rc h a m e l e o n h a s hf a m i l ya n dp r o v e di t ss 鲫r i t y k e yw o r d s ：c h a m e l e o nh a s h , k e ye x p o s u r e , c h a m e l e o ns i g n a t u r e s ，a g g r e g a t e s i g n a t u r e s ，m u l t i - s i g n a t u r e s , u n d e n i a b l es i g n a t u r e s ，o n - l i n e o f f - l i n es i g n a t u r e s , t h r e s h o l ds i g n a t u r e s i v 第1 章绪论 1 1 课题背景 第1 章绪论 变色龙h a s h 函数，由k r a w c z y k 和r a b i n 1 8 首先提出。或称为陷门h a s h 函 数，这里使用“变色龙”的名字是指陷门信息的拥有者有能力在不改变函数输出 的情况下，任意改变函数的输入。变色龙h a s h 函数是一个非标准的抗碰撞h a s h 函数，它包含一对h a s h k e y h k 和t r a p d o o r k e y t k ，并具有以下特性： 1 任何知道h a s hk e y 的人可以计算相关联的h a s h 函数； 2 对那些不知道蛔p d o o rk e y 的人，函数在通常意义上是抗碰撞的； 3 陷门信息t r a p d o o r k e y 的拥有者对任何给定输入都可以轻易的计算碰撞。 变色龙h a s h 函数的形式化定义见2 1 节。 变色龙h a s h 函数最初用于设计变色龙签名在变色龙签名中，签名的接收 者是陷门信息的拥有者。在标准的数字签名方案中，先用一个抗碰撞的h a s h 函 数对消息作用，然后用标准的签名算法对h a s h 值签名。变色龙签名把标准签名 方案中的标准h a s h 函数换成变色龙h a s h 函数日。，其中接收者r 掌握着日。的 陷门信息t k 。这一新的签名方案具有如下有趣的性质： 1 和标准签名方案一样，签名者s 不能否认他生成的签名，因为他无法计 算h a s h 函数的碰撞； 2 接收者无法向任何第三方证明s 生成的签名，因为r 可以使用陷门信息 任意改变签名消息而使输出的签名不变； 3 签名是面向特定的接收者的，也就是说，如果给两个不同的接收者签署 同一消息，则签名者需要对消息进行两次签名，这是因为变色龙h a s h 函 数对不同的接收者是不一样的。 换句话说，变色龙签名同时满足了不可否认性( 性质1 ) 和不可传递性( 性 质2 ) 不可传递性意味着，只有指定的验证者才能验证签名，而没有任何第三 方能够相信签名的真实性( 即使有接收者的帮助) ，并且第三方无法从签名中得 到任何其他信息；这是保护我们的签名不被无控制地分发的核心性质。然而，如 第1 章绪论 果没有任何第三方能够验证签名的真实性，我们如何实现不可否认性呢? 其关键在于，按照与不可否认签名相同的原理，通过与签名者合作，如上 的签名能够被确认或否认。当r 和s 发生争执时，s 被j u d g e 传唤，他被要求接 受或否认r 提供的签名。否认签名需要一个简单的步骤。其基于如下的性质： 如果r 提供了一个非法的签名，则s 能够提供变色龙h a s h 函数日。的碰撞。这 点足以证明r 的作弊( 因为变色龙h a s h 函数对于签名者s 是抗碰撞的) 。另一方 面，如果r 是诚实的，则s 无法否认签名。更进一步地，即使j u d g e ( 或其他个 体) 从签名者处获得了对签名的验证( 或否认) ，第三方也无法验证( 或否认) 签名。 变色龙签名起源于与不可否认签名相同的基本关注。在许多应用中，变色 龙签名是不可否认签名的高效替代。变色龙签名的优势在于他们的简单( 特别是， 变色龙签名按一般签名的传统模式进行，即对消息h a s h 后签名) ；验证( 或否认) 无需交互；更高的计算效率；以及若干分析优势( 特别是基于更多标准的数学假 设) 。显然，不可否认签名固有的复杂性交互的零知识证明立即被避免了。 另一方面，变色龙签名面向特定接收者的性质使其不适合某些应用。如，在同一 签名需要被不同的接收者同时验证时，或当签名者和接收者的身份需要保密时。 然而，变色龙签名满足了不可否认签名的大部分应用。 有趣的是，变色龙签名的构造与f a i l s t o p 签名【2 5 】的构造中有一点是很相似。 f a i l - s t o p 签名有这样的性质：签名者可以证明，伪造者是通过密码分析进行的伪 造还是通过窃取他的签名密钥进行的伪造。这是通过使用特殊类型的h a s h 函数 来实现的，这种特殊类型的h a s h 函数使得当且仅当给签名者提供一个密码分析 伪造时他才能计算碰撞。因此，即使f a i l - s t o p 签名和变色龙签名的构造和目的很 不一样，通过碰撞证明伪造的方法是相似的。 变色龙h a s h 的另一个重要应用是设计在线离线签名。在线离线签名的概 念由e v e n ，g o l d r e i c h 和m i c a l i 1 2 1 ，【1 3 】首先提出，其目的是提高签名的响应速 度。在线，离线签名的过程分为两个阶段。第一个阶段是离线的，在不知道签名 消息的情形下进行；第二个阶段是在线操作的，在得知签名消息之后进行。离线 阶段产生的预计算结果被保存下来用于在线阶段中对消息的签名。 e v e n ，g o l d r e i e h 和m i c a h 提出了一个把任何签名方案转换为在线离线签名 第1 章绪论 方案的通用方法。然而，这一方法并不有效，它使签名长度增加了一个平方因子。 s h a m i t 和t a u m a n 2 7 采用变色龙h a s h 函数设计了一个新的机制，即 “h a s h - s i g n s w i t c h ”机制，以设计更有效的在线离线签名方案，其形式化定义见 4 1 节。 在在线离线签名中，签名者是陷门信息的拥有者。因此，在离线阶段，签 名者首先选择一个随机的消息肼和一个附加的随机数，然后对其变色龙h a s h 值日。( m ，f ) 计算签名盯。在在线阶段，签名者对签名消息m 计算对此h a s h 值 的一个碰撞，即日。 ，) - 日腰( 册，t ) 则对消息m 的签名为二元组p ，) 。 于是，如果计算变色龙h a s h 的碰撞比直接签名更有效( 正如多数变色龙h a s h 函 数) ，则可以充分利用离线时的计算资源，提高签名响应的速度。 下面我们讨论变色龙h a s h 函数的密钥泄露问题。即，一对h a s h 碰撞将导致 变色龙h a s h 函数的t r a p d o o rk e yt k 的泄露。k r a w c z y k 和r a b i n 1 8 的原始的变 色龙h a s h 就有密钥泄露的缺陷。该文中的变色龙h a s h 函数定义为 日艘 ，) - y 9 7 ，其中，；z 。，q 是群g 的阶，g 是g 的生成元，h k - y g 。， t k x 。设，) 和伽，) 是一对h a s h 碰撞，即h - y 9 7 - y g 。，从而得 工一( ，- r ) l ( m - - m ) 。 如果变色龙签名中的变色龙h a s h 函数有密钥泄露的缺陷，则将使不可传递 性受到威胁。因为伪造签名将泄露t k ( 通常t k 等于接收者的私钥s k ，或为 s k 的一个函数) ，从而签名者可以计算h a s h 碰撞，进而否认其他的签名( 如果 每次签名使用同一个h a s h 函数) 。这样，就可能使第三方相信接收者提供的签名 的真实性，因为他知道接收者伪造签名会对自身造成极大的损失。从而使变色龙 签名的不可传递性受到威胁。在这种情况下，除非接收者在每次签名中都更换其 私钥，才能保证不可传递性，而这种开销是不能接受的。因此，变色龙签名必须 基于无密钥泄露的变色龙h a s h 函数来设计。 如果在在线，离线签名方案中采用有密钥泄露的变色龙h a s h 函数，我们必需 为每一条签名消息计算一个变色龙h a s h 值和相应的签名。这造成了在线，离线签 名过大的计算和存储开销。然而，现存的无密钥泄露的变色龙h a s h 方案并不适 合于设计有效的在线离线签名方案，有如下两个原因：一，在碰撞的计算中， 第1 章绪论 这些变色龙h a s h 方案通常要求进行费时的模指数运算；二，虽然碰撞不会造成 签名者陷门信息的泄露，但它使得验证者可以计算此h a s h 值的另外的碰撞，这 就意味着验证者可以u n i v e r s a l l y 伪造签名。注意这也许是变色龙签名的一个很好 的性质，它使签名者在否认协议中无需提供原始的签名，只需根据验证者伪造签 名产生的碰撞计算另一个签名就足以使j u d g e 相信签名确实是验证者伪造的，从 而保护了原始签名消息。然而对于此处的在线离线签名，这意味着验证者可以 u n i v e r s a l l y 伪造签名，显然是不能容忍的。 设计无密钥泄露的变色龙h a s h 函数的思想源于对变色龙h a s h 和变色龙承诺 方案紧密联系的观察【2 】。g e n n a r o 1 5 首次提出了多陷门承诺的概念。c h e n 等【8 】 提出了第一个无密钥泄露变色龙h a s h 函数。a t e n i e s e 和d em e d e i r o s 1 观察得出， 所有的s t a t e l e s s 双陷门承诺都可用于设计无密钥泄露的变色龙h a s h 方案。但是 所有这些变色龙h a s h 函数，由于以上所述的两个原因，都不适合于设计有效的 在线腐线签名。c h e n 等【9 】设计了一个特别的双陷门变色龙h a s h 函数并设计了 一个一般而有效的在线离线签名方案。 鉴于变色龙h a s h 函数的重要作用，研究变色龙h a s h 函数，总结多年来的研 究成果，不断开拓其应用领域，设计新颖有效的无密钥泄露的变色龙h a s h 方案， 就成为一项有意义的工作。 1 2 研究内容 本文主要研究无密钥泄漏的变色龙h a s h 函数的性质及其应用。首先，基于 b l s 签名本文提出了一种新的变色龙聚合签名和变色龙多签名方案，并证明了其 安全性。其次，利用双陷门的交色龙h a s h 函数族，本文提出了一个新的有效的 在线倩线门限签名方案，同时证明了方案的安全性 1 3 论文结构 数。 本文结构安排如下： 第二章，给出本文所涉及概念的定义，讨论几个有代表性的变色龙h a s h 函 第三章，基于b l s 签名【6 】和c h e r t 等的无密钥泄露的变色龙h a s h 函数【8 1 4 - 第1 章绪论 ( 见2 2 1 节) ，提出一个新的变色龙聚合签名和变色龙多签名方案，证明其安全 性。 第四章，基于c h e r t 等的双陷门变色龙h a s hi 磁 9 1 ( 见2 2 2 节) ，提出一 个新的有效的在线，离线门限签名方案，证明其安全性。 5 - 第2 章预各知识 第2 章预备知识 本章首先定义了本文中用到的一些重要概念，并介绍了若干有代表性的变 色龙h a s h 函数，按基于的困难问题的不同分类归纳。 2 1 定义 定义1 ( 变色龙h a s h 族) 一个变色龙h a s h 族由二元组( 上舅0 组成： 1 j 是一个概率多项式时间的密钥生成算法，输入1 i ，输出h a s h t r a p d o o rk e y 对( h k ，t k ) ，使得h k ，t k 的长度是k 的多项式 2 玎是随机的变色龙h a s h 函数族。玎中的每一个函数关联着一个h a s hk e y 麟，其作用于消息空间刑中的一个消息和有限空间霓中的一个随机数。 h a s h 函数日的输出与z x 无关 一个变色龙h a s h 族a ，f ) 具有如下性质： 1 e f l i d e n c y ：给定h a s hk e yh k 和一对沏，) 鲥x 雹，日伽，) 在多项 式时间内可算。 2 c o l l i s i o nr e s i s t a n c e z 没有多项式时间的算法a ，在只输入h k 的情况下， 以不可忽略的概率得到两个对( 鸭，) 伽：，r 2 ) 刑冠满足肼l - m ：且 努( 卅l ， ) 一蟊腰西2 ，2 ) ( 其概率与h k 有关，在这里( 而，r k ) 一，旷) ， 且与算法a 投掷的随机硬币有关) 。 3 t r a p d o o rc o l l i s i o n s ：存在一个概率多项式时问的算法，输入 ( h k ，t k ) 一j 旷) ，一对( 掰l ， ) 鲋x 瓯，和消息埘2 朋，输出r z 雹满 足： 1 ) 日o 吼，1 ) 一日细2 ，2 ) 2 ) 如果在览中是均匀分布的，则r 2 的分布在计算上不可区分于霓上的 第2 章预备知识 均匀分布。此性质又称为语义安全性。 a t e n i e s e 和d em e d e i r o s 1 观察得出，所有的s t a t e l e s s 双陷门承诺都可用于 设计无密钥泄露的变色龙h a s h 方案。在所有这些构造中，h a s hk e yh k 被分成两 部分，一部分是永久的( 1 0 n g - t e r mh a s hk e y ) ，另一部分是一次性i 的( o n e - t i m eh a s h k e y ) 。分别对应于l o n g - t e r mt r a p d o o rk e y 和o n e - t i m et r a p d o o rk e y 。一次碰撞只造 成o n e - t l m et r a p d o o rk e y 的泄露，而对l o n g - t e r mt r a p d o o rk e y 没有影响。每次签 名都会更换o n e t i m ek e y ，即o n e - t i m ek e y 与每次签名过程有关，如包含以下形 式的”c u s t o m i z e di d e n t i t i e s ”：i - 日p fii d ri ii d a ) ，其中h 为一个安全的h a s h 函数，其中上，i d r ，磅分别表示签名者，接收者和此次签名的i d 。一个无 密钥泄露的变色龙h a s h 函数定义如下： 定义2 ( 无密钥泄露的变色龙h a s h 函数) 一个无密钥泄露的变色龙h a s h 函数 由以下有效算法组成： 1 k e yg e n e r a t i o n 输入安全参数k ，输出h a s h t r a p d o o rk e yp a i r ( h k ，t k ) ， 这是一个概率算法，表示为： k e y g e n 1 k 一( i l k ，t k ) 2 h a s h 输入h a s hk e yh k ，”c u s t o m i z e di d e n t i t y ”i ，消息m 和一个附加的 随机数，输出固定长度为f 的h a s h 值，表示为： h 呸：( h k ，m ，) 一 0 册7 3 u n i v e r s a lf o r g e 输入t r a p d o o rk e y t k ，”c u s t o m i z e di d e n t i t y ”，消息m 和附加随机数，计算册和 ， ，使 日j ! 暖( h k ，i ，m ，r ) 一h - 日( h k , i ，m ，r ) ，表示为： u f o r g e ( t k , l ，m ，r ) - 似，) ，使得 日( ，i ，m ，r ) - h - h 腰( h k ，i ，坍，t ) 4 i a s t a n t f o r g e 输 入( h k ，i ，m ，r ) ，其 中 ， h 一日( 陇，j r ，m ，) - j j r ( h k ，i ，m ，t ) ，输出另一个碰撞( m _ d 满足 h 日膻( 脚( ，i ，辨”，r ”) ，表示为： r 第2 章预备知识 日0 k ，1 ，m ，) - h 一日臌磁，i ，坍，r ) 一日口( n k ，i ，r a f t ，”) 消息隐藏性和无密钥泄露性的要求如下： 1 ，m e s s a g e h i d i n g ：这是变色龙签名的一个很好的性质。在变色龙签名中， 假设接收者用u f o r g e 算法计算了一对碰撞，即算得另一组( m ：f - ) 满足 日艘( h k ，i ，肘，) h 日麟( 月爱，i ，r a w , r - ) ，其中帆r ) 是原始签名消息。则 签名者在看到( m ：i | ) 之后，能够成功否认( 耐，r i ) ，消息隐藏意味着签名者 可以算得第三对( m 竹，而无需提供原始签名消息就足以使j u d g e 相信签 名是接收者伪造的用信息理论的语言来表示即为， 日【伽，r ) l | i l ，伽，r 。) 伽”，”) 】- n t 伽，) i i i 】。 2 k e ye x p o s u r ef r r t e s s ：如果没有”c u s t o m i z e di d e n t i t y ”i 下的碰撞，则输 , k h - 日。( h k ，。m ，) ，不存在有效算法能找到一个碰撞。即使在敌手掌 握着o r a c l eu f o r g e ( t k ，) ，而允许其对( ，j ，m j ，) 询问多项式次数时， 此性质仍必须保持，只要询问的不等于挑战， 定义3 ( 数字签名方案) 一个数字签名方案j 由三个随机化的算 法( k e y g e n ，s i g , v e 0 组成： 1 k e y g e n ：r 一瓯x 甄是一个密钥生成算法，输入r ，其中k e n 是安 全参数，输出( p k ，s k ) 。其中p k e 毋k ，卿c 是公钥的集合，s k 5 k ， 双是私钥的集合。 2 s i g ：丽c 刑一口够是一个签名算法，其中9 , 是消息空间，5 姆，是签名 空间。简记为，令s g 伽) 一s i g ( s k ，册) ，对所有的加鲥。 3 v e t ：域刑x 脚必_ r e j e c t ，a c c e p t 是一个验证算法，其中 v e r ( p k ，r a ，j ) 一a c c e p t 当且仅当s 是s i g ( s k ，m ) f o 可能输出。简记为，令 细，s ) - v e r ( p k ，r d ，s ) ，对所有的m 掰和s 脚够。 第2 章预备知识 2 2 常见的变色龙h a s h 函数 【1 1 对变色龙h a s h 函数的密钥泄露问题进行了深入的讨论，根据变色龙h a s h 函数是否满足无密钥泄露和消息隐藏性质将其分成四种类型，指出所有的 s t a t e l e s s 双陷门承诺都可用于设计无密钥泄露的变色龙h a s h 方案。其中的双陷门 即是把t r a p d o o rk e y 分成l o n g - t e r mt r a p d o o rk e y 和o n e - t i m et r a p d o o rk e y 两部分， i n s t a n tf o r g e 只能导致o n e - t i m et r a p d o o rk e y 的泄露，不影响l o n g - t e r mt r a p d o o r k e y ，其中o n e - t i m et r a p d o o rk e y 只用一次。同时满足无密钥泄露和消息隐藏性质 的变色龙h a s h 函数适合于设计变色龙签名，只满足无密钥泄露而不具消息隐藏 性质的变色龙h a s h 函数适合于设计在线，离线签名。 2 2 1 基于c d h p 的变色龙h a s h 函数 c h e r t 等【8 】提出了第一个完全的无密钥泄露的变色龙h a s h 函数，同时满足 消息隐藏的性质，适合于设计变色龙签名。我们简单介绍如下。先给出相关的定 义。 设g 是由g 生成的循环乘法群，其阶为素数q 。假设g 中的求逆和乘法运 算可以有效地计算。我们介绍群g 中的如下问题。 1 离散对数问题( d l p ) ：给定两个元素g 和| i l ，计算整数口iz ：，使_ i l - 9 4 。 2 计算性d i f f l e h e l i m a n 问题( h p ) ：给定( g ，9 4 ，9 6 ) ，4 ，b e z ：，计算g “。 3 判定性d i f f l e - h e u m a n 问题( d d h p ) ：给定( g ，9 4 ，g b , g ) ，a , b ，c e z ：， 判定c = a b m o d q 是否成立。 如果d d h p 能在多项式时间内解决但c d h p 没有多项式时间算法，则g 称 为g a pd i f f l e - h e l i m a n 群。这样的群可以在s u p e r s i n g u l a r 椭圆曲线或h y p e r e l l i p t i c 曲线上找到。 如果c - a b m o d q ，则称g ，9 4 ，g b , g 为一个有效的d i l e h e l l m a n 组。 c h e n 等【8 】提出的变色龙h a s h 方案如下； 1 s y s t e mp a r a m e t e r sg e n e r a t i o np g ：设g 是由元素g 生成的g a p 第2 章预备知识 d i f f i e h e l l m a n 群，阶为素数鼋。定义一个安全的h a s h 函数日： 0 母一g 则系统参数为s p - a ，q ，g ，h 。 2 k e yg e n e r a f l o uk g ：每4 - ) w p 随机选择整数工与z 作为l o n g - t e r m t r a p d o o rk e y ，公布其l o n g - t e r mh a s hk e yy 一譬。y 的有效性可以由可信 赖第三方颁发的证书来保证。 3 h a s h i n gc o m p u t a t i o nh 既：输入用户的l o n g - t e r mh a s hk e yy ，随机选择 整数4 乓z ：，计算( g ，) ，。) 。变色龙h a s h 函数定义为 h - 日膳如，i ，g 。，y 4 ) 一( g 。f ) 。y 。， 其中，j 为”c u s t o m i z e di d e n t i t y 4 c o l l i s i o n c o m p u t a t i o nu f o r g e l 输入t r a p d o o rk e y x ， 仰，j ，9 4 ，y 。) e z _ x g x g x g ，及m e z 口，如下计算碰撞： u f o r g e ( x ，h ，m ，9 4 ，y a , _ i ，l ，j ) 一( g “，j ，。) ， 其中g “一g o ( g t j ) 。4 ( m “，y “一y o ( g 宰，) “”。 注意到 日积，g “，_ ) ，一) 一( g ，) y 一 一 d y 4 0 + d 8 耐 - ( g 搴，) 卅y 。 - 日藤伽，j ，9 4 ，y 4 ) 且g ，只g 。，y 。是有效的d i f f l e - h e u m a n 组。因此，碰撞计算成功。 其中0 ，) ”t g o 一4 堰”。可视为o n e - t i m e t r a p d o o r k e y ，q j r ) 可视为 o n e - t i m eh a s hk e y 。 定理1 在群g 的c d h p 难解的假设下，如上的拇造是一个变色龙h a s h 族，并且 满足无密钥泄露性和消息隐藏性。 证明请参考【8 1 第2 章预备知识 2 2 2 基于离散对数问题变色龙h a s h 函数 c h e n 等【9 】提出了一个特殊的双陷门h a s h 函数，具有碰撞计算效率高和无 密钥泄露的优点，不具有消息隐藏的性质，从而适合于设计有效的在线离线签 名，原因参见1 1 节。 1 s y s t e mp a r a m e t e r sg e n e r a t i o np g ：令1 为一个素数的幂，e ( e ) 是有限 域巧上的椭圆曲线。令# e ( e ) 为e ( e ) 的阶，e ( e ) 中元素p 的阶为素数 q 且g 降e ( 羁) 。记g 为由元素p 生成的子群。定义一个安全h a s h 函数 ，：乙g z 。则系统参数为卵- g ，q ，p ， 2 k e yg e n e r a t i o nk g ：选择两个随机数七，z 乓z ：，计算k - k p ，y - x p h a s h k e y 为h k 一僻，y ) ，t r a p d o o r k e y 为t i c 一 ，功。 3 h a s h i n gc o m p u t a t i o nh 腿：给定h a s hk e yh k ，变色龙h a s h 函数 日麟：z qx z q g 定义为： 日腿o l ，) - 厂，k ) k + r y 4 c o l l i s i o nc o m p u t a t i o nu f o r g e ：输入t r a p d o o r k e y ( k ，x ) ， ，) z qx z 口， 及历乙，计算碰撞，使得 ，o 糟，t p ) k p + r y f ( m ，丘p ) 七p + r y 则： u f o r g e ( k ，x ，m ，r ，m ) 一r - ，+ 白r - 1 ( ，( 脚，肋 一f ( m ，七p ” 其中，b 。1 - ( ，- r ) ( f 伽，卿一，一( r - r ) ( f ，趵一y o n , 足) ) 可视 为变色龙h a s h 函数的o n e - t h n et r a p d o o rk e y ，对应的o n e - t i m eh a s hk e y 为丘p 。 定理2 在群g 的离散对数问题难解的假设下，如上的构造是一个变色龙h a s h 族，并且满足无密钥泄露性。 证明请参考【9 】。 第2 章预各知识 2 2 3 基于r s a 假设和因数分解的变色龙h a s h 函数 如下的变色龙h a s h 基于一个典型的双陷门承诺，它的两个陷门为：r s a 模 数分解和求解r s a 假设。参见【l 】。该变色龙h a s h 满足无密钥泄露性和消息隐藏 性。 1 k e yg e n e r a t i o nk g ：设f 和j | 是安全参数，日是一个安全的h a s h 函数， 输出为固定长度f 。万一p q ，p 和q 为素数，且2 “墨p ，q 2 一1 ，e 2 7 为素数，且与妒o ) - 一驰一1 ) 互素，e d = l m o d o ( n ) ，d 为l o n g - t e r m t r a p d o o rk e y ，口为l o n g - t e r mh a s hk e y 。 2 h a s h i n gc o m p u t a t i o nh l ：令，为 c u s t o m i z e di d e n t i t y c ： d 册- 0 ，- - , 2 2 ；- 1 ，为安全的h a s h - a n d e n c o d e 方案，把任意长的比特 串映射为小于一的整数。通常情况下，这样的方案是概率性的，需要附 加一个随机数。例如，这里可采用e m s a - p s s 编码。这里不对随机数的 长度作讨论，因为只要编码方案是唯一可逆的，对此处的讨论就无关紧 要。对于某次签名，设j - c ( ，) z 。是0 1 1 e - t i m e h a s h k e y ，对应的o n e t i m e t r a p d o o r k e y 为b - j 。m o d n ，即是对l 的安全的r s a 签名。h a s h 函数定 义为 日藤p ，拼，r ) - j ”扣，。m o d n ，其中j c ( o 3 c o l l i s i o nc o m p u t a t i o nu - f o r g e ：输入t r a p d o o rk e y d ，) 和小，如 下计算碰撞： u f o r g e ( d ，m ，i ，m ) m r 一r b ”( _ ) 。- m o d n ，其中b - j 。m o d n 。注意到： h b q i n t , r ) i j h 9 n r ” - j 舶_ ，。b ( 佃卜刖_ ) j ”扣) ， 日联( ，m ，) 定理3 在e m s a - p s sr s a 签名安全的假设下，如上的构造是一个变色龙h a s h 族，并且满足无密钥泄露性和消息隐藏性。 证明请参考请参考【1 】a 第3 章变色龙聚合签名和变色龙多签名 第3 章变色龙聚合签名和变色龙多签名 本章基于c h e r t 等【8 】的无密钥泄露变色龙h a s h 函数和b l s 签名提出了新的 变色龙聚合签名和变色龙多签名方案，证明了其安全性，并分析了其应用。 3 1 预备知识 我们首先给出变色龙聚合签名和变色龙多签名中要用到的双线性映射的概 念。 定义4 ( 双线性映射) 令g l 是循环加法群，其生成元是p ，阶为素数碍g ：是 循环乘法群，阶同样为口。口，6 z ：假设g l 和g ：中的离散对数问题难解一个 双线性对是满足如下条件的一个映射e ：g l g g 2 t 1 双线性性：e ( 珏p ，6 q ) - e ( p , q ) “； 2 非退化性( n o n - d e g e n e r a t e ) ：e ( p ，p ) ，1 ； 3 可计算性：对于所有的p q g i ，存在有效算法计算e ( e , q ) 。 由性质1易得，对于任意的q l ，口：，q 3 g 1 ， 等式 e ( q 。q 2 ，q ，) 一e ( q 1 ，q ，) e ( q 2 ，蜴) 成立，并可以扩展到有限多个元素相乘的情形。 我们简单地回顾一下b l s 签名体制【6 】。它由密钥生成( k c y g c n ) ，鲐g ( s i g ) 和签名的验( v e t ) 三个算法组成。并采用了一个满射的h a s h 函数 h ：椰 一呸 1 密钥 成( k e y g e n ) ：用户随机选择工山z 。为私钥，计算公钥 y g 。g l 。 2 签名( s 国：给定私钥z 和消息埘 呱，计算h 一日伽) g 2 ，及口一矿， 则签名为仃g 。 第3 章变色龙聚合签名和变色龙多签名 3 签名的验i 正( v e r ) - 给定公钥y ，消息m 和签名o r ，计算h 一日西) ，并验 证 yh 盯) 是否为一个合法的d i f f i e -