（计算机软件与理论专业论文）基于安全多方计算的电子评审协议的研究与实现.pdf

基于安全多方计算的电子评审协议的研究与实现 计算机软件与理论 倪江衡 龙冬阳教授 摘要 电子投票以各种密码技术为理论基础，运用现代计算机和网络技术来实现投 票功能。保密计票值的电子评审是一种用途广泛的特殊电子投票，该方案要求输 出评审结果，即秘密地比较票数是否大于一个合格的门限，但同时又不泄露最终 计票值。现有的电子投票方案多数采用传统密码方法，着重实现对投票结果的普 遍验证性，因此不能直接应用于电子评审。 安全多方计算( 简称s m c ) 是指在一个互不信任的多用户网络中，两个或 多个用户能够在不泄漏各自私有输入数据时协同合作执行某项计算任务。从广义 上讲，所有的密码学协议都是安全多方计算的一个特例。电子评审是安全多方计 算的典型应用之一。结合安全多方求和协议和保密比较协议，可以设计一种无计 票中心的电子评审协议，投票者是评审系统的主体，每个投票者都可以计票，从 而杜绝了多计票中心系统中的计票中心联合作弊问题。 本文利用安全多方计算以及密码学的基本工具进行电子评审协议的设计。 首先对z h 电子评审协议进行了研究，详细分析了该协议的安全性，并深入探 讨了该协议的不足点。接着，分析了公告板机制、使用单向函数的承诺协议， 并提出了一个高效的安全两方计算协议基于b r e s s o n 公钥密码算法的保密 比较协议，采用两轮交互，适合两个大整数间的公平保密比较。在此基础上， 利用z h 电子评审协议的基本思想，设计了一个恶意模型下的电子评审协议， 具有更好的抗攻击性和实用性。最后，以新的协议为核心，设计了一个电子评 审系统，介绍了该系统的体系结构和模块功能，并探讨了系统关键部分的实现 技术。 关键词：电子评审，电子投票，安全多方计算，保密比较协议 r e s e a r c ha n di m p l e m e n t a t i o no fe l e c t r o n i cj u r yv o t i n gp r o t o c o lb a s e do n s e c u r em u l t i - p a r t yc o m p u t a t i o n c o m p u t e rs o f t w a r ea n dt h e o r y n ij i a n g h e n g p r o f l o n gd o n g y a n g a b s t r a c t e l e c t r o n i cv o t i n g ，w h i c hi sb a s e do na l lk i n d so fc r y p t o g r a p h yt e c h n o l o g i e s ，u s e s a d v a n c e dc o m p u t e ra n dn e t w o r kt e c h n o l o g yt or e a l i z et h ef u n c t i o n so fv o t i n g e l e c t r o n i cj u r yv o t i n gi sas p e c i a le - v o t i n gw h i c hn e e d st od e t e r m i n ew h e t h e rt h e t a l l ye x c e e d sap r e - s p e c i f i e dt h r e s h o l dw h i l ei td o e sn o td i s c l o s et h ef i n a lt a l l i e s m o s t p r e v i o u se - v o t i n gs c h e m e s ，w h i c hu s et r a d i t i o n a lc r y p t o g r a p h yt e c h n o l o g i e s ，a r en o t s e c u r ee n o u g hf o re l e c t r o n i cj u r yv o t i n gb e c a u s et h e i rf i n a lt a l l i e sa r ep u b l i ct oa l l v o t e sa n de a c hb a l l o tc a nb ee a s i l yd e d u c e df r o mt h er e s u l 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 n ( s m c ) r e f e r st ot h ep r o b l e mw h e r et w oo rm o r e p a r t i e sw a n tt oj o i n t l yc o m p u t eat a s kb a s e do nt h e i rp r i v a t ei n p u t s ，w h i l en op a r t yi s w i l l i n gt od i s c l o s eh i sp r i v a c yt oa n yo t h e ro n e g e n e r a l l ys p e a k i n g ，e v e r yc r y p t o l o g y p r o t o c o li sas p e c i a li n s t a n c eo fs m c e l e c t r o n i cj u r yv o t i n gi sat y p i c a la p p l i c a t i o no f s m c w ec a na p p l ys m ct e c h n o l o g i e st od e s i g n i n gae l e c t r o n i cj u r yv o t i n gp r o t o c o l w h i c hd o e sn o th a v ec o u n t e rc e n t e r s i nt h ee l e c t r o n i cj u r yv o t i n gp r o t o c o l ，v o t e r sa r e p r i n c i p a lp a r t sa n de a c hv o t e rc a nc o u n t et h eb a l l o t s s ot h es i t u a t i o nt h a ts o m e c o u n t e rc e n t e r sc h e a tj o i n t l yw o n ta p p e a r i nt h i sp a p e r , a ne l e c t r o n i cj u r yv o t i n gp r o t o c o lb a s e do nt h et o o l so fs m ca n d c r y p t o g r a p h yt e c h n o l o g i e si sd e s i g n e d f i r s t l y , t h i sp a p e rh a ss t u d i e dz he l e c t r o n i c j u r yv o t i n gp r o t o c o lw h i c hi sd e s i g n e db yz h o n g h o n g ，a n da n a l y s e dt h ep r o t o c o li n d e t a i l ，t h e ns e v e r a ls h o r t a g e si nt h ep r o t o c o la r ef o u n d s e c o n d l y , an e we l e c t r o n i c j u r yv o t i n gp r o t o c o lw h i c hi ss t i l ls e c u r ei nt h em a l i c i o u sm o d e li sd e s i g n e db a s e do n z hp r o t o c 0 1 t h ep r o t o c o lp r o p o s e di nt h i sp a p e rc o m b i n e sb u l l e t i nm e c h a n i s ma n d c o m m i t m e n tp r o t o c o l ，a n dan e wp r i v a t ec o m p a r i s o np r o t o c o lw h i c hi sb a s e do n i l l b r e s s o np u b l i ck e yc r y p t o s y s t e m f i n a l l y , t h i sp a p e ri n t r o d u c e st h e s y s t e m a t i c s t r c t u r e sa n dm o d u l e sf u n c t i o no ft h ee l e c t r o n i cj u r yv o t i n gs y s t e mb a s e do nt h en e w p r o t o c o l ，a n da n a l y s e st h et e c h n o l o g ys c h e m e so ft h ek e r n e lp a r t so ft h es y s t e m k e y w o r d s ：e l e c t r o n i cj u r yv o t i n g ，e l e c t r o n i cv o t i n g ，s e c u r em u l t i p a r t yc o m p u t a t i o n ， p r i v a t ec o m p a r i s o np r o t o c o l 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：百瓷硝砖 日期：避年r 月g 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：尔删多 日期：加g 年，月ge t 导师签名： 日期：涨年1 酽日 第1 章绪论 1 1 研究背景 第1 章绪论 电子投票是密码学及电子商务研究的热点问题，但在提出之后的很长一段 时间内，其发展一直比较缓慢。直到1 9 世纪中叶，密码学突破军事应用的限制， 在其它民用领域也得到广泛的应用，电子投票的研究才有了较大的进展。另外， 由于密码学研究本身的飞速发展，特别是公钥密码技术的出现，较大地促进了 人们对电子投票问题的研究。 电子投票是对传统投票的电子化，利用先进的计算机、通讯设备以及密码 学技术，使投票者可以利用计算机终端通过通讯设备完成投票工作。但电子投 票是利用开放的网络完成投票工作，使得选票信息很容易被截获甚至篡改，因 此有必要保密投票者的身份，同时防止恶意者的对系统的破坏行为。因此，除 了要求用于投票的计算机设备及网络系统正常运转之外，还必须以密码学技术 为基础，设计一个安全有效的电子投票协议。 针对不同的应用环境和不同的安全需求，设计特殊领域的电子投票方案是 当前研究的一个热点问题。现有的投票方案还无法解决一些特殊的投票问题， 比如含权投票问题、电子评审投票问题等等。 电子评审( e l e c t r o n i cj u r yv o t i n g ) 是一种特殊的电子投票，其应用非常广泛， 如法庭审判表决、股东决议、商务伙伴的投资抉择等等。在这些场合，因为投票 参与者会比较少，如果公开计票的最终结果，贿选者会很容易推断出投票者的投 票意向。因此，这些投票场合不允许泄露任何投票者的秘密，计票结果也需要严 格保密。在保密计票结果的情况下，怎样才能达到实际评审的安全要求，同时又 保证投票过程的公平性、评审结果的正确性，这正是电子评审与一般电子投票的 关键差别。 1 2 研究历史与现状 电子评审作为一种特殊的电子投票，比一般电子投票提出了更高的要求， 即不泄露最终的计票结果。而一般电子投票的研究也正是电子评审的研究基础。 中山大学硕士学位论文 早在1 8 8 4 年，t o m a se d i s o n 就发明了一种电子投票设备，他想将该设备卖 给m a s s a c h u s e t t s 州的立法机关，但最后没有被采用。后来，哥伦比亚广播公司 利用计算机技术预测投票的结果。在1 9 9 2 年美国民主党的全国代表大会上，开 始使用触摸屏进行投票，而共和党则使用计算机对投票进行管理。到2 0 0 1 年， 巴西已经大规模地使用触摸屏投票设备进行选举。但这些电子投票的方案大多 只是利用计算机或其它电子设备进行日常的投票管理，人们仍然需要到投票站 进行投票【i 】。 采用传统密码学理论进行电子投票的研究已有二十多年历史，1 9 8 1 年， c h a u m 首先提出电子投票的思想【2 】，设计了一种通过匿名信道传递选票的模型， 成为了第一个现代意义上的电子投票协议，该协议通过让投票者利用数字假名 进行投票来实现选票的匿名性。1 9 8 5 年，c o h e n 和f i s c h e r 提出了一个电子选举 方案【3 】，该方案假定选举机构不作弊，采用盲签名及混合网( m i xn e t w o r k ) 消除 投票者身份标识与选票的关系，但要求所有投票必须同时进行。接着b e n a l o h ， y u n g 等也提出了基于同态加密技术的电子投票方案【4 】。1 9 9 2 年，三位日本学者 f u j i o k a ，o k a t n o t 和o h t a 提出一个实用的电子投票协议1 5 】，利用盲签名对投票 者身份标识进行认证，通过匿名信道发送选票，消除投票者身份标识与选票的 关系。后来许多大学和研究机构都以该协议为基础，对其进行改进，丌发出了 实验性的电子投票软件系统。但此方案不允许选民弃权，否则机构管理者可以 利用弃权票伪造合法的选票。为防止贿赂选举和选票交易，1 9 9 4 年，b e n a l o h 和t u i n s t r a 首次提出了无收据的自由选举【6 】，并通过一个相当强的物理假设 投票站来实现。1 9 9 7 年，c r a m e r ，g e n n a r o 和s c h o e r a n a k e r s 采用多个授权机构， 利用同态加密系统、公告板和零知识证明等方法，提出了一个电子投票方案【7 1 ， 该方案具有普遍验证性，但注册后不允许弃权，也不具有无收据性，而且采用 了混合网、零知识证明等技术，通信代价和计算复杂度都是指数级的，不适合 大规模选举。 现有的电子投票方案都公布投票结果以实现投票的可验证性，因此这些方 案不能直接应用于电子评审问题。2 0 0 4 年，h e v i a 等人提出了个电子评审协 议【8 】，采用同态密码系统对选票加密，从而隐藏计票结果丁，把所有大于合格 门限的数值加密后保存在集合s 中，再测试，是否在s 中。 2 第l 章绪论 仲红在文献 9 】中提出了一个电子评审方案，采用安全多方计算技术，所有 投票者协作计算投票结果；并引入一个不可信第三方服务器，向每个投票者提 供随机数，以隐藏真实的选票信息，从而实现保密计票值的目的。 1 3 电子投票介绍 1 3 1 电子投票的定义与要求 电子投票的定义如下【1 0 】：电子投票以密码学为基础，使用计算机、网络通 讯等技术，用以取代传统投票方式而实现投票功能的软件、硬件系统。要使电 子投票安全可靠地进行，必须要保证计算机和网络系统能够正常运转，保证它 们能够抵御各种恶意的攻击，使投票活动能够正常的进行。另外，最重要的就 是，必须采用先进的密码学技术设计出安全有效的电子投票协议。 理想的电子投票系统的目标，就是通过计算机终端和通信网络来完成投票 功能，且以最小的代价实现最多的安全和性能需求。一般来说，电子投票系统 应该满足如下的要求： ( 1 ) 完整性：所有有效的选票都应该被正确地记入投票结果。 ( 2 ) 健壮性：不诚实的投票者不可能破坏整个选举过程；即使部分系统出 了问题，投票系统仍能正常工作。 ( 3 ) 匿名性：投票者的身份和所投选票的内容不可能被除本人以外的任何 组织或个人得到。 ( 4 ) 唯一性：每个合法投票者不可能把自己的选票投寄两次。 ( 5 ) 合法性：没有投票权的人不能参加投票活动。 ( 6 ) 公正性：投票结果在投票过程中不会被提前泄漏，投票不受任何影响。 ( 7 ) 可验证性：每个投票人都可以验证自己的选票是否被合法统计到最后 的结果中，任何人都可以对投票结果进行验证。 以上是一个电子投票系统应该满足的基本要求。为防止贿选和强制投票，实 现更高意义上的安全性，更强的目标是无收据性和抗强制性。 ( 8 ) 无收据性：任何人不能获得、构造收据来证明选票内容，无法向贿选者 提供自己的投票证据，从而阻止选票买卖。 中山人学硕一i ：学位论文 ( 9 ) 抗强制性：选举过程中选民可以欺骗攻击者，谎称按攻击者指令投票， 但仍按自己的意图投票，实现真正的自由选举。 1 3 2 电子投票常用方案分析 根据电子投票系统所采用的不同密码工具，大致可以分为匿名信道混合网、 盲签名、同态加密、可验证秘密共享等几类方案。 一、基于匿名信道混合网的方案 基于匿名信道混合网的方案利用匿名信道或混合网来实现投票的匿名性。 通过混合网中各种形式的置换，得到的最终输出就无法和原始的输入一一对应。 打开选票前，混合器必须证明选票的合法性。文献 1 1 】是采用混合网实现的投票 方案，文献 1 2 币j j 用群签名协议和时限承诺协议，给出了一种基于匿名通讯信道 的电子投票方案。 安全的混合网可以起到匿名信道的作用，只有所有混合网服务器联合起来， 才能确定输入输出密文的关系。此类方案可以处理“y e s n o ，“k - o u t o f - m ”等 多种形式的选票。但是需要大量的计算来给出零知识证明，以保证每个混合器 在处理选票过程中正确置换且没有篡改选票。而且此类方案没有底层密码支持， 很难实现。混合器越多，系统性能越差，不能抵抗服务器单点失败。因此，该 类方案不适合大规模选举。 二、基于盲签名的方案 盲签名指签名者在不知道签名内容的情况下进行数字签名，该技术已广泛应 用于电子投票方案中，既可以认证选民身份的合法性，又不会泄露选票的信息。 因此，盲签名是消除投票者身份与选票之间关系从而实现匿名投票的另一类方 法。利用盲签名，认证机构在不知道选票内容的情况下，对选民身份合法性进行 认证，从而不会泄露选票内容。文献 5 是比较典型的基于盲签名的电子投票方 案，s e n s u s 系统就是基于该方案而实现的一个电子投票系统。采用盲签名技术的 方案计算量比较小，允许多种选票形式。但该方案只有选民自己才能监督投票结 果，而且一般需要匿名信道，也不允许投票者弃权。 4 第l 章绪论 三、基于同态加密的方案 在基于同态加密的投票方案中，利用同态公钥密码系统的同态性，将选票 加密，可以直接对选票密文进行处理，从而隐藏了选票的内容，保护选民的隐 私，实现了投票的匿名性。利用加同态性质可以实现对选票密文不解密的求和 操作，计票中心直接对选票密文求和，再解密求和的结果，得出计票值。 为防止单个计票中心的作弊行为，通常将解密密钥拆分，分发给多个计票 服务器，每个服务器拥有其中一个分片，通过门限秘密分享方案恢复原始密钥。 基于同态加密的方案中，由c r a m e r ，g e n n a r o 和s c h o e n m a k e s 提出的方案是一 个较好的方梨7 1 。同态加密方案最初只能处理最基本的“y e s n o 选票，后来扩 展到其他形式的选票形式。基于同态加密的方案实现比较容易，计票高效，但 由于需要用到零知识证明，计算成本仍然较高。 四、基于可验证秘密分享的方案 基于可验证秘密分享( v e r i f i a b l es e c r e ts h a r i n g v s s ) 的投票方案，将选票拆 分成多个秘密分片，发送给若干个计票机构，每个机构得到其中的一个分片。 只有计票机构的数目达到某个门限值后，才能恢复出完整的选票。s c h o e n m a k e 提出个可公开验证的v s s 协议【1 3 】，并应用于电子投票协议的设计中，统计计 票结果需要求解离散对数难题。 基于可验证秘密分享的方案，选票发送之后由所有计票机构联合恢复完整 的选票并进行计票，实现对投票者隐私的保护及投票的匿名性。但必须保密计 票的中间结果，否则会影响投票者的投票倾向，从而影响投票的最终结果。此 类方案的选票形式为“y e s n o ”，不能处理多候选人的投票方案，也不能防止计 票机构的联合作弊，而且通信复杂度较大。 1 4 电子评审问题 现有投票方案中采用的密码技术尚无法解决一些特殊领域的投票问题，比 如含权投票、电子评审等等。针对不同的应用环境和不同的安全需求，设计特 殊领域的电子投票方案是当前研究的一个热点。 上一节对电子投票进行了概述，电子投票的研究是电子评审研究的基础， 5 中山大学硕士学位论文 电子投票协议的要求也是电子评审协议必须满足的。在不公丌计票结果的情况 下，怎样达到实际评审的安全要求，同时保证计票的正确性、公平性，这正是 电子评审与一般电子投票的关键差别。 电子评审是一种特殊的电子投票，安全的电子评审除了应具有电子投票的安 全性质以外，还应该满足电子评审的特殊要求。如果电子评审方案满足投票的隐 私性、无收据性、计票的完整性、计票结果的保密性和无争议性、系统的健壮性， 则称为安全的【1 4 】： ( 1 ) 投票的隐私性：任何投票人不能得到其他人的选票值。 ( 2 ) 无收据性：任何人不能获得、构造收据向贿选者证明选票的内容。 ( 3 ) 计票的完整性：所有合法的选票都能正确地计入投票结果。 ( 4 ) 计票结果的保密性和无争议性：除了计票结果是否大于等于指定的合格 门限m 外，不泄露任何计票信息，所有投票人都确信计票结果是正确的。 ( 5 ) 系统的健壮性：在n 个投票人中，对任何小于等于n m 个成员的错误， 不能影响投票系统的正常运行。 电子评审是一种用途广泛的特殊电子投票，因为参与评审的投票者很少，直 接使用现有的电子投票方案很难实现实际评审的安全性。电子评审要求保密最终 计票结果，只要判定总票数是否达到一个合格的门限值，即可得出评审结果，从 而判定候选人合格或不合格，方案通过或不通过【l4 1 。 现有的电子投票方案大多采用传统密码方法，一般在计票阶段结束后，都 要公开计票结果，实现对投票结果的普遍验证。因此现有方案不能直接应用于 电子评审。2 0 0 4 年，h e v i a 等人提出了一个电子评审协议【8 】，主要思想是采用 同态密码系统加密选票，从而隐藏计票结果，把所有大于合格门限的数值加密 后保存在一个集合中，再测试计票结果是否在这个集合中。该方案采用了混合 网对集合中的数据进行秘密置换，以防止测试成功时泄露计票结果。但混合网 服务器掌握了集合中的数据，可能会泄露计票结果。另外混合网是一种具有理 论意义的假设，在实际评审环境中很难实现。 仲红在文献 9 提出了一个电子评审方案，采用安全多方计算技术，所有投 票者协作计算投票结果，并引入一个不可信第三方服务器，向每个投票者提供随 机数，用于隐藏真实的计票值。 6 第l 章绪论 1 5 本文研究工作及章节安排 本论文研究安全多方计算技术及电子评审协议。分析了仲红提出的一个电 子评审方案，并深入探讨了该协议的不足点。在此基础上，增加了公告板机制、 承诺协议验证等手段，并提出了一个高效的保密比较协议基于b r e s s o n 算 法的保密比较协议，从而设计了一个恶意模型下的电子评审协议，具有更好的 抗攻击性和实用性。最后，以新的协议为核心，设计了一个电子评审系统，详 细介绍了该系统的体系结构和模块功能，并探讨了系统关键模块的实现技术。 本文由六个章节组成，其结构安排如下： 第1 章简要介绍了电子投票以及电子评审的研究背景、研究现状，对电子 投票进行了概述，并介绍了电子评审问题。 第2 章对安全多方计算技术进行了概述，并介绍了几种常用的安全多方计 算工具，然后探讨多方安全计算在电子评审中的应用。 第3 章对仲红提出的电子评审方案进行了描述，详细分析了该方案的安全 性，并指出其不足。 第4 章分析了公告板机制、使用单向函数的承诺协议，并提出了一个基于 b r e s s i o n 公钥密码算法的保密比较协议；在这些基础上，利用z h 电子评审协议 的思想，设计了一个恶意模型下的电子评审协议，并分析了新协议的安全性和 特点。 第5 章基于新的电子评审协议，对电子评审系统进行了详细的设计，并探 讨了系统关键部分的实现技术。 第6 章对全文进行了总结和展望，在总结现有研究基础上，提出不足点和 需要进一步努力的研究方向。 7 第2 章安伞多方计算技术 第2 章安全多方计算技术 本章首先对安全多方计算进行一个简单的介绍，接着讨论了安全多方计算 的模型，包括协议参与者、通信信道、协议攻击者等。然后总结了安全多方计 算几种常用的工具。最后探讨了安全多方计算的典型应用。 2 1 安全多方计算介绍 安全多方计算是指在一个互不信任的多用户网络中，两个或多个用户能够 在不泄漏各自私有输入数据时协同合作执行某项计算任务。这些合作计算可以 存在于部分不信任的合作者之间，甚至竞争者之间。一般来说，处理这些计算 问题，一个参与者必须知道其他参与者的输入。但是，在安全多方计算中，任 何一方的秘密输入都不能泄露给其他参与者。那么，在保证计算正确性的前提 下，如何保密参与者的输入将成为一个难点问题。 这个问题可以描述如下：两个或多个参与者拥有各自的秘密输入，希望共 同计算一个约定的函数，得到正确的结果，同时不泄露自己的秘密输入。那么 怎样执行这样的一个算法，使得各方得到正确输出，但又保密自己秘密的输入。 著名的百万富翁问题就是一个简单的安全多方计算的实例，两个富翁希望比较 谁拥有更多的财富，结果只是双方知道准更富有，而不知对方的具体财富。 安全多方计算问题可以用数学形式化描述为：n 个参与者 a ，仍，见) ，希 望共同计算一个约定的函数厂( 五，乇，矗) ，每个参与者持有秘密输入毛，计算 结束后参与者觑得到自己的输出z ( 五，x 2 ，毛) ，同时不泄露自己的秘密输入。 如果假设有可信第三方( t r u s t e dt h i r dp a r t y - t t p ) 存在，则这个问题的解决是非常 容易的，各参与者只需要将其秘密输入发送给t t p ，由t t p 计算出这个约定的 函数，再将计算结果广播给每个参与者。然而在现实的应用环境下，很难找到 这样一个所有参与者都足够信任的t t p ，因此，安全多方计算的研究显得非常 有必要。图2 1 给出了安全多方计算示意副9 1 。 9 中山大学硕：b 学位论文 p lp 2pn j c l 乇毛 r1r1r i厂( 五，艺，) 图2 1 安全多方计算示意图 安全多方计算理论最早由a c y a o 在文献 1 5 中提出的百万富翁协议引发开 来。后来，g o l d r e i c h ，m i c a l i 和w i g d e r s o n 提出了基于密码学安全的可以计算 任意函数的安全多方计算协议【1 6 】。g o l d w a s s e r 和l l e v i n 提出了在大部分协议参与 者( 超过半) 都被买通的情况下的安全多方计算协议【1 7 】。g o l d r e i c h ，g o l d w a s s e r 和l i n i a l 对于不安全的通讯信道、拥有无限计算能力的攻击者模型下的安全多方 计算进行了研究【1 8 】。 2 2 安全多方计算模型 2 2 1 协议参与者 在一般的安全多方计算协议中存在三类协议的参与者：提供函数输入的参与 者、执行计算的参与者和接受函数输出的参与者。所有协议的参与者都包括上述 三种类型参与者。但是在大部分安全多方计算协议中，这三类的参与者都是相同 的，即同一个人承担三种角色。 参与者可能诚实地执行协议，也可以不诚实地执行协议。根据参与者执行协 议时的诚信程度，我们将参与者分为三种类型： 诚实参与者：诚实参与者将完全按照协议的要求执行协议的每一个步骤，而 且不会向攻击者透露自己的输入输出及中间结果。 半诚实参与者：半诚实参与者也将完全按照协议的要求执行协议的每一个步 骤，但可能向攻击者泄露自己的输入输出及中间结果。 恶意参与者：恶意参与者会听从攻击者的安排执行协议的某些步骤；它不但 l o 第2 章，女全多方计算技术 会向攻击者泄露自己的输入输出及中间结果，还可以听从攻击者的安排破坏协议 的正常运行，比如改变输入信息，不严格执行预定的协议，甚至终止协议。 2 2 2 通信信道 安全多方计算协议所连接的网络可能是同步的也可能是非同步的。在一个同 步网络中，所有协议参与者共享一个全局时钟。在一个非同步的网络中，不存在 这样一个全局的时钟，一个消息从发送到接收要经历不确定个时钟周期，接收方 接收的消息可能是延迟的，也可能是无序的。 局域网中存在天然的广播信道，协议参与者可以通过物理的方法向其他参与 者广播信息。但在大多数的分布式环境中，这样的广播信道是不存在的，只有协 议参与者之间两两相连的信道。这样，如果协议参与者需要向其他参与者广播信 息，他必须借助广播协议来模拟物理上的广播。 2 2 3 攻击者 安全多方计算协议中，可能存在企图破坏协议正确性和安全性的攻击者， 攻击者可以贿赂一部分不诚实的参与者。 根据攻击者可能贿赂的参与者的不同类型，攻击者可以分为两类： 被动攻击者：被动攻击者贿赂的是半诚实参与者，只能得到参与者的所有 输入输出及中间结果，而不能改变被贿赂者的输入信息及中间结果，也不能指 使参与者去破坏协议的正常运行。 主动攻击者：主动攻击者可以贿赂恶意参与者，不但能得到被贿赂者的所 有输入输出及中间结果，还能指使被贿赂者改变输入信息以及中间结果，偏离 协议的运行，甚至破坏协议的运行。 进一步的，攻击者还可以分为静态攻击者和动态攻击者： 静态攻击者：在协议开始之前就确定贿赂哪些参与者，在协议执行过程中 不会再改变。 动态攻击者：在协议执行过程中根据协议的执行情况来决定贿赂哪些参与 者。一般情况下，动态攻击者能够贿赂的参与者的总数是有一定限制的。 中山人学颐1 ：学位论文 2 3 安全多方计算的基本工具 不同领域的安全多方计算问题有不同解法，目前已有一些解决安全多方计算 问题的通用协议，现有的许多密码工具都是安全多方计算的基础。下面对安全多 方计算的一些基本工具进行简单介绍。 2 3 1 可验证秘密分享 秘密分享( s e c r e ts h a r e s s ) 是一种分发、保存和恢复秘密的方法，是安全多 方计算所使用的一种基本工具。可验证秘密分享( v e r i f i a b l es e c r e ts h a r i n g - v s s ) 是指在秘密分发的过程中，各个成员能够验证分发者分发的秘密分片的正确性， 通常通过增加验证协议来实现验证。 目前大部分的安全多方计算协议都使用了可验证秘密分享协议作为协议构 造的基础。这类协议适合计算任意有限域上的函数。f e l d m a n 于1 9 8 7 年提出了 第一个不需要可信任第三方的非交互式的v s s 协议【l9 1 ，该协议的秘密分享方法 是s h a m i r 的门限秘密分享方烈2 0 1 ，安全性是基于计算离散对数难题。 2 3 2 茫然传输协议 茫然传输( o b l i v i o u st r a n s f e r - o t ) 也称不经意传输，是为了实现从一个消息 集合中秘密地获得其中的一部分消息的协议。茫然传输协议也是安全多方计算 的一个基本工具。 o t 协议要解决的问题可以如下描述：b o b 有n 个数据白，包，a l i c e 需 要从这n 个数据中选取k ( k j ，但都不想让对方知道自己的数。为简单起见，假设f 与_ ，的范围 为 1 ，1 0 0 】。b o b 有个公开加密算法与私有解密算法。 ( 1 ) a l i c e 选择一个大随机数x ，并用b o b 的公开密钥加密 c = 易( 力 ( 2 - 1 ) ( 2 ) a l i c e 计算c f ，并将结果发送给b o b 。 ( 3 ) b o b 计算下面的1 0 0 个数： 儿= d b p i + “) ，u = 1 ，2 ，1 0 0 ( 2 - 2 ) 其中眈是b o b 的私有解密算法。b o b 选择一个大的素数p ( p 应该比z 稍 小一点，b o b 不知道石，但a l i c e 能容易地告诉他x 的大小) 。然后计算下面的 中山大学硕上学位论文 1 0 0 个数： z u = ( 兄m o d p ) ，u = 1 ，2 ，1 0 0 ( 2 3 ) 然后验证对于所有的u 1 ， i 气一乙| 2 ( 2 4 ) 并对所有的u 验证： 0 z u j 。 ( 6 ) a l i c e 把这个结论告诉b o b 。 假设该方案需要比较的两个数的长度为，则计算复杂度为0 ( 2 7 ) ，为指数 级的。显然，这样的计算复杂性，只适合于两个很小的秘密数进行比较，对较 大的数的比较是不实用的。而且a l i c e 先于b o b 知道比较结果，有可能欺骗b o b 。 文献 2 6 】基于中一隐藏假设以及同态公钥加密体制的语义安全性假设，给出了一 个特殊的安全双方计算协议，但需要半诚实第三方的参与。 2 3 5 安全多方求和协议 安全求和是指参与计算的两方或多方成员，在保护各自输入数据隐私的情 况下，共同计算一个函数之和。安全多方求和协议是s m c 的基础协议，文献 2 7 】 给出了该协议的形式化描述方法，文献 2 8 ，2 9 分别介绍了两种不同的安全多方 求和协议。假设有n 个用户p 。，p ：，p 。参与多方计算，每个b 有自己的私有数 据葺，他们希望共同计算：蕾，但任何一个用户都不愿意向其他用户泄露自 己的私有输入。安全多方求和算法是安全多方计算的一个基本操作，基于秘 密共享技术的安全求和协议描述如下【1 4 】： 1 4 第2 章安伞多方计算技术 ( 1 ) 舅把自己的私有数据玉拆分成，z 个子秘密五。，z n , - - , ，使得 五= ：。勃，然后a 把t 。，：，靠分别发送给p ，( f ) 。 ( 2 ) 每个p ，( _ ， 1 ，n ) ) 计算= ：。嘞，并将该值发送给其他参与者。 ( 3 ) 每个辫计算s 聊= ：。弓，得到所求结果。 2 4 安全多方计算的典型应用 安全多方计算有着非常广泛的应用背景，所以对安全多方计算应用的研究也 是一个非常活跃的领域。安全多方计算研究分布式环境下多方合作计算问题，对 解决网络环境下的信息安全具有重要价值。针对不同应用环境的安全需求，寻找 高效的解决方案正成为该研究的热点。通过对一般化的安全多方计算协议进行一 些修改，去掉那些对某个具体的应用没有实际意义的部分，可以提高协议的效率。 电子投票是安全多方计算的一个典型案例，实现安全的电子投票涉及许多高级密 码协议的研究，对其它电子商务活动，如电子拍卖、电子现金、合同签署等问题 的研究具有普遍意义。 如果不采用传统的密码学方法，不采用可信任第三方进行投票的管理和统 计，是否存在安全可行的解决方案呢? 不同场合、不同环境下的投票问题应该有 特殊的解决方法，将安全多方计算的一些基本工具和新技术应用于电子投票方案 的研究和设计，将为我们提供一个不错的研究方向【引。 可以采用安全多方计算技术来设计保密计票结果的电子评审方案。传统的密 码技术中，除了同态加密，多数加密技术都不支持对加密数据的协同计算，而安 全多方计算可以实现多方成员之间安全保密的合作计算，用于解决传统密码技术 无法进行的计算问题【9 】。在电子评审过程中，要求保密计票结果，正确地判定评 审结果，可以看作安全多方计算的特殊应用。本文主要利用s m c - i - _ 具，包括安 全多方求和协议以及两方保密比较协议，结合传统密码学技术，进行电子评审协 议的设计。该协议不需要可信的计票中心，投票者是评审系统的主体，每个投票 者都可以计票，从而杜绝了多计票中心系统中的计票中心联合作弊问题。 中山大学硕j ：学位论文 2 5 本章小结 到目前为止，安全多方计算的研究已经取得了一些初步的研究成果。本章 对s m c 研究进行了简单的介绍和分析，主要描述了s m c 的计算模型和基本工 具。在s m c 的基本工具中，可验证秘密分享、茫然传输、同态加密等方法在现 有电子投票方案中得到广泛的关注和研究，安全多方求和协议和保密比较协议 更是本文重点研究及应用的对象。在s m c 工其中，除了这些基本工具外，近来 出现一些特殊应用环境下s m c 的新研究方向，值得进一步探讨。 1 6 第3 章z h 电子评审协议分析 第3 章z h 电子评审协议分析 仲红采用安全多方计算技术实现保护隐私的电子评审【9 1 。采用安全多方求和 协议、百万富翁协议，提出了一个简单实用的电子评审协议。通过保护隐私的比 较大小，不泄露最终计票值，判定计票值是否大于等于预定的合格门限参数，实 现了对投票人隐私的保护。下面我们将对z h 电子评审协议进行详细的描述和安 全性分析，并指出其不足点。 3 1z h 电子评审协议描述 3 1 1 协议的基本设置 投票模型将实际评审活动进行抽象表示，以下对评审活动中涉及的主要参 数进行定义。 ( 1 ) 选民 电子评审活动中的选民实体就是参与投票的评审员。设参加投票的评审员 有n 名，所有选民构成的集合为 日，最，只) 。 ( 2 ) 不可信第三方服务器 不可信第三方服务器以s 表示。其作用是生成均匀分布的随机数，实现对 每张选票的伪装。 ( 3 ) 选票 选票格式为“y e s n o 类型，实现对某一个候选人或者某一项活动进行表决。 合格选票集合用 o ，1 ) 表示，其中以“l ”表示赞同，“0 表示反对。 ( 4 ) 评审规则 评审规则为“少数服从多数 ，当计票结果达到或者超过预先设定的值以 后，协议的输出结果为结果是“合格”，否则为“不合格”。除评审结果外， 方案不泄露任何其它私有信息。 需要说明的是，该方案的通信通道采用安全信道模型，既接收方确切知道 发送方的身份，发出的消息都不会被监听、篡改。此外，假设参与多方计算的 1 7 中山人学硕上学位论文 所有成员都是半诚实的，其特点是完全遵守协议，但在执行过程中保留所有记 录，并图谋借此推断其它参与方的秘密输入。 3 1 2 协议的描述 z h 电子评审协议分为三个阶段：准备阶段、投票计票阶段、评审判定阶段。 下而我们将对各个阶段进行简要地捕述。 一、准备阶段 对参加投票的n 个评审员 日，罡，只) 进行授权认证，使只均为合法的投票 人。每一个鼻预置门限常数m ，通常m 为整数且满足兰2 肘 ，z 。 二、投票与计票阶段 每一个投票者填写选票后，在本地对选票进行秘密分割，一张选票划分为n 个子秘密。引入一个不可信第三方s ，s 不参加多方成员之间的相互计算，只为 它们提供随机数，以实现隐藏数据的功能。下面给出电子评审的投票与计票阶段 的详细步骤。 ( 1 ) 对每一个f l ，船) ，s 生成随机数，：。使得，z ：，；= ，其中，；是有限 域中的元素。 ( 2 ) 对所有的i l ，n ) ，s 将传送给只。 ( 3 ) 每个只( f 1 ，咒) ) 将选票薯进行随机拆分，使：嘞= 薯。 ( 4 ) 每个只( f 1 ，z ) ) 将+ 1 分别发送给弓( l ，玎) ，j f ) ；每个 e ( 1 9o ，胛) ) 计算2 。+ 并将该值发送给其余参与方。 ( 5 ) 每个p ( f 1 ，z ) ) 将收到的选票子秘密勃及随机数进行累加，得： ：。：。而+ 行2 。i 记选票总和：。：。勃= r ，则计票结束时，每个评审员曰都得到r + 厂， 其中，是不可信第三方服务器s 才知道的随机数，因此对尸而言，丁是保密的。 第3 章z h 电子评审协议分析 三、评审判定阶段 每一个投票者只( f 1 ，挖) ) 与s 之间都可以通过两方保密比较协议，对计票 结果进行判定，以下给出评审判定过程： ( 1 ) 每个投票者只( f l ，z ) ) 计算：w = ( 丁+ ，) 一m 。其中t + r 是号前一阶 段得到的输出，m 是准备阶段只已知的合格门限值。此外，是准备阶段中s 生 成的秘密随机数。因此p 和s 分别掌握了秘密值w 和，。 ( 2 ) 每个投票者霉o 1 ，以) ) 与服务器s 联合执行百万富翁协议，分别输入 w 和厂，判断是否w ，。若输出w ，则t m 。 ( 3 ) 每个投票者公开相同的评审结果：合格或者不合格。 3 2z h 电子评审协议的安全性分析 一、投票的隐私性 在投票过程中，每个投票者g ( i 1 ，z ) ) 将自己的选票进行了随机分片， 然后将其中的n 一1 张分片分别发