（计算机系统结构专业论文）安全电子选举的研究与实现.pdf

安全电子选举的研究和实现 摘要 电子选举指的是通过现代网络技术和密码学技术来实现现实生活 中的投票选举，电子选举协议是对密码学领域内多种密码学知识的 一种综合应用。它综合运用了公钥密码体制，数字签名，匿名信道， 零知识证明，安全多方计算等密码学知识来模拟并达到传统选举过程 的完备性，匿名性，保密性和公正性等安全要求。 最初的许多电子选举方案最大的缺点是实用性不强，直到1 9 9 4 年 由f u j i o k a ，o k a m o t o 和o h t a 提出了一种实用的适用于大规模选举的选 举方案后才使得电子选举方案得到了实质性的突破。目前国内外已经 出现了一些实验用的基于此f o o 方案的电子投票系统，例如由m i t 研究实现的e v o x 系统，w a s h i n g t o n 大学的s e n s u s 系统。但是目前 的电子选举系统都过于依赖对选举组织机构的信任，对于计票中心和 选举组织机构的舞弊行为存在一些安全漏洞，其主要原因是赋予选举 组织机构过大的权力；并且由于在选举过程中一些中间结果的泄漏， 使投票者能够出卖自己的选票。心 针对现有电子选举方案中自q 土述不足之处，本文提出了对利用同 态函数的k j 电子选举协议的一种改进，通过重新构造k j 协议中的 主函数，使改进的选举协议具有防止出卖选票的性质，并且通过对协 议流程的改造和完善，提高了协议对选举管理机构的权力进行监督和 限制的能力。经过作者的分析和论证，改进的协议除了达到对安全电 子选举的一般安全要求外，在防止选举组织机构和计票中心的舞弊行 为上也具有很好的特性。此外，作者在改进的电子选举协议基础上设 计并初步实现了一个名为i n j u s 的电子选举系统。 本文最后分析了新的电子选举系统的不足和缺陷，提出了今后作 进一步改进的目标和方向 关键字：多方计算，电子选举，出卖选票问影选票掩码。 r e s e a r c ha n di m p l e m e n t a t i o n o fs e c u r ee l e c t r o n i ce l e c t i o n a b s t r a c t t h ee l e c t r o n i ce l e c t i o n i st ov o t e b y m o d e mn e t w o r ka n d c r y p t o g r a p h yt e c h n o l o g y t h ee l e c t r o n i ce l e c t i o np r o t o c o li sas y n t h e t i c a l a p p l i c a t i o no f d i f f e r e n tk n o w l e d g ei nt h e c r y p t o g r a p h yf i e l d i tu s e sm a n y c r y p t o g r a p h yk n o w l e d g es u c h a s r s a ，d i g i t a ls i g n a t u r e ，a n o n y m o u s c h a n n e l ，z e r o k n o w l e d g ep r o o fa n ds e c u r em u l t i - p a r t yc o m p u t a t i o nt o s i m u l a t en o r m a le l e c t i o na n dt oa c h i e v ei n t e g r i t y , a n o n y m i t y , s e c u r i t ya n d e q u i t y t r a d i t i o n a le l e c t r o n i ce l e c t i o nm e t h o dh a sl i t t l ep r a c t i c a b i l i t y , w h i c h i si t sb i g g e s tw e a k n e s s i ti sn o tu m i l19 9 4 f u j 【i o k a , o k a m o t oa n do h t a p u tf o r w a r dan e we l e c t i o nm e t h o dw h i c hi sa p p l i c a b l et ol a r g es c a l e e l e c t i o n t h a t 廿l ee l e c t r o n i ce l e c t i o nm e t h o dh a sa ne s s e n t i a li m p r o v e m e n t n o w , t h e r ea r es e v e r a le l e c t r o n i ce l e c t i o ns y s t e mb a s e do nf o oi n i n t e m a t i o n a ll a b o r a t o r y , s u c ha se v o x b ym i t a n ds e n s u ss y s t e mb y w a s h i n g t o nu n j b u tt o d a y s e l e c t r o n i ce l e c t i o ns y s t e mr e l i e so nt h e e l e c t i o no r g a n i z a t i o nt o om u c ht on o t i c et h es e c u r i t yl e a ki nt a l l yc e n t e r a n de l e c t i o no r g a n i z a t i o n i ti sb e c a u s et h a tt h et a l l yc e n t e ra n de l e c t i o n o r g a n i z a t i o na r eg i v e nm u c h t o op o w e r a l s ob e c a u s es o m em i d d l er e s u l t s l e a ki nt h ep r o c e d u r eo fe l e c t i o n t h ev o t e r sc a ns e l lt h e i rb a l l o t s t or e s o l v et h ep r o b l e mi nt o d a y se l e c t r o n i ce l e c t i o nm e t h o d ，t h i s p a d e r r a i s e sa ni m p r o v e m e n to f k jp r o t o c o lw h i c hm a k e su s eo f p a r t i a l l y c o m p a t i b l eh o m o m o r p h i s m s b yr e b u i l d i n gt h em a i n f u n c t i o no f p r o t o c o l ， i tk e e p st h ev o t e r sf r o ms e l l i n gb a l l o t s a n db ya m e l i o r a t i n gt h ef l o wo f t h e p r o t o c o l 。i ti m p r o v e s t h e a b i l i t y o f s u p e r v i s i n g t h ee l e c t i o n o r g a n i z a t i o n i t i s a n a l y z e d a n dd e m o n s t r a t e d b ya u t h o r , b e s i d e s a c h i e v i n gt h eg e n e r a ls e c u r i t yr e q u i r e m e n t ，t h en e wp r o t o c o li sg o o da t k e e p i n g t h ee l e c t i o no r g a n i z a t i o na n d t a l l yc e n t e rf r o me m b e z z l i n g m o r e o v e r , i nt h i sp a p e r , w ed e s i g na ne l e c t r o n i ce l e c t i o ns y s t e m n a n l ei n j u s b a s e do nt h ei m p r o v e d p r o t o c 0 1 a tt h ee n do ft h i sp a p e r , w ea n a l y z et h es h o r ta n df a u l to ft h en e w s y s t e m ，a n dr a i s et h ea i m a n dd i r e c t i o no f n e x ti m p r o v e m e n t k e y w o r d s ：m u l t i p a r t yc o m p u t a t i o n ，e l e c t r o n i ce l e c t i o n ，p r o b l e mo f s e l l i n gb a l l o t s ，m a s k o f b a l l o t s 上海交通大学硕士学位论文 第1 章绪论 1 1 密码学发展简史 通信保密是- - 1 3 古老的学科，为保护军事和外交通信的安全，密码的使用已有千 余年的历史，从古代至2 0 世纪5 0 年代可以认为是现代密码学前期的时代。早在2 0 0 0 多年前，就出现了著名的恺撤密码。1 9 2 6 年，美国电话电报公司的工程师g s v e m a m 又发明了v e m a m 密码。 1 9 4 9 年c e s h a n n o n 发表的保密系统的通信理论一文，用信息论的观点对信 息保密问题作了全面的阐述。他以概率统计的观点对消息源、密钥源、接收和截获的 消息进行数学描述和分析，用不确定性和唯一解距离度量密码体制的保密性，阐明了 密码系统的完善保密性、纯密码、理论保密性和实际保密性等重要概念。这使信息论 成为研究密码学和密码分析学的一个重要理论基础，宣告了科学的密码学信息理论时 代的到来。 六十年代，微电子学和计算机技术获得了很大的发展，形成了计算机系统，进入 七十年代后，计算机和通信技术相互结合，开始出现了计算机网络，此时对密码技术 的发展提出了新的需求： m 对密码技术的需求已经远远超出了原来的军事及外交部门，扩展到包括工业、商 业和金融领域，甚至涉及到个人隐私信息的保护。 口 密码技术的安全性和经济性都放到了重要位置，而以往的密码技术用于影响到国 家安全的应用，往往以经济性换取安全性。 口 信息除了要具有保密性外，还需要具有完整性。也就是说，加密措旌要能抵抗如 消息篡改、删除和伪造等各种形式的主动攻击。 口密码技术除了要保护传输过程中的信息外，还需要保护存储的信息，其中数据库 安全是主要的目标之一。 口信息交换不仅仅是传统的点对点，而且越来越趋向于网络化。这种环境下原有的 密码技术不一定能很好地运用。 1 9 7 6 年，w d i f f i e 和m e h e l l m a n 发表了“密码学的新方向”一文，首次提出了 发送者和接收者之间不必传送密钥就能进行保密通信的可能，开创了公开密钥密码学 的新纪元。 上海交通大学硕士学位论文 八十年代，继d e s 和公开密钥密码体制之后，在密码学的理论研究方面许多新 的编码思想和技术被提出。例如，在公钥密码体制的基础上提出了概率加密算法；出 现了量子密码学；s i m m o n s 提出了鉴别理论。在密码协议方面，数字签名得到了深入 的研究，合同签署、秘密投票、智力扑克、秘密共享等更复杂的密码协议得到了一定 的发展。零知识证明、身份鉴别、认证理论、陷门函数、快速加密算法等也是今年来 的热门研究课题。 1 _ 2 电子选举的意义 当今社会，几乎我们身边的每一件事都可以被计算机实现，尤其是随着近几年来 w w w 的几乎是爆炸式的发展，通讯和网络技术的突飞猛进，我们的生活和工作都出 现一种不可避免的趋势一一无纸化，自动化。选举，作为社会公民所享有的一项基本 权利，它的方式本身也不可能在这样一个日新月异的社会环境中停滞不前，因此，电 子选举应运而生。由于电子选举系统的产生，我们可以利用先进的网络条件和密码 学技术为人们提供方便、快捷、安全的投票环境，社会公民可以利用现代网络直接在 家中或实验室进行选举，因此节省了大量的财力和人力。 1 3 安全电子选举简介 电子选举指的是通过现代网络技术来实现投票选举。电子选举的特点是方便，快 捷，但一个电子选举系统应至少达到一个普通的现实中的选举的安全性。电子选举协 议是对密码学领域内多种密码学知识的一种综合应用，我们可以用图1 - 1 来大致描述 它在密码学中的位置。一个电子选举协议通常综合运用r s a ，数字签名，匿名信道， 零知识证明，安全多方计算等方面的密码学知识来模拟并达到普通选举的完备性、匿 名性、保密性、合法性和公正性等安全要求。 上海交通大学硕士学位论文 f i g l 一1 t h es t a t u so ft h ee l e c t r o n i ce l e c t i o ni nc r y p t o g r a p h y 图1 - 1 电子选举协议在密码学中的位置 然而电子选举的发展从它在1 8 8 4 年第一次被人提出到现在这近百年并不是帆 风顺的，其主要原因是一个电子投票系统的安全性和公平性是很难得到保证的。直到 密码学突破军事应用的限制，在各领域得到广泛的应用以及密码学本身的飞速发展， 电子投票才有了可喜的进展。 8 0 年代以后一些学者先后发表了若干关于电子选举的应用方案，各种具有相应特 点的选举方案不断涌现。但是这些传统方案的一个最大弊病在于实用性不强，不适应 于大型选举。在f u j i o k a ，o k a m o t o 和o h t a 于9 2 年提出了一个实用的适应大规模选 举的方案( 见参考文献 1 】) 后，电子选举的实用方案得到了实质性的突破，并在一 些非政府部门得到了广泛的应用，其中著名的有m i t 的e v o x 系统，见参考文献【2 1 】， w a s h i n g t t o n 的s e n s u s 系统，见参考文献 2 2 1 。 虽然这些选举系统保证了一定的安全性，但是这种安全性是建立在对单个管理机 构的完全信任的基础上的。就现有的电子选举系统来说，如果没有投票人的百分之百 的共同参与，是无法严格维护选举最终结果的公正性的；当然我们也不能完全摈弃管 理机构这种可信第三方，因为正是可信第三方的参与才使得选举过程中的计算量和通 信量大大地降低，才使得举行大型的电子选举成为可能。为了限制管理机构的过大权 力，我们希望在不牺牲匿名性、保密性等安全性的条件下能够对管理机构的行为进行 监督。 1 4 安全电子选举协议的几点要求 个电子投票协议至少应达到现实生活中一个普通投票系统的安全性质，它既能 够防止欺骗又能够保护个人隐私，否则计算机化和网络化的投票系统永远不会在一个 一般的选举中使用。因此一个电子投票协议应满足下列基本性质： 投票的合法性，即只有经授权的投票者才能投票 计票的完整性，即所有的有效投票都能被正确计入 投票过程的稳固性，即不诚实的投票者不会破坏整个投票 投票的匿名性，即没有人能把投票内容和投票人联系起来 选票内容的保密性，即每个投票者的投票内容不会被除本人以外的任何个人或组 织机构得知 选票的有效性，即每张选票的内容都是有效的，符合选举中约定的选票规则 上海交通大学硕士学位论文 不可冒充性，即每张选票都不会被任何人复制， 不可重复性，即投票者本人不能把同一直选票重复投递，也即一人只能投一次票 可证实性，即任何人都不可能伪造选举结果，选举的结果可以被大家证实 上海交通大学硕士学位论文 第2 章相关的密码学基础 2 1 公开密钥密码体制 2 1 1 公开密钥密码 加密算法通常被分为两类：秘密密钥( 对称) 算法和公开密钥( 非对称) 算法。 在对称算法中，加密和解密的密钥相同，因此，需要用对称加密算法进行保密通信的 双方必需事先交换密钥。在公钥加密算法中，加密和解密密钥不同。加密密钥( 即公 钥) 是公开的，解密的私钥是秘密保存的。所以，对称加密算法要求秘密传送密钥， 而非对称加密算法只需要鉴别公钥，它的安全性要求弱得多了。 对称加密算法在恺撒时代就已经有了，但公开密钥秘密的概念在1 9 7 6 年d i f f i e 和h e l l m a n 的一篇文章“秘密学的新方向”中才首次提出。他们提出了陷门单向函数 的概念，我们知道单向函数的逆计算是非常困难的，但对于陷门单向函数如果知道了 函数的陷门，那么就可以很容易地进行单向函数的逆计算。例如给定函数：a b ， 该函数f a 可作为公钥，其陷门( 私钥) 秘密b 可以通过b = “曲计算并秘密保存。对消 息ma 的加密就是( m ) ，解密即为f b 。( 毛( m ) ) = l 。 陷门单向函数不仅用于加密，也用于实现数字签名。例如，对消息m ，b 的数 字签名为s = f b 1 ( m ) ，任何人都可用公钥验证m - - f a ( s ) 是否成立来检验签名。 2 1 2 r s a 加密 d i f f i e 和h e l l m a n 在 1 6 中提出陷门单向函数的概念后，r i v e s t 、s h a m i r 和a d l e m a n 最先提出了一个陷门单向函数的实现。该函数基于计算以合数, 为模数的e 次方根的 困难性，即r s a 问题的难解性。 加密算法如下：设p 和q 是两个大素数，p 一1 和g l 至少有一个大的素因子 = p q ，整数e 满足g c d ( e ，妒( 刀) ) = 1 。接收者b o b 的公钥是( 珂，p ) ，私钥是( p ，g ，d ) ， 其中d 满足d e e l ( m o d 伊( n ”。 假设发送者a l i c e 要将消息肼 o ，甩一1 秘密发送给b o b ，a l i c e 首先计算 上海交通大学硕士学位论文 c ；m 。( m o d n ) 并将密文c 发送给b o b ，b o b 计算m = c 。( r o o d n ) 进行解密。 由于出= 1 ( m o d o ( n ) ) ，因此c 4 ；( m 。) 4 = m ( m o d n ) ，这就说明b o b 能够解密得 到明文。该方案的安全性基于r s a 问题的难解性，但是系统并不总是安全的。例如， e 比较小的情况下攻击是可能的。 2 2 数字签名 数字签名的思想由d i f f i e 和h e l l m a n 在中提出。数字签名是以电子形式签名一个 消息的方法，和传统签名有一些相似之处。一个数字签名是一个将签名者公钥和签名 消息联系起来的二进制串。任何人都可以用签名者的公钥验证签名，另一方面，只有 知道私钥的人才能产生正确的签名。签名方案的正式定义如下所示。 麟一个签名方案是一个算法的3 元组( 船n , s i g , v p r ) ，其中伊n 是概率型算法，j 姆 通常是概率型算法，v e r 是确定型算法。g e n 输入系统参数，输出签名者s 的私钥x 和公钥y 。，s i g 输入消息搠和x ，输出肌的签名g r ，v e r 输入消息r a 、签名盯和s 的 公钥y ，输出t r u e 或f a l s e ，并满足 ，、l t r u ei f p r o b ( c r = s i g ( m ，t ) ) 0 附( m ，仃，y s ) 2 1 僦s eo t l l 唧i s e 4 而且，任何人不知道私钥就不能产生正确的签名，即签名是不可伪造的。 构造签名方案的一种方法是采用身份识别方案，将单向散列函数对承诺t 作用后 的结果代替询问c 。如果身份识别方案是零知识证明，并且单向函数是安全的，则这 种签名方案是安全的。为了严格论证其安全性，有人提出了随机提示模型( r a n d o m o r a c l em o d e l ) ，在模型中散列函数被提示器代替，提示器在请求下可产生随机二进制 串，并对相同的请求产生相同的二进制串。 2 2 1 r s a 签名算法 r s a 签名方案直接从r s a 加密方案得到，安全性基于计算模数为合数的p 次方 根的困难性。 设p 和g 是两个大素数，p 一1 和q l 至少有一个大的素因子，糟= p q ，整数e 满 8 鲁 上海交通大学硕士学位论文 足g c d ( e ，p ( ”) ) = 1 。签名者的公钥是( n ，e ) ，私钥是( p ，g ，d ) ，其中d 满足 d e ；1 ( m o d e ( n ) ) 。散列函数h ： 0 ，1 ) + 一z 。 霪鍪赡对消息m e o ，1 ) 的公钥为( ，e ) 的r s a 签名是s z 。，满足 j 8e h ( m 、( m o d n ) 。 签名者产生签名时只要计算s z ( h ( 聊) ) 4 ( r o o d n ) 。由于d e s l ( m o d e ( n ) ) ，因此 s 。= ( h ( m ) ) “= h ( 聊) ( m o d n ) ，这就说明签名是正确的。 如果不用散列函数，那么两个签名的乘积是消息乘积的签名，而且攻击者可以选 择s ，计算m = s 。( m o d n ) ，从而伪造签名。i s o i e c 9 7 9 6 标准提出了解决这个问题的 签名过程。 2 2 2 e l g a m a i 签名算法 e 1 g a m a l 在还提出了个签名算法。设g 是有限循环群，其阶为g ，g g 是g 的 生成元，在g 中计算离散对数是困难的。签名者的私钥是x ，公钥是y = g 。散列函 数h ： 0 ，1 + 一z 。 懑瀵瀚荔对消息搠 o ，1 ) 的公钥为y = g 。的e l o a m a l 签名是( “，s ) g z 。，满足 一# m 罅i ， ， g ”( ”) 。y “u 5 。 在上面的定义中，为了计算y ”，首先将“表示为z 吲中的整数“，然后计算 “= “( r o o d q ) ，最后计算y ”得到y 。在下文中，群元素、整数和字符串之间的转换 依此类推。 持有私钥z 的签名者产生对消息m 的签名( “，j ) 的过程如下： 首先选 圭堂奎望奎堂堡圭堂篁笙苎 7 z ：， 然后计算 材：占r 和j ：里业( m 咄7 ) 。 r 由于y “矿= g “g ”= g ”= gh ( 卅) ，因此签名( “，s ) 能够通过验证。显然，如果离 散对数问题被解决，就可以伪造签名。如果两次签名产生时选择的，相同，则可以计 算出私钥。数据签名算法( d i g i t a ls i g n a t u r ea l g o r i t h m ，简称d s a ) 是e 1 g a m a l 签名 的一个变形。关于数字签名方案的安全性分析可见参考文献【1 8 】【1 9 】。 数字签名作为手写签名的电子化，具有更大的安全性和更高的效率；它更容易验 证，更加难以伪造，同时也更加难以抵赖。 2 3 不可区分性 为了分析密码算法的安全性，除了需要密码假设，还经常用到随机变量的不可区 分( u n d i s t i n g u i s h a b i l i t y ) 。不可区分性在零知识证明系统定义中有重要的作用。如果 没有有效的算法可以区分两个随机变量u 和矿，则称u 和矿是不可区分的，记为 u v 。由于对任意观察者，不可区分的两个随机变量的分布是相同的，所以不可区 分也称为计算相等。两个相等的随机变量必定是不可区分的。不可区分和相等关系具 有一些相同的性质，如下所示： 口u 矿矿一w j u 矽： 口对任何可计算的函数，u v j f ( u ) f ( v ) 。 2 4 比特承诺 安全的多方计算协议将用到零知识证明，而g o l d r e i c h 等【1 7 】证明了只要存在承诺 方案，对任何n p 一语言都存在( 黑盒) 零知识证明。因此尽管比特承诺本身的实际用 途不大，但作为密码学协议的原语有着非常重要的意义。比特承诺可分为承诺阶段和 打开阶段，在承诺阶段承诺者向接收者发送一对未来事件的预测( 承诺) ，但不揭示 该预测，在打开阶段承诺者揭示预测且接收者相信揭示值就是承诺值，形式化地说： 定义2 9 比特承诺方案是 统计性隐藏的，如果在承诺阶段后( 打开阶段前) 接收者得到的关于被承诺比特 上海交通大学硕士学位论文 x 0 ，1 ) 的信息v 为l ( x i y ) 2 一“，其中a o ，n 为安全参数 d 一约束的，对o 6 。 上海交通大学硕士学位论文 ( 即公共输入为z 的v 和户在交互后v + 获得的信息) 和 m ( x ) 。( 即输入为x 的 时的输出) 是计算不可区分的，则称( p ，矿) 是计算零知识的。m 称为矿和尸交互 的仿真。 对命题进行零知识证明的一般方法是首先将命题变形然后发送给验证者，然后证 明者证明变形后的命题，或证明原命题为真当且仅当变形的命题为真。这两种证明都 没有泄露原命题的信息。如果原命题为假，则证明者作假被发现的概率是1 2 。因此， 进行若干次协议的反复执行后就可以以很高的概率确信原命题的真假。 在电子选举中，零知识证明具有重要的作用，例如对于一张选票，选票的内容信 息是不希望泄漏给任何人的，可是对于一个选举的举办单位当然是希望知道投票人的 选票内容是有效选票，才会给予投票人投票的合法权利，否则一个恶意的投票者就可 以肆意破坏整个选举过程的进行了。 2 6 散列函数 在签名方案中，散列函数可以将任意长度的二进制串映射为签名算法要求的长 度。在知识证明系统中，散列函数可以替代验证者从而构造签名方案。 鬻溪隧散列函数是将任意有限长度的二进制串映射为固定长度j 的二进制串的函 数，即h ： 0 ，1 ) + 斗 0 ，1 ) 。 散列函数应是易于计算的。密码散列函数还应难于计算其逆，即至少满足下列条 件之一： 口弱无碰撞特性：给定z ，找到满足h ( x ) = h ( x ) 的x 工是计算上困难的。 口强无碰撞特性：找到满足h ( x ) = h ( x ) 和x x 的消息x 和x 是计算上困难的。 口单向特性：给定c ，找到满足h ( x ) = c 的x 是困难的。 显然，强无碰撞散列函数是单向散列函数，也是弱无碰撞散列函数。在本文中， 弱无碰撞的散列函数能够满足应用的安全性要求，但某些特殊应用中要求散列函数具 有不相关等特性。 散列函数的坚固性因不同的安全性需求而不同。假设计算逆的最好的算法是强力 攻击，则坚固性主要取决于输出的比特数。由生日攻击，在2 爿个散列值中找到一个 圭塑銮望查兰堡主堂竺堡茎 碰撞的概率为1 2 ，因此1 6 0 比特的散列函数值已能够满足一般的安全性要求。 现有的密码散列函数可分为两种： i 1 基于分组密码的散列函数。如基于i d e a 的t a n d e md m ： 口 专门设计的散列函数。如s h a ，m d 5 ，i m e m d 1 6 0 。 2 7 多方计算 安全的多方计算协议允许两方或多方各自拥有一些秘密输入并共同计算共享的 函数f 然而各方都不想泄露秘密却要得到f 的输出，就好像有一个可信第三方收集 了各方输入并计算f 后再将结果返还给计算方。由于安全的多方计算协议的定义涉及 理想模型、半诚实模型( s e m i - h o n e s tm o d e l ) 、恶意模型( m a l i c i o u sm o d e l ) 、被动攻击 ( p a s s i v ea t t a c k ) 、适应性攻击( a d a p t i v ea t t a c k ) 等诸多复杂概念，这里就不再介绍，有兴 趣的读者可参阅文献【2 4 】。文献 2 5 】中作者给出了一个较为简单的例子：由t 方各自秘 密计算公开的多项式函数，其基本思想是先将各方的秘密数以秘密共享方案分配给所 有其他人，然后计算中的各方就按照类似解多元方程组的方法计算出多项式函数的 值。 上海交通大学硕士学位论文 第3 章电子选举协议 3 1 自我判决型协议 这种协议不需要除投票者以外的参与者，投票的安全性由投票者的多次加密和签 名来实现。匿名性由算法中对选票的多次重排序来实现，这种类型投票协议的步骤如 下： ( 每个投票者都有自己的公钥) 1 每个投票者为自己的投票v 附加一个随机数r 2 对( v ，r ) 用每个投票者的公钥依次加密 3 再对此加密结果用每个投票者的公钥依次加密，但在每次加密前都附加一个随机 数 假设有n 个投票者，那么此时加密结果如下： e n ( i 己l l ，e r i 1 ( e l ( r l ，e t l ( e n 1 ( e l ( v ，r ) ) ) ) ) ) 4 从投票者n 到投票者1 依次把所有的选票解密，抽取出自己的随机数后，把余下 的选票部分搅乱次序，发给下一个投票者，当投票者l 把所有的选票解密后，选票的 形式如下： r ( e r i 1 ( e l ( v ，r ) ) ) 5 从投票者n 到投票者1 再依次把所有的选票解密，但这次投票者i 把选票解密， 再对解密结果签名后发送给投票者i - 1 ，投票者i 1 先检验投票者i 的签名，如果是有 效的，再对其进行解密，签名，发送给下一个投票者 此过程中的选票形式如下： s j ( e i 1 ( e l ( v ，r ) ) ) 6 投票者l 的签名由所有的投票者来验证，并且检查选票列表中的随机数以确定自 已的选票被正确计入。 在整个投票过程中，投票者的总数保持不变，投票者不会被恶意的攻击者替代， 如果投票者被替代，那么在第一轮的解密过程中他将会被发现，并且根据签名追踪找 到恶意攻击者；投票者每次乱序所有的投票使得投票的保密性得以实现；随机数r 的使用使得每个投票者能够检验自己的投票是否被正确计入。 1 4 上海交通大学硕士学位论文 3 2 有可信第三方参与的协议 这种类型的协议不仅仅有投票者参加，还有其他如认证中心，计票中心等第三方 参加整个投票过程，这些中心的参与可以节约大量的计算成本和通信成本。例如认证 中心可以对投票者的身份进行认证，确认其投票的权利，投票者只有拿着认证中心签 名的选票才可以进行投票，这样也从一定程度上减小了恶意攻击的可能性。而这种有 第三方的加入的投票协议也更接近现实生活中的真正投票过程，因此有可信第三方 ( 也即官方加入) 的投票协议成为现在电子投票协议的主流，但是第三方的加入同时 也带来了许多安全隐患，尤其是在保护投票者的隐私、选票的保密性方面和防止投票 组织者伪造选票方面，这就要运用各种密码学技术例如数字签名，匿名信道，安全多 方计算来达到一个现实生活中普通的投票过程所具有的安全特性。 3 2 1 有可信第三方参与的投票协议的主体框架 在电子投票中最著名的投票方案是1 9 9 4 年由f u j i o k a , o k a m o t o 和o h t a 提出的， 参见参考文献【l 】，这种投票方案至今仍是各种投票协议设计的主要框架。下面简单 描述它的实现过程： 1 每一个投票者向认证中心提供自己的身份证明，索取认证码 2 认证中心随机产生认证码并安全分发它们 3 投票者在投票时任意选择一个随机数作d ，和自己的选票、认证码一起加入盲签因 子，用认证中的公钥加密后发给认证中心 4 认证中心用自己的私钥解密，验证投票者的身份，如果是合法投票者则为其选票 签名，发送给投票者 5 投票者去掉自己加入的盲签因子，验证认证中心的签名，用计票中心的公钥加密 后通过匿名信道发送给计票中心 6 计票中心用私钥解密，验证认证中心的签名，公布有效选票，计数并公布结果 在这个协议中不需要每个投票者都有自己的公钥，但是所有的通信需要会话密钥 加密，此协议可以在认证中心验证选票所有者身份时有效地防止选举者多次投票；因 为投票者的盲因子的存在使得即使认证中心和计票中心联合起来也不能获得选票的 内容；而匿名信道防止了计票中心对投票者的追踪；在协议的每次通信过程中都应使 用消息认证码防止恶意攻击者在窃听过程中修改选票内容。 上海交通大学硕士学位论文 3 2 2 利用匿名信道的协议 从上面描述的投票过程中可以看出匿名信道对于保证选票的匿名性的重要性，匿 名信道是通过多个被称作m 的转发中心遵从定的协议来实现，在参考文献【9 】一 文中定义了一种a m i x - t y p e a n o n y m o u sc h a n n e l ，这种匿名信道在实现匿名转发的同 时可实现个人验证，即每个投票者在通过此匿名信道转发后仍然可验证自己的选票被 正确计入，在参考文献【8 】中介绍的是建立在参考文献【9 】基础上的带有普遍认证性质 的匿名信道。所谓普遍认证是指任何个人或中心包括没有参加投票的人在内都可以对 选票者的投票进行验证，确认所有投票的投票者被匿名信道正确转发。 假设匿名信道是由n 个c e n t e r 来实现的，定义参数如下： p u b l i c i n f o r m a t i o n ：p = k q + 1 ，( p ，q a t ep r i m e ) ：g = ( g ) m o d p ，( g i s a g e n e r a t o rm o d p ) p u b l i c k e yo f c e n t e r i ：y = g r o o d p s e c r e tk e yo f c e n t e ri ：x i z q * m e s s a g ef r o m t h es e n d e r - m d e f i n e w i = y i + l y i + 2 y na n d w n = 1 c e n t e ric o m p u t e ( 3 i 十1 ，m i + 1o ni n p u tg i ，m i 如下： g ，+ l = g ，。g m o d p m ，+ l = m 。w g 。1 。 当c e n t e ri + l 收到c e n t e ri 发给它的g i ，m i 它第一步先计算并公布g i + 1 ，并利用 零知识证明g i + l 的正确性；第二步计算并以乱序公布g i + l 和m i + l ，这时它要在乱序 的条件下向所有的人证明它的确是正确计算m i + l ，并没有篡改投票者的选票内容，这 是通过利用置换群的零知识证明来实现的。 其过程简单描述如下： 设 a = 其中a 1 ) 代指前面的g ，a ，代指前面的m h ，r 1 r 2 是由c e n t e r 产生的随机数，- 1 6 p p 删删 m m g w o 但 n 订 口 口 b 上海交通大学硕士学位论文 是一个置换。 下面证明b 的确是由a 以前面定义的方式产生的，但不暴露玎的置换信息，这是 一个交互式的零知识证明过程。 1 证明者随机选取t i z p 1 和一个置换五，计算并公布 c ：fa z o 。) g ”m o d p l 。h ，) 牡”m o d p j 2 有1 2 的可能性，验证者要求证明者出示旯和t i ，验证者检查c 是否和a ，a ，l i t 一 致 3 有1 2 的可能性，验证者要求证明者出示爿= 旯。石和r i ：t i 一 验证者通 过计算 c 锇辫m 删o d p p 检查是否能由b 产生c 。 3 2 3 利用多方计算的协议 利用多方的投票协议一样需要一个认证中心对选举者的身份进行验证，并对选票 进行签名使其成为有效选票，在投票时的通信过程也同样需要加密并使用认证码，这 些与利用匿名信道的投票协议中的处理过程类似，本处不再重复描述。这种协议的主 要思想是把选票内容分割为n 个部分，分发给n 个投票中心，利用数论知识共同计 算出最终的选举结果。 这种协议使用b e n a l o h 和y u n g 3 提出的利用部分兼容的同态加密函数组e f ( x ) 来 实现高效的零知识证明过程。利用一个定义在z p 上( p 为一个大质数) 的部分兼容 的同态加密函数可以构造一个有效的交互式的零知识证明过程， 用来证明： x l + x 2 + + x n = a + b ， x + y l ，- 1 )其中x l ，x 2 ，x n ，x ，y 是对选票的随机分割。 其中e ，( z ) 为一组满足部分兼容同态属性的函数。也即它满足在群z 上， 一 圭塑奎望奎堂堡主兰望鲨奎 e ，( 工+ y ) = e i ( x ) e 。( y ) ，当x ，y z q ；并且我们要求对所有的i ，j 下面两个分布是 在计算上不可区分的： 1 ( 巨( x ) ，e ( 】，) ) ，其中x , y 是在z 。中独立随机选取的 2 ( e ( z ) ，弓( z ) ) ，其中x 是在乙中独立随机选取的 下面简要介绍一下对以上两个等式的零知识证明。 i p r o v e + 1 ( x l ，x 2 ) 证明过程 此过程在给出e 1 ( x i ) ，e 2 ( x 2 ) 的条件下证明x l + x 2 1 ，一1 m o d q 1 证明者( 这里是投票者) 随机选取，z q 和j 1 ，一1 ) ，计算矗= 日( ，) 为承诺r 计算： k = e l ( j ( z l + ，) ) = ( e l ( x 1 ) e l ( r ) ) 。 k = e 2 ( s ( x 2 一，) ) = ( e 2 ( x 2 ) e 2 ( r ) 。1 ) 7 2 交互式证明过程 a ，验证者有l 2 的可能性要求证明者出示r 和s ，那么验证者计算r s 使上面 的k y l ，y 2 一致； b ，验证者有 1 ，2的可能性要求证明者出示 s ( x i + r ) 和f = s ( x 1 + r ) + s ( x 2 一，) 1 , - 1 ) ，那么验证者检验 一= ( e 1 ( x 1 ) e l ( r ) ) 。和e = 易( t - s ( x 。+ r ) ) i i p r o v e s u n 证明过程 此证明过程在给出e ，( 而) ，e ( _ ) ，e a ( 4 ) ，e b ( 动的条件下证明 x + x2 + x 。= a + b 1 x c 于o _ k h 证明者( 也即投票者) 随机选取z 。，计算对r 的承诺胄= 日( ) 和 墨，匕，匕，圪如下： i = e ，( z ，+ ) 对于0 s | i 蹿 上海交通大学硕士学位论文 艺= e a ( 一+ r o ) k = e ( b + ( r , ) - r o ) 证明者公布r ，r 。和k ，l ，匕，兄 2 a 存在1 2 的可能性，验证者要求证明者揭示，0 ，通过计算如下等式来验 证证明者是否诚实： r ，= h ( ) 对于1 i s n r = e j ( x 。) e 。( ) 对于1 f 玎 虼= e ( 4 ) e ( ) 】， = e6 ( b ) e6 ( 一r 。+ - ) 2 b 存在1 2 的可能性，验证者要求证明者揭示+ r 0 ) ，一r o + ：。) 和 ( x 。+ ) ，对于1 i 竹，通过计算如下等式来检验证明者是否诚实： i = e ，( x ，) e i ( ) ，对于1 i 刀 l = e 。( 4 + r o ) = 口舢 e = e 。( b + ( ，：。i ) 一) = a ：8 + ：一一 最后，验证者验证：。( x ，+ ) = ( 4 + ，0 ) + ( b 一，o + ：。r ，) 当然这种交互式的零知识证明为了达到一定的安全参数需要进行许多次交互，使 用f i a t - s h a m i r 在 4 】中的方案可以使这个证明过程简化为非交互式的，以减少证明过 程中的通信量和计算量。 下面简单描述k j 协议中一个有两个投票中心的投票协议： 1 每个投票者j 选择自己的选票k 1 , - 1 ) ，l 代表赞成，- 1 代表反对，然后随机 选取x j l 和x ；2 使得： 上海交通大学硕士学位论文 x ：”+ x j 2 1 = 一m o d q 2 投票者i 公布e ，( x ：1 ) = 口。f 和e 2 ( x ：2 ) = 口。p ，并在不暴露关于x j n ，x j z l 的 条件下证明z j l + z j 2 1 1 , - 1 ) ，证明过程如前所述 3 每个投票者分别用投票中心c l 和投票中心c 2 的公钥加密尉1 和j j 2 4 投票中心收到x ，和x ；2 1 后分别用e ，和e ：对其加密，与前面投票者公布出来的数 字比较，验证其真实性 5 每个投票中心j 把所有的x i ( j ) 加起来模q 得到r ，公布结果，而最终的投票结果是t = t l + t 2 在这个过程中每个投票者都可通过计算 e ，) = 丌e ，( x j