（计算机应用技术专业论文）电子投票协议的研究.pdf

原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：碣j 茧j 丑3 一 e t 期：鳘坠坠豆三苎 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在 论文作者签名： 山东大学硕士学位论文 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 研究背景1 1 2 本文的主要工作2 1 3 本文的组织安排3 第二章电子投票相关的理论研究5 2 1 电子投票的研究现状i 5 2 2 电子投票面临哪些困难5 2 3 安全电子投票协议应具有的性质7 2 4 基础性问题与假设8 2 5 具有同态性质的加密体制1 1 2 6 门限加密系统1 2 2 7 u c 模型1 3 2 8 本章小结1 6 第三章u c 安全的两候选人电子投票协议1 7 3 1 理想功能函数1 7 3 2 电子投票方案u c - e v 1 9 3 3u c - e v 协议安全性证明2 2 3 4 本章小结2 5 第四章基于b i t 分解的电子投票协议2 7 4 1b i t 分解协议及其相关子协议2 7 4 2 协议构成2 9 4 3 安全性分析3 2 4 4 效率分析3 3 4 5 本章小结3 3 山东大学硕士学位论文 第五章电子投票系统展望与总结3 5 参考文献3 6 致 射4 1 攻读学位期间发表的主要学术论文4 2 攻读学位期间参与科研项目情况4 3 山东大学硕士学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti nn g l i s h 一 c h a p t e r1i n t r o d u c t i o n 1 1 1b a c k g r o u n do f r e s e a r c h 1 1 2c o n t r i b u t i o n s 2 1 3o r g n i z a t i o n 3 c h a p t e r2t h e o r ya b o u te v o t i n g 5 2 1s t a t u so f r e s e a r c ha b o u te v o t i n g 5 2 2w h a tm a k e sv o t i n gs oh a r d ? 5 2 3n a t u r eo f e v o t i n g 7 2 ，4b 雒i cp r o b l e ma n da s s u m e 8 2 5h o m o m o r p h i cp u b l i c k e ye b c r y p t i o n 1 1 2 6t h r e s h o l ep u b l i c k e yc r y p t o s y s t e m s 1 2 2 7u cm o d u l e 1 3 2 8b r i e fs u m m a r y 1 6 c h a p t e r3t w o c a n d i d a t e se v o t i o n gp r o t o c o l sb a s e do nu c 1 7 3 1i d e a lf u n c i t o n 1 7 3 2u c e - v o t i n g 1 9 3 3s e c u r i t yp r o v e 2 2 3 4b r i e f s u m m a r y 2 5 c h a p t e r4e - v o t i n gb a s e do nb i t - d e c o m p o s i t i o n 2 7 4 1b i t d e c o m p o s i t i o na n ds u b p r o t o c o l 2 7 4 2c o n s t i t u e so f p r o t o c o l 2 9 4 3a n a l y s i so fs e c u r i t y - 3 2 4 4a n a l y s i so f e f f i c i e n t 3 3 4 5b r i e f s u m m a r y 3 3 c h a p t e r5s u m m a r ya n do u t l o o k 3 5 山东大学硕士学位论文 r e f e r e n c e s 3 6 a c k n o w l e d g e m e n t 4 1 p a p e r sp u b l i s h e d 4 2 p r o j e c t sa n dr e s e a r c hw o r k s 4 3 山东大学硕士学位论文 摘要 随着网络的迅速发展和应用，人类己逐步进入信息社会，信息作为一种重要 的资源，在社会生产生活中的作用越来越重要。电子投票也正是信息化的产物， 其已成为电子商务、电子政务的一个重要组成。虽然目前电子投票方式还存在很 多的不足，但是从长远来看，电子投票由于其快捷方便并且可提供更高的安全性 的特点必将取代传统的投票方式。 传统的电子投票协议大都采用零知识证明来验证选票的合法性，由于零知识 证明过程效率很低，极大的制约了选举的效率，并不适用于全国性大选这样的大 规模选举，因此本文主要围绕无需零知识证明的电子投票系统展开研究。 首先，本文系统介绍了电子投票的基本概念及原理，概述其发展过程和研究 进展，对电子投票中所用到的基本的技术进行了介绍。 其次，随着电子投票协议研究的进展，安全的电子投票协议所要满足的条件 越来越多。这样导致设计者必须按照所有的安全性质逐条地设计协议，如此设计 是困难和复杂的。所幸的是，r a nc a n e t t i 提出了u c 安全的概念。u c 框架为协 议的设计提供了模块化的方式。本文利用数论中模数的性质构造了，具有u c 安 全的两候选人电子投票协议。在u c 的框架下采用一种新的编码手段以达到无需 零知识证明即可验证选票的合法性，并利用基于身份的( 刀，刀) 门限加解密以及双 线性对来实现多个计票中心联合计票的多候选人选举方案。 第三，本文基于多方安全计算中的b i t 分解协议构造了，无需零知识证明多 候选人选举协议。i v a nd a m a r d 在2 0 0 6 年t c c 会议中首次提出了b i t 分解的概 念，作为安全多方计算的一个典型应用，通过高性能服务器的合作将比特串的加 密值分解成其对应每一位的加密值，因此利用该协议对重新编码后的选票进行分 解得到其对应候选人的选票，再通过同态加密运算即可得到选举结果，通过上述 手段将大量选票分解统计工作交给高性能服务器完成，可极大提高选举效率，适 用于全国大选等大规模的选举。 关键词：u c 安全；零知识证明；b i t 分解；同态加密；电子投票 v e r i f yt h el e g i t i m a c yo fv o t e s w h i l et h el o we f f i c i e n c yo ft h ez e r o - k n o w l e d g ep r o o f p r o c e s se f f i c i e n c yg r e a t l yr e s t r i c t e dt h ee f f i c i e n c yo ft h ee l e c t i o n ，s oi td o e sn o ta p p l y t oal a r g e - s c a l en a t i o n a le l e c t i o n t h ef o c u so ft h i sa r t i c l ei se l e c t r o n i cv o t i n gs y s t e m w i t h o u tz e r o k n o w l e 电ep r o o f f i r s t , i nt h i sa r t i c l e ，i ti sd e s c r i b e dt h a tt h ee l e c t r o n i cv o t i n gp r o t o c o l ，t h eb a s i c c o n c e p t sa n dp r i n c i p l e s ，a no v e r v i e wo fi t sd e v e l o p m e n tp r o c e s sa n dt h e b a s i c t e c h n o l o g y s e c o n d ，w i t ht h ep r o g r e s so ft h ee - v o t i n gp r o t o c o l ss t u d y , t h ec o n d i t i o n so fs e c u r e e l e c t r o n i cv o t i n gp r o t o c o l sw e r e p r o p s e dm o r ea n dm o r e ，s ot h ed e s i g n e r sm u s tf o l l o w a l lt h es e c u r i t yn a t u r e so ft h ed e s i g no ft h ep r o t o c o l s ，i nt h i sw a yt h ed e s i g ni sm o r e d i f f i c u l ta n dc o m p l e xt h a nb e f o r e f o r t u n a t e l y , r a nc a n e t t ip r o p o s e du c c o n c e p t i n u cf r a m e w o r k ，t h ed e s i g no fp r o t o c o li si nam o d u l a ra p p r o a c h i nt h i sp a p e r , a l l e l e c t r o n i cv o t i n gp r o t o c o l 、析t ht w oc a n d i d a t e sw a s p r o p o s e db a s e do nt h en a t u r eo f m o d u l u si nn u m b e rt h e o r y i nt h eu cf r a m e w o r kw ea d o p tan e wc o d et ov e r i f yt h e l e g i t i m a c yo fv o t e sw i t h o u tz e r o - k n o w l e 如ep r o o fa n du s ei d e n t i t y - b a s e d 伽，力) t h r e s h o l de n c r y p t i o na n dd e c r y p t i o n ，a sw e l la sb i - l i n e a rt oa c h i e v et h em u l t i p l e c o u n t i n go ft h ec e n t e rf o rc o u n t i n go ft h em u l t i - c a n d i d a t ee l e c t o r a ls c h e m e t h i r d , b a s e do nb i td e c o m p o s i t i o np r o t o c o l ，aw i t h o u tz e r 0 一k n o w l e 电ep r o o f 山东大学硕士学位论文 m u l t i - c a n d i d a t ee l e c t i o np r o t o c o lw a sp r o p o s e d i n2 0 0 6t c cb i td e c o m p o s i t i o nw a s f i r s tp r o p o s e db yi v a nd a m a r da sat y p i c a l a p p l i c a t i o no fs e c u r em u l t i p a r t y c o m p u t a t i o n b yt h ec o o p e r a t i o no fh i g h p e r f 6 r m a n c es e w e r , t h ee n c r y p t i o nb i ts t r i n g v a l u eo f e a c ho n eb r o k e nd o w ni n t oi t sc o r r e s p o n d i n ge n c r y p t e dv a l u e ，w h i c hi su s e d t od e c o m p o s et h er e e n c o d e dt h ev o t e si n t ot h ev o t e st h ec a n d i d a t e s b yt h e i r c o u n t e r p a r t s a n dt h e nt h r o u g ht h eh o m o m o r p h i ce n c r y p t i o na l g o r i t h mw i t ht h es t a t e e l e c t i o nr e s u l t sc a nb e o b t a i n e d u s i n ga b o v e m e n t i o n e dm e a s u r e st h a tt h e h i g h 。p e r f o r m a n c es e r v e ri su s e dt od e c o m p o s eal a r g en u m b e ro fv o t e sa n dc o m p l e t e t h es t a t i s t i c a lw o r kc a nb eg r e a t l yi m p r o v et h ee f f i c i e n c yo ft h ee l e c t i o n sf o rt h e n a t i o n a le l e c t i o n ，o ra n o t h e r l a r g e - s c a l ee l e c t i o n k e y w o r d s ：u o ；z e r o k n o w l e d g ep r o o f ；b i td e o o m p o s i t i o n ：h o m o m o r p b i o e n o r y p t i o r l ：e - v o t i n g i l l 山东大学硕士学位论文 1 1 研究背景 第一章绪论 随着网络的迅速发展和应用，人类已逐步进入信息社会，信息作为一种重要 的资源，在社会生产生活中的作用越来越重要。电子投票已成为电子商务、电子 政务的一个重要组成。 想象一下【l 】，通过电脑登录网络链接到您自己的私人电脑，轻点几下鼠标， 您就可以行使宪法赋予您的权利，为大选投下选票。如果能避开寻找投票站的麻 烦，免受排队之苦，选民的参与度会提高吗? 我们何时能看到这样的系统成为现 实呢? 通过互联网投票只是电子投票( e v o t i n g ) 的一种。一般来说，电子投票指以 电子方式进行投票，也指通过电子方式统计票数。按照这个定义，目前在美国使 用的多种投票方式已经是电子投票了。比如，打孔卡和光学扫描卡就是通过电子 手段计票的，它们已经被使用了几十年。 由于2 0 0 0 年美国总统大选出现的打孔计票争议【2 1 ，使人们认识到必须开始关 注电子投票箱的完善使用，以提高电子投票的安全准确性和投票效率。并于2 0 0 2 年1 0 月通过“协助美国投票法案h a 、，a ( t h eh e l p a m e r i c a v o t e a c t ) ”。拨款3 8 亿 美元用于升级全美的投票系统。2 0 0 6 年【3 1 ，美国中期大选采用电子投票方式，采 用了电子投票的最新应用是d r e ( d i r e c tr e c o r d i n ge l e c t r o n i c ，直接记录电子投票 机) 系统和网络投票。d r e 系统是一种与大众直接互动的电子系统。当然，这些 新系统同时也受到了很多批评和监督。但仍被专家称为最失败的i t 计划，这次失 败也足以让人们更加认真地思考电子投票的存在的困难和问题，也引起学者对于 电子投票更广泛的关注和思考。 这里我们以2 0 0 6 年美国选举为例介绍一下电子投票系统的应用，我们首先 要简单了解一下选举的管理情况。在美国，各州会对所有选举进行监督，甚至包 括联邦选举。这种权力下放的原因主要在于选民的规模。根据美国选举数据服务 公司( e l e c t i o nd a t as e r v i c e s ) 的数据，美国登记在册的选民超过1 7 亿人。对数目 如此巨大的选民进行协调、帮助并统计选票的难度之大，可想而知。您要是真正 山东大学硕士学位论文 看到实际的工作量，就会意识到集中投票制是不现实的。在总统大选时，您要 在投票时间内到当地的投票站完成投票。在投票前，投票站里的地方选举工作人 员或者志愿者会先核实您的注册选民身份。投票结束后，选举工作人员会将选票 收集到一起，并将它们送到集中计票站点。在那里工作人员们将统计选票，然后 对外报告结果。 面对如此大规模、如此重要的的选举，关于电子投票技术的争论的核心仍是 进行电子选举的软件和硬件的安全问题。不仅仅技术领域，从电子投票系统是否 能正确地记票，到制造这些设备的外国公司是否值得信赖，也都是人们关注的问 题。 1 2 本文的主要工作 本课题关注于电子投票系统的理论研究，以提高电子投票系统的安全性和效 率为根本出发点。从美国大选来看，安全隐患有可能不是最主要的问题，效率将 成为掣肘大选的主要因素。 由于以往的电子投票系统所采用的协议，投票者都需要通过零知识证明来向 验证者证明选票的合法性。然而零知识证明过程复杂，极大的降低了电子投票的 效率，尤其是遇到总统大选、领导换届等大规模选举发生时，显得效率过低，不 能适用于该类大规模选举。 随着电子投票协议研究的进展，安全的电子投票协议所要满足的条件越来越 多。这样导致设计者必须按照所有的安全性质逐条地设计协议，如此设计是很困 难和复杂的。2 0 0 1 年r a nc a n c t t i 提出t u c 安全的概念【2 2 1 给电子投票系统的模块 化设计带来了福音，然而在2 0 0 8 年，m a n o jp r a b h a k a r a n 等人证明了零知识和比 特承诺是不具备u c 安全特性的【3 5 1 。这也就说明要设计具有u c 安全的电子投票协 议就不能使用零知识证明。并且近些年多方安全计算研究的不断深入，也为电子 投票理论研究提供了基础，利用多方安全计算中的b i t 分解协议便可高效的构造 电子投票协议。 本课题正是对基于上述问题对电子投票协议进行了深入研究，提出了几个更 好的解决方案。本文的工作及创新之处： ( 1 ) 对电子投票系统进行了综述。 2 也 夕 哥 - 1 l i 双 山东大学硕士学位论文 介绍了电子投票协议的发展过程和最新研究成果： 介绍了电子投票协议设计中面临的难题； 给出了设计一个安全电子投票协议所需要的密码学基础知识。 ( 2 ) 重点研究了u c 模型下的电子投票协议，提出了具有u c 安全的两候选人电子 投票协议。 介绍了u c 安全的相关知识； 设计了电子投票的理想功能函数； 提出了一个具有u c 安全的两候选人电子投票协议，新协议的特点： 使用较为简单的方法实现选票验证性； 采用了具有同态性质的门限广播加密方案； 进行了较为充分的安全性分析，并给出了u c 安全证明； 效率有了很大程度的提高。 ( 3 ) 利用安全多方计算中的b i t 分解协议，构造了无需零知识证明的多候选人电子 投票协议。 介绍了b i t 分解协议的发展及其相关子协议； 提出了一个新的无需零知识证明的多候选人电子投票协议，新协议的特点： 投票者无需采用零知识证明来证明选票的合法性； 选举过程主要工作都通过用于选票分解的高性能服务器来完成； 采用p a i l l i e r 同态加密来实现选票的计算； 在效率方面与以往协议进行了比较。 1 3 本文的组织安排 本文包括五个章节。 第二章，对电子投票系统进行了较为全面的理论综述，并对电子投票协议中 需要用到的密码学手段进行了分析描述； 第三章，对基于u c 安全模型的电子投票协议进行研究，并提出了一个具有 u c 安全的两候选人电子投票协议： 第四章，利用安全多方计算中的b i t 分解协议，构造了无需零知识证明的多 候选人电子投票协议； 山东大学硕士学位论文 第五章，对整个工作进行了总结并对进一步的研究工作进行了展望。 4 1 山东大学硕士学位论文 第二章电子投票相关的理论研究 2 1 电子投票的研究现状 1 9 8 1 年，c h a u m 4 1 明确提出了基于公钥密码的电子邮件概念，它也是电子投 票的雏形，它以各种密码学技术为理论基础，通过计算机和网络来完成投票的整 个过程。随后，j o s h 5 1 ，m a g k o s t 6 1 ，c r a n o r 7 1 分别着手实现了保密、无收据性和安 全实用的投票方案。1 9 8 5 年，j o s h 5 1 提出了电子选举的概念。1 9 9 4 年，b e n a l o h t 8 1 引入了电子投票的无收据性。1 9 9 7 年，c r a n o r 9 1 设计并完成了一个能用于因特网 的投票协议s e n s u s 。2 0 0 0 年，m a r t i n i l 0 1 指出，b e n a l o h 方案只有在一个监票机构 的情况下才具有无收据性。同年，l e e 1 1 1 提出了真正具有无收据性的电子投票方 案，他引入了诚实的监票人，是建立在监票人完全可信的基础之上的。2 0 0 3 年， 陈晓峰等人提出了一种基于半信任模型的电子投票方案1 3 】，在l e e 方案【1 1 】的基础 上引入多个监票人。2 0 0 3 年b u r m e s t e r 1 4 1 、l a m b r i n o u d a k i s t ”】中详细介绍了安全 电子投票应该具有的7 中安全属性，秘密性、唯一性、公平性、稳固性、完整性、 无收据性、广义可验证性。2 0 0 6 年b e na d i d a t l 6 】在其博士论文中则详述了采用密 码技术构造投票系统所面临的难题和大多采用的技术手段。同年，b e na d i d a 、 r i v e s 构造了一个具有最小花费和复杂度的电子投票方案【1 7 】 2 2 电子投票面临哪些困难 为了说明电子投票的困难性 1 6 1 ，先做如下假设： ( 1 ) a l i c e 和a d r i e n n e 是两个投票者。 ( 2 ) c a r l 是一个试图控制、影响a l i c e 的攻击者。 ( 3 ) b l u e 和r e d 是两个候选人。 a l i c e 想要将选票投给b l u e ，a d r i e n n e 想要将选票投给r e d 。c a r l 试图干扰 a l i c e 让其将选票投给r e d ，从而干扰选举。 山东大学硕士学位论文 2 2 1 可验证性v s 安全性 在电子投票中，存在一对固有冲突那就是可验证性和安全性。一方面，a l i c e 想要验证整个投票过程正确的执行，其选票正确的投给了b l u e 。但是，如果a l i c e 能够从选举过程中获得足够的信息向c a d 证明其选票准确投给b l u e 还是r e d ， 这样就会产生买卖选票的欺骗行为，c a r l 可以用钱收买a l i c e 的选票使其投给 r e d ，从而影响选举。 因此，在理想电子投票系统中，a l i c e 能获得足够的信息来个人验证选票确 实投给b l u e ，但a l i c e 不能向c a j l 证明其选票投给了谁。更准确的说，如果a l i c e 将选票投给b l u e ，a d r i e n n e 将选票投给r e d ，a l i c e 和a d r i e n n e 都会收到相应信 息确保他们的选票正确的投出并且参与最终计票。并且他们都会告知c a r l 将选 票投给了r e d ，其中a l i c e 在撒谎，a d r i e n n e 是诚实的，然而c a r l 无法辨别谁的 信息是诚实的，谁的信息是虚假的。这样c a d 也不会去够买选票，因为他并不 能正确判断其投资是否真具有价值。 2 2 2 攻击者 t ， - 以美国大选为例，2 0 0 4 年总统选举预算接近1 0 亿美元，此时攻击并控制投 票机将是最有效的手段。在如此巨大的资金投入下，任何选举参与者都可能成为 攻击者，任何选举系统的管理者也都有可能成为攻击者。 选举系统就如同银行系统一样，完全置于最恶劣的环境中，因此，考虑的攻 击者都将是主动攻击者，并且应考虑具有最强攻击能力的敌手模型。 攻击者的行为：一般对攻击者有以下几种分类： 按计算能力，划分为： 拥有无限计算能力的攻击者； u 只有多项式时间计算能力的攻击者。 一个协议如果对于拥有无限计算能力的攻击者而言是安全的，则称为是信息 一 论安全的或无条件安全的；如果对于拥有多项式计算能力的攻击者是安全的，则 称为是密码学安全的或条件安全的。 根据攻击者对参与者的控制程度，攻击者可分为： 被动攻击者； 6 纽 - 强 山东大学硕士学位论文 主动攻击者。 被动攻击者只是窃听参与者的输入输出，但是参与者还是照协议所规定的程 序执行规定的动作。主动攻击者则不仅窃听恶意参与者的输入输出，还要控制参 与者按照自己设计的方式参与协议，我们可以简单地把此时受控制的参与者看成 是攻击者本身，因为受控制的参与者只是一个傀儡。 根据攻击者买通参与者的时间点，攻击者可分为： 静态攻击者： 动态攻击者。 如果攻击者在协议一开始就确定买通任意的组参与者( 数量是有一定限制 的) 作为恶意参与者，在协议执行以后就不改变了，则称这种攻击者是静态攻击 者。如果攻击者不是在协议执行之前就确定他要买通的参与者，而是在协议执行 中根据协议的执行情况来决定买通那个参与者，这种攻击者称为动态攻击者。当 然，动态攻击者能够买通的参与者的总数是有一定限制的，也就是说协议中的恶 意参与者的数量是有一定限制的。 对于电子选举系统，本文考虑多项式时间的、主动的、动态的攻击者。 2 3 安全电子投票协议应具有的性质 秘密性：除投票者自己以外，选票的内容其他人无法得知。 公平性：在选举的中间过程，任何人的行为都无法影响选举的结果。 无收据性：任何人都无法将一张选票和某一投票者联系起来。 唯一性：只有有资格的人能提交一张合法的选票，冒充他人选举则一定能被 追踪到。 完整性：所有合法的选票都能被正确计入。 稳固性：不诚实的投票者不能破坏选举。 广义可验证性：选举的结果可以被检验，任何人无法伪造选举结果。广义的 可验证性可以使任何感兴趣的第三方参与检验，同时不泄露投票者的隐私。 山东大学硕士学位论文 2 4 基础性问题与假设 2 4 1 双线性映射( 双线性对) 双线性对最初用于密码攻击，被认为是对密码体系不利的，比如用w e l l 对的 m o v 攻击可以将超奇异椭圆曲线或超椭圆曲线上的离散对数问题归约为有限域 上的离散对数问题。直到2 0 0 0 年，j o u x 1 8 1 做出了突破性的工作，提出了一个基 于超奇异椭圆曲线上的双线性对的基于身份的d e f i e h e l l m a n 密钥协商协议。双线 性对在密码学上的积极作用被发现，此后双线性对的大量应用相继提出。 g 和q 是p 阶循环群，p 为大素数，g 是群g 的生成元，e 是一个双线性映 射e g x g 专q 。两个群之间的双线性映射应该满足下面的属性： ( 1 ) 双线性：对所有的甜，1 ，g ，口，b z ，有p 4 ，矿) = e ( u ，d 西 ( 2 ) 非退化性：e ( g ，g ) l ( 3 ) 可计算性：对于任何p ，o g ，存在有效的算法计算e ( p ，q ) 如果存在群q 和一个可有效计算的上述双线性映射p ：g x g g ，则g 是 一个双线性群。p 是对称的，因为p ( 9 4 ，9 6 ) = e ( g ，g ) 曲= f ( 矿，9 4 ) 。 对于素数阶群g ，使用g 表示g 1 g ) 集合，其中l g 是g 的代表元素。 利用超奇异椭圆曲线或超椭圆曲线上的w e i l 对和t a t e 对可以构造出满足以 上条件的双线性对。 2 4 2 判定性d j 什i e h o ii m a n ( d d h ) 问题 群g 上的d d h 问题就是区分元组 和 ，其中 口，b , c 从z ：中随机选取，g b k g 。中随机选取。j o u x a n d n g u y e n 在文献1 中指出 ， g 上的d d h 是易解的，因为对于给定的尸，舻，卯，c p g 有： c = a b m o d q e ( g ，g 。) = p ( 9 4 ，g b ) 。 i “ 山东大学硕士学位论文 2 4 3 计算性0 i 仟i a h e li m a n ( o o h ) 问题 群g 上的c d h 问题是对于给定的随机的元组 ，计算出g 曲。j o u x 和n g u y e n 在文献【1 9 1 中指出群g 上的c d h 是难解的，虽然d d h 是易解的。 2 4 4 双线性d i 仟i e _ h e li i n ( b d h ) 假设 群g 上的b d h 问题是：对于给定的元组g ，g a9 9 bg 。g 作为输入，输出 e ( g ，g ) 咖q 。 如果一个算法a 在解决g 上的b d h 问题时满足下面的关系，则该算法有优 势s ：p r a ( g ，9 4 ，g bg 。) = p ( g ，g ) 口6 。】s 其中生成元g 吒g ，a , b ，c 乙。 类似地，如果一个输出b 0 ，1 ) 的算法b 在解决g 上的判定性b d h 问题时 满足下面的关系，则该算法有优势s ： p r b ( g ，g a9 6 ，g 。，p ( g ，g ) 4 如) = o 】一p r 【召( g ，9 4 ，g b , g 。，丁) = o 】i 占 其中生成元g g ，a , b ，c 乙，r 吒q 。 如果在解决g 上的( 判定性) b d h 问题时，不存在t 时间的算法有至少为s 的 优势，则称( 判定性) ( f ，占) 一b d h 假设成立。 2 4 5 双线性d i f f i e h e ii m a n 置换( q - b d h i ) 假设 群g 上的g b d h i 问题定义如下：对于给定( q + 1 ) 阶元组 ( g ，g x , g ( a ，g 一) ( g ) 州作为输入，计算e ( g ，g ) q 。 如果一个算法a 在解决g 上的g b d h i 问题时满足下面的关系，则该算法有 优势占：p r a ( g ，g 。，g ，) = e ( g ，g ) 1 7 。】5 其中生成元g g 。，x r 乙。 9 山东大学硕士学位论文 类似地，如果一个输出b 0 , 1 的算法曰在解决g 上的判定性g - b d h i 问题时 满足下面的关系，则该算法有优势占： i p r 【b ( g ，g 。，g ( 妒) ，p ( g ，g ) 1 h ) = o 】一p r b ( g ，g 。，g ( 妒) = o 】i 占 其中生成元g rg 。，x r 乙，t rg r 。 如果在解决g 上的( 判定性) g b d h i 问题时，不存在f 时间的算法有至少为占 的优势，则称( 判定性) ( f ，g ，s ) b d h i 假设成立。 2 4 6 双线性d i 仟i e - h e ii m a n 指数( q - b d h e ) 假设 群g 上的q b d h e 问题定义如下：对于给定的2 q + 1 个元素的向量： ( g ，g ，g 。，g ( “h ，g ( 扪，g 扩“，g ( a 2 9 ) g 2 p 1 作为输入， 计算输出 e ( g ，g ) q 。 由于在给定的向量中缺少g ( 项，所以双线性映射对于计算e ( g ，g ) 口科无任 何帮助。 如果一个算法彳在解决g 上的g b d h e 问题时满足下面的关系，则该算法有 优势占：p r a ( g ，g ，旷，g ( 扪，g ( ) ，g ( x 2 4 ) = p ( g ( ) ，g ) 】s 其中生成元g g 。，x r 乙。 类似地，如果一个输出b 0 ，1 的算法b 在解决g 上的判定性g - b d h e 问题 时满足下面的关系，则该算法有优势占： i p r 【b ( g 。，g ，g 。，g ( 扪，g ( 艄，g ( 奶，p ( 黜) ) = o 卜p r 【b ( g ，g ，g 。，g ( 川，g ( 艄，g ( 一，r ) = o 牡s 其中生成元g 吒g ，x 吒z 口，t rq 。 如果在解决g 上的( 判定性) q - b d h e 问题时，不存在t 时间的算法有至少 为s 的优势，则称( 判定性) ( f ，g ，g ) - b d h e 假设成立。 山东大学硕士学位论文 i mii_ii i_ii 2 4 7 h a s h 函数 h a s h 函数在密码学领域中担当着十分重要的角色，很多情况下，我们需要通 过它实现加密、签名等系统的安全性。 h a s h 函数是将一串可变长的输入串转换成固定长度输出串的函数。在密码学 上，除了要求h a s h 函数的映射容易外，还要满足以下一些性质： ( 1 ) 单向性：给定一个c ，很难找到一个z ，使得日( z ) = c 。 ( 2 ) 抗碰撞性：给定一个c ，很难找到一个l = x ，使得日( 功= t t ( x ) 。 ( 3 ) 强抗碰撞性：很难找到一对( x ，) ，z 一，使得h ( x ) = 日( ) 。 2 5 具有同态性质的加密体制 r s a 未作任何处理的r s a 2 0 1 ，其加密过程可描述为c = 柳。m o d n 。显然， c o q = ( m 0 铂) 。m o d n ，满足( ，) 同态运算。然而未加工的r s a 不满足i n d - c p a 安全，因此在很多应用中无法直接应用。r s a o a e p 应用于多种场合，但由于非 延展性的o a e p 添加，使其失去了同态特性。 e i g a m a l 在e 1 g a r n a l 体制中，密文可表示为c = ( 9 7 ，m y 7 ) 。因此，我们定 义。作为密文间的运算符，那么e 1 g a m a l 体制满足( ， ) 同态： ( g ，m a y 5 ) o ( g 吃，m 2 y 哇) = ( 9 5 + 屹，( 朋1 m 2 ) y + 屹) e 1 g a m a l 体制的特性表明，其具有同态特性，并且具有i n d c p a 安全。 指数e 1 g a m a l 体制的执行过程如下： 密钥生成阶段：选择一个大素数p ，使得p = 2 q + 1 ( q 为一大素数) 。选择z ： 的q 阶子群的生成元g 。m 加= 乙，睹= z ( x 为z ：中的一个随机数) ， p k = y = g xr o o d p 。 加密阶段：选择一个随机数，并利用公钥础加密得 厶伽；，) = ，) = ( g ，g ”y 7 ) m o d p 。 山东大学硕士学位论文 解密阶段：巩 ，力= l o g s l f “ bj l m o d p 加同态运算：靠( 铂；，i ) 靠伽：；，2 ) = ( 9 1 ，g y 4 ) ( g 吃，g 耽y 吃) = ( g t i + r 2 ，g 愧y ”吃) = 靠( m + 彤2 ；巧+ 吃) p a i l l i e r 基于计算和判断z ：上的力次剩余问题的困难性假设，p p a i l l i e r 在 1 9 9 9 年亚洲密码会议上提出了一种抵抗c c a 2 攻击的密码体制【2 1 】。p a i l l i e r 3 j l ：l 密体 制的密文可表示为c = g ，m o d n 2 。显然，这种体制满足乙上的( + ，) 同态性， 号础( 铂；) 号加( 朋：；，2 ) = ( g 一”) ( g ”2 巧) = g 啦( ，i 吃) ” = ( 铂+ ；，i 吃) p a i l l i e r 体制执行过程如下： 密钥生成阶段：n = p q 是r s a 模数，g 乙，五= l c m ( p 一1 ，q 一1 ) 。肚= 以，g ， s k = a 。 加密过程：m 乙是待加密的消息。随机选取，艺，加密得 解密过程： 气( m ；，) = c = g m ，- ”m o d n 2 驰) = 描 其中，( x ) ：_ x - - 1 ；x 乙：，且z 三1 m o d 刀。 刀 ” 2 6f - j 限加密系统 当一个面向团体或组织的密码系统被采用时，需要