（信息与通信工程专业论文）非交互式可否认认证协议的研究.pdf

摘要 摘要 可否认认证协议是一种特殊的认证协议，它允许消息的接收方认证发送方的身 份，但不能向任何第三方证明消息来源。这种认证协议不仅能够在高压政治下给 电子选举方案提供投票自由，还可以给互联网上的谈判提供安全性，甚至能够在 电子商务中保护消息发送者的隐私，防止接收方保留不利于发送者的认证消息并 将其作为证据。在近几年，研究人员设计出了各种各样的可否认认证协议，但还 不能满足应用的需要。 本文深入地研究了可否认认证协议及其相关理论的特征和应用，在此基础上， 针对电子邮件协商和电子投票等应用领域设计了多个拥有不同属性的非交互式可 否认认证协议。归纳起来，本文的工作主要包括以下几个方面： 1 提出非交互式可否认认证协议中的“弱化的密钥泄露模仿安全性 ( w e a k e n k e y - c o m p r o m i s ei m p e r s o n a t i 0 1 1 ，w - k c i ) 以及“w - k c i 攻击一两个概念。本文深 入分析了现有的研究成果，并针对非交互式可否认认证领域提出了“w k c i 安全 性厣和“w - k c i 攻击”的概念。 2 提出一种基于身份的可否认认证协议。为了抵御提出的w - k c i 攻击，本文 提出一种基于身份的可否认认证协议。新的协议不仅满足了受限制的可否认性， 还提供了灵活的数据传输方式，能够应用于电子投票领域。 3 提出一种基于匿名代理的可否认认证方案和一种基于身份的用于秘密信息 传输的代理可否认认证协议。在研究代理签名体制的基础上，本文根据要求代理 匿名的应用，设计出一种基于匿名代理的可否认认证方案。新的方案不仅满足了 消息的可否认性，还实现了代理的匿名。最后，文章借鉴基于身份的密码体制的 思想，提出一种基于身份的用于秘密信息传输的代理可否认认证协议，并分析了 协议的安全性。 关键字：双线性对，可否认认证，代理签名，指定验证者签名 a b s t r a c t t h ed e n i a b l ea u t h e n t i c a t i o np r o t o c o li sas p e c i a la u t h e n t i c a t i o np r o t o c 0 1 i te n a b l e s a ni n t e n d e dr e c e i v e rt oi d e 而匆t h es o u r c eo fa g i v e nm e s s a g e ，b u tt h ei n t e n d e dr e c e i v e r c a n n o tp r o v et h es o u r c eo fag i v e nm e s s a g et oa n yt h i r dp a r t ye v e ni fh ei sw i l l i n gt o r e v e a lh i ss e c r e tk e y t h u si tc a nb eu s e dt op r o v i d ef r e e d o mf i o mc o e r c i o ni ne l e c t r o n i c v o t i n gs y s t e m s ，p r o v i d es e c u r i t yf o rn e g o t i a t i o no v e rt h ei n t e r n aa n dp r o t e c ts e n d e r s p r i v a c yi ne l e c t r o n i c - c o m m e r c et op r e v e n tt h er e c o v e r sf r o mu s i n gh i ss i g n e dm e s s a g e s t od os o m e t h i n gb a dt oh i m d u r i n gt h e s ey e a r s , v a r i o u sd e n i a b l ea u t h e n t i c a t i o n p r o t o c o l sh a v eb e e np r o p o s e d , b u tm c ) ，c a nn o tm e e tt h en e e d s o f t h ea p p l i c a t i o n t h i sd i s s e r t a t i o ni n t e n s i v e l yi n v e s t i g a t e st h ec h a r a c t e r i s t i ca n dt h ea p p l i c a t i o no f d e n i a b l ea u t h e n t i c a t i o np r o t o c o l sa n ds o m eo t h e rr e l a t e dt h e o r i e s b a s e do nt h er e s e a r c h , s o m en o n i n t e r a c t i v ed e n i a b l ea u t h e n t i c a t i o np r o t o c o l sw h i c hh a v ed i f f e r e n ta t t r i b u t e s a r ep r o p o s e dt oa p p l yi nt h ef i e l do f n e g o t i a t i o nt h r o u g he - m a i la n de l e c t r o n i cv o t i n g t o s u mu p , t h er e s e a r c h e sc g t nb ec o n c l u d e d 够f o l l o w s 1 t h en o t i o n so fw e a k e nk e y - c o m p r o m i s ei m p e r s o n a t i o n ( w - k c i ) s e c u r i t ya n d w - k c ia t t a c ki nn o n - i n t e r a c t i v ed e n i a b l ea u t h e n t i c a t i o np r o t o c o l sa r ep r o p o s e d t h i s d i s s e r t a t i o ni n t e n s i v e l ya n a l y z e st h ep r e s e n tr e s e a r c h e sa n dp r o p o s e st h en o t i o n so f w - k c is e c u r i t ya n dw - k c ia t t a c ki nn o n - i n t e r a c t i v ed e n i a b l ea u t h e n t i c a t i o np r o t o c o l s 2 a ni d e n t i t y - b a s e dr e s t r i c t e dd e n i a b l ea u t h e n t i c a t i o np r o t o c o li sp r o p o s e d t o r e s i s tt h ew - k c ia t t a c k , a ni d e n t i t y - b a s e dd e n i a b l ea u t h e n t i c a t i o n p r o t o c o lf r o m b i l i n e a rp a i r i n gi sp r o p o s e d t h en e wp r o t o c o lh a st h ep r o p e r t yo fr e s t r i c t e dd e n i a b i l i t y a n dp r o v i d e saf l e x i b l ew a yo fd a t at r a n s m i s s i o n , i nw h i c hu s e r sc a nd e c i d et os e n d e n c r y p t i o nm e s s a g e so rn o n - e n c r y p t i o nm e s s a g e s 3 ad e n i a b l ep r o x y - a n o n y m o u ss i g n a t u r es c h e m ea n da ni d e n t i t y - b a s e dd e n i a b l e a u t h e n t i c a t i o np r o t o c o lf o rs e c r e tc o m m u n i c a t i o na r e p r o p o s e d t h i s d i s s e r t a t i o n i n v e s t i g a t e sp r o x ys i g n a t u r es c h e m e sa n dp r o p o s e sad e n i a b l ep r o x y - a n o n y m o u s s i g n a t u r es c h e m ew h i c hc a np r o t e c tt h ep r o x y si d e n t i 姒i nt h ep r o p o s e ds c h e m e ，t h e p r o x ys i g n e rc a nn o to n l ys e n dd e n i a b l em e s s a g e so nb e h a l fo ft h eo r i g i n a ls i g n e r , b u t a l s oh i d eh i si d e n t i t y a tl a s t ，a n o t h e ri d e n t i t y - b a s e dd e n i a b l ea u t h e n t i c a t i o np r o t o c o lf o r a b s t r a c t s e c r e tc o m m u n i c a t i o ni sd e s i g n e da n di t ss e c u r i t yi sa n a l y z e d k e yw o r d s ：b i l i n e a rp a i r i n g s ，d e n i a b l ea u t h e n t i c a t i o n , p r o x ys i g n a t u r e ，d e s i g n a t e d v e r i f i e rs i g n a t u r e i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名： 日期：扣夕年衫月多日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 虢诧硝哟 导师始冈垅 1 日期：o 舾7 年石月岁日 第一章绪论 第一章绪论 本章说明了论文的背景与意义，然后在此基础上给出了本文的研究内容，即以 双线性对和可证安全理论为基本工具，设计一批具有某些特殊性质的可否认认证 协议，满足应用需求。最后，第三节介绍了本文的组织结构。 1 1 研究背景及意义 1 1 1 研究背景 据中国互联网络信息中心( c n n i c ) 最新发布的第2 3 次中国互联网络发展 状况统计报告【l 】显示，截至2 0 0 8 年底，我国互联网普及率达到2 2 6 。同时， 我国网民数达到2 9 8 亿，宽带网民数达到2 7 亿，国家c n 域名数达1 3 5 7 2 万。 同时，随着3 g 时代的到来，无线互联网还将呈现出爆发式的增长趋势。毫无疑问， 所有的数据均表明社会已经进入一个崭新的时代。 伴随着i n t e m e t 的飞速发展，传统的商务活动、事物处理及政府服务已经或越 来越多的将要通过开放的i n t e m e t 来实施和提供。无论是方便快捷的网络聊天、家 中购物，还是复杂如银行业务和税收的庞大系统，都让人们感受到了强大的科技 给生活带来的巨大变革。然而，由于i n t e m e t 本身的开放性、匿名性、数据传输透 明性，以黑客、计算机欺诈、计算机破坏、计算机病毒等为代表的计算机犯罪对 社会造成了巨大损失。为了让开放的网络能够提供安全通信，实现家中购物、股 票交易银行业务等商务活动、事务处理，人们采用以密码技术为基础的安全协议 来保护通信。具有代表性的协议包含用于实现即时电子支付的s e t ( s e c u r e e l e c t r o n i ct r a n s a c t i o n ) 协议、用于邮件加密的p g p ( p r e t t yg o o dp r i v a c y ) 协议和 用于保障w e b 站点间的交易信息传输安全性的安全超文本传输协议( s h t t p ) 等 等。 1 1 2 意义 在现实世界中，商务活动、事务处理以及服务是千差万别的。为了实现一个网 络化的虚拟社会，必须建立各种各样的应用环境满足不同的应用需求。在分布式 电子科技大学硕士学位论文 网络中，主要问题是有效控制用户对于网络组成部分和资源所进行的访问，因此 分布式网络协议需要满足认证和密钥建立的安全性。在电子商务交易中，人们关 心的是货款的等价交换，电子商务协议需要满足原子性；此外，电子商务交易还 必须向交易双方提供处理交易争端的手段，因此，不可否认性被认为是电子商务 交易的重要属性。但是，不可否认性使得协议的参与方与特定行为相连，不能够 保护用户的隐私，因此在一些需要保护用户隐私和商业机密的业务中，不可否认 性并不适用，可否认性更能切实满足应用需要。 在电子投票中，投票协议的安全运行要求投票者和计票机构必须能够彼此确认 对方的身份。同时，出于保护投票人的目的，计票机构不能泄露投票人的投票结 果，也就是不能向第三方证明某个投票确实是来自特定投票者。 在电子竞标中，协议的双方必须能够互相确认对方身份才能保证竞标协议的正 常运行，并在确认身份的情况下商议密钥用于机密信息( 如标价) 的加密。但是， 在电子竞标的过程中，出价人和拍卖人的地位是不对等的，为了防止拍卖人( 消 息接收方) 获得不正常的价格优势或者拍卖人获利( 将收到的信息篡改，然后向 第三方证明) ，需要在协议中制定规则，让拍卖人无法向第三方证明某个出价来自 特定出价者，而不是拍卖人刻意伪造的。 在电子商务中，某公司a 向特定客户b 推销产品。由于通信信道的认证性， 客户能够确认这一过程的真实性，在合乎自己的要求的情况下必然接受产品。但 出于自我保护的目的，a 公司绝对不希望客户b 利用这一通信记录作为证据来证 明b 也是合法销售商，而另一方面却推销假冒产品。也就是说，这个通信记录应 该是可以否认的。 由于i n t e r n e t 的普及，电子商务、电子政务等系统已经广泛应用，但用户的隐 私在这些系统中还没有得到很好的保护。因此，迫切需要设计一类用于保护用户 隐私的认证协议，满足电子投票和电子投标等环境中的可否认应用需求。 1 2 本文的主要工作 本文源自国家自然科学基金项目认证协议及其相关模块的可证安全理论 与构造，是项目中的一个重要的研究内容。本文详细介绍了可否认认证协议，并 针对电子邮件协商、电子投票和电子竞标等应用领域中的非交互式可否认认证协 议的理论和相关应用进行深入分析和研究。然后，在此基础上提出一批拥有不同 性质的非交互式的可否认认证协议。以下是对本文主要工作的详细描述： 2 第一章绪论 1 本文在分析两个可否认认证协议安全性的基础上，提出了非交互式可否认 认证协议中的“弱化的密钥泄露模仿安全性 ( w e a k e nk e y - c o m p r o m i s e i m p e r s o n a t i o n ，w - k c i ) 以及“w - k c i 攻击 两个概念。此外，本文通过深入分析 电子投票领域说明了这两个概念在电子投票领域中的意义。 2 针对提出的w - k c i 攻击，本文设计了抵御此类攻击的一种基于身份的可否 认认证协议。新的协议不仅满足受限制的可否认认证的特性，还提供了灵活的数 据传输方式，满足了认证协议的安全性要求。 3 在深入研究代理签名体制的基础上，本文根据现有代理签名方案在电子商 务、电子投票等应用中的不足，提出基于匿名代理的可否认签名方案。新的方案 不仅满足被传递消息的可否认性，还以代理匿名的形式保护了代理人的身份。最 后，本文对提出的基于身份的受限制的可否认认证协议进行扩展，设计出一种用 于秘密传输的代理可否认认证协议，实现了基于代理的受限制的可否认认证。 1 3 章节安排 本文共分为五部分，分别以绪论、基本概念及其相关理论、基于身份的可否 认认证协议、基于代理的可否认认证协议和总结进行论述。 第一章主要介绍了本文的研究背景、现实意义、研究内容以及本文的章节安排。 第二章详细介绍了可否认认证协议的概念和研究现状，并按协议的通信方式分 为非交互式和交互式两类。此外，第二章还详细介绍了双线性对和可证安全等与 设计可否认认证协议相关的理论。 第三章主要探讨的是基于身份的可否认认证协议的设计。首先，介绍了两个典 型的可否认认证协议，然后对协议的安全性进行了分析。通过分析现有协议的不 足，本文使用双线性对设计了一种基于身份的可以灵活选择消息传输方式的新型 可否认认证协议。 第四章讨论的是基于代理的可否认认证协议。本文在分析现有的基于代理的可 否认认证方案的基础上，采用双线性对构造了基于匿名代理的可否认签名方案和 用于秘密信息传输的可否认认证协议两种算法。它们满足不同的特性，可以分别 在不同的应用环境中使用。 第五章对全文进行总结，并指出需要进一步研究的方向。 3 电子科技大学硕士学位论文 第二章可否认认证协议及其相关理论介绍 与传统的认证方式相比较，可否认认证是一个相对较新的概念。本章较为详细 地介绍了可否认认证协议的概念及其应用，总结了现有的研究成果，并介绍了包 括双线性对和可证安全在内的相关理论。 2 1 可否认认证协议 2 1 1 概念 可否认认证协议【2 】是指消息的接收方能够辨别出发送方的身份，但是不能向第 三方证明发送方身份的一类协议。它具有两个特征：首先，跟传统认证一样，接 收方可辨别消息的来源；其次，接收方不能向任何第三方证明消息的来源。作为 认证协议，它还应该能够抵抗各种已知的安全协议的攻击。 2 1 2 可否认认证协议的分类 生活中存在各种各样的问题。在每一个应用中都有其特有的应用需要。本节 根据可否认认证协议的不同的应用环境把可否认认证协议分为交互式和非交互式 两类。 2 1 2 1 交互式可否认认证协议 可否认认证协议的交互式可以分为两种情况，一种是参与方为了传递一条可 否认认证消息而进行信息交换；另一种是为了生成会话密钥而交互。假设需要传 递以条消息，每条消息需要交互m 次，那么在第一种类型的可否认认证协议中，传 递刀条消息就需要交互m x n 次。另一方面，假设会话密钥的协商需要交互的次数 是口，那么在会话密钥k 协商完成之后，发送方每次只需要发送如( m ，m a c ( m ，七) ) 的消息就可以既让接收方认证又能否认发送过消息m ，这里的m a c ( m ，尼) 表示消 息肘的验证码。在第二种方式中，传递栉条消息的通信次数只有口+ 甩次。在消息 条数n 足够大( m 口( n 一1 ) ) 时，口+ 刀m x n ，所以当发送的消息较多时，首 先生成会话密钥的方式明显优于第一种。 4 第二章可否认认证协议及其相关理论介绍 所以，遇到应用业务需要系统参与者进行大量信息交互时，让计算开销最理 想的方法是用密钥交换的方式得到会话密钥。只要密钥交换的过程是可否认的， 那么双方得到的会话密钥也是可否认的，所以利用会话密钥的所有消息都是可否 认的。这种用协商后的会话密钥通信的可否认认证形式，主要用于在线的网络协 商或者网络会议等工作。比如，网络会议本身要求认证性，而会议交流协商过程 中的信息是只需要对方认证的消息，不应用作其他用途。 2 1 2 2 非交互式可否认认证协议 在实际应用中，很多业务只需要发送一条消息就能完成。在这类应用中，如 果每次发送消息都协商会话密钥，那么在发送真正有实际意义的消息之前就需要 通信多轮。仍然假设会话密钥的协商需要交互的次数是口，那么仅仅为了发送一 条有实际意义的消息m ，就需要先进行口次信息传递，发送和接收多条冗余的消 息。显然，采用非交互式的可否认认证协议更适合这类应用。下面分别以电子投 票和电子邮件协商为例详细说明上述应用。 在网络投票的过程中，每个选民按照要求填写规定的选票，选择候选人并将 填好的选票投给指定的网络计票器。虽然需要接收选票、填写选票等几个步骤才 能完成投票，但是投票行为只需要一次。众所周知，一次完整的网络选举要求投 票者和计票机构可以彼此确认对方的身份。同时，参与者为了保护自己，需要在 选举过程中保持选票的匿名，即使是计票机构也不能在事后向其他人证明投票者 投出的选票信息。显然，投票过程中的投票行为就是一次非交互式的可否认认证 消息。 同样的，电子商务协商过程中，签订合同之前需要对合同的内容进行多次修 改才能定稿。对未定稿的合同，如果采用任何人都可验证的签名，那么处心积虑 的恶意参与者就可能将利于自己的未定稿合同用作其他用途。所以，应该采用可 否认的认证方式在电子邮件中传递未定稿的合同。与上一个例子类似，虽然在电 子邮件发送之前要做很多的其他工作，但是最后只需要将邮件发送给目标邮件服 务器，而不是与邮件服务器多次交互消息。 2 1 3 可否认认证协议的研究现状 在a 0 0 3 】和c a n e t t i 等人【2 】的早期文章中，对可否认性的概念及其应用进行了探 讨，根据被攻击方将其分为发送方可否认和接收方可否认：根据密钥的类型又分 为共享密钥和公钥可否认密码方案。1 9 9 8 年，d w o r k 等人【4 】提出一个基于零知识 电子科技大学硕士学位论文 证明的方案。该方案需要时间限制，而且其中的知识证明受限于认证过程中的时 间延迟。同年，a u m a n n 和r a b i n 5 】提出了一个基于大数分解的方案。但是，在这 个方案中，需要一个发送方和接收方都信任的公共目录。2 0 0 1 年，d e n g 等人【6 】提 出了两个分别基于大数分解和离散对数问题的协议，此协议跟a u m a n n 和r a b i n 的协议一样，需要一个发送方和接收方都可信的公共目录。此后，徐崇祥等人【7 】 提出一个基于d i f f i e - h e l l m a n 密钥协商的可否认认证协议，他们的协议不需要可信 第三方，但是发送方无法辨别接收方的身份。为了解决这一问题，c h a n g 等人嶂】 和y o o n 等人【9 】分别对徐崇祥等人【7 】的协议进行了改进。此外，还有很多研究人员 采用不同的数学方法提出了不同类型的可否认认证协议。比如，黄秋生等人【l o 】设 计了基于椭圆曲线的可否认认证协议；w a n g 等人【l l 】利用e 1 g a m a l 密码学设计了一 种新的可否认认证协议；l u 等人【1 2 】采用门限方式让多个发送者给一个指定的接收 者发送消息；程继承的协议【1 3 】考虑了秘密消息的传输情况；c h o u 等人【1 4 】贝0 使用双 线性对提出一种基于身份的可否认认证协议，但是不能抵抗k c i 攻击。为了完善 c h o u 的协议，l i r a 等人【1 5 】对c h o u 的协议进行了修改。在考虑并行可否认认证的 情况下，冯涛等人【1 6 】和j i a n g 1 7 】分别提出了各自的可否认认证协议。当然，文章 1 8 】 和 1 9 对已有可否认认证协议的分析也对可否认认证协议的研究起到了推动作用。 值得一提的是，文章 2 0 ，2 1 ，2 2 ，2 3 ，2 4 针对信息多次交互的情况进行了分析，提出 采用可否认的方式协商会话密钥，只要协商的过程是可否认的，那么会话密钥也 是可否认的。 随着上述交互式的可否认认证协议的发展，非交互式的可否认认证协议也被提 出并得到了长足的发展。在 2 5 1 中，s h a o 第一个提出了一个基于广义e 1 g a m a l 签 名体制的可否认认证协议。同年，m u 等人【2 6 】提出一种用于代理的可否认签名，实 现了代理和原签名人的双重可否认。在此之后，众多密码研究人员在可否认认证 领域取得进展，提出了各种基于不同数学难题的可否认认证协议。这其中，既有 基于r s a 的【2 7 1 ，也有基于因数分解的【2 引，还有基于e 1 g a m a l 的1 2 9 1 。此外，由于 双线性对理论在密码学中的发展，很多研究人员采用双线性对理论设计了可否认 认证协谢弘3 4 j ，并分析了协议的安全性。 2 1 4 对当前现状的总结 在前文中已经将可否认认证协议按通信方式分为交互式和非交互式两类。本节 在分析研究现状的基础上，做出如下总结： 6 第二章可否认认证协议及其相关理论介绍 首先，在电子投票和电子邮件协商等领域，完成业务工作只需要发送一条消息， 所以在这类领域中，往往采用非交互式可否认认证协议。而当通信双方发送的消 息数较大时，最好的方式是先协商会话密钥然后再进行通信。 其次，关于非交互式可否认认证协议在电子投票和电子邮件协商等领域中应用 广泛，但现在的研究相对较少。此外，现实中的每种应用还包含很多各自领域内 独有的细节问题，现有的研究成果远远不能满足应用需要。 最后，双线性对是近年发展起来的构造密码体制的一个重要工具。用双线性对 设计的密码协议在密钥长度等方面有明显优势。然而，从实现可否认认证协议的 数学工具来看，基于双线性对的可否认认证协议还比较少。 基于以上观点，本文针对在电子邮件协商、电子投票和电子竞标等领域中的非 交互式可否认认证协议进行了深入分析和研究，并提出了三个拥有不同性质的可 否认认证协议。 2 2 双线性对 双线性对指的是循环群之间相对应的线性映像关系。它是构造密码体制的一个 重要的数学工具，目前只能通过对超椭圆曲线中的w e i l 对或t a t e 对进行变形而得 到【3 5 1 。本节详细介绍了双线性对的概念和性质，并列出了基于双线性对的各种数 学难题。 2 2 1 概念和性质 在现阶段，主要存在两种类型的双线性对。第一种类型如定义2 2 1 所示，它 不仅能从从超奇异椭圆曲线，也能从某些普通椭圆曲线上的w e f t 对或 f a t e 对推导 出来。第二种类型在定义2 2 2 中给出，它只能从超奇异椭圆曲线上的w e i l 对或 t a t e 对推导出来，但它应用起来更方便。 定义2 2 1 设( g o ，+ ) 和( g i ，+ ) 是两个阶为q ( q z + ) 的加法循环群，其零元 分别记作o 。和o 。；( g 2 ，) 是一个阶为g 的乘法循环群，其单位元记作1 。如果一个 二元函数 e ：g o q - - - g 2 满足下述性质，则称该二元函数e 为双线性对( b i l i n e a rp a i r i n g ) ： 双线性性：对明，昱g o ，v q g l ，e ( p i + ，q ) = e ( p t ，q ) e ( p 2 ，q ) ； 对v p g o ，v q i ，幺g i ，e ( p ，q i + q 2 ) = e ( 尸，q ) e ( e ，q 2 ) 。 7 电子科技大学硕士学位论文 非退化性：对v p g o ，p o o ，存在q g l ，使得e ( p , q ) 1 ； 对v q g i ，q q ，存在p g o ，使得p ( 尸，力1 。 从定义2 2 1 中可以看到，第一种类型的双线性对建立在三个不同的群上，所 以应用时不太方便。在密码学中，研究者们更偏向于使用定义2 2 2 中给出的第二 种类型。 定义2 2 2 设( q ，+ ) 是阶为g ( q z + ) 的加法循环群，其零元记作0 。；( g 2 ，) 是一个阶为g 的乘法循环群，其单位元记作l 。如果一个二元函数 g ：g i g i 专g 2 满足下述性质，则称该二元函数e 7 为双线性对： ( 1 ) 双线性性：对即，昱，q g l ，e ( 日+ e ，q ) = e ，( e l ，q ) e ( ，q ) ； 对明，q ，q 2 g l ，e ( p q + q 2 ) = e ( 只g ) e ( p ，q 2 ) 。 ( 2 ) 非退化性：存在p q q ，使得e ( 只q ) 1 。 ( 3 ) 可计算性：对v p ，q g l ，存在有效的算法计算e ( 只q ) 显然，定义2 2 2 是定义2 2 1 在a o = g l 时的特殊形式。为便于讨论，本文中 如不特别说明，均指第二种类型的双线性对，而且用统一的符号e 表示。 由定义2 2 2 ，可以推出第二种类型的双线性对的如下性质。 定理2 2 1 双线性对e 具有如下性质： ( 1 ) 对v p ，q g i ，有e ( - p , 9 = p q ) = e ( p 一q ) 。 ( 2 ) 对吧q g i 和v a ，b z ，有p ( 口尸，b q ) = e ( 只9 曲。 证明：( 1 ) 根据双线性对的双线性性，有如下推导： p ( 只q ) “一尸，9 = d p p ，q ) = p ( q ，q ) = 1 j “一尸，q ) = 2 ( p ，q ) 。1 e ( p ，锄e ( p ，q ) = p ( p - q + q ) = p ( 墨，d i ) = 1j p ( p q ) = e ( p ，q ) 1 因此，性质( 1 ) 成立。 ( 2 ) 为证明性质( 2 ) ，分别证明对v p ，q g l 和v a ，b z ，以下两式成立： p ( 口只9 = p ( 只q ) 4 ( 2 一1 ) “p ，b q ) = e ( p ，q ) 6( 2 - 2 ) 首先证明式( 2 1 ) ，即对v p ，q g l 和v a z ，有e ( a p , q ) = p ( p ，q ) 4 ： 当a = 0 时，e ( a e , q ) = “d l ，9 = 1 = p ( 尸 q ) o = e ( e ，q ) 4 ； 当a 0 ，所以根据性质( 1 ) 可以得到如下推导： e ( 以q ) = p ( 弋一a ) p ，q ) = p ( ( 一口) 只q ) 叫 = ( p ( 尸，q ) 1 ) 一= e ( p q ) 4 8 第二章可否认认证协议及其相关理论介绍 当a 0 时，有 e ( a p , q ) = p ( 尸+ - o p ，q ) = e ( p ，q ) e ( ( 口- o e ，q ) = p ( p q ) e ( p + ( 口- 2 ) p , q ) = d 尸 q ) 2 e ( ( a - 2 ) p , q ) = = e ( p ，q ) a - 2 e ( p + p , q ) = e ( p ，q ) 4 综上所述，对犯q q 和v a z ，有p ( 叱9 = d 尸，9 4 。 同理，对v p ，q g 1 和v bez ，可以得至：l j e ( p , b q ) = p ( p q ) 6 。所以，对v p ，q g l 和v a ，b e z ，有e ( 以b q ) = d p b q ) 4 = ( p ( 只q ) 6 ) 4 = e c p , q ) 曲，即性质( 2 ) 成立。 2 2 2 基于双线性对的困难问题 密码学中的认证协议、签名体制等都是基于某些数学困难问题，比如r s a 是 基于大整数分解的困难性；e 1 g a m a l 签名体制则是基于计算离散对数的困难性。所 有基于双线性对的协议和方案也都是基于计算离散对数的困难性而提出的。文献 3 6 q 口介绍了大部分与双线性对相关的数学难题，本节将它们一一罗列在下文中。 2 2 2 1d i f f i e - h e l l m a n 问题 首先，设( g i ，+ ) 是如2 2 2 所述的加法循环群，p eg l ，g = 撑q 是一个素数。 定义2 2 3 离散对数问题( d i s c r e t el o g a r i t h mp r o b l e m ) ：对给定的q = x p eq ， 计算工z ：。离散对数问题常简称为d l 问题。 离散群上的d l 问题是一个困难问题。与d l 问题密切相关的是计算 d i 伍e - h e l l m a l l 问题和判断d i f f i e - h e l l m a n 问题 定义2 2 4 计算d i f f i e - h e l l m a n 问题( c o m p u t a t i o n a ld i f f i e h e l l m a np r o b l e m ) ： 对给定的a p ，b p eg i ，计算q = a b peg l ，这里a , b z ：是未知的整数。计算 d i 伍e - h e l l m a n 问题常简称为c d h 问题。 这里，将试图解决c d h 问题的概率多项式时间算法f 成功的概率定义为 s u c c _ c d o = p r a ( p , a p , b p , c p ) = 1 ：口，b e 足z ：】。 那么，c d h 问题假设，对于任何试图解决c d h 问题的概率多项式时间算法， 成功的概率砌群是可忽略的。 9 电子科技大学硕士学位论文 定义2 2 5 判定d i f f i e h e l l m a n 问题( d e c i s i o n a ld i f f i e - h e l l m a np r o b l e m ) - 对给 定的尸，叱b p , c p g l ，判断等式c = a b m o d q 是否成立，这里口，6 ，c z ：是未知的 整数。判定d i 伍e h e l l m a n 问题常被称为d d h 问题。 将试图解决d d h 问题的概率多项式时间算法，成功的概率优势定义为 a d v d d n 刊p r a ( p , a p ，6 尸 c 尸) = 1 - p r a ( p , a p , b p , a l p ) = 1 】：口，b ，c z i ：i d d h 问题假设，对于任何试图解决d d h 问题的概率多项式时间算法f ，成功的 概率优势a a v , 删4 是可忽略的。 上述三个困a , 难性问题的困难程度不一样。显然，如果能够计算d l 问题，那么 便能计算出c d h 问题和d d h 问题；如果能够计算出c d h 问题，d d h 问题也就 容易解决了。所以，c d h 问题比d d h 问题更难；d l 比c d h 问题更难。它们之 间的关系可以表示为： d l c d h d d h 其中a b 表示问题a 至少和问题b 一样困难。 一般来说，c d h 问题常被认为和d l 问题一样困难，但d d h 问题在群g l 上却 是容易解决的。理由如下： 设e ：g l g l - - g 是定义2 2 2 所描述的双线性对，且群g l 上的d l 问题和c d h 问题是困难的。令叱b p ，c p eg i 是群g i 中的任意元素，于是由双线性对的非退化 性有“尸，p ) 1 。又由双线性对的双线性性可得： e ( a p , b p ) = p ( p p ) 曲 e ( p ，c p ) = p ( 只p ) 。 所以， ( 2 3 ) ( 2 4 ) c 毫a b m o d q 营p ( 只p ) 曲= e ( p ，d 。营e ( a e , b p ) = d 只c p ) 显然，借助于双线性对，群g i 上的d d h 问题变得容易起来。因此，可以得到定义 2 2 6 所描述的g d h 群。 定义2 2 6 如果群g l 上的c d h 问题是困难的，而d d h 问题却是容易解决的， 则称群g i 为间隙d i f f i e - h e l l m a n 群( g a pd i f f i e h e l l m a n ) ，简称为g d h 群。 除了以上常见的难题外，还有很多其他不同类型的难题也被用于设计密码协 议： 定义2 2 7 弱d i f f i e h e l l m a n 问题( w - d h 问题) ：给定三元组( 尸，q ，其中 p ，q g i ，j z ：是未知整数，计算s q 。解决w - d h 问题的难度不高于c d h 问 1 0 第二章可否认认证协议及其相关理论介绍 题。 定义2 2 8c d h 逆问题( r c d h 问题) ：给定三元组( 尸，卯，p ) ，其中口，厂z ： 是未知整数，计算6 p ，使得c = r b m o d n ，b z ：。解决r c d h 问题的困难度与在g l 上的c d h 问题困难度相当。 定义2 2 9 ( 七+ 1 ) 指数问题( ( 七+ 1 ) - e p ) ：对给定的( k + 1 ) 元组 ( 只妃y 2 p ，j ，p ) ，其中y z ：是未知整数，计算y h l p 。( k + 1 ) - e p 问题的困难 性不高于c d h 问题。 定义2 2 1 0k - d i f f i 争h e l l m a n 转置问题( k d i f f i e - h d l m a ni n v e r s i o n 问题) ： 对给定的( k + 1 ) 元组( p ，皿y 2 p ，y p ) ，其中j ，z ：是未知整数，计算 ! p 。 y k - d h i 问题的困难性与( 忌+ 1 ) e p 问题的困难性相当。 定义2 2 1 1k - 强d i f f i e - h e l l m a n 问题( k - s d h 问题) ：对给定的( 七十1 ) 元组 ( 尸，皿y 2 只，y p ) ，其中ye 瓦是未知整数，计算二元组 ( c ，l _ p ) ，c z ：。 c y k - s d h 问题实际上是k d h i 问题的一个加强版本。当c 被预先指定时，k - s d h 问 题与k - d h i 相当。 定义2 2 1 2k - c a a 问题( c o l l u s i o n a t t a c k a l g o r i t h mw i t hk - t r a i t o r s ) - 对给定的 元组 ( 只矾肛z o 赤南p ) , y e z ：，计算专p ， 其中h 盛 j l l ，) 。k - c a a 问题的困难性强度与( k - 1 ) 一d h i 问题相当。 除了上述1 0 类d i f f i e - h d l m a n 问题外，还有g i 上的l m a n yd i f f i e h c l l m a n 、 c h o s e n t a r g e tc d h 问题和c h o s e n - t a r g e t i n v e r s i o nc d h 问题等等。在这里，本文 不再赘述，有兴趣的读者可以翻阅文献 3 6 1 。 2 2 2 2 双线性d i 伍e - h e l l m a l l 问题 引入双线性对之后，文献 3 7 】讨论了一种新的类型的困难性问题，称之为双线 性d i 伍e - h e l l m a n 问题。 定义2 2 1 3 双线性d i f f i e - h e l l m a n 问题( b i l i n e a rd i f f i e h e l l m a np r o b l e m ， 电子科技大学硕士学位论文 b d h 问题) ：给定尸护，b p ，c p g l ，计算d 只p ) 咖，这里口，b ，c z ：是未知的整数。 双线性d i f f i e h e l l m a n 问题常常简称b d h 问题。 b d h 问题的困难性不高于c d h 问题，理由是： 首先，如果群g i 上的c d h 问题是可计算的，比如由叱卯可计算出q = a b p ， 那么d 9 c p ) = e ( a b p , c p ) = d p ，p ) 出，这样就解决了一例b d h 问题，所以说b d h 问题不会比群g l 上的c d h 问题更难。 其次，b d h 问题还依赖于g 0 上c d h 问题的困难性，设p ( 尸 竹= h ，那么有以 下等式 e ( p ，= h 4 e ( b