（计算数学专业论文）基于安全多方计算的电子投票系统应用研究.pdf

摘要安全多方计算应用研究 摘要 安全多方计算最早是由a y a o 在1 9 8 2 年通过“姚氏百万富翁问题提出。经过 几十年的不断研究，安全多方计算已取得丰硕的研究成果。目前，安全多方计算已成 为现代密码学领域中一个非常重要的分支，并成为信息安全的一个重要研究方向。利 用安全多方计算协议，一方面可以充分实现网络的互连合作，另一方面又可以保证网 上合作各方的秘密安全性。因此，安全多方计算体制在密钥管理，网上投票，电子投 标，联合签名等方面有着非常广泛的应用。同时，它与签密技术、身份认证以及其他 密码技术结合，进一步拓宽了安全多方计算的应用领域。对该课题的研究不但具有很 重要的理论意义，而且在我国经济和社会领域具有非常广阔的应用前景。 本文首先介绍了安全多方计算的定义、研究意义和发展现状，对现有的一些安全 多方计算协议进行了概述。结合安全多方计算的具体应用，对电子选举协议进行了介 绍，研究分析了f o o 协议( a f u j i o k a , t o k a m o t o ，k o h t a 提出) 中存在的一些问题。 文中着重将电子选举和安全多方计算结合起来进行研究，并取得了以下成果： ( 1 ) 提出了一种基于同态承诺可验证秘密共享的电子投票方案。该方案运用同 态承诺技术，在协议执行过程中，具有双向验证特点，能很好地区分不诚实的投票者 和不诚实的计票机构，投票的安全性和公平性得到了很好的保证。 ( 2 ) 结合给出的方案我们在计算机上进行了模拟实现。系统以j 2 e e 技术为平台， 采用m v c 架构模式，分为模型、视图和控制器三个部分，分别按功能对各种对象进行 了分割，有效地将各对象间的耦合程度降到了最低，较好地符合了实际应用环境的需 要。 关键词：安全多方计算；电子投票；同态承诺；秘密共享。 安全多方计算应用研究 a b s t r a c t s e c u r em u l t i p a r t yc o m p u t a t i o nw a sf i r s ti n t r o d u c e db ya y a oi n19 8 2t h r o u g h y a o sm i l l i o n a i r e sp r o b l e m ”r a i s e d a f t e rd e c a d e so fc o n t i n u o u sr e s e a r c h ，s e c u l e m u l t i p a r t yc o m p u t a t i o nh a sb e e ng r e a t l yd e v e l o p e da n da c h i e v e df r u i t f u lr e s u l t s c u r r e n t l y , s e c u r em u l t i p a r t yc o m p u t a t i o nh a sb e c o m ear e s e a r c hf o c u so fm o d e mc r y p t o g r a p h ya n d i n f o r m a t i o ns e c u r i t y w i t hs e c u r em u l t i p a r t yc o m p u t a t i o np r o t o c o l ，o n ec a l ln o to n l y r e a l i z ec o o p e r a t i o no fn e t w o r ki n t e r c o n n e c t i o n , b u ta l s oc a ne n s u r eo n l i n es e c u r i t yo fa l l p a r t i e s s e c r e t s o ，s e c u r em u l t i p a r t yc o m p u t a t i o nh a s av e r yw i d er a n g eo fa p p l i c a t i o n si n t h ef i l e d so f k e ym a n a g e m e n ts y s t e m ，o n l i n ev o t i n g , e l e c t r o n i cb i d d i n g , a n dj o i n ts i g n a t u r e a n ds e c u r em u l t i p a r t yc o m p u t m i o nh a sw i d e ra p p l i c a t i o n si nc o n j u n c t i o nw i t ht h e s i g n c r y p t i o nt e c h n i q u e s ，a u t h e n t i c a t i o n a n do t h e r c r y p t o g r a p h i ct e c h n o l o g i e s t h e s i g n i f i c a n c eo ft h i ss u b j e c ti sn o to n l yi nt h e o r ys i g n i f i c a n c e ，b u ta l s oi nc h i n a se c o n o m i c a n ds o c i a lf i e l d s ，a n dt h ep r o s p e c ti so p t i m i s t i c t h eb e g i n n i n go ft h i sp a p e ri n t r o d u c e s t h ed e f i n i 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 , s i g n i f i c a n c eo fr e s e a r c ha n dd e v e l o p m e n ts t a t u s ，t h e nw ep r e s e n ta no v e r v i e w f o rs o m ei m p o r t a n to fe x i s t i n gs e c u r em u l t i p a r t yc o m p u t a t i o np r o t o c 0 1 f o rt h es p e c i f i c 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 yc o m p u t a t i o n , w em a i n l yi n t r o d u c e ds o m e e l e c t r o n i cv o t i n g p r o t o c o l sa n da n a l y s i ss o m ep r o b l e m so f t h ef 0 0 p r o t o c 0 1 t h i sp a p e rc o n c e n t r a t e so nt h e 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 yc o m p u t a t i o ni nt h ee l e c t r o n i cv o t i n g , a n dh a sa c h i e v e dt h e f o l l o w i n gr e s u l t s ： ( 1 ) w eg i v e sa ne 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 cc o m m i t m d n t v e r i f i a b l es e c r e ts h a r i n g 、m mt h et e c h n o l o g yo fh o m o m o r p h i cc o m m i t m e n t ，t h i ss c h e m e h a st w o w a ya u t h e n t i c a t i o nf e a t u r e s ，c a ni d e n t i f yd i s h o n e s tv o t e r sa n dd i s h o n e s tc o u n t i n g b o d i e s ，t h es e c u r i t ya n df a i r n e s sh a v eb e e nw e l lg u a r a n t e ei nt h ep r o c e s so fv o t i n g ( 2 ) w ec o n d u c t e dac o m p u t e rs i m u l m i o ni m p l e m e n t a t i o nf o rt h eg i v e np r o t o c 0 1 t h e s y s t e m ，a d o p tt h em v c f r a m e w o r kw h i c hi n c l u d em o d e l ，v i e wa n dc o n t r o l l e r , b a s e do n j 2 e et e c h n o l o g yp l a t f o r m t h ec o u p l i n gb e t w e e nt h eo b j e c t si se f f e c t i v e l yr e d u c e dt om e e t t h ep r a c t i c a la p p l i c a t i o n k e y w o r d ：s 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 ；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 c c o m m i t m e n t ；s e c r e ts h a r i n g 1 1 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名： b ( d 年6 嗽日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名： 硕士论文安全多方计算应用研究 1 绪论 1 1 现实存在的问题 在现实生活中常常存在如下一些问题： 百万富翁问题：两个增强好胜的富翁在一次聚会中相遇，他们急欲向众人证明自 己比对方更富有，但又不愿意暴露各自财产的具体数目。那么如何比较才能知道两人 谁更富有，并保证他们各自财产的隐私性? 电子选举问题：假设某一企业要进行管理层的换届选举，企业的员工都十分珍惜 自己手中的投票权利，期望能选出一位有经验有能力的管理者带领企业不断开拓创新 以便走出当前的经营困境。但大家又不愿让他人知道自己的投票情况，担心日后遭到 其他候选人的打击报复。如何才能保证选举结果的正确性和选票的匿名性，即每个人 的选票不被泄露? 以上两类问题有相同的特点：即两方或多方参与运算，并且在计算过程中要保证 各方输入的隐私性。对于这类问题，如果存在可信、可靠的第三方，由该第三方负责 收集问题参与者的输入，并执行相应的计算，计算结束后再将结果秘密交给相应的参 与者即可。但这时候该第三方就成为问题安全性保障的关键。如果存在不诚实的参与 者通过不正当的手段将该第三方收买，那么整个解决方法的安全性就得不到保障，所 谓的“可信”第三方也就失去了存在的意义。 因此，基于以上的一些问题，如何解决计算中的安全性问题，成为了我们急需考 虑的问题，在这种情况下，促使了人们对安全多方计算的研究。 1 2 安全多方计算的定义 所谓安全多方计算问题，就是假设有n 个参与者届，p 2 9o o 9 以，每个参与者只只持 有秘密输入薯，共同计算函数值厂( 五，屯，毛) = ( 咒，儿，只) ，要求即使在某些参与 者不诚实的情况下，这种计算也能保护参与者输入的秘密性，同时保证计算结果的正 确性，使得第f 个参与者确保能够得到( 毛，咒) 以及从中推导出的信息之外得不到任何 其他的信息。这里的秘密性，是指每个人的输入除了自己知道之外其他人不能够获知。 1 3 安全多方计算协议的要求 ( 1 ) 可计算性：是指对于变量空间中的任意函数( 五，而，) ，在执行安全多方 计算协议后可以计算出与输入所对应的输出。 ( 2 ) 安全性：如果攻击者控制的参与者集合没有达到协议攻击者结构的规模， 1 绪论 硕士论文 则除了函数的最终输出外，任意参与者的输入、中间过程的输出结果都是未知的。 ( 3 ) 可验证性：是指安全多方计算协议执行的每个过程的正确性都是可验证的， 这包括输入的一致性、结果的正确性验证。 1 4 安全多方计算协议的研究意义和现状 安全多方计算是从众多具体的密码学问题中抽象出来的，对它的研究以及由此得 到的一些结论对于具体的密码学问题都具有指导意义。因此，我们可以将安全多方计 算与具体的密码学问题结合起来进行应用研究。例如对于一个具体的密码学问题，我 们可以先根据安全多方计算的研究结论，从理论上确定这个问题是否存在解决的可能 性。如果存在可以解决的可能性，则说明存在满足安全性要求的算法或模型，这时就 要寻找和设计具体的算法和模型；如果不存在，就没必要去考虑如何设计算法或模型。 可以说，安全多方安全计算是密码学协议的理论基础或者说是基石。 安全多方计算的含义极为广泛，且具有广泛的应用背景。它在电子选举、电子投 票、电子拍卖、秘密共享、网上商业谈判、门限签名、身份识别、比较薪水、年龄等 趣味性问题及场景中有着重要的作用 对于安全多方计算的应用前景，密码学领域的权威人士s g o l d w a s s e r 曾预言：安 全多方计算领域的今天，就象是l o 年前的公钥密码学。它是一个强大的工具且蕴含 丰富的理论，其实际应用刚刚开始，但必将变成计算王国的主干。 实际上任何一个协议都可以化为一个特殊的安全多方计算协议。因此，我们如果 能够安全地计算任何函数，也就掌握了一个很强大的工具。这也就是它目前成为人们 致力研究的热门课题的充分理由，也是我们研究的目的和意义所在。 第一个两方安全计算协议是a c y a 0 【l 】于1 9 8 2 年提出的，其实质就是解决两个 整数如何比较大小的安全多方计算问题。之后许多学者对安全多方计算做了大量的研 究工作，并取得了很好的成果，其中o g o l d r e i c h ，s m i c a l i 及a w i g d e r s o n 【2 ，3 】提出了 基于密码学安全模型的安全多方计算协议，并给出了当存在被动攻击者时n s e c u r e 协 议的存在性证明以及当存在主动攻击者时( n - 1 ) - s e c u r e 协议的存在性证明，从理论上 对安全多方计算的安全性进行了论述；之后，d c h a u m ，c c r e p e a u 和i d a m g a r d 分别 对信息论安全模型下当存在被动攻击时( n 1 ) - s e c u r e 协议以及主动攻击下( n 2 1 ) - s e c u r e 协议【4 】的存在性进行了证明。s g o l d w a s s e r 和l l e v i n 结合计算模型对当超过 半数的协议参与者都被买通情况下的安全多方计算协议【5 】进行了研究。 o g o l d r e i c h ，s g o l d w a s s e r 和n l i n i a l 对于不安全的通信信道、拥有无限计算能力的攻 击者模型下的安全多方计算协议 6 1 进行了研究。r o s t r o v s k y 和m y u n g 在安全通信信 道模型下对移动攻击者进行了研究【7 1 。 此后，许多学者在如何提高安全多方计算协议的效率上做了大量的研究工作， 2 硕士论文安全多方计算应用研究 并提出了一些新的安全多方计算协议的构造方法，同时，人们还对通用的安全多方计 算协议结合具体的问题进行裁减，使之与实际应用结合起来，从而更好地服务了实际 应用。 我国的学者刘木兰、张志芳也对安全多方计算做了大量的研究【3 4 1 ，先后提出了 基于乘性单调张成方案的安全多方计算协议、统计的安全多方计算协议、并行的安全 多方计算协议等，进一步拓展了安全多方计算的一般实现方法。 电子投票是一种特殊的安全多方计算问题。它是以密码学为基础，利用计算机 和网络技术来实现投票人登记及认证、电子选票分发、电子选票收集、电子投票计票 等一系列过程的选举方式。使用电子投票不仅可以简化投票手续、节省投票时间，还 能减少投票过程中的人力、物力投入，而且投票过程更加公开、客观、迅速。自从 1 9 8 1 年第一个密码学意义上的电子投票协议提出到现在，广大学者对电子投票协议 做了大量的研究工作，并取得了较多的研究成果。目前，广大学者主要是围绕提高电 子投票协议的效果和实现选举的无收据性上进行深入的探索。 1 5 论文的组织结构 第一章介绍了安全多方计算的定义以及研究的意义和现状等。第二章主要介绍与 本文联系紧密的相关技术。主要包括公钥密码体制、秘密共享、承诺、不经意传输以 及本文后面电子投票系统实现所用到的j 2 e e 技术等。第三章对目前相对研究较多的 几种安全多方计算协议进行了综述，并分别按照协议中所用到的密码学工具进行了分 类。第四章主要介绍了电子选举方面的相关知识。在这一章中，我们结合同态承诺可 验证秘密共享，提出了一种新的电子投票方案，并给出了安全性分析。在论文的最后 一章，我们利用j 2 e e 技术，结合前面提出的方案在计算机上进行电子投票系统的实 现。 3 2 相关技术介绍硕士论文 2 相关技术介绍 2 1 公钥密码体制 公钥密码体制也称为非对称密码体制。与传统的对称密码体制不同，公钥密码 体制【3 3 】的加密密钥和解密密钥是不相同的。公钥密码体制的安全性并不像对称密码学 一样，它的安全性并不是基于加密和解决算法的保密性的，它更强调的是密钥的安全 性。因此，在实际应用中我们可以将加密密钥和算法公诸于众，而只需保密解密密钥。 任何人利用这个加密密钥和算法向该用户发送的加密信息，该用户均可以将之还原。 公钥密码体制与数学是密切相关的，可以认为公钥密码体制是把数学函数应用于数 字。在加密和解密过程中，明文和密文都是数字，加密和解密就是对这些数字进行运 算的过程。公共密钥密码的优点是不需要经安全渠道传递密钥，大大简化了密钥管理。 2 1 1r s a 公钥密码体制 r s a 是目前最流行的公钥加密算法，其安全性是基于大素数分解的困难性 从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数的乘积。 系统初始化：选取两个大素数p ，g ，计算疗= p q 。随机选取加密公钥e ，使e 与 矽( ，1 ) = ( p 1 ) ( g 1 ) 互素，用欧几里得扩展算法计算私钥d ，满足e d = 1m o do ( n ) 。 公开e ，以作为公开密钥，d 作为私钥为个人保留，要注意p ，q ，矽( 咒) ，d 不能泄露。 加密：密文c = m o d n 。 解密：明文m = c d m o d n 。 2 1 2e i g a m a l 公钥密码体制 一 e 1 g a m a l 算法的安全性依赖于计算有限域上离散对数的困难性。 系统初始化：选择一个素数p ，两个随机数g ，工 p ，然后计算y = g 。m o d p 。公 开密钥是y ，g 和p ，私钥是x 。 加密：选择随机数k ，m 对应的密文为( 口，b ) = ( m y m o dp ，g m o d p ) 。 解密：m = 口扩( m o d p ) 。 2 2 秘密共享方案 秘密共享是在行个参与者中共享秘密j ，令尸= 弓，昱9o 0 9 只) 代表 个参与者的集 合，r 勋的子集的集合，且r 的子集能计算出共享秘密s 。称r 为访问结构，r 的子 集为授权子集。共享秘密s 由分发者d 分发给以个参与者只，昱，只，只有授权子集 4 硕士论文安全多方计算应用研究 中的参与者联合能恢复共享秘密s ，而非授权集合中的参与者得不到关于秘密的任何 消息，这就是一般访问结构上的秘密共享方案。 2 2 1s h a m i r 的( t n ) 门限秘密共享方案 第一个( t ，n ) 门限秘密共享方案是s h a m i r 和b l a k l e y 于1 9 7 9 年分别提出了的，该 门限方案是采用l a g r a n g e ( 拉格朗日) 插值法来实现的，具体原理是：构造一个t 1 次 多项式f 【x ) ，并将需要共享的秘密作为该多项式的常数项，每个份额为多项式f i x ) 的 输入x 的一个取值所对应的函数值。通过这样的设置，参与分享秘密的参与者只能得 到与秘密相关的一个函数值，也即是秘密的一个子份额，而不能得到秘密的全部信息。 由l a g r a n g e 插值定理可知，任意多余或等于t 个份额才可以重构该多项式从而恢复秘 密，而t - 1 个或更少的份额不能重构该多项式，因而得不到关于秘密的任何信息。 l 初始化阶段 。 分发者d 选择一个有限域g f ( q ) ( g 为大素数) ，在此有限域内选择以个元素 x i ( f = 1 ，2 ，n ) ，将五分发给以个不同的参与者p i ( i = 1 ，2 ，甩) ，五的值公开。 2 秘密分发阶段 d 要将秘密s 在行个参与者q ( i = l ，2 ，n ) 中共享，首先d 构造t 一1 次多项式 厂( x ) = j + 口l x + a 2 x 2 + + q i ，一其中a i g f ( q ) ，f = 1 ，2 ，t - 1 ，且a i 是随机选 取。 d 计算厂( ) ( f = 1 ，2 ，刀) 并将其分配给参与者只作为只的子秘密。 3 秘密恢复阶段 ，1 个参与者中的任意f 个参与者可以恢复秘密j ，不妨设置，罡，只参与秘密恢复， 出示他们的子秘密，这样得到f 个点( 五，厂( ) ) ，( 艺，厂( 恐) ) ，( ，厂( ) ) ，从而有插值 法可恢复多项式厂( x ) ，进而得到秘密j 。 厂( x ) = ( 薯) 兀导 置i j = l “ij i # t j = ( o ) = 厂( t ) 兀壬i i i o d q t 2 i j = l “i “j j l 而对于任意少于f 个参与者无法恢复多项式，因而得不到关于秘密的任何消息。 2 2 2b l a k l e y 的秘密共享方案 b l a k l e y 的( f ，n ) f - j 限方案是利用多维空间点的性质来建立的，它将共享的秘密看 成t 维空间中的一个点，每个子秘密为包含这个点的t 一1 维超平面的方程，任意t 个 t 一1 维超平面的交点刚好确定所共享的秘密，而t 一1 个子秘密( 即t 一1 个t l 维超平面) 仅能确定其交线，因而得不到共享秘密的任何信息。 5 2 相关技术介绍 硕士论文 假设n 为分解的子秘密个数，也是超曲面的总数。对b l a k l e y 门限方案作如下描 述： 将t 维空间中的点表示为矢量形式】，= ( 咒，奶，以) ( 待分解的秘密) ，刀个含有此 点的f 一1 维超曲面对应刀个f 元线性方程，于是有线性方程组口x = ，口= ( ) 膦，且任 意f 阶子式不等于0 ，x = ( 五，毛，) ，= ( 岛，如，吃) ( 分解的子秘密) ，则根据 方程组中任意t 个方程( 即已知任意t 个2 5 1 ) 可求得唯一解，此解即确定点 y = ( y l ，儿，只) 。 2 3 承诺与同态承诺 承诺是指【3 , 1 2 1 ：a l i c e 想对b o b 承诺一个预测( 即一位或者位序列) ，但是直到某 个时间以后a l i c e 才揭示她的预测。而另一方面，b o b 想确信a l i c e 承诺了她的预测 以后，她没有改变她的想法，也就是说b o b 也能验证a l i c e 的承诺。承诺的实现方法 有很多，有使用对称密码学、使用单向函数、使用模糊点等。下面介绍一个使用对称 密码学的承诺协议： 承诺：1 、b o b 产生随机位串尺，并将r 发送给a l i c e 。 2 、a l i c e 产生她想承诺的位b ( 或位串) ，将b 及r 组合成串s = b i l r 。然 后使用某个随机密钥足对s 进行加密。并将加密结果返回给b o b 。 验证：l 、a l i c e 将随机密码k 发送给b o b ； 2 、b o b 解密先前收到的密文，检验得到的明文是否是r 和承诺b 的组合 串 同态承诺最先由c r a r n e r 和d a m g a r d 提出，设日是承诺函数，h ( a ，) 是对a 的承 诺，其中，是选取的随机数。对于函数h ： 设m = h ( a i ，毛) ，3 2 = h ( a 2 ，r 2 ) ，等式y l y 2 = h ( a l + a 2 ，毛+ 吒) 成立，并且满足如下 性质： 1 、保密性：如果知道h ( a ，) ，不可能计算出任何关于a 的信息。 2 、无碰撞性：不可能计算出两个数值对( 口。，吒) 和( 呸，吒) ，使h ( a 。，毛) = 日( ，吒) 成 立。 3 、可验证性：如果知道y ，a ，厂，则任何人都可以验证y = h ( a ，r ) 。 那么我们称函数日是同态承诺函数。 2 4 不经意传输 通常一个不经意传输( o t ) 协议【2 2 2 3 斟】有两个参与者，称为发送方，简记为s ， 和接收方，简记为r 。s 掌握行个秘密聊。，鸭，r 掌握一个整数f 1 ，n 】。 一个o t 协议要满足以下的要求： 6 硕士论文安全多方计算应用研究 ( 1 ) 如果s 和r 忠实地执行协议，那么最后r 得到秘密砚，同时要求除了慨以 外，r 对s 其他的秘密一无所知。 ( 2 ) 协议执行完后，s 对r 的选择f 一无所知，即s 不知道r 到底选了哪一个 秘密。 目前o t 协议可以大致归类为如下几类：r a b i n o t 、1 - 2 o t 、1 - n o t 、k n o t 、 q u a n t u m o t 、c o t 等。 2 4 1r a b i n 的o t 协议 这是由m r a b i n 于1 9 8 1 年提出来的。该协议是一个双方的协议，其要解决的问 题与目前的情况稍有不同，但是可以证明它与1 - 2 o t 是等价的。假设发送方s 以一 个1 2 的概率传输一个比特的秘密j 给接收方r 。协议的过程如下： s 选择两个大的强素数p ，q ，计算，l = p q ，并随机的选择t z n + ，将( 以，( 一1 ) 础t ) 发 送给r 。r 选择x z n + ，计算a = x 2 ( m o d n ) ，并将a 发送给s 。s 很容易求出a = 工2m o d n 的四个平方根，并随机的选择一个记为b ，发送给r 。 r 收到b 后，检查b = + x ( m o d n ) 是否成立。若成立，r 什么也得不到；否则，r 利用g c d ( x + b ，n ) 可以分解n ，并计算： f 0 ，若( 一1 ) 3 t 2 是模n 的二次剩余 i1 ，若( 一1 ) s t 2 不是模n 的二次剩余 在a 的模疗的四个平方根中，恰好有两个模，z 同余于z 。因此，r 将以1 2 的概 率恢复出秘密5 ；但是s 不知道b 是否收到了秘密s 。 2 4 2n a o r 的o t n l 协议 系统初始化：假设g 为大素数，g 为z 口的一个生成元。发送方s 随机选择一个 数，；，。s 再随机选择he z q + ，并且计算9 6 。发送方s 将，：| 和9 6 发送给接收 方r 。同时，s 事先计算( ) 6 ，其中l s j 5 ，l 。 协议的第一步：接收方r 确定自己的选择i ( 1 ，2 ，刀) ，随机选择k z ，令 眺= g ，r 计算p k o = ，；g ，并将p * o 发送给发送方s 。r 的解密密钥为( 9 6 ) = ( 眺) 6 。 协议的第二步：发送方s 接收到砘，计算( 砘) 6 ，对l 万，计算 似，) 6 = q y ( p k o ) 。s 选择随机串r ，并且计算日( ( 础，) 6 ，r ，_ ，) o s ，其中h 为h a s h 函数。发送方s 将( ，h ( ( p k ，) 6 ，j ) o s j ，1 j 以) 传送给接收方r 。 最后r 用h ( ( 眺) i l ，厂，f ) 解密得到s ，。 2 5j a v a 安全模型 j a v a 是由s u n 公司开发的，经过十几年的不断完善，它已发展成为人类计算机 7 2 相关技术介绍硕士论文 史上影响最深远的编程语言，从某种程度上来看，它甚至超出了编程语言的范畴，成 为一种开发平台，一种开发规范。目前，作为一个网络平台，j a v a 的安全体系结构越 来越完善。另外，j a v a 2 对密码学提供了完整的支持，其内部已经内置了j a v a 2 安全 体系结构核心和j a v a 加密体系结构( j c a ) ，两者构成j a v a 2 所带的安全平台。鉴于 j a v a 的诸多优点及对密码学的良好支持，在本文的电子投票系统中将采用j a v a 语言 进行设计。 2 6j 2 e e 平台简介 j 2 e e 是一套全然不同于传统应用开发的技术架构，包含许多组件，主要可简化 且规范应用系统的开发与部署，进而提高可移植性、安全与再用价值。 j 2 e e 可分为经典的j 2 e e 和轻量级的j 2 e e 。经典的j 2 e e 采用f _ j b 作为j 2 e e 的 核心，开发成本高，部署成本也高，只有具备较强编程能力的程序员才能很好的使用 它，从而限制了j 2 e e 的发展和应用。由此，人们开始思索对j 2 e e 的改进。轻量级 的j 2 e e 正是在这样的一种背景出现的。轻量级j 2 e e 在保留经典j 2 e e 的应用架构、 良好的扩展性、可维护性的基础上，对经典j 2 e e 进行了简化，较好地符合了实际的 应用领域。通过简化，使得广大程序员都能迅速掌握这种编程技能，j 2 e e 的应用得 到了极大地发展。j 2 e e 技术的基础就是核心j a v a 平台或j a v a 2 平台的标准版，它不 仅巩固了标准版中的许多优点，同时还提供了对e j b 、j a v as e r v l e t sa p i 、j s p 以及 x m l 技术的全面支持，从而大幅降低了企业将其产品投放市场的时间，节约了成本， 使得企业在激烈的市场竞争中能迅速占领市场，赢得发展的主动力。由于轻量级的 j 2 e e 的广泛优点，本文中主要采用轻量级j 2 e e 进行系统的开发。 8 硕士论文安全多方计算应用研究 3 几种常见的安全多方计算协议 目前对安全多方计算协议的研究成果很多，但就其中使用的密码学工具而言，可 将安全多方计算协议概括为以下几种：基于o t 的安全多方计算协议，基于可验证秘 密共享的安全多方计算协议，基于同态门限加密的安全多方计算协议等。 大部分安全多方计算协议都是按照下面的一种思路进行设计的。 ( 1 ) 确定安全多方计算协议计算域上的原子运算，使得域上的所有运算都可以分 解为这些原子运算的组合。 ( 2 ) 确定一种恰当的秘密分享方案，使得在秘密恢复阶段，只有满足条件的参与 者集合才能恢复秘密，而其他的参与者不能得到秘密的任何信息。 ( 3 ) 设计所有原子运算的安全多方计算协议。 ( 4 ) 得到任何函数的安全多方计算协议。 下面我们结合上面的思路，对这几种安全多方计算协议进行介绍。 3 1 基于o t 的安全多方计算协议 这种类型的安全多方计算协议，其计算域为g f ( 2 ) 。由于g f ( 2 ) 上的所有运算都 可以由“异或运算( 记作国)“与运算”( 记作) 及“非运算”( 记作一) 组成，因 此，这些运算也构成了该类型协议的原子运算。 秘密共享方案采用( 刀，行) 门限方案：设要被分享的秘密为b 。分享阶段：随机选 择n 个比特6 i ，包使得b = 岛。吃o o 吃，并将岛秘密发送给只；恢复阶段：各只公 开各自的岛，则被分享的秘密为b = 6 l06 2o o 吃。 下面我们分别按照原子运算就两方的让算情形进行介绍 ( 1 ) 二元比特异或运算 设运算为a0 6 ，其中口，b 已被分享在参与者中，即a = 口lo 口：o oa 。， b = 岛o6 2o o 吃，参与者b 知道q ，勿。则各参与者见将各自计算的结果设置为 ，；= 口f + 岛 很明显o r 2o 口o = ( 口i + 岛) o ( 口2 + 6 2 ) o o ( 口。+ 吃) = 口0 6 即二元比特异或的结果已经被分享在参与者之中。 ( 2 ) 一元比特非运算 即求万，其中口已被分享在参与者中，即a = a 。o 口：0 o 巴，参与者b 知道q 。 各参与者只将各自分享的结果设置为：若f = i o 则，：= 磊：否则，；= q 。通过上面的设 置石已经在参与者中进行了分享。 可以验证： 9 3 几种常见的安全多方计算协议 硕士论文 ，io r 2o o r = ( qo 吒o o 口f 一1 ) o 瓦o ( 气+ lo o q ) = 万 ( 3 ) 二元比特与运算 即求a b 。二元比特与运算相对复杂一些，为了叙述方便，在这里主要介绍运算 的参与者是两方的情况。这时就要用到0 t 协议。具体的说，参与者p 。随机选择毛 g f ( 2 ) ，令 r x = z l + a i 岛，r 2 = z l + 口i ( 岛+ 1 ) ，r 3 = 毛+ ( a l + 1 ) h i ，= z i + ( a l + 1 ) ( 岛+ 1 ) 然后，p l 和岛执行一个o t l 4 ：p 。作为发送方，掌握秘密r l , r 2 ，吩，r 4 ；p 2 作为接收 方，掌握选择i = l + 2 a 2 + 红 1 ，2 ，3 ，4 。协议执行完之后，见得至l j z 2 = ，：。 从下面的表容易看出，z + z = a b 表3 1 a b = ( 口。+ 口2 ) ( 6 l + 6 2 )i = 1 + 2 a 2 + 6 2z 22 ，： a 2 = 0 ，6 2 = 0q 6 l l g l + 口l 岛z a 2 = o ，6 2 = 1a 。( 6 i + 1 ) 2 毛+ 口l ( 6 i + 1 ) a 2 = l ，如= 0( q + 1 ) 包 3 毛+ ( a l + 1 ) 6 l a 2 = 1 ，6 2 = 1( 口i + 1 ) ( 岛+ 1 ) 4 z l + ( a l + 1 ) ( 6 l + 1 ) 3 2 基于可验证秘密共享的安全多方计算协议 这种类型的安全多方计算协议，其计算域为f ( p ) 。 秘密共享方案采用s h a m i r ( n ，f ) 门限方案，在恢复秘密阶段只要有f 个及以上参与 者就可以通过拉格朗日插值多项式就会恢复出秘密了。 协议的初始阶段：每个参与者将自己拥有的自变量以一个f ( p ) 上的t 一1 次随机多 项式f ( x ) 进行分享，并将f ( i ) r o o d p 秘密发送给只。 ( 1 ) 二元加法运算 即求a + b m o d p ，其中a 被分享在z ( 工) 中，b 被分享在五( 功中，协议的参与者e 知道f o ( i ) r o o dp ，五( i ) m o dp 。 协议执行中，每个参与者只需将各自的值设置为f o ( i ) + a ( i ) = z 岫( f ) 。 很显然a + b 已在正+ 。( 力进行了共享，在协议的最后只需执行拉格朗日插值多项 式就会恢复出a + b 了。 ( 2 ) 二元乘法运算 设要求的运算为a b m o d p ，其中a 被分享在z ( z ) 中，b 被分享在以( z ) 中，协议 的参与者只知道f o ( i ) m o d p ，l ( i ) m o d p 。求a b m o d p 相当于寻找f ( p ) 上的另一个t - 1 次多项式厶( 工) ，使得a b m o d p 被分享。 l o 硕士论文安全多方计算应用研究 令z ( 力= l ( x ) a f x ) ，显然有f o ( o ) = a b 。 根据拉格朗日插值多项式， 2 t - i a b 2 ，置i 兀 ：兀 耥鹏) ) _ 善 彳南肥堋) m o d p ) m o d p l ，玉2 卜i ，村i s j s 2 t i j 卅 此时，如果只( 1 l ，2 2 t - 1 ) ) 使用f ( p ) 上的f 一1 次随机多项式五( x ) 将 ni ， 2 1 尚驰w f f ) l n 甜p i ，2 t l ，t ， 进行分享，_ k r , - ( o ) ，将( ) l n o d p 秘密发送给乃最后每个乃将得到 2 ，一1 ，舢) r o o dp 】r oo dp ，= l 令2 各+ ”+ 气2 卸1 1 d d p ，则有： 1 ) 厶( 0 ) 2 ( 0 ) + + 五纠) ( o ) 2 气+ 乞+ 一+ 气神2 曲1 n o d p 2 ) 厶( f ) 2 + + 名砷( i ) 只有乃才知道。 3 3 基于同态门限加密的安全多方计算协议 具有加法同态性的门限密码体制的定义如下： 设( s k ，p k ，m ，c ，e ，d ) 是一个公钥密码体制，其中政是私钥，肚是公钥，m 是 明文空间，c 是密文空间，e 和d 分别是加密和解密算法。对任意的明文m m ， 加密为e 肿( 朋) ；解密为o a k ( c ) = 玩( e 肚( ，1 ) ) = m 。我们称该密码体制具有加法同态性， 是指对于任意的m ，m ：m ，有e 融( ) ( ) = e 砂( ，l l + ) 。也就是说可以由m l 和 鸭的密文直接得到，l i + 鸭的密文。 协议的初始阶段：公开公钥肿，采用特定的秘密分享方案将私钥妣在参与者中 进行分享，参与者只得到子私钥s 岔。该类型协议的原子运算为二元加法运算和二元 乘法运算。在协议执行之前，参与者需将各自的输入使用肚加密，将密文m = e “( m ) 公开( 为了方便起见，我们将m 对应的密文用m 表示) ，将m 保密。 ( 1 ) 二元加法运算 设要进行的运算为a + 6 ，运算前知道口和b 。由于同态门限加密具有的加法同态 性，任何人可得到口+ 6 = a + 6 。 ( 2 ) 二元乘法运算 3 几种常见的窒全兰查生簦堡堡生! ! 垒兰 _ _ _ - _ - _ _ _ _ _ _ _ _ _ l _ - _ _ 一。一 设要进行的运算为a b ，要求执行协议后得到a b 执行过程如下： 1 ) 各参与者p i 随机选择喀，使用公钥p k 将4 加密，公开密文虿，将西保密。 2 ) 由同态加密的“加法同态性 ，任何人可计算嚷+ + d n + 口2 盔+ 吃+ 口。 3 ) 所有参与者将百i j 砑了口解密，得到d _ 匾+ 畋+ + 反+ 4 。 4 ) 指定i o ( i o l ，以) ) ，各参与者p i 设置自己的q ：若i - - i o ，a t - - - d 一噍；若 f 乇，贝0 q = 一或 很明显有q + + a n = ( 一4 ) + + ( 一吃一。) + ( d 一吒) + ( 。噍+ 1 ) + ( 一t ) = 口。 5 ) 每个参与者知道自己的a t 和石，由同态体制的同态性，参与者p 可求出 币= q o 云。公开币，将q 保密 6 ) 由于a b - - ( a i + + q ) 6 = 口1 6 + + 口。b 。 至此，乘法运算结束。 1 2 因此，所有的参与者均可计算口6 ， 硕士论文 安全多方计算应用研究 4 电子选举协议 电子选举【2 7 娜，2 9 , 3 0 , 3 1 1 是密码学的一个重要的应用方面，它以各种密码学技术为理 论基础，通过计算机和网络来完成选举的整个过程。与传统的人工投票相比，电子选 举具有明显的优点，不仅可以节省大量的人力物力，而且能在一定程度上保证选举的 公正性。电子选举与安全多方计算是紧密相连的。电子选举问题是目前安全多方计算 领域非常热门的一个研究方向，在现实生活中具有非常重要的意义。本章首先介绍电 子选举的背景以及f 0 0 协议( 该协议是以a f u j i o k a , t o k a m o t o ，k o h t a 的名字命名) ， 最后我们将结合安全多方计算给出一个基于同态承诺的可验证秘密共享电子投票方 案。 4 1 电子选举的背景 4 1 1 电子选举的发展 出于对选举的公平性追求，在人类漫长的历史长河中，人们一直憧憬选举方式的 改变。1 8 8 4 年，美国著名的点学家t h