（计算机应用技术专业论文）面向特殊应用的安全多方计算协议的研究.pdf

西华大学硕士学位论文 面向特殊应用的安全多方计算协议的研究 专业：计算机应用技术 研究生夏梅宸指导教师陈广贵( 教授) 何明星( 教授) 随着人们对信息安全的日益关注，作为保证数据安全的关键技术，密码学 也得到了极大的发展。密码学应用已经渗透到社会各个领域，其中安全多方计 算作为密码学的一个重要研究方向，为保证信息安全发挥着重要作用。安全多 方计算需要解决以下问题：n 个参与者p ，f = 1 玎，每个参与者提供秘密输入 x ，他们想要共同计算关于这些输入x ，i = 1 的某个函数厂，其中 f i x l ，一，x 。) = c v l ，一，y 。) ，每个参与者只得到对应的输出y ，除此之外，他们不 能得到其它的任何消息。 安全多方计算是密码学协议的理论基础和基石，安全多方计算问题是从众 多具体的密码学问题中抽象出来的，安全多方计算问题的研究对具体的密码学 问题有着指导意义。目前，对安全多方计算的研究集中在理论研究和应用研究 两方面。 本文主要研究了电子选举和集合运算两类特殊应用的安全多方计算。 1 、本文对基于m i xn e t 、基于签名和基于多方求和的三类电子选举协议进 行研究，从选票的类型、计算量、通信量、选举规模、模型等方面对比、分析 了三类协议，并在网络环境下实现了基于多方求和的选举协议。针对在选举过 程中的一些恶意行为，对半诚实模型下的、基于多方求和的电子选举协议进行 了改进，设计了恶意模型下基于多方求和的电子选举协议，当有叛逆者试图改 变选举结果时，该协议可以实现叛逆者追踪。 2 、本文研究了基于置换和多项式表示的集合运算。应用集合的多项式表示 方法和秘密分享的相关知识，设计了一个新的集合运算协议，在新协议中，交 第1 页 西华大学硕士学位论文 集的势没有达到门限值时，两个参与者都不能得到任何与集合相关的信息，并 对协议进了分析。 3 、此外，本文对匿名数字水印技术进行了研究。从购买者和销售者两方面 的利益考虑，提出了一个具有信息保护的匿名数字水印仲裁方案。协议中加入 数字作品的数字水印由购买者和销售者两方生成，不需要可信第三方的协助， 而且数字水印含有购买者匿名身份的相关信息，当发生非法分发的版权纠纷时， 不需要购买者提供秘密信息，仲裁者就可以完成裁决，在仲裁者没有裁定购买 者有罪之前，其身份不会泄露。 关键字：密码学，安全多方计算，电子选举，集合运算，零知识证明，位承诺， 秘密共享 第1 1 页 西华大学硕士学位论文 s p e c i a l a p p l i c a t i o n - - o r i e n t e ds 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 p r o t o c o l s m a j o r ：c o m p u t e ra p p l i c a t i o n m a s t e rc a n d i d a t e ：x i am e i c h e n s u p e r v i s o r ：p r o f c h e ng u a n g g u i p r o f h em i n g x i n g a l o n g 、析t hc o n c e r n i n ga b o u tt h ei s s u e so fi n f o r m a t i o ns e c u r i t yi sg r o w i n g h i g h e ra n dh i g h e r , a st h ek e yt oe n s u r ed a t as e c u r i t y , c r y p t o g r a p h yh a sa l s ob e e na g r e a td e a lo fd e v e l o p m e n t ，t h ea p p l i c a t i o no fc r y p t o g r a p h yt o d a yh a sp e n e t r a t e di n t o t h ec o m m u n i t yi nv a r i o u sf i e l d s 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 p c ) i sa n e x t r e m e l yg e n e r a ls u b j e c t ，a n dp l a y sa ni m p o r t a n tr o l ei ni n f o r m a t i o ns e c u r i t y i n m u l t i p a r t yc o m p u t a t i o n ，o n ec o n s i d e r sa n u m b e ro f p l a y e r s 只，i = 1 刀，w h oi n i t i a l l y e a c hp o s s e ss o m ei n p u t sx ，i = 1 玎，a n dt h e yt h e nw a n tt os e c u r e l yc o m p u t es o m e f u n c t i o n s f ，w h e r ef ( x l ，一，) = 1 一，y n ) ，a f t e rp r o c e s s i n g ，只l e a r n sy f b u t n oo t h e ri n f o r m a t i o n t h es m p cp r o b l e mi sa b s t r a c tf r o mn u m e r o u sc r y p t o g r a p h i cp r o b l e m s ，a sw e l l a ss o m eo ft h ec o n c l u s i o n so b t a i n e df r o mt h es p e c i f i ci s s u e sh a v eg u i d i n g s i g n i f i c a n c e ，i tc a nb es a i d ，s m p ci st h ef o u n d a t i o no fc r y p t o g r a p h i cp r o t o c 0 1 a s p r e s e n t ，t h es t u d i e so fs m p cf o c u so nt h e o r ya n da p p l i c a t i o n i nt h i sp a p e r , w ef o c u so nt h ep r o b l e mo fe l e c t r o n i cv o t i n ga n ds e to p e r a t i o n b a s e do ns m p c 1 w eh a v ea n a l y z e dt h r e et y p e so fe l e c t r o n i cv o t i n gp r o t o c o l s ，b a s e do nm i x n e t ，b a s e do nb l i n ds i g n a t u r ea n db a s e do nm u l t i p a r t ys e c u r es u m ，a n dr e a l i z e dt h e l a s ti nn e t w o r ks e t t i n g c o n c e r n i n ga b o u ts o m em a l i c i o u sb e h a v i o r s ，w ed e s i g n e da n e l e c t r o n i cv o t i n gp r o t o c o lb a s e do nm u l t i p a r t ys e c u r es u mi nm a l i c i o u sa d v e r s a r y m o d e lw h i c hc o u l dt r a c i n gt h et r a i t o rw h e nh ew a n tt oc h a n g et h ev o t i n gr e s u l t 第l i i 页 堕兰奎堂堡主堂垡笙茎一一 一 2 w eh a v ea n a l y z e dt h ep r o t o c o l so fs e to p e r a t i o n sb a s e do np e r m u t a t i o n a n d p 0 1 y n o 血a 1 ，a n dp r o p o s e dan e w o v e r - t h r e s h o l ds e to p e r a t i o np r o t o c o li nw l l l c nt h e t 、op a r t i e sd on o tk n o wa n y t h i n ga b o u ts e t - i n t e r s e c t i o n b u tt h ec a r d i n a l i t yo f s e t i n t e r s e c t i o no v e rt h r e s h o l d 3 w ep r o p o s e dap r i v a c y p r e s e r v i n ga n o n y m o u sd i g i t a lw a t e r m a r k i n gp r o t o c o l 舶mt h eb e n e f i to fb o t hs e l l e ra n db u y e ri nw h i c h t h es e l l e ra n dt h ea r b i t e rc f l r lt r a c e t l l ei l l e g a ld i s t r i b u t o rw i t h o u tb u y e r sa s s i s t a n tt or e s o l v et h ep i r a c yd i s p u t e ，w h l l e t h eb u v e rc a i lk e e pa n o n y m i t yd u r i n gt h et r a c t i o nu n l e s sh ei sj u d g e db y a r b i t e r 协b e g u i 埘o fp r i v a c y , s ot h ep r i v a c yo f s e l l e ra n db u y e ra r ea l lp r o t e c t e d - k e y w 。r d s ：c r y p t 。g r a p h 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 n ，e 1 e c t r o n i cv o t i n g ，s e t o p e r a t i o n ，z e r o k n o w l e d g ep r o o f , c o m m i t m e n t ，s e c r e ts h a r i n g 西华大学硕士学位论文 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此声明。 僦名酗脚咽 刷谧名易他眇口日挎 第6 l 页 西华大学硕士学位论文 1 绪论 1 1 研究目的及意义 新的世纪是信息的世纪，信息在社会中的地位和作用越来越重要，已经成 为社会发展的重要战略资源，信息技术越来越多地改变着人们的生活和工作方 式，信息产业已经成为新的经济增长点，社会的信息化已成为当今世界发展的 潮流和核心，而信息安全扮演着极为重要的角色，它直接关系到国家安全、企 业经营和人们的日常生活。信息安全包括系统安全、数据安全和内容安全。随 着人们对信息安全问题的关注度越来越高，作为保证数据安全的关键技术，密 码学也得到了极大的发展，今天密码学的应用已经渗透到了社会的各个领域。 安全多方计算是密码学中的一个重要研究领域，在保证信息安全中发挥着 重要的作用，安全多方计算问题是从众多具体的密码学问题中抽象出来的，对 它的研究以及由此得到的一些结论对于具体的密码学问题都有着指导意义。另 一方面，由于安全多方计算是非常抽象的一个问题，使得我们很难找到有效的 算法实现它，这导致了它在应用上的局限性。对于一个具体的密码学问题，我 们可以先根据安全多方计算的结论，在原则上确定这个问题是不是可以解决。 如果不可以解决，就没必要去考虑如何设计算法或模型，因为不存在或不可能 有满足安全性要求的算法；如果可以解决，则说明存在满足安全性要求的算法 或模型，这时就要寻找和设计具体的算法和模型。可以说，安全多方计算是密 码学协议的理论基础或者说是基石。 安全多方计算要解决的问题可以做如下描述：甩个参与者只，i = 1 ，每个 参与者提供秘密输入x ，他们想要共同计算关于这些输入x 。，i = 1 以的某个函 数厂，其中厂b l ，x 。) = ，y 。) ，每个参与者只得到对应的输出y ，除此之 外，他们不能得到其它的任何消息。 安全多方计算是一个很有趣的研究领域，对安全多方计算协议研究的意义 在于，从理论上讲在分布式的环境中有多个参与者的任何协议都可以看作是安 全多方计算的一个特例j 。实际上，安全多方计算不仅具有很重要的理论意义， 而且具有广阔实际应用前景，安全多方计算的相关研究在互联网的环境下更是 具有十分现实的意义。 第1 页 西华大学硕士学位论文 1 2 安全多方计算的研究背景和现状 安全多方计算( 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 ) 是分布式密码学的理论基 础，也是分布式计算研究的一个基本问题。它蕴含了密码学中任何协议问题在 原则上的实现方案。g o l d w a s s e r 曾预言1 6 】：多方保密计算今天所处的地位正是 公开密钥密码学1 0 年前所处的地位。它是密码学研究中一个极端重要的工具， 在计算科学中的应用才刚刚开始，丰富的理论将使它成为计算科学中一个必不 可少的组成部分。g o l d w a s s e r 的预言激励着越来越多的学者投身到安全多方计 算的相关研究中来。 概括起来，目前众多的学者对安全多方计算的研究主要集中在以下两方面： 1 安全多方计算协议的理论研究。 这类研究的内容是如何提高安全多方计算协议中的计算效率和通信效率： 如何减少安全多方计算协议中的计算轮数；攻击者能力的研究；以及如何设计 一种高效的、安全的、能够计算任意函数的安全多方计算协议。 安全多方计算协议的理论研究还包括对于安全多方计算进行形式化的定 义。安全多方计算协议的构造形式不同，研究的安全模型也不同，因此安全多 方计算至今还缺乏一个为大家所认同的、完备的定义。 新的安全多方计算协议的构造方法也是安全多方计算协议的理论研究的内 容。目前大部分学者提出的安全多方计算协议都使用了同态加密、秘密共享 ( v s s ) 、不经意传输( o t ) 子协议作为其构造基石，许多学者也在研究有没有 其他的方法来构造安全多方计算协议。 2 安全多方计算的应用研究。 如果用一个从一般条件导出的、广泛适用的协议来解决具体的安全多方计 算问题可能是不实际的，低效的。不同背景下的特殊应用，比如：电子选举、 电子拍卖、集合运算、数据库安全查询、保密的几何计算、保密的入侵检测、 保密的统计分析等等，它们所期望达到的安全目标是不同的，因此在设计面向 特殊应用的安全多方计算协议时需要考虑的安全性要求也是不同的，如何对一 般性的安全多方计算协议进行剪裁，把在安全多方计算理论研究中所取得的研 究成果更广泛地应用到相关特殊问题的研究中来，使其适用于一些特殊情形， 这也是众多学者研究的一个热点。 以下将从安全多方计算协议的理论研究和两类特殊应用研究描述安全多方 第2 页 西华大学硕士学位论文 计算的国内外研究状况和发展趋势。 1 安全多方计算协议的理论研究 最早是由a y r a o 【l 】于1 9 8 2 年通过姚氏百万富翁问题提出了安全两方计算 问题，并给出了两方安全多方计算协议。姚氏百万富翁问题是指两个百万富翁 希望知道谁更富有，但是除此之外不希望泄露任何其它的信息。5 年后， 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 提出了密码学安全的可以计算任意函数 的安全多方计算协议p j ，证明了在被动攻击的情况下，有，z 个半诚实参与方的多 方计算协议是存在的；在主动攻击的情况下，有刀一1 个半诚实参与方的协议是 存在的，并且还展示了如何构造这样的协议。1 9 8 8 年，d c h a u m ，c c r e p e a u 及 i d a m g a r d 对信息论安全的安全多方计算协议进行了研究【_ 7 1 ，证明了在被动攻击 的情况下n 一1 个半诚实参与者的协议是存在的，在主动攻击的情况下ln 2l 1 个半诚实参与方的多方计算协议是存在的。在c h a u m 及g o l d r e i g n 提出的安 全多方计算协议中，使用了大量的零知识证明，这使得协议参与者之间要传输 大量的数据，其适用性受到了很大的限制；然而，他们的工作指明了安全多方 计算的理论前景。1 9 9 0 年，s g o l d w a s s e r 及l l e v i n 对于计算模型下，大部分 协议参与者( 超过半数) 为恶意参与者的情况下的安全多方计算协议进行了研 究【8 】；1 9 9 1 年，o g o l d r e i c h 等人【9 l 对于不安全信道、拥有无限计算能力的攻击 者模型下的安全多方计算协议进行了研究；r o s t r o v s k y 等人f l o 】于1 9 9 1 年对安 全信道下移动攻击者进行了研究；s m i c a l i 、p r o g a w a y 1 1 】和d b e a v e “1 2 】对安全 信道下的安全多方计算给出了形式化的定义；r c a n n e t t i 于2 0 0 0 年给出了安 全多方计算协议应有的性质0 3 1 。g o l d r e i c h 等人证明了所有多方保密计算问题 在理论上都是可解的，定义了多方计算的保密性，建立了多方保密的计算模型 以及模拟范例，协议f 3 0 】p 7 1 从安全多方计算的效率方面进行了研究，为多方保密 计算奠定了理论基础。 2 电子选举 g o l d w a s s e r 的预言激励着人们不断地探索新的具有实际应用背景的多方 保密计算问题并研究它们的解决方案，这些问题包括电子选举、保密集合运算 等。从1 8 8 4 年电子选举第一次提出到现在，由于其安全性和公平性很难得到保 证，所以发展并不顺利，随着密码学本身的发展和在各领域的广泛应用，电子 选举才有了一定的发展。第一个密码学意义上的电子投票协议是d c h a u m 1 5 】 于1 9 8 1 年提出来的。该协议采用了公钥密码体制。通过设立一个可信任的机 第3 页 西华大学硕士学位论文 构m ，专门负责为投票人产生数字假名，投票人利用该数字假名进行投票。 数字假名虽然隐藏了投票人的身份，然而却不能无条件地保证投票人的身份不 被跟踪。p a r k 等人在公平性和有效性上对该方案进行了改进【l6 1 。c h a u m 1 。7 j 和 o h t a o s 也分别利用匿名信道给出了一个适合于大群体选举的投票方案，而且保 证了投票者的匿名性，然而这两个方案都没有解决选票的秘密性和公平性。当 投票者发现自己的选票没有被正确计入时，他必须通过公开选票来要求计票机 构加入自己的选票，这样就泄露了自己的身份：而且，管理者可以知道选举的 一些中间结果，所以他能通过泄露这些信息影响选举的最终结果，从而破坏了 选举的公平性。针对安全方面的不足，b e n a l o h 等人【1 9 】于1 9 9 4 年提出了一个 可验证选举结果的协议，b a u d r o n 等人【2 0 】提出了采用一个称为随机化处理器 r a n d o m i z e r 的第三方来对投票人的选票再加密，并且不改变选票内容，还有设 置防串扰随机化处理器t a m p e r - r e s i s t a n t r a n d o m i z e r 的投票协议【2 l 】等等。但是， 这些协议要么太复杂，不适合大型选举，要么就是安全方面仍存在大的漏洞。 1 9 9 2 年，f u j i o k a 等人基于公开密钥、数字签名、盲签名、位承诺等多种密码 学技术提出了一个较为成功的电子投票方案f o o t 2 2 1 。该方案保证了选票的合法 性和投票人身份的保密性，同时其算法易于实现、网络通信量较小，适合进行 大规模投票。后来许多大学和公司的研究机构都以f o o 协议为基础，对其加 以改进，开发出了相应的电子投票系统，并在各个非政府部门得到了广泛应用， 其中著名的有m i t 的e v o x 系统【2 3 】和w a s h i n g t o n 大学的s e n s u s 系统【2 4 1 。 但是，f o o 方案仍然存在一些缺陷：不允许投票人弃权、选票碰撞、无法区分 不诚实的计票机构和不诚实的投票人等。 3 集合运算 两方秘密值相等测试问题( p e t ) 解决的问题是：两方各持有一个值，在 不泄露秘密信息的的情况下，比较出两个值是否相等。1 9 9 6 年，f a g i n 等人冽 对这类问题进行了了研究，目前为止，大多数p e t 协议采用的是同态加密和不 经意传输的方法。p e t 问题可以看成是集合运算的特例，但是对于p e t 问题的 解决方法不能简单的应用到多方的情况来，否则会引起秘密信息的泄露。2 0 0 4 年，f r e e d o m 等人j 基于多项式表示集合根的方法首先解决了多方秘密求集合 交集运算的问题。2 0 0 5 年，k i s s e r 等人【4 l 】通过挑选随机的多项式来隐藏表示集 合的多项式，利用多项式的运算规则等知识把集合的运算从交集运算扩展到并 集、交集的势、超过门限的交集等问题，进一步丰富了集合运算问题的研究内 第4 页 西华大学硕士学位论文 容。 从国内来看，对子集合运算的研究也比较活跃。2 0 0 4 年，秦静等人6 8 1 1 6 9 1 基于尹一隐藏假设及同态公钥加密体制的语义安全性假设，对p e t 问题进行了 了研究。2 0 0 5 年，李顺东等人提出了采用长度函数和不经意传输来设计p e t 方 案【7 0 j ，还运用随机模拟方法和c a n t o r 编码方法解决任意几何图形包含的特殊集 合问题 7 1 1 。池兆峰等人研究了带构建了一类解决带秘密信息的点包含问题安全 协议【7 2 】。2 0 0 7 年，李荣花等人【铜基于集合的多项式表示方法设计了一个无条件 安全的多方集合运算。但是这些方案大多数都是解决安全多方计算中的交集问 题，对于一些特殊的集合运算，如元素超过给定门限值的交集等，则没有太多 涉及。 1 - 3 本文的组织 本文分为6 个部分。 第l 部分主要阐明本文的研究目的和意义，以及国内外安全多方计算理论 研究现状。 第2 部分主要介绍了本文涉及到的一些预备知识和密码学基础，如秘密共 享、位承诺、不经意传输、零知识证明等，并介绍了安全多方计算中的参与者、 攻击者及计算模型的定义。 第3 部分主要讨论了一类面向特殊应用的安全多方计算电子选举，从 协议框架、选票类型、适用规模等方面对现有的几类电子选举协议进行了分析。 实现了在网络环境下基于多方求和的电子选举协议。分析了投票人的恶意行为， 设计了恶意模型的安全多方计算电子投票协议，当选举结果被改变时，协议可 以追踪到叛逆者。 第4 部分主要讨论了一类面向特殊应用的安全多方计算集合运算，对 现有的实现集合运算的方法进行研究。设计了一个新的门限集合运算协议，在 该协议中，交集的势没有达到门限值时，两个参与者都不能得到任何与集合相 关的信息，并对协议进了分析。 第5 部分设计了一个具有信息保护的匿名数字水印仲裁方案。协议从购买 者和销售者两方面的利益考虑，由购买者和销售者两方共同生成水印，当发生 版权纠纷，在裁定购买者有罪之前，其身份不会泄露。 第5 页 西华大学硕士学位论文 第6 部分对本文进行了总结，也对今后的研究工作及目标进行了展望。 第6 页 西华大学硕士学位论文 2 安全多方计算密码学基础 本章第1 、2 节主要介绍一些构造安全多方计算协议所用到的密码学理论知 识。在第3 节中对安全多方计算中参与者、攻击者和计算模型进行了了定义和 划分。 2 1 预备知识 2 1 1 计算不可区分 计算不可区分也称为多项式时间不可区分 7 7 1 ( p o l y n o m i a l t i m e i n d i s t i n g u i s h a b i l i t y ) ，设x 和】，是有限集d 上的两个概率分布，k 是安全参数， 称x 和y 是计算不可区分的，如果对于任意概率多项式时间( p r o b a b i l i s t i c p o l y n o m i a lt i m e ) 算法丁，l d 6p 伍，1 y ：1 】- p r 0 6 防 ，1 y ：1 】是关于七的可忽 略的函数。 2 1 2 访问结构 访问结构( a c c e s ss t r u c t u r e ) 首先是在秘密分享协议的研究中被提出来的。 假设秘密的分发者a l i c e 有秘密s 需要在秘密分享的参与者只( f - 1 胛) 者中 分享，每个p i ( i = 1 门) 得到子秘密s ，。在恢复秘密时，只有某些特定的( 授 权的) 参与者集合可以恢复，而非授权子集中的参与者不能得到秘密s 的任何 信息。由所有授权子集组成的集合称为访问结构。 2 2 密码学基础 目前，大部分学者在设计安全多方计算协议时都使用了秘密共享、位承诺、 不经意传输等子协议作为其构造基石，接下来，对本文所要用到的一些基础协 议作一些介绍。 2 2 1 秘密共享 秘密共享( s e c r e ts h a r i n g ) 是信息安全和数据保密中的重要手段，它在重要信 息和秘密数据的安全保存、传输及合法利用中起着非常关键的作用。秘密分享 的概念最早是由s h 撇i r 【6 l 】和b l a l d e y t 6 2 1 分别提出的，基于拉格朗日插值公式和 第7 页 西华大学硕士学位论文 一 多维空间点的性质提出的。秘密共享由两个算法：秘密份额的分配算法和秘密 的恢复算法构成。 在执行秘密份额的分配算法时，分发者将秘密s 分割成若干个份额( s h a r e ， 或小块p i e c e ，或影子s h a d o w ) 在一组参与者p ( f = 1 1 ) 中进行分配，使得每 一个参与者都得到关于该秘密的一个秘密份额；秘密的恢复算法保证只有 只o = 1 疗) 的一些特定的子集( 称为合格子集) 才能有效地恢复s ，而尸的其它 子集不能有效地恢复秘密占，甚至得不到关于秘密s 的任何有用信息。 s h a m i r t 6 1 】的o ，n ) 门限共享协议只适用于单调的访问结构，方案如下： 系统设置：p 是一个大素数，并且p 玎，g 是z 。的生成元。( f = 1 力) 表 示参与者，x 疋= 1 ，”) 表示参与者只的身份，s 表示共享的秘密。 秘密分配：任选口，z 。，f = 1 ，f l ，a o = s 构造t 1 次多项式 厂g ) = b o + a l z + a x x 2 + + q t - i x 卜1 ) m o d p 计算每一份子秘密s ，= f ( x ，) m o d p ，待1 ，1 ，并通过安全信道将传送到 参与者只。 秘密恢复：f 个参与者交出各自的秘密份额，利用拉格朗日插值公式，恢复 出秘密j 。 2 2 2 单向函数 单向函数( h a s hf u n c t i o n ) 有很多名字：散列函数、压缩函数、消息摘要、数 字指纹、消息检验码( m d c ) 【_ 7 6 】。h a s h 函数就是把可变输入长度串( 原像，p r e i m a g e ) 转换成固定长度输出串( h a s h 值) 的一种函数。h a s h 函数是在一个方向上 工作的，从原像的值很容易计算其h a s h 值，但要产生一个原像的值使其h a s h 值等于一个特殊值却是很难的。 h a s h 函数是公开的，对处理过程不用保密。单向h a s h 函数的安全性是它 的单向性。原像的值的单个比特的改变，平均而言，将引起h a s h 值中一半的 比特改变。己知一个h a s h 值，要找到原像的值，使它的h a s h 值等于己知的 h a s h 值在计算上是不可行的。它的模型为：d = h ( m ) ，m 是待处理的明文，可 以为任意长度：h 是单向散列函数，d 是生成的报文摘要，它具有固定的长度， 并且和m 的长度无关。其中h 具有以下的单向性质： 1 给定h 和m ，很容易计算出d ； 2 给定h 和d ，很难计算m ，甚至得不到m 的任何消息； 第8 页 西华大学硕士学位论文 3 给定办，要找到两个不同的所，和m ：，使得办如，) = h ( m ：) 在计算上是不 可行的。 2 2 3 位承诺 位承诺( b i tc o m m i t m e n t ) 6 5 l 协议是许多密码学协议的基本组成元素，发送者 s 向接收者r 发送关于位b 的承诺c ，使得接收者灭无法从承诺c 中得到任何 有关位b 的信息，但是，当协议结束时，尺可以得到位b 并验证开始得到的c 的 确是b 的承诺。位承诺协议主要有以下两个特性： 1 一旦发送者声明消息是由他发出的，他就无法修改消息的内容，即：发 送者s 可以改变初始承诺位的概率小于( x ) ，这里的( x ) 为可忽略函数； 2 除非发送者解开承诺，否则没有人能够读到消息的内容，即：接收者r 可以猜到初始承诺位的概率等于1 2 + ( x ) 。 第一个特性要求发送者使用的映射函数不可替代，第二个特性则保证接收 者无法利用接收到的承诺位判断发送者发布的信息。 a l i c e 向b o b 承诺消息m ，简单的承诺方法可以由单向函数来实现： 1 a l i c e 生成两个随机数：和 2 a l i c e 用h a s h 函数对消息m 、 和巧进行计算生成随机串 h a s h ( r l ，r z ，m ) ，并向b o b 发送h a s h ( f i ，r 2 ，聊) 和_ 3 解承诺时，a l i c e 向b o b 发送m 和一 4 b o b 根据接收到的h a s h 函数、朋、n 和如计算随机串，并与从a l i c e 处收到的随机串进行比较，如果匹配，则接受承诺。 根据h a s h 函数的单向性和抗碰撞性，b o b 不能从a l i c e 发送的 h a s h ( r 。，m ) 和中获得消息m ，同时a l i c e 也很难找到满足 h a s h ( r i ，r 2 ，m ) - - h a s h ( r 1 ，m ) 的m 和呓来欺骗b o b 。 2 2 4 不经意传输 不经意传输( o b l i v i o u st r a n s f e r ) u 4 】协议要解决的问题可以如下描述：a l i c e 有n 个数据b ，b 2 ，一，b 。，b o b 需要从这玎个数据中选取尼( 七 跟) 个数据，出于某 种考虑，a l i c e 只允许b o b 知道她自己选择的k 个数据而对其它的r 一k 个数据 一无所知，同时，b o b 则不希望a l i c e 知道她具体得到的是哪k 个数据。 1 9 8 1 年r a b i n 1 4 1 第一次提出了不经意传输协议：发送者向接收者发送位 第9 页 西华大学硕士掌位论文 b ，协议完成时接收者得到b 的概率是1 2 ，无法得到6 相关信息的概率是1 2 。 协议如下： 1 a l i c e 选择两个大的强素数p ，q ，其中p = 2 p + 1 ，q = 2 q + l ，p ，q 也 是大素数，计算，2 = p q ，将6 加密得到e p q ( 6 ) 。a l i c e 将玎，e 冈( 6 ) 发送给b o b ： 2 b o b 随机选择x g 以) ，计算y = x 2m o d n ，并将y 发送给a l i c e ； 3 由于知道p ，q ，a l i c e 很容易得到方程y = x 2m o d n 的四个解，a l i c e 随 机的毪爨，1 ) x 2 , x 3 ) x t 其中一个解t 发送给b o b ： x l5y 2 m o d n ； 。 x 2 ；，2 一x 1 ； x 3 = y 一x 4 ； x 3 = k 。m o d p x q m o d p ) q + ( - x 1m o d p x p m o d q ) p m o d n ； 4 存在1 2 的概率，b o b 知道的两个解氏，x 。，分别在集合扛。，x ： ，扛：，x 。 中，也就是说b o b 有1 2 的概率得到p ，q ( p = g c d ( x n + x j 2 ，n ) ，g = g c d ( x f l + x i 2 ，, 门) ) 2 2 5 零知识证明 零知识证明( z e r o k n o w l e d g e ) 1 7 8 1 协议有两方参与。拥有知识的一方叫证明 者( p r o v e 0 ，简记为p ：而另一方叫验证者( v e r i f i e r ) ，简记为y 。另外，不需要 验证者y 提供质询值( c h a l l e n g e ) 的知识证明协议称为非交互式的，否则就称为 交互的。 零知识证明协议从本质上说也是安全计算协议的一种特例，它的安全性主 要包含以下三方面： 1 完备性( c o m p l e t e n e s s ) ：完备性指的是若证明者确实拥有秘密信息，且p 和y 都是诚实的，则y 总会接受尸的知识证明( 即相信尸拥有该秘密信息) ； 2 合理性( s o u n d n e s s ) ：合理性是指若p 并不知道秘密信息，则他要利用知 识证明协议使y 相信他拥有这样的秘密信息是几乎不可能的； 3 零知识性( z e r o k n o w l e d g e ) ：零知识性指的是就算y 确信尸知道秘密信 息，但矿并没有得到其它关于该消息的信息，从而也就不能向别人证明他( 验证 者1 也知道这一消息。 下面介绍二次剩余的完备零知识证明协议【7 8 】： 1 共公输入为n ，x ，其中n 为一个大的奇合数，不一个素数的幂，x 与 互素，x 鲫( ) ，鲫( ) 是所有的n 与模n 的二次剩余( ，x ) 的集合； 第l o 页 西华大学硕士学位论文 2 重复执行下列3 - 6 步l1 0 9 1 次； 3 尸按等概分布从z 二中选取一个v ，计算y = ，2 ( r o o d ) ，p 将y 发送给矿； 4 v 收到了y 后，按等概分布选取一个盯 o ，1 ，y 将盯发送给p ， 5 p 收到了盯后，计算z = u v v ( m o d ) ，其中u 为x 的一个模的平方根， 尸将z 发送给y ； 6 若y 收到尸发送的z 满足z = x 5 y ( m o dn ) ，则y 接受验证，否则y 拒绝 验证。 2 2 6 同态公钥密码体制 对于两个代数结构么和召，其中。是4 中的运算，木是b 中的运算，如果 v x ，y a ，有f ( x 。y ) = 厂g ) 木s o y ) ，则映射f ：a 专b 称为彳到b 的同态。对于 公钥加密算法e ( o ) ，如果给定e ( x ) 和e ( y ) ，在没有私钥的情况下能够计算出 e b o y ) ，则称该公钥加密算法具有同态性质。例如，r s a 公钥密码算法具有乘 同态性质，而p a i l l i e r 5 6 1 、br e s s o n 5 8 1 算法具有加同态性质。 本文采用了p a i l l i e r 等人提出的公钥加密算法，算法描述如下。参数选择和 预定义：选择胛= p q ，p 和q 为大素数，兄) 为c a r m i c h a e l 函数，即 兄0 ) = l c m ( p 一1 ，g 1 ) ，g 为模刀2 的乘法群，即g = ww z ： 。 b 。= kig ，g ”= l m o d n 2 ，b = u 乙b 。，文献 5 6 】中证明：如果g b ，则 i ( x ，y ) = g x y 一是z 。z ：一z ：的双射。定义函数三 ) ， v u 最= 缸 阼2i 材= l m o d n ，三0 ) = 0 1 ) n 。显然l 是良定义的( 只具有 唯一解) 。 密钥生成：随机选择g b 且g c d ( l ( g 五r o o d n 2l 刀) = 1 ，( y ，g ) 为公钥，名0 ) 为 私钥。 加密过程：对于明文m z 。，随机选择r z ：，密文c = g m r ”r o o d n 2 。 解密过程：c z ：，m = 三( c 五m o d n 2 ) 三b 五m o d n 2 ) m o d n 。 p a i l l i e r 公钥加密算法具有语义安全性和加同态的性质【5 6 1 ，即给定明文 m 。，m ，不存在多项式时间算法区分e 如。) 和e ( m ，) ，且e 如。) e ( m 。) = e 如。+ m 。) ， e ) = e ( 砌) 。 2 3 安全多方计算的定义和模型 第1 1 页 西华大学硕士学位论文 由于安全性是针对具体的攻击者而言的，并不是任何安全性要求( 即针对 任何的攻击者) 都有算法实现。因此，我们首先应对安全性要求进行具体刻画， 而后设计满足这个安全性要求的算法。 2 3 1 参与者 参与者按照协议所规定的程序执行规定的动作，如：提供输入、得到输出 并且执行实际计算，其集合记作 只，只 。本文假设所有参与者的初始状态都 是诚实的，其行为不会超过协议规定的范围，也不会与外界产生额外的通信与 计算，同时还要保证其所有内部数据的保密性，但是他们一旦被攻击者收买， 有可能恶意地参与协议的执行( 根据攻击者的能力) 。 2 3 2 攻击者 文献【6 3 】【硎为了形式化最坏情况下参与者的行为，在进行安全计算的研究 时，通常将所有的不诚实参与者形式化地表示为在单一攻击者控制下的参与者。 协议的安全性是相对于攻击者能力而言。因此，在谈安全性之前，应对攻击者 的能力有一个严格的界定。依据网络性质、计算能力以及攻击者的行为模式， 可以将安全计算问题归结为不同的攻击者模型，然后分析不同的攻击者行为可 能会对系统产生的影响。攻击者形式化地表示参与者之间的信任关系，安全计 算协议在不同的攻击者模型下实现的要求也不同。 ， 一般对攻击者有以下几种分类： 按照攻击者的计算能力分为： 拥有无限计算能力的攻击者 只有多项式时间计算能力的攻击者 事实上，攻击者的计算能力由通信模型确定。在安全多方计算协议中，我 们考虑两种通信模型，即信息论模型和密码学模型。对于拥有无限计算能力的 协议攻击者而言，不存在诸如大素数分解困难性等数学难题，它可以通过大量 的计算来获得足够的信息从而破坏系统或协议，相应的，在无限计算能力攻击 者模型下安全的多方计算协议称为信息论安全的多方计算协议。 由于实际应用的密码协议和算法很少能够满足信息论安全的标准，密码学 研究者通过降低对手的计算能力，允许对手拥有多项式或者概率多项式的计算 能力。对于拥有多项式时间计算能力的协议攻击者而言，无法在合理的时间内 第1 2 页 西华大学硕士学位论文 求解基于计算复杂性理论的数学难题。在多项式时间计算能力攻击者模型下安 全的多方计算协议称为密码学安全的多方计算协议。密码学安全是基于计算复 杂性理论的安全标准。因此基于数学难题的密码系统是有条件的安全，它成立 的前提是计算复杂性理论中的数学难题不存在有效的算法，但是谁也不能保证 现在没有多项式时间算法的问题将来也一定没有多项式时间算法，尤其是量子 计算的出现，已经为几个不可解决的问题提出了有效的算法。如r s a 问题等。 当然量子计算现在还远远没达到实用的目的，因此现阶段对具有多项式计算能 力的攻击者进行的安全性分析还是可信的。 在本文中主要考虑具有多项式计算能力的攻击者。 由于安全多方计算协议的执行涉及到多个协议的参与者，各个参与者之间 需要通过某种方式进行通信，对于攻击者而言，控制参与者间的通信是一种非 常有效的攻击方式。 对应于不同的通信控制程度，可以将攻击者分为如下几种： 保密信道下的攻击者 认证信道下的攻击者 未认证信道下的攻击者 在安全信道下，攻击者对信道没有任何控制能力，既不能窃听、又不能窜 改。在这种模型中，提供的是最好的通信安全性；在认证信道下，攻击者可以 对通讯信道进行侦听，但不能对信道进行窜改：在未认证的信道下，攻击者对 通讯信道具有完全的控制能力，既可以对通讯数据进行窃听、又可以按照自己 的意图进行删除、修改参与者之间传递的消息。有时候我们还会