（概率论与数理统计专业论文）基于同态加密的安全电子投票方案.pdf

摘要 摘要 电子投票是现代网络技术发展的产物，安全电子投票是密码学技术的一个重 要的应用，并且是未来选举系统发展的方向本文提出了一个基于同态加密技术 的电子投票方案方案的安全性主要基于e l g 锄a l 门限密码系统的可再加密性和 同态性方案满足合格性，保密性，正确性，公平性，投票者可验证性，普遍可验证 性，健壮性等重要的安全性质以及无收据性和抗强迫性，有效的防止了贿选和抵 抗了强迫投票人的攻击方案设计了“信任状生成器”和“选票处理器”，使投票委员 会掌握的秘密和权利降至很低，并且完全出于公共的监督之下；没有使用级别较 高但较难实现的不可窃听信道，在不损害安全性的情况下提高了实用性，从而实 现了互联网上的安全电子投票 关键词电子投票，同态加密，e 1 g a m a l 密码系统，抗强迫性 a b s t r a c t a b s t r a c t s e c u r ee l e c t r o n i cv o t i n gi so n eo ft h em o s ts i g n i f i c a n ta p p l i c a t i o n so fc r y p t o g r a p h y a n dt h ed i r e c t i o no fe l e c t i o ns y s t e md e v e l o p m e n ti nt h ef u t u r e ，s i n c ee l e c t r o n i cv o t i n g i sam e t h o db a s e do nm o d e mn e t w o r kt e c h n o l o g y w ep r o p o s ea s e c u r ee l e c t r o n i cv o t - i n gs c h e m eb a s e do nh o m o m o r p h i ce n c r y p t i o n t h es e c u r i t yo ft h es c h e m ei sm a i n l y b a s e do nt h eh o m o m o r p h i cp r o p e r t ya n dr e - e n c r y p t a b i l i t yo fe 1 g a m a lc r y p t o s y s t e m w i t ht h r e s h o l dd e c r y p t i o np r o t o c 0 1 t h es c h e m es a t i s f i e ss i g n i f i c a n ts e c u r i t yp r o p e r t i e s i n c l u d i n ge l i g i b i l i t y ，p r i v a c y , c o r r e c t n e s s ，f a i r n e s s ，v o t e rv e r i f i a b i l i t y , u n i v e r s a lv e r i f i - a b i l i t y , r o b u s t n e s sa n dr e c e i p t f r e e n e s s ，c o e r c i o n - r e s i s t a n c ew h i c hc a nr e s i s tt h ev o t e b u y i n ga n d v o t e rc o e r c i o n t h es c h e m ed e s i g n sc r e d e n f i f lg e n e r a t i o nd e v i c ea n db a l l o t p r o c e s s i n gd e v i c e ，i no r d e rt or e d u c et h es e c r e ta n dp o w e r w h i c ht h ev o t i n gc o m m i s s i o nh o l d s ，a n dm a k et h ec o m m i s s i o nb eu n d e rs u r v e i l l a n c eo ft h ec o m m o n s ；d o e s n o t u s et h eu n t a p p a b l ec h a n n e lw h i c hi si n f e a s i b l ei nt h er e a lw o r l d ，e n h a n c e sp r a c t i c a l i t y w i t h o u tb r e a k i n gt h es e c u r i t yp r o p e r t i e s t h e n , s e c u r ee l e c t r o n i cv o t i n gv i ai n t e r n e ti s r e a l i z e d k e yw o r d s e l e c t r o n i cv o t i n g ，h o m o m o r p h i ce n c r y p t i o n ，e l g a m a lc r y p t o s y s - t e m ，c o e r c i o n - r e s i s t a n c e 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：鸯日同易 2 d d 吕年箩月筋日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 杏翮多 2 0 口2 年5 月甥日 第一章引言 第一章引言 1 1 研究意义 选举是民主政治的基石，是共和制度的前提，一个民主的国家必须有一套完 善的选举制度作保障，而这又需要由公正安全的投票系统来实现在日常工作生 活中，投票也无时无刻不在进行，对社会的民主进程起到了重要的作用 几百年来，尽管在规模方法内容上有一定的差异，世界上的各种投票基本上都 是通过我们常见的投交纸质选票的形式完成的然而，随着社会的发展，这种投票 方式在实际进行过程中安全性和正确性方面都出现了很多的问题，而且暴露出效 率较低的缺陷，往往浪费了大量的人力物力，2 0 0 0 年美国大选时佛罗里达州的重新 计票事件就是个很典型的例子 另一方面，随着计算机的发展和网络的普及，信息的传输变得异常的简单和便 利；电子邮件，手机短信等新兴的信息传输方式正逐渐取代传统的纸质品，使我们 进入了“无纸”时代将通常的投票电子化，在投票的各个阶段都会节省大量的人力 物力，并使正确性得到更好的保证；特别是密码学领域的发展更好的保证了电子 投票系统安全性因此，电子投票已经成为投票系统改进发展的方向和社会的迫 切需要，而对于电子投票的研究也有着越来越重要的意义 1 2 文章结构 本文将提出一个基于同态加密技术的电子投票方案，该方案实现了互联网上 的投票，没有使用不可窃听信道和投票屋等级别较高的物理设备，并且满足了合 格性，保密性，正确性，公平性，投票者可验证性，普遍可验证性，健壮性，无收据性 和抗强迫性等重要安全性质第二章介绍电子投票的历史与现状第三章介绍诚 实验证者零知识证明，同态加密，e 1 g a m a l 密码体制以及密钥分享等在方案中需要 用到的密码学知识第四章给出电子投票方案及方案中用到的相关证明协议第 五章分析方案的安全性，并对方案进行评价，改进和完善 第二章电子投票的历史与现状 第二章电子投票的历史与现状 2 1 电子投票的发展 历史上首个进行电子投票研究的人是美国的大发明家爱迪生，他在1 8 6 9 年研 制了一个“电子投票装置”，并获得了美国专利，他曾试图将这个装置推销给马萨诸 塞州的立法机构但最终没有成功直至u1 9 7 0 年，d r e ( d k e c tr e c o r d i n ge l e c t r o n i c ) 系 统首先应用于投票站，实现了计票器的电磁化储存1 9 9 7 年4 月，美国加州的一个县 首次试验了电子邮件投票系统v b m ( v o f i n gb ym i l l ) 第一个密码学意义上的投票协议是c h a u m 于1 9 8 1 年在【7 】中提出来的，该协议 利用公钥密码体制，基于混合网络( m i x n e t s ) 建立数字签名花名册，从而达到匿名 投票在这之后，1 9 8 5 年，c o h e nb e n a l o h 和m i c h a e lj f i s c h e r 在【1 3 1 提出了基于同 态加密的电子投票方案；1 9 9 2 年，a t s u s l l if u j i o k a 等人提出了适合大型选举的安全 投票方案【2 0 ，使基于这个方案的现实投票系统在非政府部门广泛使用；1 9 9 4 年， b e n f l o h 和t u i n s t r a 【6 】提出了电子投票的一个重要的性质一无收据性，使得电子投 票能更好的接近于实际，抵抗选举中的贿选者；【3 8 1 和【2 3 分别将基于盲签名和同 态加密的投票协议无收据化 进入新世纪，研究者们又在投票方案的各个方面进行了深入的研究近几年 来，由于贿选和选举中的政治强迫成为困扰现实选举的主要症结，有关无收据性 和抗强迫性的研究成为一个热点问题，文献【3 2 ，【2 7 】，【3 3 ，【2 】，【3 1 ，【2 6 】，【1 8 都 对这个问题进行了讨论，特别是【2 6 1 给出了这两个性质的确切定义，【1 8 1 n 用p i c f l c u l u s 【3 指出了它们的差别并给出了应用实例此外在其他方面，也有许多新的 方案提出：例如【2 】【3 0 1 对带有可写入选票的投票进行了讨论，【3 0 提出了向量选 票的方案，【4 5 】利用经济学中c l a r k et a x 原理提出了无需投票委员会的大型投票方 案，【3 5 提出了具有永久保密性的无收据普遍可验证投票方案，【1 5 】提出由投票人 控制匿名程度的方案，【1 0 】提出了利用可视加密【3 6 1 得到保密选票收据的方案等 在实际应用中，虽然技术还没有达到完全成熟，但在部分地区已经开始试验使 用电子投票：例如在日内瓦附近的居民已经能够通过国际互联网参力n 2 0 0 3 - - 0 4 年度 的瑞士的公民投票；而英国政府也宣布计划“将在2 0 0 6 年以后的某个时间”允许公 2 第二章电子投票的历史与现状 民进行电子投票电子投票取代目前的纸质投票将是社会发展的一个必然趋势 2 2 电子投票的参加者和相关工具 电子投票作为纸质投票的电子化，参加人员同普通的投票相似，由候选人，投 票人和投票委员会组成候选人事实上并不参加投票过程，但有可能成为贿选者 或强迫者投票人需要做的主要有：与投票委员会联系提交自己的有效身份，经投 票委员会验证通过后得到一张合法的选票，按照自己的意愿投出有效的一票给投 票委员会，获得委员会公布投票结果投票委员会根据安全性的要求，一般为一个 由亿个人组成的集合，主要负责：验证每个合法投票人的身份，向通过身份验证的 投票人发放选票，收集投票人投出的选票并执行计票，最后公布计票结果 电子投票用到的工具通常有一般通信信道，电子公告板( b u l l e t i nb o a r d ) 和投票 屋( v o t i n gb o o t h ) 在电子投票中所谓的选票实际上是一个或一组有意义的数据，选 票的收发以及投票人与投票委员会间的交互验证都是通过信道传送的，也可以说 整个投票过程是投票人与投票委员会通过信道传送信息并处理各自相关信息的过 程常用的信道主要有公共信道，匿名信道( a n o n y m o u s ) 和不可窃听( u n t a p p a b l e ) 信 道电子公告板是一种有存储能力的公共广播信道，所有通过电子公告板的通信都 是公开的，任何人包括被动的观察者都可以阅读，没有人可以擦除电子公告板上的 任何信息，但是每个主动的参加者可以在他的特定的区域增加信息匿名信道是为 达到安全性所使用的程度最弱的保密信道不可窃听信道是级别较高的物理设备， 它可以达到使所传递的信息对于发送方和接收方以外的任何方完全保密，但在实 际应用中较难达到投票屋的级别更高，类似于普通投票时所用的投票密室，对于 使用这个物理设备的投票者y 来说，只有y 可以同某一方进行交互的通信，而这些 通信对于所有的其他方是完善保密的 2 3 电子投票的一般过程及分类 电子投票的主要过程一般分为4 个阶段：初始化阶段( i n i t i a l i z a t i o ns t a g e ) ，投票 前阶段( p r e v o t i n gs t a g e ) ，投票阶段( v o t i n gs t a g e ) ，计票阶段( t a l l y i n gs t a g e ) 初始化 阶段主要是由系统生成一些重要的参数和一些相关的公钥和私钥值，公布需要公 开的参数并把密钥按照选举方案分发给相关方面的人员投票前阶段主要进行投 票人的身份验证及选票发放工作投票阶段主要由投票人进行投票计票阶段主 3 第二章电子投票的历史与现状 要进行验证所投选票的合法性，计票并公布投票结果以及用于满足安全性的相关 证明目前发表的方案由于采用的技术和为达到安全性应用的方法不同，具体的 过程和阶段的划分会有一定的差异：例如在基于盲签名的一些方案中，选票的制 作是由投票人与投票委员会共同完成的；有些方案( 例如【2 6 】【2 0 ，【3 7 ，【3 8 1 ) 中，投 票人的身份登记或验证工作和计票工作是由投票委员会的两个相互独立的人员集 合进行；【2 9 中又提出了自计票( s e l f - t a l l y i n g ) 方案，该方案中的计票阶段是一个公 开的过程，任何感兴趣的第三方都可以进行；在一些小型投票方案中，无需投票委 员会，投票人同时也是计票人，【4 5 1 提出了无需投票委员会的大型选举投票方案 目前的已经发表的电子投票方案按其采用的技术主要分为3 类： 基于混合网络( m i x n e t s ) ：主要是基于【7 】中提出的混合网络原理，投票时对选 票进行多层加密，而计票之前利用混和器在每一层解密后都对所有选票置换，从 而打乱投票人与选票间的对应关系，以达到选票的保密性混合网络是最早提出 的电子投票应用技术，在后来提出的许多著名方案中都利用了这种思想，并将其 和其他的技术结合使用：比较有名的混合有【7 】中的r s a 解密混合，【1 1 中的用户 中。c , ( u s e r - c e n t r i c ) 混合网络，【2 3 】【2 5 中的再加密( r e e n c r y p t i o n ) 混合等基于混合 网络的方案还有 4 0 1 ，【4 4 1 ，【3 4 ，【2 3 【2 8 等 基于盲签名( b l i n ds i g n a t u r e s ) ：利用盲签名的性质，投票人将其选票加密并盲 化后，连同相关的合格性证明一起提交给投票委员会进行有效性确认，当投票委 员会验证并使其选票生效后，投票人对选票解盲并投出，这样可以不泄露投出的 选票与之前提交的盲化选票的任何关系，以达到选票的保密性基于盲签名的方 案有【9 1 ，【2 0 ，【4 l 】，【2 2 ，【3 8 】，【11 】，【3 9 等 基于同态加密和同态秘密分享( h o m o m o r p h i ce n c r y p t i o na n dh o m o m o 删cs e c r e ts h a r i n g ) ：主要是利用同态的公钥密码体制，对加密的选票进行“求和”，并对和 数进行解密。无需对单张的选票进行解密即可得出投票的结果，从而保证了选票 的保密性这方面的文章主要有【1 3 ，【1 7 1 ，【4 】，【6 】，【4 3 】，【1 4 1 【1 6 ，【2 3 ，【5 1 ， 【3 3 等，本文方案采用的也是这个技术 2 4 电子投票的安全性 保障投票结果的公正性和保护投票人的个人利益不受侵犯是电子投票最基本 的目标，也是最重要的要求因此，对于一个具体方案来讲，安全性是衡量其好坏 的最重要标准一个安全的电子投票方案需要满足的性质主要有以下几点： 4 第二章电子投票的历史与现状 1 民主性：也称为合格性，是指只有符合投票条件的人才可以进行投票，且每 个投票人投票不能多于一张 2 保密性：保证每张选票内容的秘密，每个投票人所投选票的内容任何其他 人都不能知道这是最基本的性质 3 正确性：没有选票可以被篡改，复制或除去而不被发现 4 公平性：在投票过程结束之前，没有人能够得到部分计票的任何信息 5 投票者可验证性：投票者可以确定他投的票被正确地计入最后的计票中 6 普遍可验证性：任何一个观察者都能确信最后的计票结果是计算正确的， 即所有的有效票都被正确的计入最后的计票结果中 7 健壮性：系统可以容忍一定数量的出现错误的参加者，出错误的或恶意的 投票人会被侦测出来，不会影响整个过程的进行 8 无收据性( r e c e i p t f r e e n e s s ) 和抗强迫性( c o e r c i o n r e s i s t a n c e ) ：这两个性质在 电子投票中非常重要，主要针对在现实投票中出现的贿选和强迫投票人按其意愿 投票的个人和集团很多文章认为这两个性质是一样的，【2 6 ， 1 8 指出了它们的 差别并给出了确切定义无收据性在 6 】首次提出( 尽管 6 】中的方案后来被证明 【2 3 不满足无收据性) ，是指一个投票者不能得到任何可向贿选者或强迫者证明他 所投选票内容的信息( 收据) 抗强迫性是指一个投票者不能通过与强迫者合作来 证明他所投选票的内容抗强迫性是比无收据性更强的性质 2 5 典型方案介绍 下面对于上文介绍的三种基于不同技术的方案，分别给出实例具体介绍： 2 5 1 基于混合网络的【7 】方案 文献【7 】首次提出了混合网络的概念并提出了第一个密码学意义上的投票方 案方案使用r s a 或类似的公钥密码系统：记k ，i n v k 为公钥和对应的私钥，k ( z ) 为 k 对z 的加密，且系统满足i n v k ( k ( x ) ) = k ( i n v k ( x ) ) = z 所谓混合网络主要是 用到一种称为r r f i x 的电子计算装置，每个m i x 都有自己的公钥对于一个m i x ，它的 输入为甄( r 1 ，m ) ，其中k 1 为m i x 的公钥，r 1 为输入者任选的随机串，m 为信息条目； 经过m i x 解密并去掉冗1 ，输出为m m i x 的关键之处是它是批处理装置，对m i x 无论 按任何顺序输入一批尬( 冗1 l ，m i ) ，输出的内容都是按字典排序的，这就隐藏了输入 条目和输出条目之间的对应关系具体使用时一般是多层m i x ：m i x l ，m i x n ，输 5 第二章电子投票的历史与现状 入形式为 玩( r ，恐( 岛，k 1 ( r 1 ，m ) ) ) 其中k 为m i x ；的公钥，输入依次通过m i x i ，每个m i x i 解密后去掉冗并进行字典排 序然后传至m i x t 一1 ，经过最后一个m i x l 的解密去掉r - 并进行字典排序后的输出作 为最终的输出使用混合网络技术可以实现选票的保密性，方案主要过程如下： 1 投票前阶段：每个投票人向投票委员会匿名发送申请，申请包括为使投票 委员会接受所需的一切信息，和一个特殊的无地址数字信件，其内容为申请者的 公钥k ，称为假名( p s e u d o n y m s ) 对于n 层m i x 系统，这些信的形式为 ( r ，鲍( r 2 ，k a ( r 1 ，k ) ) ) 投票委员会将接受的申请中的无地址数字信制成一个批处理输入，经过m i x 处理 后输出为字典排序的被接受申请者的公钥k ( 假名) 列表，成为数字假名花名册 2 投票阶段：对于n 层m i x ，每个投票者所投票的形式为 ( ，尬( 岛，k 1 ( r 1 ，k ，i n v ( k ) ( c ，y ) ) ) ) 其q b i n v ( k ) ( c ，y ) 为投票人对选票y 用常数c “签名”后的加密密文所有投票经过 m i x 批处理后得到形式为k ，i n v ( k ) ( c ，y ) 按第一分量k 进行字典排序的列表 3 计票阶段：计票人检验若每组数值的第一分量k 在数字假名花名册中，且 恰好解密了“签名”的选票y ，则将y 计入有效票中 这个方案只是基于混合网络协议的雏形而已，并不能满足之后又提出的许多 安全性，但是它提出的混和网络构造思想非常重要，在后来提出的许多著名方案 中都利用了这种思想因此，虽然并不成熟，但【7 】作为一篇开创性的文章，在电子 投票的研究中有着重要的地位 2 5 2 基于盲签名的【3 7 1 方案 1 9 9 2 年， 2 0 首次提出了基于盲签名的大型投票方案，但文章只是给出了方案 的一个框架后来陆续提出的基于盲签名的方案，基本上都借鉴了它的思想，这里 介绍的【3 7 方案就是这其中比较有名的一个 所谓盲签名是指在发送者b 和签名者a 间的协议，b 想要a 对于消息m 进行签 名但不想让4 知道消息的内容，则b 使用一个盲化函数，对m 加盲后传给a ，4 对 ，( m ) 签名s z 驰( 厂( m ) ) 将其送回b ，b 使用满足g ( s i g a ( f ( m ) ) ) = s i g a ( m ) 的去盲 函数g 得到a 关于m 的签名，而a 既不知道m 也不知道s i g a ( m ) 6 第二章电子投票的历史与现状 【3 7 方案采用r s a 盲签名算法【8 】： 1 a 随机生成两个大素m r ，q ，计算佗= p q ，= p 一1 ) ( g 一1 ) ，选取随机 数e ，1 e ，g c d ( e ，) = 1 ，计算唯一整数d ，满z _ e d 三l ( m o d ) ，a 的公钥 是( 佗，e ) ，私钥是d ，a 使用r s a 签名算 法s i g a 2 b 选取整数k ，g c d ( k ，扎) = 1 ，建立盲化函数门铂去盲函数g ： f ：磊_ 磊，f ( m ) = m k e m o d 佗 g ：z n _ 磊，g ( m ) = m k - x m o d 死 对于这样的厂，g ，s i g b ，满足 g ( s i g a ( f ( m ) ) ) = g ( s i g am u m o d 礼) ) = g ( m d k m o d 扎) = m d m o dn = s i g a ( m ) 按上面描述的进行即可 方案的参与者有投票人k ，i = 1 ，投票委员会包括多重管理委员，多重 秘密委员和多重适时( t i m e l i n e s s ) 委员这个方案由于使用了混合网络以及多重秘 密委员而假设没有匿名信道为了容易理解，以下假设投票委员会包括单个管理 者a ，单个适时委员t ，并设匿名信道但不使用秘密委员方案的过程共分为4 个阶 段：批准阶段，投票阶段，声明阶段，计票阶段 1 批准阶段：系统生成并公布p ，q ，g ，h ，其中p ，口为大素数且q l ( p 一1 ) ，9 ，h 露且阶数都等于g ，使得满足h = g a m o dp 的口对任何方保密 ( 1 ) k 随机生成o t i 乙并计算g i = g m m o dp ，定义b c ( v t ，死) = 夕蚍g m o dp ， 这里b c ( v i ，亿) 为一个陷门比特承诺( t r a p d o o rb i t c o m m i t m e n t ) ，因为利用使得 仇+ 锄r i = + a r ：( m o dq ) 成立，则可用( ，n ) ，( ，吒) 等多种形式打开比特承 诺k 制作他的选票v t 并且使用随机数n 计算m i = b c ( v l i ，r i ) = g , g ：i i m o dp ，并计 算以= h ( m | i g i ) t ；m o dn 这里t t 是磊上的随机数，( e ，n ) 是a 的r s a 签名公钥，日是 一个h a s h 函数，则瓤即为r s a 盲签名的盲信息k 对于翰生成他的签名z i = ( 鼢) ， 并且利用a 的公钥计算e a ( z t i i 乞i i ，d k ) 进行加密 ( 2 ) 传送互( 甄i i z , l l i d v , ) 给a ( 3 ) a 解密信息并根据投票人名单表检查磁是否有权投票，同时检验k 是否已 经使用过了若无权投票或已经使用过则拒绝k ；若k 被接受，则a 检查x t 的签 名旎，若它们是有效的，则a 生成签名y i = 1 e u u - - 礼并传y i 给k ( 4 ) 计算8 t = 玑屯m o dn 去盲，得到a 对仇t 的签名8 = h ( m i i i c , ) 1 8 m o d 佗 7 第二章电子投票的历史与现状 2 投票阶段：k 将( m t i i g i ，8 ) 由匿名信道传到电子公告板上，将( v i ，n ，砚) 由 匿名不可窃听信道传给适时委员t 3 声明阶段：k 检查自己的投票是否列在电子公告板的投票列表上，若他的 投票没被列入，则k 通过出示( m i j g ，& ) 声明 4 计票阶段：t 以随机的顺序将选票v ；的列表公布在电子公告板上，并出示 非交互的零知识证明仃，来证明虢的列表中只包括m t 列表正确的打开值，但不泄 露v i 和观间的联系即丁公布忱的随机顺序列表口i ，嵋，t = ( i ) 0 = 1 ，) ， 7 r 为一个，个元素的随机置换给出( m l ，m a ( q ，秽；) ，t 证明他知道使得 m t = b c ( v i ，n ) ，= ( t ) 成立的( 7 r ，n ) ，但不泄露( 7 r ，n ) 的具体值 【3 8 对【3 7 的方案进行了修改，提出了3 个无收据化方案，这3 个方案都用到了 不可窃听信道或投票屋，这两个设备都是较强的物理假设，实现起来比较困难 2 5 3 同时基于同态加密和混合网络的【z 3 1 方案 下面以【2 3 中的方案介绍基于同态加密的方案【2 3 是对【1 6 方案的无收据 化，同时基于同态加密和混合网络两种技术所谓同态加密是指加密函数e 是同态 的，即若e 1 e ( v 1 ) ，e 2 e ( 也) 为明文v 1 ，v 2 在e 作用下的密文，“+ ”，“0 ”分别为明 文空间和密文空间的“求和”运算，则密文e = e 1o e 2 e ( v 1 + v 2 ) 方案假设有m 个 投票人，k ，个投票委员会成员a 1 ，a 2 ，a s 和l 个候选人 初始化阶段：【2 3 方案使用的是e 1 g a m a l 公钥密码体制【1 9 】和s h a m i r 的( 亡，) 一 门限秘密分享方案【4 2 在这个阶段，对于e 1 g a m a l 公钥体制，系统生成：口阶可交 换群g ，其中q 为大素数g 可被构造为露的子群，其中p 为大素数，也可由椭圆曲 线得到，所有运算在g 上进行夕为g 的生成元，私钥为名r 磊，公钥为h = g ： 系统公布p ，q ，9 ，h 并将私钥用s h a m i r l l 限秘密分享方案分发给a 每个a k 得到份 额z k 后公布h 七= 夕作为比特承诺设y 为有效选票的集合，包含乙上o o l 个值，可 定义v = f 1 ，m ，舻，m k l ) ( 若只有两个候选人，可简化为v = + 1 ，一1 ) ) ， 则一张选票钉v 的加密定义为e ( v ) = ( g n ，r 胪) ，其中，y 为g 上另一个生成元， o t r 乙为一个随机数，y 口相当于e 1 g a m a l 中的被加密信息 投票前阶段：对于每个合法的投票人，投票委员会要制作选票，这是方案 的核心部分注意到e l g a m a l 公钥密码体制是满足再加密性的，即对于v 的某个加 密密文e = ( z ，秒) ，它的再加密e ，= ( ，矿) = ( 矿z ，硝y ) ，毒r 磊仍为v 的加密 密文利用这个性质，投票委员会进行多轮洗牌生成选票：首先对于三个候选人的 8 第二章电子投票的历史与现状 选票仇，i = 1 ，l 系统生成并公布标准加密票e ( 0 ) ，e 2 ，e 5 0 ) = ( 1 ，俨) 显 然e ：0 ) t u v ；的对应关系是公开可验证的而后每个九轮流进行洗牌式加密： ( 1 ) a 得到加密有效票序列e ，- 1 ) ，e 等- 1 ( a 1 得到e ( 0 ，e 竺) ，对序列进 行洗牌：随机选择置换孤： 1 ，l ，_ 1 ，l ，计算e ：七1 ，的再加密并将其置 为e 篓么、( 对所有的i = 1 ，l ) ( 2 ) a 公开证明洗牌的正确性：对于每个i ，证明在序列e 子) ，e 等中存在e _ 1 ) 的再加密但不泄露是哪一个 ( 3 ) a 通过私人信道秘密将矾传给k ，并秘密向k 证明洗牌的正确性，即将7 r k 和 一个指定验证者证明( 证明对i = 1 ，le 罢曲为e - 1 ) 的再加密) 由不可窃听信道 传给 ( 4 ) 若k 不能接受a ( 3 ) e e 的洗牌正确性证明，可公开对a 七提出抗议，这时九的 洗牌将被忽略，置e p = e p _ 1 ) ，e 等= e z - 1 ) t h s h a m i r 彭j ( t ，) 门限秘密分享 方案限制，k 最多可抗议一亡个投票委员会成员 ( 2 ) ( 3 ) 中的两个证明在安全性方面非常重要，他们使得方案满足了投票者可验 证性，普遍可验证性和无收据性，证明的具体内容参见【2 3 ，【1 2 1 ，【1 4 ，【1 6 1 投票阶段：k 得到e p ) ，e | ! v ，并且清楚的知道它们与仇，i = 1 ，l 的对 应关系( 只有他一人知道) ，投票通过在电子公告板上声明所选对应的标号i 即可 计票阶段：所有k 投票完成后，投票委员会利用同态加密性质对加密票求和： 两个加密票e 1 = ( z 1 ，y 1 ) ，e 2 = ( x 2 ，y 2 ) 的求和定义为e l e 2 = ( x l x 2 ，可1 抛) 将所有 票求和后得到形如( z ，y ) = ( g a ，7 t h a ) 的加密向量其中t 为所有选票v 的加法和， q 的值没有任何人知道解密时每个a 计算钆= z 缸，再利用s h a m i r l 拘l ( t ，) - 门限 秘密分享方案得到圣= 矿，注意e i g a m a l 私钥z 始终是保密的最后，计算 里：一y ：, t t h a ：， 一= 一= 一= 7 y 2 z ： ( 夕口) 2 虽然离散对数是难解的，但t 的取值范围有限，可以在o ( _ 1 ) 内算出 1 6 1 这个方案并没有给出投票人的身份认证问题的解决办法，对于安全的方案来 说这是一个不完善的地方方案满足了较高的安全性要求，但需要投票人的工作 相对复杂，通信花费也较高，实用性方面还值得推敲 9 第三章基本知识 第三章基本知识 3 1 知识的证明 所谓知识的证明是指证明者p 要使验证者y 相信p 知道某个秘密的一种交互 证明这个秘密通常比较典型的是一个公开可知的信息在某个单向函数下的原像， 例如一个离散对数或r s a 根 本文主要用到一种对于某个关系尉拘知识的证明协议：诚实验证者零知识 ( s p e c i a lh o n e s tv e r i f i e rz e r o - k n o w l e d g e ) ，即协议对一个诚实的y 来说是零知识，不 会泄露任何东西( 如p 的秘密) 给诚实验证者，而对于一个欺骗的验证者不是必然 安全的，但这己能满足我们的目的 一个协议被称为对关系r 的知识的证明，若它满足完备性和特殊稳固性简 要地说，完备性是指给定诚实的p 和诚实的y ，协议将以很高的概率进行( o o v 接 受p 的证明) ；特殊稳固性是指存在一个知识析取器，它可以在多项式时间内以不 可忽略的概率析取任何p 在证明时选取的“证据”( w i t n e s s ) 更详细标准的定义参见 文献 1 2 】【1 6 一个协议被称为诚实验证者零知识是指存在一个模拟器，当输入内容相同时， 其模拟的交互对话与p 和y 的真实交互对话是不可分辨的；更强的，若有一个程序， 可以取任意c 作为y 的质询( c h a l l e n g e ) 输入产生对话，使其与所有尸和y 以c 为质询 对话的空间不可分辨，则称为特殊诚实验证者零知识( s h v z k ) 下面给出方案中将用到的离散对数等价性的知识的证明，同时说明上述性质： 勘，g 为两个大素数，满足9 1 0 1 ) 令g 口为露的阶数为q 的子群，且在g 口上求 解离散对数是困难的 证明者尸要向验证者y 证明等式 l 0 9 9 lh i = l o 9 9 2 h 2 其中夕1 ，9 2 ，h 1 ，h 2 g 口且九1 = g m o dp ，h 2 = g 呈m o dp ，即尸向y 证明他切实掌握着 满足上面等式的离散对数a 乙但不泄露口的信息 尸通过以下步骤向y 证明，其实现过程如表3 1 所示： 1 0 第三章基本知识 表3 1 离散对数相等证明 ( 1 ) p 选取叫r 磊，计算8 1 = g m o dp ，8 2 = g 考 m o dp ，发送8 l ，8 2 给y ( 2 ) y 计算并发送随机质询c r 乙给p ( 3 ) p 计算7 = ( w + o t c ) m o dq ，并将r 发送给y ( 4 ) y 验证鳋= h i s l m o dp i n 9 2 = h ；s 2 m o dp 是否成立如果成立，则p 在不泄 露口的情况下向y 证明了九1 ， 2 相对于9 1 ，9 2 的离散对数相等 定理3 1 上述协议是一个3 步( 3 一舢坩) 的对于关系l o 岛。h i = l o 9 9 2 2 的知识的 证明，该- i z - 明满足特殊稳固性并且是特殊诚实验证者零知识 证明协议满足特殊稳固性是因为对于两组第1 步传送相同的可接受对话 ( 8 1 ，8 2 ，c ，r ) 和( s 1 ，8 2 ，c ，) ，c d ，一个满足8 1 = 鳄和8 2 = g y 的“证据”w = 岩可 以被析取出来而协议满足诚实验证者零知识是因为给出随机的c 和7 ，存在对话 ( 夕r 。j 1 i 。，钙s i c ，c ，r ) 是一个可接受的对话并且和一个由诚实的p 和诚实的y 生成的 可接受对话是不可分辨的由于“质询”c 可以自由的选择，则s h v z k 性质也可以得 到 口 利用著名的f i a t s h a m i r 启发式【2 1 可以使证明转化为非交互的，并能确保c 是 “诚实”选择的：设日是一个安全的h a s h 函数，则定义c = h ( h l ，h 2 ，8 1 ，8 2 ) 由p 公布 数组 ，v 利用h a s h 函数计算c 并验证第4 步中的两个等式 3 2 同态加密 所谓同态加密是指加密函数e 是同态的，即若e l e ( m 1 ) ，e 2 w ( m 2 ) 为明 1 1 第三章基本知识 文m 1 ，r n 2 在e 作用下的密文，“+ ”，“。 分别为明文空间和密文空间的“求和”运算， 则密文e = e 1oe 2 e ( m l4 - m 2 ) 若将明文理解为选票的话，则可以做到在不知 道每张选票秘密的情况下计算所有选票求和的结果，基于同态加密的投票方案就 是利用加密函数的这个性质在计票阶段达到每张选票的保密性的 3 3e i g a m a l 密码体制 e 1 g a m a l 密码体制【1 9 是著名的公钥密码体制，同时也满足同态加密性质其 内容如下： 锄，口为两个大素数，满足q l p 一1 ) g 口为露的阶数为g 的循环子群，且在g q 上 求解离散对数是困难的，9 为g 。的生成元( g 。也可由有限域上的椭圆曲线得到) 明 文空间p = g 。，密文空间c = g 。，i cg 。，从磊中选取整数8 作为私钥，相应的公钥 为h = g * m o dp ，所有运算均在g g 上进行对于给出的明文信息m g 口： ( 1 ) 加密：选取秘密的口r 磊，密文 ( z ，y ) = e ( m ，0 1 ) = ( g a m o d p ，m h a m o d p ) 其中e ( m ，口) 表示用秘密随机数o t 对m 加密 若取o t = 0 ，贝l j e ( m ，0 ) = ( g o m o dp ，m o m o dp ) = ( 1 ，m ) ，称其为标准加密 ( 2 ) 解密：对于密文( z ，) ，利用私钥8 计算 石y 删p = 淼m o d p 硼 此外，e 1 g a m a l 密码体制还有2 个重要性质：可再加密性和前面提到的同态性 ( 3 ) 可再加密性( r e e n c r y p t a b i l i t y ) ： 可再加密性是指任何人只需知道公钥即可在不知私钥的情况下对密文进行随 机的再加密对于某个明文信息m 的一个加密密文( z ，y ) = ( g a m o d p ，m h q m o d p ) ， 已知公钥h 的操作者可以通过计算 ，y ) = ( g 9 m o dp ，m h m h a 2 r o o d p ) = ( g a m o dp ，m h 口m o dp ) 进行再加密，其中口2 rz g 由操作者随机选取，o t = o t i + o r 2 而对于其他人来说， 想要确认( z ，可) 和( x ，y ) 是否为同一个明文的加密密文是不可能的 ( 4 ) 同态性：若e l = ( x l ，y 1 ) 和e 2 = ( x 2 ，抛) 代表的密文对应的明文分别是m l 和 忱，贝, l j e = e 1 圆e 2 = ( x l x 2 ，y l y 2 ) 为m = m l 仇2 的一个加密密文 1 2 第三章基本知识 3 4 e i g a m a l 密码体制的密钥分享 本文方案中使用的e 1 g a m a l 密码体制的私钥需要在投票委员会的一定数量的 成员中分享：即将私钥8 分成若干个份额( s h a r e ) ，并分发给不同的成员掌握( 所有的 人都不知道8 的真实数值) ，只有达到某个规定人数以上的成员联合他们的份额才 能重构私钥来对密文进行解密 这里采用s h a m i r ( t ，他) f - j 限方案 4 2 1 一个( ，n ) f q 限方案是指由可信系统利用 私钥s 计算分享的份额s j ，1 j 礼，分发给n 个成员a j ，1 j 扎，使得任意t 个 或更多的成员联合他们的份额就可以重构s ，但只掌握任意t 一1 个或更少的份额的 成员集合不能重构8 整个e 1 g a m a l 密码体制的( 亡，佗) 门限方案执行过程如下： ( 1 ) 密钥分享：可信系统生成e i g a m a l 密码体制的私钥8 后，计算公钥h = 旷并 对所有参与者公开对于要分享的8 乙，系统秘密选取t 一1 个元素a l ，a 2 ，a t l 乙，对于1 j 几计算s j = ( s + ：三：a i j ) m o oq ，并将s j 秘密的分配给如，1 j 佗，没有人知道s 的具体数值如得到勺后计算吻= 9 8 j m o dp 作) 白b i t 承诺公开 注：s 可由任何一个由t 个份额组成的集合a 利用l a g r a n g e 插值进行重构： s = s j ，a m o dq a _ 击 ( 3 1 ) j c a t e a u 。 其中i a i = 且a 1 ，2 ，扎) ( 2 ) 解密：对于一个加密密文( z ，y ) = ( g 1 m o dp ，m h q m o dp ) ，分享份额的成员 们执行下面的协议，在不重构8 的情况下进行解密： 1 每个如计算公布嘶= x j m