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

西华大学硕士学位论文 安全多方计算协议的研究与应用 计算机应用技术 研究生张雷征指导教师何明星( 教授) 摘要 安全多方计算( 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 ) 在密码学中拥有相当 重要的地位，它是电子选举、门限签名以及电子拍卖等诸多应用得以实施的 密码学基础。安全多方计算协议牵涉到众多的底层密码协议，露前提出的方 案使用到了秘密共享、公钥和私钥加密、同态加密以及不经意传输等诸多常 用的安全协议和算法。可以说，目前安全多方计算领域的研究和1 0 多年前的 公钥密码学的研究类似。也就是说，它已经拥有了丰富的理论，正在成为密 码学领域一个强有力灼工具。虽然它在现实生涟中的应用还只是刚刚开始， 但将来必将成为信息安全体系的一个重要和必不可少的部分。 8 0 年代，安全多方计算领域的研究主要关注于如何获得一般化的可计算 任意函数的协议，以及针对不同类型的攻击者和网络条件来分析协议的安全 性能。而目前的研究主题是如何针对一些特殊问题获彳导高效的无交互式的协 议，这些重点问题包括安全多方计算在门限密码学、数据库的安全访问和统 计分析、科学计算以及a dh o c 网络中的应用等。目前，一些新的方向正在逐 渐获褥越来越多的关注，翔参与者对鲁身行为的不可否认性、参与者的匿名 性问题和全局可组合安全性的证明等。 本文主要研究内容是安全多方计算的基础协议以及针对特殊应用的安 全多方计算问题。论文的主要工作表现如下： 王。对实现安全多方计算所需要的基础协议进行归纳和描述。对现有的 基于秘密共享的安全多方求和协议作了改进，从而提高了协议效率。 第1 页 西华大学硕士学位论文 2 对保护隐私的安全多方统计分析问题进行了模型分析，将改进后的 安全多方求和协议运用其中，在保证安全通信的基础上，降低了用户之闻的 复杂性，提高了运算速度。 3 探讨了安全多方计算在计算在几何中的应用问题，研究了双方保护 私有信息的空间几何对象之间相对位置的判定方法，描述了相关实现的协 议，提出多方保护私有信息的空闻几何对象之闻相对位置的判定方法。 关键字：安全多方计算协议；安全求和；统计分析；计算几何 第l l 炎 西华大学硕士学位论文 s t u d yo ns 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 s m a j o r ：c o m p u t e ra p p l ic a tio nt e c h n o l o g y m a s t e rc a n d i d a t e ：x u e z h e n gz h a n g s u p e r v i s o r ：p r o f m i n g x i n gh e 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 np r o t o c o li sa ni m p o r t a n ta r e ai n c r y p t o g r a p h y i t st h eb a s iso fm a n yd is t r i b u t e dc r y p t o g r a p h i c p r o t o c o l ss u c ha s t h r e s h o l dc r y p t o s y s t e m 、 e l e c t r o n i cv o t i n ga n d e l e c t r o n i ca u c t i o n ，e t c i nf a c t ，a l m o s ta l lp r o t o c o l si nd i s t r i b u t e d e n v i r o n m e n tc a nb ev ie w e da sas p e ci a lc a s eo fs e c u r em u lti p a r t y c o m p u t a t i o n i ti sb a s e do nm a n yb a s i cc r y p t o g r a p h i cp r o t o c o l s ( e g 。 h o m o m o r p h i ce n c r y p t i o n a n dz e r o k n o w l e d g ep r o o f ) a n ds o m eb a s i c p r o t o c o l si nd i s t r i b u t e dc o m p u t a t i o n ( e g o b l i v i o u st r a n s f e ra n d b r o a d c a s tp r o t o c 0 1 ) i ti sb e l i e v e dt h a tt h ef i e l do fm u l t i p a r t y c o m p u t a ti o n si st o d a yw h e r ep u b li c k e yc r y p t o g r a p h yw a st e ny e a r sa g o ， n a m e l ya ne x t r e m e l yp o w e r f u lt o o la n dr i c ht h e o r yw h o s er e a l 。li f e u s a g ei sa tt h i s t i m eo n l yb e g i n n i n gb u tw i l lb e c o m ei nt h ef u t u r e a ni n t e g r a lp a r to fo u rc o m p u ti n gr e a lit 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 na l l o w sas e to fp l a y e r st oc o m p u t e a na r b i t r a r ya g r e e df u n c t i o no ft h e i rp r i v a t ei n p u t si nas e c u r ew a y ， e v e ni fa na d v e r s a r ym a yc o r r u p ts o m ea r b i t r a r yp l a y e r s s e c u r i t yo f m 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 lm e a n sg u a r a n t e e i n gt h ec o r r e c t n e s s o ft h eo u t p u ta sw e l la st h ep r i v a c yo ft h ep l a y e r s i n p u t s 。t h em a i n r e s e a r c hr e s u l t so fs e c u r em u l t i p a r t yc o m p u t a t i o na r el i s t e db e l o w ： 第1 i i 页 西华大学硕士学位论文 a tf i r s t ，w es t u d yt h eg e n e r a ls e c u r em u l t i p a r t yc o m p u t a t i o na n d p r o p o s ean e ws e c u r es u mp r o t o c 0 1 n e x t ，w ed e v e l o ps o m es e c u r em u l t i p a r t ys t a t i s t i c a la n a l y s i s p r o t o c o l ss u c ha sc o r r e l a t i o na n dl i n e a r r e g r e s s i o na n d t h e i r p e r f o r m a n c e f i n a l l y ，w e d i s c u s st h e a p p l i c a t i o n o f s e c u r e m u l t i p a r t y c o m p u t a t i o ni nc o m p u t a t i o n a lg e o m e t r ya n ds y s t e m a t i c a l l ys t u d yt h e d e t e r m i n a t i o no ft h er e l a t i v ep o s i t i o no ft w og e o m e t r i co b j e c t su n d e r t h ep r i v a c y p r e s e r v i n gs i t u a t i o n k e y w o r 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 np r o t o c o l s ，s e c u r es u m s t a t i s t i c a la n a l y s i s ， c o m p u t a t i o n a lg e o m e t r y 第1 v 页 西华大学硕士学位论文 声明 本人声骢所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表过或者已经撰写过的研究成果，也不包含为获得西华大学或者其 他教育机构的学位或者证书焉使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已经在论文中作了明确说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文 成果归西华大学所有，特此声明。 作者签名：弘移脚r 月尹 日 导师躲向北滞，胃尹圜 第4 8 荑 西华大学硕士学位论文 第一章绪论 1 1 密码学及安全多方计算介绍 1 1 1密码学介绍 当前计算机和网络技术迅猛发展，i n t e r n e t 的普及使人类进入信息时 代，人们之间的信息交流变得更加容易、更加频繁。信息技术的发展是人类 社会的一次革命，它在很大程度上改变了人们的生活观念。随着信息化的不 断发展，信息安全已经成为全社会的需求，信息安全保障也将成为国际社会 关注的焦点，因为信息安全不但关系国家政治安全、军事安全、社会稳定， 也关系到社会中每一个人的数字化生存的问题。信息时代给我们一个最为重 要的观点是信息本身就是财富源泉，是一种重要的资料来源，网络在给人们 的日常生活带来极大方便和部分经济效益的同时，也给一些不法份子予以可 乘之机。由于信息网络国际化、开放化的特点，使之在给人们提供信息共享 的同时也给人们带来了不安全因素，信息本身作为一种财富，其自身的安全 必然会受到严重的威胁。从长远来看，人类要真正地进入信息社会，首先必 须解决信息安全的问题，否则我们期盼的信息社会将是一个无序混乱的社 会；从短期来看，信息安全问题如果不能更好地解决，那么网上信息服务、 电子商务、电子银行、电子拍卖、电子投票等业务就无法顺利地开展。 密码学最早起源于隐写术，可以追溯到古代人类的象形文字及保密代码 书写，但是直到第二次世界大战中解密器的研究才开创了近代密码学的历 史。1 9 4 9 年，近代密码学的奠基人c e s h a n n o n 1 发表了一篇具有划时 代意义的论文“保密系统的通信理论 ，将密码学归入通信理论并首次用概 率统计的观点对明文、密文、密钥、信息的传送进行了数学描述和定量分析， 提出了通用的通信系统模型，标志着密码学的研究走上了科学的轨道。7 0 年 代中期，随着计算机技术、通讯技术的发展，为了适应信息化的要求，公钥 密码体系 2 和美国数据加密标准的诞生引发了密码学研究的重大变革。以 公钥密码为基础的数字签名、认证加密以及数字证书等技术在信息安全领域 第1 页 西华大学硕士学位论文 有了非常广泛的应用。如今，密码学的理论和技术不再是为少数人掌握的服 务于国家军事和政治的学科，而是深入的渗透到了人类社会的各方各面，在 人们的经济理财、日常生活等应用范围中不断扩大。这十几年，密码学的技 术得到了飞速发展 3 5 ，它已经成为一门结合数学、计算机科学、电子与 通信等诸多学科于一身的交叉性学科。 现代密码学以研究秘密通信为基本目的，即研究对传输信息采取何种变 换以防止有效消息被第三者窃取。它包含的内容很多，主要可分为两大部分： 算法和协议。算法主要包括加密算法和解密算法：加密算法即是按某种方式 将原始信息转换成看起来毫无意义的文字；解密算法即指授权接受者通过相 应的方法将这些文字转换为发送者所发送的原始消息，而非授权者从这些文 字中得不到任何有用的信息。除了加密和解密算法，现代密码学算法还包括 数字签名算法、单向函数( h a s h 函数) 算法和伪随机数的生成算法等。协议 包括认证协议、知识证明协议、密钥交换协议、密钥托管协议、电子支付协 议、安全多方计算协议等。流行的加密算法分为两类：分组密码算法与公钥 密码算法。最著名的分组加密算法有美国的数据加密标准d e s 算法、高级加 密标准a e s 算法、r c z 算法、i d e a 算法和r c s 算法等。最著名的公钥密码算 法有r s a 算法、e i g a m a l 算法和椭圆曲线算法等。 使用密码技术不仅可以保证信息的机密性，而且可以保证信息的完整性 和不可否认性，防止信息被篡改、伪造和假冒。大致说来，其主要功能体现 在以下几个方面： ( 1 ) 身份可验证与数据保密性。防止非法用户进入系统以及合法用户对 系统资源的非法使用：通过对一些敏感数据文件进行加密来保护系统之间的 数据交换，使得除合法接受方之外的任何人即使获得了数据也不能够得到其 真正的内容。 ( 2 ) 数据的完整性。防止非法用户对要实现交换的数据进行无意识或者 恶意的修改、插入等操作，防止交换数据的丢失等。 ( 3 ) 数据的不可否认性。对数据和信息的来源进行验证，以确保数据由 合法的用户发出：防止用户在数据发出后又予以否认，同时防止接受者在收 到数据后否认曾经接受过此数据或者是篡改数据。 第2 页 西华大学硕士学位论文 1 1 2 安全多方计算介绍 随着i n t e r n e t 的快速增长，带来了巨大的共同计算的机会，人们基于 自己的输入共同完成一个计算任务。计算可能发生在都是诚信的合作者之 间、也可能发生在部份是诚信的合作者之间、也可能是竞争者之间。 1 9 8 2 年，a c y a o 首先在文献 8 中介绍了安全多方计算的概念，随后 g o l d r e i c h ，m i c a l i ，w i g d e r s o n 在文献 6 3 中将其推广。考虑这样一个有趣的 问题，一组参与者各自拥有自己的信息，他们之间互不认识所以不信任，但 是他们希望安全地计算一个约定的函数，这个函数的输入由他们各自提供。 这里安全地计算一个约定函数的意思是：即使在有不诚实参与者的情况下， 每个参与者都能得到正确的计算结果，同时每个参与者的输入对除他本人以 外的任何人是保密的，也就是说一个参与者无法得知其他任何一个参与者的 输入，除非某些参与者的输入可以从函数的输出推导而得。这就是著名的安 全多方计算问题。如果这时有可信第三方t t p 的存在，这个问题的解决将是 十分容易的，参与者只需将自己的输入加密后传送给t t p ，由t t p 统计数据 并计算这个函数，然后将计算结果广播给每一个参与者，这样每个参与者都 得到了正确的结果，同时自己的输入也没有被泄露。然而在现实的应用中， 很难找到这样一个所有参与者都信任的t t p ，因此安全多方计算的研究主要 是针对无t t p 的情况下，如何安全地计算一个约定函数的问题。安全多方计 算在安全多方数据统计、空间几何对象相对位置判定、电子拍卖、秘密分享、 门限签名等场景中有着重要的作用。由此，以色列学者y e h u d al i n d e l l 在 他的的博士论文 7 中指出安全多方计算安全性的核心的概念包括：保密性、 正确性、输入独立性、确保输出发送、公平性等。安全多方计算的研究主要 集中在了两个方面，一般理论的研究和具体应用的研究。 1 1 3 安全多方计算与密码学的关系 安全多方计算是许多密码学协议的基础，现在许多应用密码学协议，如 电子选举、电子拍卖等都是安全多方计算的特殊应用。这些协议的区分在于 用于安全多方计算的函数不同。所以安全多方计算还包含了密码学中的诸多 第3 页 西华大学硕士学位论文 基础协议、基础算法和基础数学知识，例如数字签名、零知识证明、v s s 、 对称加密、非对称加密、h a s h 函数、数论、线性代数等。 1 2 安全多方计算研究背景和现状 近年来，网络技术的不断发展，极大地改变了计算的含义及计算的方式， 人们面临的是以高性能计算机、网格等为代表的日益强大的计算环境，用户 可以通过网络使用这些强大的计算资源完成自己的计算任务。而在这种环境 中，保证用户数据的安全，是计算的基本要求。安全多方计算( s e c u r e m u l t i - p a r t yc o m p u t a t i o n ，s m p c ) 正是在这样的背景之下日益引起人们的 关注的。 所谓安全多方计算问题，用数学方式描述就是假设有n 个参与者 异，罡，只，每个参与者只持有秘密输入而，共同计算函数值 厂( 五，x 2 ，吒) = ( k ，e ，e ) ，要求即使在某些参与者不诚实的情况下，这种计 算也能保护参与者的输入的秘密性，同时保证计算结果的正确性，使得第j 个参与者确保能够得到z ，除此之外得不到任何其他的信息。例如，在利用 网络进行商务活动时，经常要建立某些网络协议，参与的双方或多方提供自 己的( 一般是秘密的) 输入，在协议被完全诚实地执行时，参与各方获得预 期的( 一般是秘密的) 输出信息。但是，在现实世界中，参与各方的诚实性 往往难以保证，我们必须要考虑某些参与方企图通过各种欺诈手段( 比如， 提供假的输入、提供假的身份信息、恶意终止协议) 获得利益的情况，当然 也要考虑由于无意的输入错误或网络故障导致协议不能正常完成的情况及 来自外部的恶意或无意攻击，在所有这些情况下，我们必须保证诚实参与者 的信息安全，使欺诈者或攻击者不能获得额外利益。g o l d w a s s e r 曾经预言： “多方计算领域的今天，就像是1 0 年前的公钥密码学。它是一个强大的工 具且蕴含丰富的理论，其实际应用刚刚开始，但必将变成计算王国的主干。” 这从某种程度上，也反映出安全多方计算研究的远大前景 为了保护参与者输入的秘密性，一个最简单的方式就是找到一个可信任 第4 页 西华大学硕士学位论文 的实体，大家把各自的输入秘密地交给这个可信方，由可信方来计算出函数 值，然后将相应的函数值返回给参与计算的各方。但是现实世界中很难找到 这样的可信第三方，这就导致了安全多方计算问题的研究。 s m p c 的含义极为广泛，且具有广泛的应用背景。保密通信、数字签名等 都可视为安全多方计算的特殊情况，典型应用如认证协议、在线支付协议、 拍卖协议、选举协议、隐私保护的数据查询数据挖掘等等。甚至从某种意 义上讲，任何计算都可以被看作是安全多方计算的一个实例。 s m p c 最早是由a c y a o 8 于1 9 8 2 年提出的，即广为人知的百万富翁 问题，实际上是解决两个整数比较大小的s m p c 问题。随后，广大的研究工 作者对s m p c 进行了广泛的研究，产生了一批具有代表性的成果。目前所有 的工作可以分为两类。第一类工作致力于在理论上研究任意函数的一般化的 安全多方计算方法。作为解决问题的一般性方法，这类研究在理论上具有很 大价值，但是目前得到的结果，都存在着时间、空间以及通信复杂度的代价 太高的问题，还不能应用于解决实际问题。另外一类工作重点讨论特定函数 的多方计算，以期待对于特定的问题找到更高效的可以实用的解决方案。 1 、理论上一般化方法的研究 理论上的一般化方法首先是将任意函数用基本操作表示，然后讨论这些 基本操作的安全多方计算方法。事实上，要计算的函数可视为某空间f 上的 一个算法电路c ，而c 可以被分解为一系列依次被处理的基本运算门，因此 任意函数的多方安全计算转化为基本运算门的安全多方计算。现有的c 的分 解方式有两种，一种是将其分解为只有加法门与乘法门构成，这种情况下， 任意函数的计算则可以认为是依次进行一系列f 上的函数输入值( 或中间结 果) 间的加法与乘法：另外一种分解方式是将c 分解为基本的比特运算，也 就是二元与a n d ，异或x o r 以及一元非n o t 的运算。 2 、特定的安全多方计算问题 在已有文献中，有很多针对特定安全多方计算应用问题的特定解决方 案，比如私有信息的查询问题 1 7 ( p r i v a t ei n f o r m a t i o nr e t r i e v a l ，p i r ) ， 隐私保护的统计数据库问题 1 9 ，隐私保护的数据挖掘问题 3 4 ，加密数据 计算问题 3 7 等。 p i r 系统由多个客户端和相应的服务器组成，某个客户端需要访问服务 第5 页 西华大学硕士学位论文 器，得到它所具有数据的二进制序列的第j 个比特，但是又不想让服务器知 道j ，同样的服务器也不想让客户端得到除第j 个比特之外的其他任何信息。 这个问题的解决方案并不困难，然而想要得到一个高效的解决方案，特别是 一个通信代价较小的便于实现的解决方案，并非一件简单的事情。文献 9 1 5 在这方面作了大量工作，相对于使用一般化的安全多方计算方法，对p i r 问 题，得到了通信复杂度大大降低的专用方案。 加密数据计算( c o m p u t i n gw i t he n c r y p t e dd a t a ，c e d ) 1 6 问题也是 s m p c 问题的一个特殊形式，是只有一方存在输入与输出的s m p c 。典型的两 方c e d 问题的目的是安全地借用对方的计算能力，例如，客户端借用高性能 计算中心或网格的计算能力，智能卡借用主机计算能力等。目前c e d 问题的 主要解决思路是利用同态加密的思想同态加密的理论基础是环的同态，设 明文空间p 以及密文空间c 都是环，e 是p c 上的加密函数。记明文 口，b p 验证算法p l u s 及m u l t ，如果算法满足e ( a + 6 ) = p l u s ( e ( a ) ， e ( 6 ) ) ，e ( a 功= m u l t ( e ( a ) ，e ( 6 ) ) ，则我们称加密算法e 满足加法同态 以及乘法同态性。利用加密同态算法，我们就可以在不需要知道明文日，6 的情况下，利用a ，b 的密文e ( a ) 、e ( 6 ) ，计算出e ( a + b ) 与e ( a 功的值， 再解密就可以得到昌+ 6 及日6 的值。目前典型的c e d 方案是f e i g e n b a u m 的，给出了离散对数问题的c e d 方法 4 4 ，并指出n p c 问题都是可加密计算 的。而在应用中，目前对于比如公钥运算等具体问题的c e d 协议还没有人涉 足。 综上所述，s m p c 问题，是一个在信息安全领域中被广泛关注的问题， 从s m p c 领域的最初成果出现以来，己经有许多的工作提升了得到的结果， 至今还有大量文献出现，这些文献得到了一些在更强或更一般化的敌手攻击 下的处理方案，在降低通信或者交互轮次的复杂性方面也有一些进展。但是 目前的成果仍然只停留在理论研讨的阶段，其效率低下，远远没有达到可以 实用化的程度。随着高性能计算、网格计算环境的发展，s m p c 问题具有了很 强的实用化需求，需要大力研究可以实用的方案。 第6 页 西华大学硕士学位论文 1 3 本文研究内容 本文将对已有安全多方计算协议进行分析和研究做出以下工作，重点是 在一些特殊应用协议上。主要研究内容表现在以上几个方面。系统阐述了常 用的安全多方计算基础协议，例如：同态加密协议、点积协议、判定相等协 议等：在已有的基于秘密共享的安全多方求和协议的基础上提出一些改进， 能够有效提高协议运行效率，减少通信次数；介绍安全统计分析问题模型， 将改进的安全多方求和协议运用于数据的统计分析方面，针对这类特殊安全 多方计算问题可以大大缩减其运算时间；利用已有的基础安全多方计算协 议，归纳了平面上几何对象间的相对位置判定的方法和协议，能够具体解决 一些具体的应用问题。 1 4 论文结构 本论文分为六章； 第l 章主要说明本文的研究目的和意义，回顾了安全多方计算的发展 历程，分析了当前国内外对其的研究现状，还介绍了本文的研究内容。 第2 章主要阐述了安全多方计算涉及的相关密码学知识以及基本术 语，包括零知识证明、哈希函数等理论及技术；攻击者、半诚实模型、计算 复杂度等。 第3 章着重介绍了安全多方计算中最基础的工具及协议并对各个协议 的通信次数、信息传输量以及计算复杂度做了较为详细的分析，对现有安全 多方求和协议以及求点积协议进行改进，以提高运行效率，减少通信次数， 能够更有效的投入实际应用。 第4 章研究了安全多方求和计算在统计分析数据问题中的应用，使用 改进后的安全多方求和协议解决实际问题，能有效提高运算效率、显著减少 通信次数。 第5 章根据点积协议基本思路，构造出判断数据成比例协议，并对其 进行了通信次数、通信信息量以及计算复杂度的分析，最后将其应用于判断 第7 页 西华大学硕士学位论文 空间几何对象位置，可以解决实际问题。 第6 章对本文进行总结，也对今后的研究目标进行展望。 第8 页 西华大学硕士学位论文 第二章安全多方计算密码学基础 2 1 安全多方计算的标准符号 p ，q大素数 z 。模1 7 的整数集合，乙= o ，1 ，n 一1 z模7 的整数乘法群，z ：= 缸l x z 。：g e d ( x ，咒) = 1 ) 卵例包含p 个元素的有限域 最，皿公开加密算法和解密算法 ixl整数x 的位长度，i xl = l + l l o g ：x _ 工1 ，也表示x 的绝对值 g e d ( x ，y ) 求x 和y 的最大公约数 z l i yx 和y 联接 c m 伍求x 和y 的最小公倍数 2 2 安全多方计算基本术语 2 2 1 参与者行为 参与者即参与协议的各个方，他们提供输入、得到输出并且执行实际计 算。我们用p p ，p ：，p ，z ) 表示参与者集合，a 表示单独的参与者各方。 安全多方计算协议的参与者的行为，决定了安全多方计算协议设计的难 易程度：根据参与者在协议中的行为，我们将参与者分为三种类型。 诚实参与者：在协议的执行过程中，诚实参与者完全按照协议的要求完 成协议的各个步骤，同时保密自己的所有输入、输出及中间结果。 第9 页 西华大学硕士学位论文 注意，诚实参与者可以根据自己的输入、输出及中间结果推导另外的参 与者的信息。诚实参与者与半诚实参与者的区别仅在于：诚实参与者不会被 攻击者腐败。 半诚实参与者：在协议的执行过程中，半诚实参与者完全按照协议的要 求完成协议的各个步骤，同时可能将自己的所有输入、输出及中间结果泄露 给攻击者。 恶意参与者：在协议过程中，恶意参与者完全按照攻击者的意志执行协 议的各个步骤：他不但将自己的所有输入、输出及中间结果泄露给攻击者， 还可以根据攻击者的意图改变输入信息、中间结果信息，甚至终止协议。 安全多方计算协议，需要保护诚实的各种安全需求；不保护半诚实参与 者的安全；并且，需要及时发现恶意参与者。 2 2 2 变量 全部的变量空间胞括协议执行过程中生成的所有变量，如：输入、输 出和本地数据。协议在一次特定的执行工程中，每个变量都有一个专门的值， 如本地变量，事实上是只有特定的参与者和参与者集合能看到的相应的专门 的值。用k 表示每个参与者的观察，参与者集合e 的观察k 是指只中所有 参与者的观察的总和。看到一个变量和知道一个变量是不同的，如果变量x 在参与者的观察中，则称参与者看到这个变量，如果参与者能够从他的观察 值中计算出x ，则称参与者知道这个变量。 2 2 3 攻击者及其能力 攻击者：安全多方计算协议中，将一个企图破坏协议安全性或正确性的 人称为攻击者。攻击者可以腐败参与者的一个子集。我们可以将攻击者看成 一个电脑黑客，他可以破坏或控制参与者的计算机。 根据攻击者腐败的参与者的不同类型，攻击者可以分为两类： 被动攻击者：如果腐败者集合中的被腐败者都是半诚实参与者，即攻击 者只能得到被腐败者的所有输入、输出及中间结果，那么称这个攻击者是被 第1 0 页 西华大学硕士学位论文 动攻击者，或称攻击者是被动的。被动攻击者不能改变被腐败者的输入及中 间结果，也不能终止协议的运行。 主动攻击者：如果腐败者集合中的被腐败者有恶意参与者，即攻击者不 但能得到被腐败者的所有输入、输出及中间结果，还能指示被腐败者改变输 入信息、中间结果信息，甚至终止协议的运行。那么称这个攻击者是主动攻 击者，或称攻击者是主动的。 攻击者能力的大小，还取决于另一个重要的参数，就是攻击者能够腐败 的子集的结构和数量。如果任意的参与者子集都能被腐败，那么就没有什么 协议是安全的，我们甚至不能定义所有的参与者都是腐败的协议的安全性。 因此，必须对攻击者能够腐败的集合进行一些限制，我们用攻击者结构来定 义攻击者能够腐败的子集集合。 攻击者结构a ：在一个安全多方计算协议中，攻击者可以腐败的子集的 集合称为攻击者结构( 或称腐败结构) 。也记为一攻击者，一个一攻击 者只能腐败一中的一个参与者子集。 经常考虑的攻击者结构有两类： l 、门限结构a ： a ： 所有参与者人数小于t 的集合) ) 。 2 、普通结构a ： a ，a 。) 显然，如果有攻击者结构a ，b c a ，那么b a 。也就是说，如果 一个攻击者能腐败子集a ，那么攻击者能腐败属于a 的任意子集。 根据攻击者对腐败子集的选取方案，攻击者还可分为静态攻击者和动态 攻击者： 静态攻击者：在协议开始前就确定了腐败子集的攻击者称为静态攻击 者。 动态攻击者：在协议过程中随时改变腐败子集的攻击者称为动态攻击 者。 静态攻击者是安全多方计算中经常考虑的攻击者，在实际的安全多方计 算中，由于动态攻击的复杂性，目前相对考虑较少。 第l l 页 西华大学硕士学位论文 2 2 4 通信模型 在安全多方计算中，通常考虑的通信模型概念有：密码模型和信息理论 模型、同步通信和异步通信、广播等。 密码模型：该模型在公开信道进行，攻击者可以得到协议过程中的所有 交换信息，信息的安全性完全依赖于加密算法的安全，即必须要假定攻击者 没有破译密码的能力。 信息理论模型：该模型假设参与者通过他们自己的安全通道交换信息， 即攻击者不能了解诚实参与者之间交换的任意信息，即使攻击者有无限的计 算力，也不能对诚实者之间的数据安全构成威胁。 同步通信与非同步通信：在通信过程中，通信各方有一个时间标记，一 个发送的信息必须在一定的时间内到达的通信称为同步通信。相反，没有时 间限制的通信称为异步通信。 在安全多方计算中，为了方便研究，一般都假设通信双方的通信是同步 的。在异步的模型中，信息发送可能没有保障，但是异步模型可以解决更多 问题。 上述概念可以组成：密码一同步通信模型、信息理论一同步通信模型、密 码一异步通信模型、信息理论一异步通信模型i 广播：一个参与者同时发送同一个信息给若干个参与者的通信行为称为 广播。 如果攻击者是主动的，并且广播者是个恶意参与者时，广播会带来一个 难于解决的问题。所以说，如何防止广播者的恶意行为( 如广播者给不同的 参与者不同的信息) ，是比较困难的，在新的安全多方计算协议的设计中应 该加以考虑。 2 2 5 半诚信模型 在半诚信模型中参与者除了正确的遵守协议外，会保留所有中间计算结 果。宽松的讲，一个半诚信参与者的集合在参与协议后可以从每个参与者的 输入和输出来秘密地计算厂。 第1 2 页 西华大学硕士学位论文 定义2 1 ( 半诚实模型) ：令f ：( o ，1 ) ) h ( o ，1 ) ) 是m 元函数， z ( 墨，以) 表示五( 墨，以) 中的第j 个元素。对 j = f 1 ，) c m 卿= 1 ，m ，令乃( x ，x 。) 表示子序列五( _ ，x 。) ， 以( 五，) ，r i 是一个计算厂的萌协议。在用输入i = ( 一，x 。) 执行协议 的过程中， 第j 个参与者卑的观察表示为k n ( i ) 。 令 妒( i ) 蟛= ( j ，k 。n ( i ) ，v 。，n ( i ) ) ，其中i = ，i t ) 。 决策阶段：在厂是一个确定的厩函数的情况下，如果存在一个多项式 时间算法s ，使得每个如上所述的毋都有( 2 一1 ) 式成立，则说协议秘密计 舆 o c 一 s ( ，( 气，) ，石( i ) ) ) i 。( o 。1 ) ) 。兰 玎( x ) ) ；。( o l 广) _ ( 2 1 ) 生成阶段：如果存在多项式时间算法s ，使得每个如上所述的只都有 ( 2 2 ) 式成立，则说明协议n 秘密计算厂。其中o p n ( x ) 表示在观察1 ( x ) 中 执行协议的过程中，所有参与者的输出序列。 0 ( ，( 黾，x j ，) ，乃( x ) ) ，厂( x ) ) ) ；。( o ，l 尸暑 w ( x ) ，o p 兀 ) ) ；。( o l r ( 2 2 ) 2 3 计算复杂性与安全需求 2 3 1 计算复杂性 计算复杂性是定义安全多方计算安全性的一个重要概念，这里主要涉及 计算不可区分与统计不可区分两个概念。 可忽略函数：一个函数：nh 【o ，1 】，如果对任意首项为正的多项式p ， 和所有充分大的7 ，有：q ) 1 p ( 刀) 。那么称j 2 ：nh 【0 ，1 为可忽略函数。 随机变量集：一个随机变量集是一个族： x 。) 。，每一个x 。都是一个随 机变量( 或者分布) ，s 是一个集合，如整数集。 两个随机变量集，x 何= x 。 憾。和y 珂= 匕) 憾。，如果对任意的w s 和任意的口有： 第1 3 页 西华大学硕士学位论文 p 瓦= 口 - p 匕= 口 称这两个随机变量集具有相同的分布，记为x 暑y 统计不可区分：两个随机变量集x 和y ，如果存在一个可忽略函数 x ：nh 0 ，l 】，和所有的w s ，有： p r x 。= c r - p r y 。= 口 i ( 1 w 1 ) 则称这两个随机变量集是统计不可区分的，记为x 量y 计算不可区分：两个集合，x 何= k ) 。，和y 村= 】，。) 。，如果对任意 的多项式级的计算电路族 见) 。，存在一个可忽略函数：nt - - ) 0 , 1 满足： i p r d ( w ，k ) = 1 卜p r 乜( w ，匕) = 1 1 i 3 ) 参与计算的情况。在实际的应用中，提供统 计信息的用户数往往很多，因此，多方统计问题更具有实际的应用价值。 定义4 1 ( 安全多方统计问题) ：假设有个用户p 。，p ：，p 。参与计算， 每个用户p ，：f i n ，个私有数据，记b = ( 嘞，y 口) i ，= 1 ，2 ，吩，：。玎，= ，1 ) 他们希 望在数据集合d = ij 口上进行统计分析，而任何一个用户p ；都与不愿意向其 函 他用户泄露自己的私有数据集d 第2 4 页 西华大学硕士学位论文 4 2 统计分析的基本知识 引理4 1 5 2 假设集合刃包含有7 个数据记录，其中每个记录仅包含两 个小同的i 贝，我们记d = ( 鼍，乃) l i = 1 ，2 ，以) ，则： ( 1 ) 平均值；2 i l 乞瑚一，歹2 i 1 己蚓咒： m 相芏玄黼2 。( 一一_ ) ( m 一_ ) ( 2 ) 相关系数，= 1 叁尘尘兰= 竺竺一： ：。( t - x ) 2 ：。( m 一歹) 2 ( 3 ) 线形回归方程y ：h + ( 歹一b x ) ，其中6 ：委等等 4 3 安全多方的基本统计分析问题 本节我们讨论多方参与的平均值及相关系数计算协议，为了描述方便， 我们首先假设每一条记录只包含两个不同的项( 五，y i ) ，对于有多个项的情 况可以依此类推。 ( 1 ) 平均值的计算协议 为了计算口中x 与y 的平均值，可以首先让每个用户p i 在本地计算 各自的私有数据的和，然后再采用第三章中的安全多方求和协议k l u l t y _ s e e 计算所有数据的总和，最后，每个用户在本地计算平均值，我们命名协议为 av e r a g e ： 输入：1 1 1 个用户各自的数据集合d 。 输出：廖个用户都得到数据集合刃中j 和j ，的平均值，但是都不知道除 了自己的数据数据集合d 以外的任何数据。 ( 1 ) 每个用户各自在本地对自己的局部数据求和， 得到五= ：。x o 和i = ：。均。 第2 5 页 西华大学硕士学位论文 ( 2 ) m 个用户共同调用安全多方求和协议肋t y _ 5 讹计算 x = m u l t y _ 配瞅墨，置，l ) 和y = m u l t y _ 吼拟x ，e ，匕) 。 ( 3 ) 历个用户在等到j 和j ，后， 分别在本地计算叉= i x = i 乙m 汹五和可= i y = 去：，z 。玎玎“。l ，l刀“。1 协议a v e r a g e 实现的主要步骤为调用中安全多方求和协议m u l t y _ s u m , 由于安全多方求和协议肋t y _ s u m 是安全有效的，所以该协议也同样安全有 效，能够在保证各个用户的私有数据不泄露的情况下，实现求所有数据的平 均值的目的。若每个用户的数据个数也需要保密，同样也可以再使用一次安 全求和协议计算数据总量1 i 。 a v e r a g e 协议在第一步和第三步中的计算代价分别为0 ( 而和0 ( m 2 ) ， 由于本协议只在第二步调用了一次安全多方求和协议m u l t y _ s u m , 那么可以 知道本协议的通信次数仍然小于2m 2 ，通信总量还是小于2 m 2d ，计算的时 间复杂度同样为小于0 ( 一晰2 ) 次基本运算的。 ( 2 ) 相关系数计算协议 根据引理4 1 ，相关系数，：产= 三圣兰二垒尘 ：。( 一一；) 2 ：。( 咒一歹) 2 一 己i - l x i y i n x y ( ：。# 一门丸：。拜一，z _ 2 ) 6 ：叁生! 苎丝二! 型。 ：。# 一，z _ 2 为协作进行相关系数及线性回归分析，每个用户只可以首先各自在本地 对自己的私有数据计算：。x i , j y l , j 、：。x “2 及2 。一，然后分别对它们用协 议m u l t y _ s u m 进行安全多方求和，最后每个用户都可以在本地计算出，和b 。 我们命名协议为c o r r e l at i o n ： 输入：1 1 1 个用户各自输入私有数据集合口 输出：m 个用户共同在这些数据集合的并集上计算相关系数，得到 第2 6 页 西华大学硕士学位论文 ，卜产至丝，一一，卜ftx,r,-nxyb 。 ，一1 2 = = = = = 垒兰= = = = = = = = = = = = 2 ，一1 2 = = = = = = = = = o ( 巧：一玎牙2 ) ( 弓：一刀f 2 )一甩叉2 ( 1 ) f 1 个用户各自输入私有数据集合q 。 ( 2 ) 1 1 1 个用尸共同调用协议月v e r a g e ，执行a v e r a g e ( d l ，砬，巩) ， 得到平均值叉= 鲁= 丢：。置和7 = i y = 去：。k 。力玎“2 l ”玎“8 1 ( 3 ) 历 i n p # r 自在本地计算毛l ：= 盖。鼍，_ ，y i ，、= 二。、 毛：= 。一，。 ( 4 ) 历个用户共同调用安全多方求和协议m u l t y _ s u m ，计算 = m u l t y s u m ( t x , r , ，& 矿，) 、& z = m u l t y s u m ( t x ；，) ， i ：= m u l t y s u m ( t z ? ，礓，) o ( 5 ) 每个用户在收到广播数据后，各自在本地计算相关系数 r 卜蛙丝，6 卜 f 一， 一 、( 巧z 一刀) ( i ：一九】，) 吒巧一n x y 本协议是安全有效的。具体分析我们不在叙述。 由于协议c o r r e a t i o n 在第二步中调用了协议a v e r a g e 来求平均值， 在第四步中调用了三次安全多方求和协议m u l t y _ $ u m , 所以我们可以计算出 协议c o r r e j a t i o n 的通信次数是小于5 * 2 肌2 的，通信总量小于5 * 2m 2d 计 算复杂性为0 ( 肿珑2 ) 次基本运算。 4 4 本章小结 在安全多方计算中，很多情形下有多个用户协作参与计算。本章介绍了 常用安全多方统计分析模型的基础上，专门针对此种应用分析了能够解决问 题的协议，基于改进的安全多方求和协议，改进了多用户参与计算的求平均 第2 7 页 西华大学硕士学位论文 值、求相关系数