（计算机应用技术专业论文）高效环签名方案研究.pdf

哈尔滨工程大学硕士学位论文 摘要 数字签名技术作为保证信息完整性和身份认证的重要工具，己成为信息 安全领域的一个关键机制。在现实应用中，为适应不同环境的需要，产生了 许多特种签名方案，如：群签名、环签名、盲签名、代理签名、门限签名等。 其中，环签名解决了对签名者完全匿名的问题，并作为一种匿名技术得到了 广泛的应用。当今信息时代，当环签名从理论研究走向实际应用时，效率便 成了人们所关注的问题。 本文首先对文中用到的密码学知识进行了简单介绍，包括：环、有限域， 二次剩余问题，单向函数，哈希函数，随机预言模型和数字签名。此外，详 细叙述了近些年密码学领域的一些最新成果：环z 。上的圆锥曲线和x t r 公 钥密码体制。 其次，系统综述了环签名的研究进展。以环签名的发展为线索，从环签 名的基本概念、环签名的分类( 包括门限环签名、关联环签名、可撤销匿名 的环签名、可否认的环签名等) 、环签名的应用等方面进行了比较研究。最后 总结了环签名领域仍存在的问题及进一步的研究方向。 在对环签名进行了深入研究的基础上，利用基于环z ，i 上圆锥曲线的性质， 如明文嵌入、阶的计算、点的运算及在圆锥曲线中逆元计算十分容易等，构 造了安全高效的环签名方案。然后，基于x t r 密码体制，构造了高效的盲环 签名和关联环签名方案，并将其用于设计多银行电子现金协议。此协议可以 保证发币银行的匿名性，并可追踪重复花费者的身份。 最后，总结论文工作，提出了需继续研究的问题。 关键词：环签名；匿名控制；圆锥曲线；x t r 密码体制；电子现金 哈尔滨工程大学硕士学位论文 a b s t r a c t d i g i t a ls i g n a t u r ei so n eo ft h ek e yt o o l si ni n f o r m a t i o ns e c u r i t y b e c a m eo f d i f f e r e n ta p p l i e de n v i r o n m e n t s ，t h e r ea r cd i f f e r e n ts p e c i a ls i g n a t u r es c h e m e s ，s u c h a sg r o u ps i g n a t u r e ，b l i n ds i g n a t u r e ，p r o x ys i g n a t u r e ，t h r e s h o l d s i g n a t u r e ，r i n g s i g n a t u r e , e t c a m o n gt h e m ，r i n gs i g n a t u r e , w h i c hr e s o l v e st h ep r o b l e mo f c o m p l e t e l ya n o n y m i t yt os i g n e r , h a sb e e nw i d e l yu s e d i nt h ei n f o r m a t i o ne r a , w h e nt h es t u d yo f r i n gs i g n a t u r ef o c u s e so nt h ea p p l i c a t i o n , t h ee f f i c i e n c yt u r n st o b e t h e k e y p o i m f i r s t l y , t h eb a s i ck n o w l e d g eo fc r y p t o g r a p h yi si n t r o d u c e d ，i n c l u d i n gr i n g ， f l , d t ef i e l d , a n dq u a d r a t i cr e s i d u ep r o b l e m , o n e - w a yf u n c t i o n , h a s h i n gf u n c t i o n , r a n d o mo r a c l em o d e la n ds i g n a t u r e t h e nn e wa c h i e v e m e n t so fc r y p t o g r a p h yi n r e c e n ty e a r sa r ed e p i c t e di nd e t a i l t h e yr r et h ec o n i cc r r v eo v e rt h er i n gz | ia n d x t r c r y p t o s y s t e m s e c o n d l y , t h ea c h i e v e m e n t si nt h ef i e l do f r i n gs i g n a t u r ea n di t sa p p l i c a t i o n s a r es u r v e y e d 1 r i 圮c o n c e p t , s o r t sa n da p p l i c a t i o n so fr i n gs i g n a l u r ea l es t u d i e d t h e n ，s o m ep r o b l e m sa n do p e np r o b l e ma l ec o n c l u d e d 1 1 ：d r d l y , t h ep r o p e r t i e so fc o n i cc u r v eo v e rr i n g 乙( c c c ) a r eu s e dt o c o n s t r u c ts e c t l r ea n de f f i c i e n tr i n gs i g n a t u r e s c c ci se a s i e rt oa c c o m p l i s hf o r e m b e d d i n gp l a i n t e x t ，c o m p u t i n gd e m e m o r d e ra n dp o i n t si nc u r v e s , a n ds p e e d i n g u pt h ei n v e r s eo p e r a t i o n , s oi ti sf i t f o rc o n s t r u c t i n gc r y p t o 鲫h i c a lp r o t o c o l s n e wb l i n dr i n gs i g n a t u r ea n dl i n k a b l er i n gs i g n a t u r eb a s e do nx t r a 托p r o p o s e d t h e nt h e ya r eu s e dt oc o n s t r u c te - c a s hp r o t o c o lw h i c hc a np r o t e c tt h ea n o n y m i t y o f t h eb a n ka n dt r a c ed o u b l es p e n d e r s f i n a l l y , t h ew o r ko f t h et h e s i si sc o n c l u d e d k e y w o r d s ：r i n gs i g n a t u r e ，a n o n y m i t yc o n t r o l ，c o n i cc u l n e ，x i r , e c a s h n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的 指导下，由作者本人独立完成的。有关观点、方法、 数据和文献的引用已在文中指出，并与参考文献相对 应。除文中已注明引用的内容外，本论文不包含任何 其他个人或集体已经公开发表的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本人完全意识到本声明的法律结果由本人 承担。 作者( 签字) ：寻骖移 日期：硼7 年弓月g - e t 哈尔滨工程大学硕士学位论文 1 1 课题背景 第1 章绪论 网络的飞速发展，电子商务、电子政务及日常生活的信息化，使得与公 钥密码体制相伴的数字签名技术具有了广泛的应用前景。数字签名之于数字 文件，正如手写签名之于纸质文件，在电子商务和电子政务中扮演着重要的 角色。自从w d i f f i e 和地h e l l m a n 首先提出了“数字签名”的概念以后， 相继出现了以r s a ，e i g a m a l 和d s s 为代表的数字签名方案。在现实环境中， 应用于不同领域的签名方案也层出不穷。 然而，一般的签名方案对于某些特殊情况，满足不了其需求。例如，一 个工厂的工人想向记者举报厂长贪污，但他又不想泄露自己的身份，举报人 不能用一般的数字签名把消息传给记者，因为虽然使记者确信这个消息来自 这个工厂，但同时也透露了举报人的身份。举报人也不能通过一般的匿名方 式把消息传给记者，因为这样虽然举报人的身份没有暴露，但记者不能确信 消息来自这个工厂，没有理由相信消息是真实的。因此，构造满足以上需求 的特殊签名方案就成了所关注的问题。为了适应不同应用环境的需求，在普 通的数字签名基础上附加一些特殊性质后，出现了群签名、环签名、盲签名 和可传递签名等许多特种数字签名。研究特种数字签名必将丰富信息安全与 密码学理论，对构建安全、实用、高效的电子商务、电子政务及军务等系统 具有重要意义。 本课题在黑龙江省自然科学基金( f 2 0 0 4 0 6 ) 和哈尔滨工程大学基础研 究基金( h e u f t 0 5 0 6 7 ) 的资助下，深入研究了特种数字签名中的一种环 签名。环签名是r r i v e s t 等人于2 0 0 1 年首先提出的一种新型数字签名方案。 这种方案是在“安全泄漏秘密”的背景下产生的，它是一种特殊的面向群体 的签名，不需要群的建立过程，没有管理员，签名者只需随意选取一部分成 员的公钥，再通过自己的私钥就可以产生一个环签名，减少了很多复杂的交 互证明过程。环签名最大的特点是签名者具有完全匿名性，可以保护签名者 的隐私，且易于高效实现。环签名在匿名电子选举、电子政务、电子货币系 哈尔滨工程大学硕士学位论文 统、密钥分配以及多方安全计算中都有广泛的应用，而成为当前研究的一个 热点。 当环签名从理论研究走向实际应用时，效率便成了人们所关注的问题。 已有的环签名方案大都基于传统的密码体制( 如：r s a ，e c c 等) ，其中基于 e c c 的环签名方案效率较高，也具有很多优点。相对于椭圆曲线，1 9 9 9 年， 曹珍富首次构造了基于圆锥曲线的密码体制( c c c ) 。c c c 除具有e c c 的优点 外，还具有明文嵌入，阶的计算及点的运算都更容易，特别是在圆锥曲线中 逆元计算十分容易的优势，使得基于圆锥曲线的密码体制对于设计密码算法 非常具有吸引力。本文正是利用了此种密码体制的优势构造了安全高效的环 签名方案。此外，近几年有学者提出另一种新密码体制基于x t r 的公钥 密码体制( 简称为x t r ) ，即有效的紧致的子群迹表示。x t r 对于构造高效的 环签名方案也将发挥巨大的作用。因为在同等安全程度下，x t r 的采用可以 减少大量的数据存储量、计算量和通信量。x t r 已成为一种非常有吸引力的 新公钥密码体制。 1 2 研究内容与论文组织 本文针对效率问题对环签名的相关理论和应用进行了研究，按论文的结 构顺序，包括： ( 1 ) 第二章，密码学基础。环签名涉及密码学和信息安全的大部分领域， 首先回顾文中将用到的密码学概念。对近些年密码学领域的一些最新结果进 行了较为详细的叙述，包括哈希函数攻击、环z 。上圆锥曲线基本理论、x t r 公钥密码体制等。 ( 2 ) 第三章，环签名综述。系统全面地对环签名的研究进展进行了归总， 包括环签名的定义、环签名的安全模型、环签名的分类( 包括门限环签名、 关联环签名、可撤销匿名性的环签名和可否认的环签名等) 、与环签名相关的 一些数字签名( 包括代理环签名、盲环签名、环签密等) 以及环签名的一些 应用领域。最后对环签名有待研究的问题进行了总结。 ( 3 ) 第四章，基于环乙上圆锥曲线的环签名方案。利用基于环乙上圆 锥曲线的性质，构造了安全高效的环签名方案。开创性地将c c c 引入了环签 2 哈尔滨工程大学硕士学位论文 名的研究中，并给出了方案在随机预言模型中的安全性证明。 ( 4 ) 第五章，基于环乙上圆锥曲线的前向安全环签名方案。除了考虑 构造高效的环签名方案外，本章还特i i i i 强了环签名方案的安全性。针对环 签名方案中的密钥泄漏问题，结合前向安全理论，提出了基于环乙上圆锥曲 线的前向安全环签名方案。 ( 5 ) 第六章，基于x t r 环签名的多银行电子现金协议。利用盲环签名和 关联环签名的特殊性质，将其用于构造公平的多银行电子现金协议。首先基 于x t r 密码体制构造了新的盲环签名和关联环签名方案，并将其用于设计电 子现金协议此协议可以保证发币银行的匿名性，并可以追踪重复花费者的 身份。 最后，对论文进行了总结，并给出了下一步要研究的问题。 哈尔滨丁程大学硕七学位论文 第2 章密码学基础 环签名作为一种高层应用协议，涉及很多信息安全的理论和技术，其基 础就是密码学。本章对一些基本的密码学理论作以简单介绍，这些是本文以 后章节的基础。 2 1 代数学基础 本小节介绍两种代数结构：环乙和有限域只，它们将为本论文中的密码 协议提供基本元素和运算。 定义2 1 1 ( 环乙) 环乙是指对于整数模一的剩余类集合乙，它具有两 个二元运算，即+ ( 加法) 和( 乘法) ，满足以下条件。 ( 1 ) ( 乙，+ ) 为一个阿贝尔群，单位元素以0 表示。 ( 2 ) 运算满足结合律。即对所有a , b , c e 互，都有1 x p x 力= ( 口x f 。 ( 3 ) 存在一个乘法单位元，以1 表示且1 0 ，使得对于所有的a z ， 者b 有口1 = 1 a = 口。 ( 4 ) 运算对于+ 满足分配律，即对所有的口，b ，c z ，都有 a x ( b + c ) = ( 口b ) + ( a x c ) ，p + c ) 口= ( b x 4 ) + ( c 口) 。 定义2 1 2 ( 有限域e ) 设f 为一个非空的集合，在f 中定义了两种代 数运算：加、乘，且满足下面的条件： ( 1 ) f 在加法下为a b e l 群。该群中单位元写为0 。 ( 2 ) f 中除去元素0 外，对乘法构成a b e l 群。该乘法的单位元写为1 。 ( 3 ) 乘法和加法之间有分配律：对任意的口，b ，c f ，有 a ( b + c ) = a b + 卯( 6 + c ) 口= b a + c 口。 则称f 为一个域。域中的元素是有限的，则称为有限域，一般用g f ( q ) 或 只表示，口表示其元素的阶。有限域又称为g a l o i s 域。 2 2 数论基础知识 这一小节将概要介绍数论中的一些基本概念。 4 哈尔滨工程大学硕士学位论文 定义2 2 1 ( 模乘法群) 令是一正整数，定义模乘法群为大于1 小于朋且与互素的所有正整数的集合，即： z ：= 缸1 1 j s n ，g c d ( x ，) = 1 定义2 2 2 ( 模二次剩余) 我们称j 是模 ，二次剩余( q u a d r a t i cr e s i d u e m o d u l o 肋，如果存在整数w e z ：，满足工；w 2m o d n 。否则，称其为模 二次非剩余( q u a d r a t i cn o n - r e s i d u em o d u l o 肋。z ：中的二次剩余集合和 二次非剩余集合分别记为鲫。和q _ 胀，。定义二次剩余谓词为： = o 姗是篙二次剩余 如果是素数，可以在关于i 州的多项式时间内计算出级o ) 。 定义2 2 3 ( 二次剩余问题和二次剩余假设) 给定整数7 和a ， ( 0 a 疗) ，判定是否存在整数w ，( 0 1 ， 甩) ，使w 2 = a m o d n 成立。 可以用l e g e n d r e 符号判定整数a 是否是素数的二次剩余。 二次剩余假设是指：不存在有效算法，其解决二次剩余问题的概率是不 可忽略的。 定义2 2 4 ( l e g e n d r e 符号和j a c o b i 符号) 对素数尸，定义工模p 的 l e g e n d r e 符号为： c 毋 ! 。骗驯。0 给定朋的素分解= 兀力，这里只为互异的素数，定义j 模朋均j a c o b i 符号为： ( 枷= 兀( z 只) 这里，( 只) 是z 模p 的l e g e n d r e 符号。 2 3 单向函数 单向( o n e - w a y ) 函数，直观上就是容易计算但难于求逆的函数。在计算模 型中，有两类单向函数，一类称作强单向函数，另一类称作弱单向函数。强 单向函数是指求此函数逆函数成功的概率是可以忽略的，而弱单向函数是指 哈尔滨工程大学硕士学位论文 存在一个多项式求逆算法，它失败的概率是可忽略的。弱单向函数的存在性 意味着可以构造出强单向函数。 定义2 3 1 ( 单向函数) 一个函数，： o ，1 ) 一 o ，1 ) 被称作( 强) 单向 函数，如果它满足以下两个条件： ( 1 ) 容易计算：存在一个确定的多项式时间算法a ，对于输入而其输 出为“神，即彳( 曲= ，( 曲。 ( 2 ) 难于求逆：对任意的概率多项式时间算法，任意的正多项式p ( ) ， 以及任意大的刀，有 1 p r o b ( a ( ，( 玑) ，l ”) 厂u ( 玑”) 6 。在g f ( p ) 中一定存在一个q 阶元毋 g f ( p ) 的子群白，称为x t r 群。 令c = t r ( g ) ，多项式f ( c ，x ) = x 3 一c x 2 + c 9 j 一1 g f ( p 2 ) 【石】。对整 数珂z ，定义c 。为f ( c ，x ) 的根的1 1 次幂之和，即如果f ( c ， ，) = 0 ，卢0 ，1 ，2 ， 则厶= w - i - w + 醚= t r ( g ”) ，显见c 1 = c 。 下面给出有关x t r 的一些性质： 定理2 7 1 ( 只g 彬的基本性质) 多项式，亿z ) = z 3 一c x 2 + c p x l ， f 。= w + w + 绣= r r ( g ”) ，有 ( 1 ) f ( c ，矗j 9 ) = 0 ，户0 ，1 ，2 ( 2 ) c 一。= c 。= 簖，行z ( 3 ) c “+ v = c q c r 一衫c q + c u 一2 ，v z ( 4 ) ，( 厶，j l ? ) = 0 ，卢0 ，1 ，2 ，r z 定理2 7 2 给定c c n - l ，c n ，c n “，有 ( 1 ) c 2 = c n 2 2 c f ( 2 ) + 2 = c c n + l - - c ，c n + c n i ( 3 ) c 2 n - ! = t 厶一c 9 c ：+ 碾l ( 4 ) 吃。+ | = c 胂j 一c 砰+ _ 一般来说，x t r 的公钥数据包含上述两个素数p ，q 以及x t r 群的某个生成 元f 的迹t r ( 宙，这些数据可以在参与者之间共享。 2 8 小结 本章简要介绍了文中用到的一些密码学基础知识，其中包括：代数学基 础中的环、有限域，数论基础知识，单向函数，哈希函数，随机预言模型和 数字签名。此外对近些年密码学领域的一些最新结果进行了较为详细的叙述， 包括哈希函数攻击、环乙上圆锥曲线基本理论、x t k 公钥密码体制等。 哈尔滨工程大学硕士学位论文 第3 章环签名综述 本章力图对环签名的研究进展作一个全面的综述。白2 0 0 1 年r i v e s t 等 人提出环签名的概念后，环签名作为一种匿名技术成为信息安全领域的研究 热点，并在众多方面取得了成果。环签名的研究涉及理论、技术、应用等众 多方面。本章以环签名的发展为线索，从基本定义、不同应用驱动的环签名 ( 包括门限环签名、关联环签名、可撤销匿名的环签名、可否认的环签名等) 、 环签名的应用等方面对环签名进行了综述。另外，还总结了一些存在的问题 及研究方向。 3 1 概述 2 0 0 1 年，r i v e s t 等人在如何匿名泄漏秘密的背景下提出了一种新型签名 技术，称为环签名( r i n gs i g n a t u r e ) 1 7 环签名可以被视为一种特殊的群签 名，它没有可信中心，没有群的建立过程，对于验证者来说签名者是完全匿 名的。环签名提供了一种匿名泄露秘密的巧妙方法。环签名的这种无条件匿 名性在对信息需要长期保护的一些特殊环境中非常有用。例如，即使r s a 被 攻破也必须保护匿名性的场合。 自环签名的概念被提出后，引起了各国学者的广泛关注。2 0 0 2 年， m a s a y u k ia b e 等人提出了如何使用不同签名方案产生的公钥来构造 卜o u t o f - n 签名 s l 。f a n g g u oz h a n g 等将基于身份的密码体制和双线性对用于 构造基于身份的环签名方案例。e m m a n u e lb r e s s o n 等提出了门限环签名的概 念，并将其应用于a d - h o c 网络“q 。鉴于隐私保护的需求，m o n in a o r 提出了 可否认的环认证方案，。 2 0 0 3 年，w i l l ys u s i l o 等在文 1 1 的基础上提出了非交互的可否认环认 证方案旧。j i q i a n gl v 等提出了环签名的匿名撤销方案一可验证的环签名方 案”。c h o n gz h ig a o 等基于n y b e r g r u e p p e l 签名方案提出了新的环签名方 案l 。j a v i e rh e r r a n z 等提出了便于环签名方案安全性证明的分叉引理“”。 f a n g g u oz h a n g 等将代理签名引入环签名，提出了代理环签名的概念”q 。l i q u n t h e n 等用环签名方案构造了并发签名方案旧。d u n c a ns w o n g 等提出了环签 1 4 哈尔滨工程大学硕士学位论文 名方案的另一种构造方法：r e e d - s o l o m o n ( r s ) c o d e 构造法，并给出了相应 的门限方案” 。 2 0 0 4 年，j o s e p hk l i u 等与p a t r i c kp t s a n g 等就签名人身份的关联问 题进行了详细的讨论。目。y e v g e n i yd o d i s 等讨论了a d - h o c 群体的匿名认证 问题，并提出了基于单向累加器嗍的环签名方案阱l 。g a nz h i 等使用在阀下 信道中嵌入认证信息的方法，提出了更高效的可验证环签名方案圈。a m i tk a w a s t h i 等提出了高效的基于身份的环签名和代理环签名方案1 。j a v i e r h e r r a n z 等提出了新的基于身份的环签名方案渊。j i q i a n gl v 等将环签名与 认证加密结合提出环认证加密方案嗍。t i a n j i ec a o 等指出文献 2 5 的方案 不满足签名人可验证性和接收者可验证性，并提出了改进方案嗍。王继林等 基于环签名思想提出了一种类群签名方案吲。t o n yk c h a n 等提出了盲环签 名的概念网。 2 0 0 5 年，针对门限环签名，文献 2 9 ，3 0 又进行了进一步的研究。k c l e e 等提出了另一个匿名撤销的环签名方案p 1 1 。p a t r i c kp t s a n g 等设计了简短 的关联环签名方案，并将其用于电子投票、电子现金等系统中嗍。l a nn g u y e n 将基于双线性对的累加器用于构造基于身份的环签名方案，其签名大小是固 定不变的鲫。q i a n h o n g 轧等构造了高效盲环签名方案叫j o s e p hk l i u 等 针对密钥泄漏问题，首次提出了前向安全的环签名和密钥封装的环签名方案， 并推广至门限方案嗍。 2 0 0 6 年，f a n g g u oz h a n g 等对文 3 3 的认证方案进行了分析和改进阁。 y i q u nc h e n 等提出了适用于p 2 p 网络的基于身份的匿名指定环签名方案鲫。 已有环签名方案的安全性证明几乎全是在随机预言模型( r o m ) 下考虑的。然 而，该模型没有全面考虑实际攻击者的能力，因而该模型对于环签名来说安 全性较弱。随着环签名的不断发展，s h e r m a ns 1 lc h o w 等基于双线性对， 首次提出了在标准模型中( n - q ) 一d s j s d h 假设下可证安全的环签名方案鲫。 同年，a d a mb e n d e r 等分析了已有环签名方案的安全性定义，全面考虑了实 际攻击者能力后给出了更加可靠的安全性定义，并提出了在标准模型下安全 的两个环签名方案嗍。黄欣沂等基于签密思想提出了基于身份的环签密方案 嗍。此外，m a nh oa u 等指出文献 3 2 的方案存在安全缺陷，并提出了新的 简短关联环签名方案l 。 1 5 哈尔滨工程大学硕士学位论文 从环签名发展的整个过程来看，它的发展经历了三个阶段： 2 0 0 1 2 0 0 2 ，以r i v e s t 提出环签名的观点为标志，这一阶段的工作主要 是参考r i v e s t 观点，提出具体的签名方案； 2 0 0 3 2 0 0 4 ，在经过两年对环签名的概念和意义的认识和理解后，一些密 码界人十开始对环签名进行研究。这一时期涌现了很多新思想、新模型和新 方案，是环签名发展的关键时期； 2 0 0 5 现在，这一阶段更加注重环签名的安全性、效率和实用性的研究。 有安全高效的环签名方案的研究，有环签名与通常的数字签名相互转化的研 究，还有环签名的推广方面的研究。 本章第二节首先介绍了环签名的相关概念。其次，在综合分析了已搜集 到的所有文献后，把现有的一些典型方案归纳为四类，即门限环签名、关联 环签名、可撤销匿名性的环签名、可否认的环认证和环签名。再次，概述了 与环签名相关的数字签名：代理环签名、盲环签名和环签密。最后讨论了环 签名的应用，并于第六节总结了环签名存在的问题及值得进一步研究的阃题。 3 2 环签名基本概念 定义3 2 ，1 ( 环签名) 假定有7 个用户，每一个用户拥有一个公钥) ， 和与之对应的私钥葺。环签名是一个能够实现签名者无条件匿名的签名方案， 它主要由下述算法组成： ( 1 ) 生成g e n 一个概率多项式时间( p p t ) 算法，输入为安全参数缸 输出为公钥和私钥。这里假定g e n 为每一个用户q ，产生一个公钥y ，和私钥 毛，并且不同用户的公私钥可能来自不同的公钥体制，如有的来自r s a ，有 的来自d l 。 ( 2 ) 签名s i g n 一个p p t 算法，在输入消息廖和疗个环成员的公钥 l = y i ，j ，2 ， 以及其中一个成员的私钥后，对消息厨产生一个签名尼 其中用中的某个参数根据一定的规则呈环状。 ( 3 ) 验证v e r i f y 一个确定性算法，在输入( 皿励后，若厅为m 的环签 名则输出。t r u e ”，否则为“f a l s e ”。 环签名因为其签名隐含的某个参数按照一定的规则组成环状而得名。而 6 哈尔滨工程大学硕士学位论文 在之后提出的许多方案中不要求签名的构成结构成环形，只要签名的形成满 足自发性、匿名性和群特性，也称之为环签名。 定义3 2 2 ( 环签名的安全性) 环签名必须满足以下的安全性要求： ( 1 ) 正确性如果按照正确的签名步骤对消息进行签名，并且在传播的 过程中签名没有被篡改，那么环签名满足签名验证等式。 ( 2 ) 无条件匿名性攻击者即使非法获取了所有可能签名者的私钥，他 能确定出真正的签名者的概率不超过1 n ，这里n 为成员( 可能签名者) 的个 数。 ( 3 ) 不可伪造性外部攻击者在不知道任何成员私钥的情况下，即使能 够从一个产生环签名的随机预言者那里得到任何消息1 1 1 的签名，他成功伪造 一个合法签名的概率也是可以忽略的。 3 3 环签名的分类与述评 环签名由于它的自发性、无条件匿名性和群特性而具有广泛的应用领域。 然而不同的应用领域要求环签名还应具有一定的特殊属性，如：门限特性、 关联性、可撤销匿名性、可否认性等。依据不同的应用需求，环签名所具有 的特殊属性也不尽相同。按照环签名所涉及的不同属性，把现有的环签名方 案归纳为以下四类并分别予以述评。 3 3 1 门限环签名 门限机制是团队或组织内部成员分享权力和秘密的重要方法。在已有的 诸多门限签名方案中，人们大都采用a s h a m i r 提出的基于l a g r a n g e 插值的 门限方案或g r b l a k l e y 提出的基于几何的门限方案。 2 0 0 2 年，b r e s s o n 等人将门限机制应用于文献 7 的环签名方案，构造出 门限环签名方案b s s ，并在r o m 下证明方案是安全的l = o l 。b s s 使用了公平划 分的技术，使验证者确信n 个成员的群中至少有k 个成员签署了信息，但是 并不知道是哪k 个成员做了签名。 2 0 0 3 年，d u n c a ns ，w o n g 等人提出使用新技术：r e e d - s o l o m o nc o d e 构 造环签名和门限环签名方案的方法o ”。之后，j o s e p hk l i u 等人考虑允许 1 7 哈尔滨工程大学硕士学位论文 多个签名人使用不同公钥体制的情况，提出了可分( s e p a r a b l i l i t y ) 的概念。 j o s e p hk l i u 将可分性与门限环签名结合，给出了可以混合使用基于r s a 和基于d l 公钥体制的可分门限环签名方案。 2 0 0 4 年，s h e r m a ns m 等人提出了第一个基于身份的门限环签名方案。 该方案是建立在秘密分享技术之上的，在r o m 下是不可伪造的，并且对于群 成员属于不同可信机构的情况仍然适用。同年，j o s e p hk l i u 等对环签名 方案的安全模型进行了级别划分，并给出了三个级别的安全模型，同时指出 同一方案在不同的安全模型下会有不同的安全性能。j o s e p hk l i u 等提出 了基于知识协议部分证明的门限环签名方案，给出了与之对应的安全模型。 p a t r i c kp t s a n g 等人将可分性与关联性用于门限环签名，首次提出了可分 关联的门限环签名方案，并给出了方案的安全模型。特别的，p a t r i c kp t s a n g 等人还提出了针对关联环签名的指责关联性和抗诽谤性的安全概念。j a v i e r h e r r a n z 和g e r m a ns a e z 提出了基于身份的分布式环签名的概念。针对于一 般集合和门限集合，他们分别提出了两个具体的方案，并且给出了在c d h 问 题难解的情况下，方案的安全性证明过程。该方案允许签名人选择任意的存 取结构，而不仅局限于门限结构。2 0 0 4 年，伍前红等人在第八届中国密码学 术会议上提出了一种基于离散对数公钥体制的( t ，而环签名。其主要思想是： 为了产生一个( 毛而门限环签名，每个参与的签名者只都在基于离散对数的 ( 1 ，曲环签名嘲中嵌入一个零知识证明。这个零知识证明暗示着p 知道与公钥 列表中的某个公钥对应的私钥，但不知道具体是哪一个。最后，个参与 者的子签名构成了( t 痨门限环签名。 2 0 0 5 年，t o s h i y u k ii s s h i k i 和k e i s u k et a n a k a 针对“当t 相对于刀 较大时b s s 方案低效”的缺点，提出了改进方案嗍。该方案是通过对陷门单 向函数进行修改并结合公平划分的思想而提出的。相对于b s s 方案使用公平 划分是为了保证方案的正确性和匿名性，文献 2 9 】的方案运用公平划分可以 确保方案的正确性