（交通信息工程及控制专业论文）群数字签名方案的设计与研究.pdf

西南交通大学博士研究生学位论文第1 页 摘要 自从d i f f i e 和h e l l m a n 提出数字签名的概念以来，数字签名技术得到了 广泛而深入的研究。除了对传统意义上的数字签名技术进行研究以外，研 究者们还衍生出了盲签名、门限签名、代理签名、前向安全性的签名等等 签名方案。本论文对于群签名方案的研究就属于这诸多的研究方向之一。 群签名方案，如同传统的签名方案，允许签名者向验证者证明：关于 消息的签名是其利用签名密钥得到的。并且，对于任何一个知道群公钥的 验证者来说，该签名是可以公开验证的。然而，群签名是匿名的。任何验 证者都无法知道是哪一个群成员对消息签的名。此外，群签名还具有无法 链接性：验证者无法判定多个不同的签名是否来自同一个群成员的签名。 如果验证者对签名者的身份起了疑心，他可以通过群管理者恢复出签名者 的身份。同多重签名比较而言，多重签名可被看成不具备追踪功能的群签 名；同代理签名比较而言，代理签名则是不具备匿名性的群签名。 本论文从第3 章到第5 章分别就群签名的三个大的方面进行了研究： 一是设计了新的群签名方案，给出了严格的安全性证明；二是设计了具有 权限特性的群签名方案；三是设计了两个新的群盲签名方案。具体的创新 工作如下： 在第3 章的3 3 节，本论文在b b 方案( b o n e h 和b o y e n 提出的在q s d h 假设之上构建的短签名) 的基础上演化出一个新的签名方案。 在第3 章的3 4 节，本论文利用c s 9 8 加密方案( c r a m e r 和s h o u p 构建 的i n d c c a 2 安全的公钥加密方案) 和新的签名方案构建了一个新的群签 名方案。新的群签名方案的安全性建立在随机预言机模型下，q s d h 假设 和判定d i f f i e h e l l m a n 假设之上的。新提出的群签名方案的签名长度比b b s 的短群签名方案的签名长度略长，但新的群签名方案在为群成员发放资格 证书以及成员私钥时，不需要可信任第三方的参与。 在第4 章，本论文在b m w 方案( b e l l a r e ，m i c c i a n c i o 以及w a r i n s c h i 构建的标准假设之上的群签名方案) 的基础上加入了权限产生算法 d u t h g e n ，利用其产生成员的权限a u t h , ，由密钥生成算法产生s 七和p k ， 第u 页西南交通大学博士研究生学位论文 其中叱是权限证书发布密钥，p k o 是权限证书验证密钥。利用北对 ( f ，4 h 魄) 进行签名生成成员的权限证书a u t h c e r t ，。同b m w 方案比较，虽然群 签名方案的实例生成速度降低，但为群签名方案添加了权限特性；并且， 对群签名方案应具备的完全可追踪性的安全性的证明比b m w 方案更加简 洁。 在第5 章5 3 节，本论文在a c j t 方案( a t e n i e s e ，c a m e n i s c h 。j o y e 以及 t s u d i k 构建的实用性极高的群签名方案) 基础上创建了新的群盲签名方案， a c j t 群盲签名方案。同已有的l r 9 8 方案比较，新方案的安全性建立在强 r s a 以及判定性d i f f i e h e u m a n 假设之上，在盲化a c j t 群签名方案时，新 方案仅添加了模指数和模加运算，而u t 9 8 群盲签名方案在盲化c s 9 7 群签 名方案时，则添加了求双重离散对数、离散对数根以及随机置换运算。两 者比较，新方案计算复杂度更低，效率更高。 在第5 章5 4 节，本论文在c z k 方案( c h e n ，z h a n g 以及k i m 构建的 一个高效的i d 群签名方案) 的基础上构建了另一种新型的群盲签名方案， i d 群盲签名方案。同已有的l r 9 8 方案比较，新方案安全性建立在计算 d i f f i e h e l l m a n 问题假设之上，在盲化c z k 的i d 群签名方案时，新方案仅 添加了模加运算，而l r 9 8 群盲签名方案在盲化c s 9 7 群签名方案时，则添 加了求双重离散对数、离散对数根以及随机置换运算。两者比较，新提出 的方案效率更高。 西南交通大学博士研究生学位论文第1 i i 页 a b s t r a c t s i n c ed i f f i ea n dh e l l m a np r o p o s e dt h e c o n c e p to fd i g i t a ls i g n a t u r e ，t h e t e c h n i q u eo fi th a sb e e ne x t e n s i v e l ya n dd e e p l ym i n e d b e s i d e sf o l l o w i n gt h e t r a d i t i o n a lr e s e a r c ho f d i g i t a ls i g n a t u r e ，r e s e a r c h e r sh a v ed e r i v e d b l i n d s i g n a t u r e ，t h r e s h o l ds i g n a t u r e ，p r o x ys i g n a t u r e ，f o r w a r d s e c u r es i g n a t u r e ， a n ds oo n t h eg r o u ps i g n a t u r es c h e m er e s e a r c h e di nt h i sd i s s e r t a t i o ni sa m o n g t h e m ，w h i c hh a sa t t r a c t e dal o to fa t t e n t i o n si nt h i sw o r l d t h eg r o u ps i g n a t u r ee x t e n d st h et r a d i t i o n a ld i 舀t a ls i g n a t u r ec o n c e p tt oa m u l t i p a r t ys e t t i n g i nag r o u pd i g i t a ls i g n a t u r es c h e m e ，m e m b e r so fa 百v e n g r o u pa r ea l l o w e dt os i g no nb e h a l fo ft h ee n t i r eg r o u p t h es i g n a t u r e sc a nb e v e r i f i e du s i n ga s i n g l eg r o u pp u b l i ck e y h o w e v e r , t h es i g n a t u r e sa r ea n o n y m o u s , w h i c hm e a n sn o b o d ye x c e p tt h ed e s i g n a t e dm e m b e r , c a l l e dg r o u pm a n a g e r , 啪 o p e nt h es i g n a t u r eo rr e v o k et h ei d e n t i t yo f t h es i g n e ti na d d i t i o n ，t h es i g n a t u r e s a r eu n l i n k a b l e i ti si m p o s s i b l et od i s t i n g u i s hw h e t h e rt h ed i f f e r e n ts i g n a t u r e s c o m ef r o mt h es a m es i g n e r t h e r ee x i s ts e v e r a lo t h e rg r o u p - o r i e n t e dc o n c e p t s f o rs i g n a t u r es c h e m e s 。t h em o s ti m p o r t a n to n e sa r em u l t i - s i g n a t u r e sa n dp r o x y s i g n a t u r e s m u l t i s i g n a t u r e sc a nb es e e na sg e n e r a l i z e dg r o u ps i g n a t u r ew i t h o u t t h ea b i l i t yo f “o p e n i n g ”s i g n a t u r e s ，w h i l ep r o x ys i g n a t u r e sa r eg r o u ps i g n a t u r e s t h a td on o tp r o v i d ea n o n y m i t y i nt h i sd i s s e r t a t i o n ，f r o mc h a p t e r3t o5 ，i tt a k e sad e e pr e s e a r c ho nt h r e e a s p e c t so fg r o u ps i g n a t u r e t h ef i r s to n ei st od e s i g nan e wt y p eo fg r o u p s i g n a t u r e ，t h es e c o n di s t od e s i g nak i n do fg r o u ps i g n a t u r es c h e m ew i t h a u t h o r i z a t i o n ，a n dt h et h i r di st od e s i g nt w on e wk i n d so fg r o u pb l i n ds i g n a t u r e s c h e m e t h ed e t a i l sa r ea sf c i l l o w s ： h ls e c t i o n3 3o fc h a p t e r3 i td e r i v e san e wt y p eo fs i g n a t u r es c h e m eb a s e d o nt h es c h e m ep r o p o s e db yb o n e ha n db o y e n i ns e c t i o n3 4o fc h a p t e r3 ，t a k i n ga d v a n t a g eo fc s 9 8e n c r y p t i o ns c h e m e a n do u rn e w s i g n a t u r es c h e m e ，i td e s i g n san e wt y p eo fg r o u ps i g n a t u r es c h e m e t h es e c u r i t yo ft h en e wg r o u ps i g n a t u r es c h e m ei sb a s e do nt h eq - s t r o n g d i f f i e h e u m a na s s u m p t i o na n dt h ed e c i s i o n a ld i f f i e h e l l m a na s s a m 【p t i o ni nt h e r a n d o mo r a c l em o d e l ，t h el e n i g t ho ft h en e wg r o u ps i g n a t u r ei sal i t t l el o n g e r 第1 v 页西南交通大学博士研究生学位论文 t h a nt h a to fb b ss h o r tg r o u ps i g n a t u r es c h e m e h o w e v e r , i nt h eg r o u ps i g n a t u r e s c h e m e ，g i v i n gc e r t i f i c a t e sa n dp r i v a t ek c y st og r o u pm e m b e r sd on o tn e e da n y t h i r dt r u s t e dp a r t y , w h i l ei nb b ss h o r tg r o u ps i g n a t u r es c h e m ei td o e sn e e d i ns e c t i o nc h a p t e r4 ，i ta d d s a l g o r i t h ma u t h g e n t ot h eb m wg r o u p s i g n a t u r es c h e m e u s i n ga u t h g e n ，w eo b t a i nm e m b e ra u t h o r i z a t i o na u t h i b y m e a n so fk e yg e n e r a t i o na l g o r i t h m ，w eo b t a i ni s s u i n gk e yf o ra u t h o r i z a t i o n c e r t i f i c a t e s k 4a n dv e r i f y i n gk e yf o ra u t h o r i z a t i o nc e r t i f i c a t ep k 。w i t ht h e h e l po f 晚，w ec a ns i g no n ( f ，a u t h , ) t op r o d u c em e m b e r sa u t h o r i z a t i o n c e r t i f i c a t ea u t h c e r c o m p a r e dw i t hb m w ss c h e m e ，a l t h o u g ht h es p e e do f i n s t a n c ep r o d u c t i o no fg r o u ps i g n a t u r es c h e m es l o w sd o w n ，t h en e ws c h e m e s t r e n g t h e n sg r o u ps i g n a t u r e s c h e m ew i t ha u t h o r i z a t i o nc h a r a c t e r i s t i c f u r t h e r m o r e ，t h ep r o o fo ff u l lt r a c e a b i l i t ys e c u r i t yo fg r o u ps i g n a t u r ei nt h i s p a p e ri ss i m p l e rt h a nt h a to fb m w s s c h e m e i ns e c t i o n5 3o fc h a p t e r5 ，i tc o n s t r u c t san e wg r o u pb l i n ds i g n a t u r e s c h e m eo nt h eb a s i so fa c j tg r o u ps i g n a t u r es c h e m e t h es e c u r i t yo ft h en e w s c h e m ei sb a s e do nt h e s t r o n g r s aa s s u m p t i o na n dt h ed e c i s i o n a l d i f f i e h e l l m a na s s u m p t i o n ，o fw h i c hi sd i f f e r e n tf r o mt h es c h e m eo fl r 9 8 i n t h em e a nt i m e ，t h ee f f i c i e n c yo ft h eu s e rt ob l i n dt h ec o n t e n to ft h es i g n e ri s i m p r o v e d t ob l i n dt h eg r o u ps i g n a t u r eo fa c j t , t h i sp a p e ro n l ya d d st h e c o m p u t a t i o no fm o d u l a re x p o n e n t i a t i o na n dm o d u l a ra d d i t i o n ；w h i l et h es c h e m e i nl r 9 8a d d st h ec o m p u t a t i o no fd o u b l ed i s c r e e tl o g a r i t h m ，r o o to ft h ed i s c r e e t l o g a r i t h ma n dr a n d o mp e r m u t a t i o ni no r d e rt ob l i n dt h eg r o u ps i g n a t u r eo fc s 9 7 a sar e s u l t ，t h es c h e m ep r o p o s e db yt h i sp a p e ri sm u c hl o w e rt h a nt h eo n ei n l r 9 8w i t hr e s p e c tt o c o m p u t a t i o nc o m p l e x i t ya n dh i g h e rw i t hr e s p e c t t o e f f i c i e n c y i ns e c t i o n5 4o fc h a p t e r5 ，i tc o n s t r u c t sap r o v a b l ys e c u r i t yi d - b a e s dg r o u p b l i n ds i g n a t u r es c h e m eo nt h eb a s i so fc z k si d b a s e dg r o u ps i g n a t u r es c h e m e t h es e c u r i t yo ft h en e ws c h e m ei sb a s e do nt h ec o m p u t a t i o n a ld i f f i e h e l l m a n a s s u m p t i o nu n d e rt h er a n d o mo r a c l em o d e l ，o fw h i c hi sd i f f e r e n tf r o mt h e 西南交通大学博士研究生学位论文第v 页 s c h e m eo f1 2 , 9 8 i nt h em e a nt i m e ，t h ee f f i c i e n c yo ft h eu s e rt ob l i n dt h ec o n t e n t o ft h es i g n e ri si m p r o v e d t ob l i n dt h eg r o u ps i g n a t u r eo fc z kt h i sp a p e ro n l y a d d st h ec o m p u t a t i o no fm o d u l a ra d d i t i o n ；w h i l et h es c h e m ei nl r 9 8a d d st h e c o m p u t a t i o no fd o u b l ed i s c r e e tl o g a r i t h m ，r o o to ft h e d i s c r e e tl o g a r i t h ma n d r a n d o mp e r m u t a t i o ni no r d e rt ob l i n dt h eg r o u ps i g n a t u r eo fc s 9 7 a sar e s u l t ， t h es c h e m ep r o p o s e db yt h i sp a p e ri sm u c hl o w e rt h a nt h eo n ei nl r 9 8w i t h r e s p e c tt oc o m p u t a t i o nc o m p l e x i t ya n dh i g h e r w i t hr e s p e c tt oe f f i c i e n c y k e yw o r d s ：d i g i t a ls i g n a t u r e ；g r o u ps i g n a t u r e ；g r o u ps i g n a t u r e w i t h a u t h o r i z a t i o n ；g r o u pb l i n ds i g n a t u r e 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密团，适用本授权书。 ( 请在以上方框内打“v ”) 学位论文作者签名：膨彳1 茚 e t 期：们7 年7 月6e l 指导教师签名。哆屯冯 日期：。叼年月莎日 西南交通大学 学位论文创新性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本文论不含任何其 它个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个 人和集体，均己在论文中作了明确的说明。本人完全意识到本声明的法律 结果由本人承担。 本学位论文的主要创新点如下： ( 1 ) 在b b 方案( b o n e h 和b o y e n 提出的在q s d h 假设之上构建的短签 名) 的基础上演化出一个新的签名方案。具体方案见第3 章3 3 节。 ( 2 ) 利用c s 9 8 加密方案( c r a m e r 和s h o u p 构建的i n d c c a 2 安全的公钥 加密方案) 和新的签名方案构建了一个新的群签名方案。新的群签名方案的 安全性建立在随机预言机模型下，q s d h 假设和判定d i f f i e h e l l m a n 假设 之上的。新提出的群签名方案的签名长度比b b s 的短群签名方案的签名长 度略长，但新的群签名方案在为群成员发放资格证书以及成员私钥时，不 需要可信任第三方的参与。具体方案见第3 章3 4 节。 ( 3 ) 在b m w 方案( b e u a r e ，m i c c i a n c i o 以及w a r i n s c h i 构建的标准假设之 上的群签名方案) 的基础上加入了权限产生算法a u t h g e n ，利用其产生成员 的权 a u t h ，由密钥生成算法产生丸和p k , ，其中叱是权限证书发布密 钥，砘是权限证书验证密钥。利用s k 对( f ，o u t h , ) 进行签名生成成员的权 限证书a u t h c e r t i 。同b m w 方案比较，虽然群签名方案的实例生成速度降低， 但为群签名方案添加了权限特性；并且，在论文中，对群签名方案应具备 的完全可追踪性的安全性的证明比b m w 方案更加简洁。具体方案见第4 章4 3 和4 4 节。 ( 4 ) 在a c j t 方案( a t e n i e s e ，c a m e n i s c h ，j o y e 以及t s u d i k 构建的实用性极 高的群签名方案) 基础上创建了新的群盲签名方案，a c j t 群盲签名方案。 同已有的l r 9 8 方案比较，新方案的安全性建立在强r s a 以及判定性 d i f f i e h e l l m a n 假设之上，在盲化a c j t 群签名方案时，新方案仅添加了模 西南交通大学博士研究生学位论文第1 页 1 1 研究背景和意义 第1 章绪论 随着计算机技术和通信技术的飞速发展，信息化的浪潮席卷全球，网 络已经成为人们工作生活的一部分。电子邮件，网络银行，网站发布，电 子商务等等网络化服务迅猛发展。然而网络的安全问题随着网络应用的普 及和深入而日益突出。信息安全问题已经成为信息产业的瓶颈。古老而年 轻的密码技术是保证信息安全的最重要的手段之一。密码技术包括加密、 消息认证、数字签名、零知识证明、多方计算等。 数字签名在密码技术中占有举足轻重的地位，其重要性随着电子商务 与电子政务的日益普及而愈发凸显。数字签名的本质就是保证数据的完整 性。在h l t e m e t 构成的网络世界里，如何保证数据的完整性是一个很复杂的 问题。它包括网络设备中的路由器能否处理海量的数据；网络中某些设备 出现故障，数据能否抵达目的地：数据被网络攻击者窃取后能否抵抗其攻 击、串改。数字签名处理的就是数据如何抵抗攻击者的恶意攻击。 在d i f f i e 和h e l l m a n 1 这篇开创了现代密码学先河的文章中，两位研究 者首次提出了公钥加密学和数字签名的概念。数字签名技术与公钥加密技 术具有对偶性。签名者使用的签名密钥是解密者用于解密的私钥，验证者 使用的验证密钥是加密者用于加密的公钥。这里，签名密钥( 私钥) 是秘 密保存的，而验证密钥( 公钥) 是公开的。数字签名技术与手写的签名具 有同等的作用。签名者的身份就是其验证密钥，一个公开可查询的字符串， 签名者秘密持有其签名密钥。签名者利用其签名密钥对消息m 签名，验证 者利用签名者的验证密钥验证签名的合法性。攻击者在获得签名者的签名 后，不能伪造出一个合法的消息一签名对。签名者对消息签名后，他不能 否认对消息签了名。这是因为，通过验证，该签名是合法的。而一个合法 的签名只可能由签名者产生。如同手写的签名，对于现实生活中的各项工 作，数字签名技术保证了下面两点：( 1 ) 数据来源于一个可靠的人，该数据 是完整而可靠的，即便数据经过了攻击者的蓄意串改；佗) 可以向第三方证 明该数据来源于签名者。 第2 页西南交通大学博士研究生学位论文 自从d i t ! f i e 和h e l l m a n 提出数字签名的概念以来，数字签名技术得到了 广泛而深入的研究。除了对传统意义上的数字签名技术进行研究以外，研 究者们还衍生出了盲签名、门限签名、代理签名、前向安全性签名等等签 名体制。本论文关于群签名体制的研究就属于这诸多的研究方向之一。 群签名方案，如同传统的签名方案，允许签名者向验证者证明：关于 消息的签名是其利用签名密钥得到的。并且，对于任何一个知道群公钥的 验证者来说，该签名是可以公开验证的。然而，群签名是匿名的。任何验 证者都无法知道是哪一个群成员对消息签的名。此外，群签名还具有无法 链接性：验证者无法判定多个不同的签名是否来自同一个群成员的签名。 如果验证者对签名者的身份起了疑心，他可以通过群管理者恢复出签名者 的身份。同多重签名比较而言，多重签名可被看成不具备追踪功能的群签 名：同代理签名比较而言，代理签名则是不具备匿名性的群签名。 群签名方案具有的显著特性使其在电子商务领域得以广泛应用。例如： 电子选举、电子投标等等场合。具体说来，群签名方案可以隐藏组织机构 的构成。比如，公司需要一个共同的身份标志。公司中的职员可以代表整 个公司同客户签合同。但对于客户来说，他只知道合同是其与该公司签的， 并不知道签名者在公司处于什么样的地位，换句话说，不知道其身份。倘 若合同在后来实施中出现了麻烦，公司的主管可以追查到签署合同的职员 的身份。 自从c h a u m 和v a nh e y s t 2 提出群签名的概念以来，理论密码学界对群 签名作了大量的、细致入微的研究工作。文献 f 8 , 9 ，1 0 ，1 2 ，1 3 ，1 5 ，1 6 ，2 7 ，3 2 ，3 3 ，3 6 ，5 4 ，5 5 ，1 2 3 ，1 2 5 】都是对标准群签名方案的研 究。此外，研究者们结合数字签名技术中的盲签名、前向安全性签名以及 基于身份的签名衍生出不同的以群签名为主体的方案。文献p 0 】是群盲签名 方案，文献1 4 9 是具有前向安全性的群签名方案，文献 2 4 ，2 5 ，2 6 是基于身份 的群签名方案。 群签名方案属于可证明安全性的密码体制。它包括了可证明性安全的 三个要素，即安全性的定义，安全性所基于的假设以及归约化证明。 目前群签名方案的安全性基于的模式可分为两大类：随机预言机模型 ( r a n d o mo r a c l em o d e l ) 和标准化假设模型( s t a n d a r d a s s u m p t i o nm o d e l ) 。由 于在标准化假设模型中，研究者们在构建群签名方案时去处了理想的哈希 西南交通大学博士研究生学位论文第3 页 函数，与随机预言机模型下的群签名方案比较，其效率有所降低，但方案 的安全性更高。 1 2 群签名方案的安全陛定义 研究理论密码学，一项很重要的工作就是为其中不同密码组件的安全 性提供相应的标准化定义，然后，利用一些通用的计算上困难的假设构建 不同的方案。群签名方案是由公钥加密( p u b l i c - k e ye n c r y p t i o n ) 体制和数字 签名( d i g i t ms i g n a t u r e ) 体制以及非交互式零知识证明系统( n o n i n t e r a c t i v e z e r o k n o w l e d g ep r o o f s y s t e m ) 共同实现的，这里有必要简单地阐述一下这三 种体制的安全性。 公钥加密体制的安全性按照目标可以分为两大类：不可区分性 ( i n d ，i n d i s t i n g u i s h a b i l i t y ) 和非延展性( n m ，n o n m a l l e a b l i l i t y ) 。n m 的安全性 比i n d 强。按照攻击模型可分为：选择明文攻击( c p a , c h o s e np l a i n t e x t a t t a c k ) ，非适应性选择密文攻击( c c a l ，n o n a d a p t i v ec h o s e n c i p h e r t e x t a t t a c k ) ，适应性选择密文攻击( c c a 2 ，a d a p t i v ec h o s e n c i p h e n e x ta t t a c k ) 。其 中c c a 2 的安全性晟强。组合安全性目标和攻击模型，可以获得六种不同 的安全性：i n d c p a , i n d c c a l ，i n d c c a 2 ，n m c p a , n m c c a l ，n m c c a 2 。 其中i n d c c a 2 和n m c c a 2 是安全性最强的，并且二者被证明是等价的 5 6 1 。数字签名体制的安全性的标准定义由文献 6 2 1 给出，即抗适应性选择 消息攻击( a g a i n s ta d a p t i v ec h o s e n m e s s a g ea t t a c k ) ：攻击者在给出伪造的消息 一签名对f m ，口) 之前，他可以向签名预言机询问多项式个不同的消息，并得 到相应的签名。这里限定伪造的伽，o ) 不是由签名预言机获得的，即消息m 没有询问签名预言机。非交互式零知识证明系统的定义由文献【6 9 】给出。它 的本质含义是指证明系统( p ，y ) 共享一个随机串r ，证明者p 能向验证者y 提供关于定理羔的证明w ，验证者能在参数为i 工i 的多项式时间内验证 伍，们e p ，p 表示一个p 关系。验证的时候，验证者不知道证明定理x 的 过程。换句话说，证明者知道这一过程，他能够向验证者证明自己知道过 程的这一事实。但作为验证者，她除了知道这一事实外，对过程本身毫不 第4 页西南交通大学博士研究生学位论文 知情。 1 9 9 1 年，c h a u r i l 和v a nh e y s t 首次提出群签名的概念，但直到2 0 0 3 年 b e l l a r ee ta 1 5 4 1 才将群签名方案诸多的安全特性标准化。b e l l a r ee ta 1 在文中 指出一个群签名方案只要满足完全匿名性( f u l l a n o n y m i t y ) 和完全追踪性 ( f u l l t r a c e a b i l i t y ) ，这个方案就是安全的。下面，给出完全匿名性和完全追踪 性的定义，并具体说明为什么这两种特性就是群签名方案所需要的安全特 性。 为了定义完全匿名性，首先要构建一个攻击者攻击群签名方案完全匿 名性的模型。假定存在群签名方案g s ，其中群公钥为g p k ，群管理者的私 钥为g m s k ，群成员的私钥为g s k i i ，l n o ，不 等式o c 。g ( n ) s ，0 ) s c z g ( n ) 成立。 。通常记为( n ) 一e 括( n ) ) 。它表示 函数，o ) 的增长速度当参数n z 以。时，：i ! e q g ( n )c 2 9 ( n ) 之间。事实上，当 且仅当，o ) 一d ( 9 0 ) ) 和g ( n ) - d ( ，0 ) ) 时，( n ) 一e ( 9 0 ) ) 。可用图2 2 来 直观地描述其含义： 图2 2f ( n ) - 0 ( 9 0 ) ) 第1 8 页西南交通大学博士研究生学位论文 3 ) 符号q 。对于一个给定的函数g o ) ，表达式q ( g ( h ) ) 表示一个函数的集合。 q ( g ( h ) ) - ( ( n ) ：存在正的常数c 和正的整数，对于所有的n 2 ，不等 式0 蔓鳄( ”) s ( n ) 成立。) 。通常记为( n ) ；q ( g o ) ) 。它表示函数，o ) 的 增长速度当参数，1 2 时，比曙0 ) 快。可用图2 3 来直观地描述其含义： 图2 3 f ( n ) 一q ( g o ) ) 在计算复杂性理论中，通常将可判定或可解的算法归为p 类，这类算 法是多项式时间内可解的：这些算法在输入为n 时，对于某个常数k ，它们 最坏的运算时间为o ( n ) 。另一类的算法为n p 类。这类算法可为所需解决 的问题提供一个可在多项式时间内验证的“证明”。任何p 类算法都属于p 类，即p n p ，但n p p 这一难题到目前为止尚未解决。此外，随机算法 在密码学领域有着广泛的应用，占有举足轻重的地位。下面，分别给出计 算复杂性理论中的p 类，n p 类以及b 尸_ p 类的定义。所给的定义与文献 6 4 1 中的定义类似。 定义2 1 p 类。令是一种语言，工 0 ，1 ) 。如果存在一个确定性图灵机 m ，一个多项式p ( ) ，v x e l ，当确定性图灵机j l f 的输入为x ，在最多p d 工1 ) 步，肘0 ) = 1 ，那么就称语言l 能在确定性多项式时问内被识别。p 类是指 一类能在确定性多项式时间内被识别的语言。 西南交通大学博士研究生学位论文第1 9 页 p 问题是理论密码学领域的基础，下面给出其定义。令l 是一种语言， 工 0 ，1 。凡 o ，1 ) o ，1 是一个定义在语言上的二元关系。 r o ) = ：0 ，f o ) r ，称为x 的解。k - x ：j n ，s 1 ，甜) 吃) 。如 果对于所有的o ，m ) 咒，存在一个多项式p ( ) 使得i k p ( i x l ) 成立，就称 r ，是多项式内有界的。 定义2 2 p 类。语言。属于 驴，如果存在上述的多项式内有界的二元关 系也 0 ，”+ x o ，1 ，其中对于v 膏，| ，使得( x ，w ) 琏成立，并且该 关系可在多项式时间内识别。 由于随机算法在密码学中的重要性，这里有必要对其作一简单的叙述。 一个随机算法在运行时，可以随机选择下一步的执行。随机算法通常理解 为概率多项式时间图灵机。对于一个概率多项式时间图灵机，它的t r a n s i t i o n f u n c t i o n 将“蜘龆) ，( s y m b 0 1 ) ) 映射成两对“s 纪纪) ，( s y m b 0 1 ) ，( 够) ) ， “s 细纶) ，( s y m b 0 1 ) ，( r i g h t ) ) a 即概率多项式时间图灵机通过随机比特6 办以去 的概率选择下一步的执行。在密码学中，有效的计算通常指能在概率多项 式时间内完成的计算。一个概率多项式时间图灵机j | l f ，其输入为x ，它的 运行时间的上限为一个多项式p q z j ) ，它的随机串的长度为d - 1 ) 。 定义2 3 艘p 类。令是一种语言， 0 ，1 ) 。语言能被概率多项式时 间图灵机m 识别，如果它满足： 1 1 ) v x e l ，p r m ( x ) 一1 】；2 ) v x 譬三，p r m o ) 一1 1 妄 j j b p p 类是指一组能被概率多项式时间图灵机识别的语言类。 在密码学中，经常用到可忽略函数这一概念，这里给出其定义。 第2 0 页西南交通大学博士研究生学位论文 定义2 4 可忽略函数( n e g l i g i b l e f u n c t i o n s ) 。函数z ：n r 是可忽略的，如 果对于所有的多项式p ( ) ，存在一个正的整数，当n n o 时，( 行) c 页1 石 成立。 此外，计算复杂性理论中的预言机( o r a c l em a c h i n e l 在密码学的公钥加 密、数字签名等领域的安全性证明中占有重要的地位，这里对其作一简单 的叙述。简单地说，一个预言机就是一个加强版的图灵机m ，。该图灵机可 以向预言算法提问，并从预言算法获得答案。定义预言算法为 f ： 0 1 ) 一 o ，1 ) + 。如果图灵机的询问为q ，那么，图灵机从预言算法获得 的答案就为f ( q 1 。 2 1 2 交互式证明系统 6 3 】 交互式证明系统是指在一个证明系统中存在两个相互联系的个体：证 明者( p r o v e r ) 和验证者( v e r i f i e r ) 。这两者交互地发送信息给对方，发送的过 程是单向的。证明者产生一个证明，将证明发送给验证者，验证者验证该 证明的正确性。值得注意的是，上述的证明者和验证者可以理解为算法或 是图灵机。 定义2 5 交互式图灵机( i n t e r a c t i v et u r i n gm a c h i n e ，1 t m ) 。一个交互式图灵 机是多带图灵机。该多带图灵机有只读输入带、随机带、工作带、只读通 信带和只写通信带。随机带上有一无限长的随机串，随机串只能从左往右 读入。交互式图灵机随机地抛一枚硬币指它在自己的随机带上读取下一个 比特。 定义2 6 交互式协议( i n t e r a c t i v ep r o t o c 0 1 ) 。交互式协议指的是一对 i t m ( p y ) ，其中( p ，矿) 共享输入带，v 的只写通信带是p 的只读通信带，p 的只写通信带是v 的只读通信带。p 的计算能力不受限制，y 的计算上限 需在一个多项式时间内完成，该多项式的参数为( p ，y ) 的共同输入的长度。 西南交通大学博士研究生学位论文第2 1 页 p 和v 轮流处于激活状态，y 首先处于激活状态。当p ( v 1 处于激活状态， p ) 利用输入带、工作带、通信带以及随机带上的数据进行内部运算，并 将其结果写在它的只写通信带上，而该结果将被y ( p ) 读取。v ( v ) 的第f 次 消息就是它写在只写通信带上的数据。一旦p ( 矿) 在只写通信带上写了消息， 它就转为非激活状态，而矿( p ) 处于激活状态，除非协议已经终止。p 或矿都 可以在其激活状态下不写消息在只写通信带上来终止协议的运算。y 输出 a c c e p t 或r e j e c t 来表示它是接受还是拒绝它在只读通信带上的数据。v 的计 算时间是它所有激活状态下的计算时间总和，该总和的上限是参数为m 的 多项式。 可通过图2 4 来描述交互式协议( p ，v ) 的计算： 凰r r 、 二= ， 二二 r 图2 4 交互式协议( r 表示只读头，w 表示只写头) 定义2