（计算机科学与技术专业论文）安全多方排序协议的研究.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 ) 正是在这样的背景 之下日益引起人们的关注。 安全多方计算问题最早由a c y a o 提出，描述如下：有n 个参与者 ，罡，只，每个参与者拥有一个输入五，x 2 ，气，要以一种安全的方式 共同计算一个函数厂( 五，x 2 ，毛) 。这里的安全是指输出结果的正确性 与输入信息、输出信息的保密性，即计算结束之后各参与方只能得到 正确的厂( 五，而，t ) 的值，而不能了解其他方的其他任何信息。 安全多方计算是电子选举、电子拍卖、门限签名等许多应用得以 实现的密码学基础。安全多方计算协议牵涉到众多的底层密码协议， 目前提出的方案使用到了秘密共享、公钥和私钥加密、同态加密以及 不经意传输等诸多常用的安全协议和算法。由于安全多方计算理论对 于网络协议的安全具有重要的指导作用，仍然有很多研究人员投入到 这个领域来，并且己经取得了丰硕的成果。目前安全多方计算的研究 领域包括保护私有信息科学计算问题，保护私有信息计算几何问题， 保密数据挖掘问题，安全多方统计分析问题等。 本文的主要成果如下： l 、对s m c 的理论、技术与研究现状进行了系统总结，提出了 安全多方多数据排序问题，并将前面的技术应用于解决安全多方多数 据排序的问题。为安全多方多数据排序问题提出了一个模型，该模型 涉及到了安全多方多数据排序问题的各个方面。 2 、提出了一个用r s a 密码体制和不经意传输来解决安全多方 多数据排序问题的解决方案。该方案与多次使用y a o 的协议相比，在 安全性和公平性上都有很大提高。 3 、提出了一个基于大数分解困难性的解决安全多方多数据排 序问题的解决方案，该方案可以保证安全性、公平性，同时该方案不 需使用任何的加密算法，效率很高。 关键词：密码学；安全多方计算；安全多方多数据排序；r s a 同 态加密；大数分解困难性 北京邮电大学硕士论文 r e s e a r c ho fs e c u r en ，t i p ar t y ra n k i n g p r o b l e m a b s t r a c t a l o n gw i t ht h ec o n t i n u o u sd e v e l o p m e n to fn e t w o r kt e c h n i q u e ，a n d w i t ht h ea p p e a r a n c eo fh i g hq u a l i t yc o m p u t e ra n dn e tg r i d ，t h em e a n i n g s a n dm o d eo fc o m p u m t i o n sa l em o s t l yc h a n g e d a l lo ft h i sm a k e si te a s y t h a tt h eu s e r sc a nm a k eu s eo ft h ep o w e r f u lc o m p u t a t i o nr e s o u r c e s i n s u c hc i r c u m s t a n c e ，t h es a f e t yo fu s e r s d a t ab e c o m ev e r yi m p o r t a n ta n d n e c e s s a r y s 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 nc o m e sf o r t h 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 nw a sf i r s t l yb r o u g h tf o r w a r db ya c y a oi n l9 8 2 ： t h e r ea r enp a r t i c i p a n t sp l ，w h ow a n ts a f e l yc o m p u t eaf u n c t i o n t o g e t h e r a n dt h ew o r ds a f em e a n st h a tt h ec o r r e c t n e s so fo u t p u tm e s s a g e a n dt h e s e c r e c yo fi n p u t a n d o u t p u tm e s s a g e c o n c r e t e l y ，e a c h p a r t i c i p a n tp , h a sh i ss e c r e ti n p u tm e s s a g e 玉，a n da l lt h enp a r t i c i p a n t s c o m p u t eaf u n c t i o nt o g e t h e r ：厂( 五，屯，吒) ，w h e nc o m p u t a t i o nh a sb e e n f i n i s h e d ，e a c h 霉k n o w so n l yv a l u eo f 厂( ，屯，毛) ，b u t n o to t h e r i n f o r m a t i o 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 np r o t o c o li sa l li 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 i so fm a n yd i s t r i b u t e dc r y p t o g r a p h i cp r o t o c o l s ， s u c ha st 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 de l e c t r o n i ca u c t i o n e t c 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 c e n c r y p t i o na n dz e r o k n o w n e d g ep r o o f ) a n ds o m eb a s i cp r o t o c o l si n d i s t r i b u t e d c o m p u t a t i o n( e g o b v i o u st r a n s f e r a n d b r o a d c a s t p r o t o c 0 1 ) r e s e a r c h i nt h es m ca r e ah a sb e e n f o c u s i n g o n p r i v a c y p r e s e r v i n gs c i e n t i f i cc o m p u t a t i o n s ，p r i v a c y p r e s e r v i n gg e o m e t r i c c o m p u t a t i o n s ，p r i v a c y p r e s e r v i n g d a t a m i n i n g ，p r i v a c y - p r e s e r v i n g s t a t i s t i c a la n a l y s i se t c t os u mu p ，t h ei n n o v a t i o n so ft h i st h e s i sc o u l db es u m m a r i z e da s f o l l o w i n g ： i i i 北京邮电大学硕士论文 l 、w es u m m a r i z et h e o r y 、t e c h i n i q u ea n da c t u a l i t yo fs m c ，a n d p r o p o s es m m r ( s e c u r em u l t i p a r t ym u l t i - d a t ar a n k i n g ) p r o b l e m w eg i v e am o d e la b o u ts m m rp r o b l e mt od e s c r i b ei t 2 、w ep r o p o s ea p r o t o c o l b a s e do nr s ah o m o m o r p h i c e n c r y p t i o na n d0 tp r o t o c o lt os o l v es m m rp r o b l e m t h i sp r o t o c o l s a t i s f ys e c u r i t ya n df a i m e s sc o m p a r i n gu s i n gy a o sp r o t o c o lr e p e a t e d l y 3 、w r ep r o p o s eap r o t o c o lb a s e do nl a r g en u m b e rf a c t o r i z a t i o nt o s o l v es m m r p r o b l e m t h i sp r o t o c o ln o to n l ys a t i s f ys e c u r i t ya n df a i m e s s ， b u ta l s od o n tu s ea n ye n c r y p t i o n i th a sb e t t e re f f i c i e n c y k e yw o r d s ：c r y p t o 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 ； s e c u r e m u l t i p a r t y m u l t i - d a t ar a n k i n gp r o b l e m ；r s ah o m o m o r p h i c e n c r y p t i o n ；d i f f i c u l t yo fl a r g en u m b e rf a c t o r i z a t i o n ； i v 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期： 关于论文使用授权的说明 本人完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在 校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅：学校 可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段 保存、汇编学位论文。 本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期：塑皇：呈：! 1 日期：w 筇鼍j 北京邮电大学硕士论文 第一章引言 1 1 密码学及安全多方计算介绍 1 1 1 密码学介绍 计算机和网络技术的发展，使我们进入了信息时代。i n t e r n e t 的迅速普及使 人们之间的信息交流变得更加容易，更加频繁。信息技术的发展是人类社会的一 次革命，它将在很大程度上改变人们的生活和观念。信息时代给我们一个最为重 要的观点是：信息本身就是财富，是一种重要的资源。网络给社会和人们的日常 生活带来极大方便和经济效益的同时，也给一些不法份子以可乘之机。由于信息 网络国际化、开放化的特点，使之在给人们提供信息共享同时，也给人们带来了 不安全的因素，信息本身作为一种财富其自身的安全受到了严重的威胁。从长远 来看，人类要真正地进入信息社会，首先就要解决信息安全的问题，否则我们憧 憬的信息社会将是一个无序、混乱的社会。从短期来看，信息安全问题如果不能 很好地解决，那么网上信息服务、电子商务、电子银行等就无法顺利地开展业务。 密码学为信息安全提供了关键理论和技术。密码学有着悠久的历史，在2 0 世纪4 0 年代以前，密码学还只是为军事和政治服务。1 9 4 9 年，s h a n n o n 1 发表了 一篇具有划时代意义的论文“保密系统的通信理论，首次用概率统计的观点对 明文、密文、密钥信息的传送进行了数学描述和定量分析，提出了通用的通信系 统模型，标志着密码学的研究走上了科学的轨道。7 0 年代中期，随着计算机技术、 通讯技术的发展，为了适应信息化的要求，公钥密码体系 2 和美国数据加密标 准的诞生引发了密码学研究的重大变革。以公钥密码为基础的数字签名、认证加 密以及数字证书等技术在信息安全领域有着广泛的应用。而今，密码学的理论和 技术不再是仅仅为少数人掌握的服务于军事和政治的学科，而是渗透到了人类社 会的方方面面，在人类经济生活、日常生活中的应用范围日益扩大。这十几年来， 密码学技术得到了空前的发展，关于密码学的进展应用可参见文献 3 。 密码学尤其是现代密码学为解决信息安全问题提供了许多有用的实用技术， 它可用来对信息提供保密性，对身份进行认证，保证数据的完整性和不可否认性。 现代密码学的内容很多，主要可分为两大部分：算法和协议。算法包括加密算法、 解密算法、数字签名算法、单向函数( h a s h 函数) 算法和伪随机数的生成算法等。 协议包括认证协议、知识证明协议、密钥交换协议、密钥托管协议、电子支付协 北京邮电大学硕士论文 议、安全多方计算协议等。流行的加密算法分为两类：分组密码算法与公钥密码 算法。最著名的分组加密算法有美国的数据加密标准d e s 算法、高级加密标准a e s 算法、r c z 算法、i d e a 算法和r c s 算法等。最著名的公钥密码算法有r s a 算法、 e l g a m a l 算法和背包算法等。 i 1 2安全多方计算介绍 考虑这样一个问题：一组参与者，他们之间互不信任，但是他们希望安全地计 算一个约定的函数。这个函数的输入由这些参与者提供。这里安全地计算一个约 定函数的意思是：即使在有不诚实参与者的情况下，每个参与者都能得到正确的 计算结果，同时每个参与者的输入是保密的。也就是说一个参与者无法得知另一 个参与者的输入，除非某些参与者的输入可以从函数的输出推导而得，这就是著 名的安全多方计算问题。如果有可信第三方t t p 的存在，这个问题的解决是十分 容易的，参与者只需将自己的输入加密传送给t t p ，由t t p 计算这个函数，然后将 计算的结果广播给每一个参与者，这样每个参与者都得到了正确的结果，同时自 己的输入也是保密的。然而在现实的应用中很难找到这样一个所有参与者都信任 的t t p ，因此安全多方计算的研究主要是针对无t t p 的情况下如何安全地计算一个 约定函数的问题。安全多方计算在电子选举、电子投票、电子拍卖、秘密分享、 门限签名等场景中有着重要的作用。 1 i 3 安全多方计算在密码学中的地位 安全多方计算协议利用了许多基础的密码学协议，如数字签名零知识证明 等，也利用了许多分布式环境的基础协议，如广播问题和b y z a n t i n e 问题( b a ) 。 同时安全多方计算协议中的一些理论和解决问题的思路又可以应用到许多其他 密码学协议( 如电子选举电子拍卖等) ；从广义上讲在分布式的环境中有多个参 与者参与的密码学协议都是安全多方计算的一个特例这些密码学协议都可以看 作是一组参与者之间存在各种各样的信任关系，最弱的信任关系就是互不信任。 他们希望通过交互或者非交互的操作来完成一项工作：计算某个约定的函数。这 些协议的不同之处在于协议计算的函数是不一样的，例如电子拍卖是计算出所有 参与者输入的最大值或最小值，而门限签名是计算一个正确的签名。 可以将密码学中的各种协议算法在密码学中的地位用图i - i 来表示： 北京邮电太学颈论文 围卜1 轩码学中的各种协议算法在密码学中的地位 12 安全多方计算的研究背景和研究现状 最早的安全多方计算理论是由y a o 在文献 4 中提出的两方安全计算协议。5 年以后，c o l d r e i c h ，m j c a l i 和w i g d e r s o n 在文献 5 中提出了可以计算任意函数 的基于密码学安全的安全多方计算协议。 目前研究者们经常使用的两种安全模型是密码学安全模型和信息论安全模 型。在密码学安全模型中，h 个协议的参与者连接在一个同步的网络中，他们之 间的通讯通道是不安全的，所有协议的参与者( 包括攻击者) 的计算能力都是有 限的。在信息论安全模型中，n 个协议的参与者连接在一个同步的网络中，他们 之间有安全的通讯信道，共享一个有身份认证的广播信道，攻击者的计算能力都 是无限的。 5 中的协议考虑密码学安全模型。在这种模型下，他们证明了在被动攻击 的情况下，月一s e c u r e 的协议是存在的：在主动攻击的情况下，“一1 ) 一s e c u r e 的 协议是存在的。 5 也展示了如何有效地构造这样的协议。 c h a u m ，c r e p e a u 和d a m g a r d 在文献 6 中对信息论安全模型进行了研究。他们 证明了在信息论安全的模型中，在被动攻击情况下，抽一l 卜s e c u r e 的协议是存 在的，在主动攻击的情况下，( 1 兰j 一1 ) 一s e c u r e 的协议是存在的。 12 j 由于c h a u m 和g o l d r e i g n 提出的协议大量地用到了零知识证明，协议参与者之 间需要传输大量的数据，这使得协议显得极其不适用。但是，这些论文指明了安 全多方计算广阔的理论前景，安全多方计算吸引了众多研究者的注意。 此后，许多学者在如何提高安全多方计算协议的效率、如何对安全多方计算 进行形式化的定义、如何对通用的安全多方计算协议进行剪裁，使之能更加有效 地适用于不同的应用环境、新的安全多方计算协议的构造方法、安全多方计算攻 插 滤嚣：i 吝问 基m g h 别 1 圣 盲 洲 越 瓢 密 难 俘 加 学 、 称 散 咐 对 岛 征 非 常 识 ， 知 密、敷 霉 加 代 、 称 泉 名 对 抽 签 宇 法 论 数 算 数 学 ： 试 码 础 协 密基 础 末 学 基 垂 眭 北京邮电大学硕士论文 击者结构定义等方面进行了大量的研究。 g o l d w a s s e r 和l e v i n 在 7 中提出了对于计算模型下，大部分协议参与者( 超 过半数) 都被买通情况下的安全多方协议。c h o r 和k u s h il e v i t z 提出了对于安全信 道模型下，大部分协议参与者( 超过半数) 都被买通情况下的安全多方协议。 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 在 8 中提出了对于在不安全的通讯信道中，拥 有无限计算能力的攻击者模型下的安全多方计算协议。o s t r o v s k y 和y u n g 在 9 中对于安全信道模型下的移动攻击者( o b i l ea d v e r s a r i e s ) 进行了研究。 m i c a l i r o g a w a y 1 0 和b e a v e r 1 1 对安全信道模型下的安全多方计算给出了形式 化的定义， 1 2 给出了安全多方计算协议应有的性质。 概括起来现有的研究主要集中在如下一些方面： 1 、一般意义的安全多方计算协议。这类研究的目的是设计一种高效的、安 全的、能够计算任意函数的安全多方计算协议。希望能够通过这样的协议一劳永 逸地解决所有的涉及到安全多方计算的问题。在这方面研究的代表性文献主要有 e 1 3 ，1 4 ，1 6 ，1 7 2 1 等。 2 、对一般化的安全多方计算协议进行剪裁。这类研究注意到如果一个协议 是广泛适用的，那么必然会以牺牲一些性能为代价来满足其广泛适用性。针对于 某一个具体的应用如电子选举，对一般化的安全多方计算协议进行一点剪裁，去 掉一些对某个具体应用没有意义的部分可以大大提高效率。这类研究往往称作安 全多方计算的应用研究，这类研究的主要目的是将安全多方计算的理论和技术应 用到一个具体应用中去。在这方面研究的文献主要有 2 2 - 3 2 等。 3 、安全多方计算的定义。安全多方计算的目的和应该具备的性质都为在这 一领域研究的学者所熟知，但是安全多方计算至今还缺乏一个为大家所认同的完 备的定义，这主要是因为安全多方计算协议的构造形式可以有多种，各个学者研 究的安全模型也是不一样的。r c a n e t t im i c a l ir o g a w a y 和b e a v e r 对存在安全 信道的网络中的安全多方计算给出了一些形式化的定义，这些定义首先考虑定义 在理想的情况下存在可信第三方t t p 时的安全多方计算，然后考虑如何用协议来 模拟t t p 的作用这方面研究的文献有 1 7 ，1 8 等。 4 、新的安全多方计算协议构造方法。目前大部分学者提出的安全多方计算 协议都使用了v s s ( v e r i f i a b l es e c r e ts h a r i n g ) 子协议作为其构造基石，因而 这类协议在大体结构上都是类似的。有没有其他的方法来构造安全多方计算协议 呢? 文献 2 6 ，3 3 - 3 6 等对此作了研究。 5 、多方计算协议生成器。许多安全多方计算协议的研究在研究了如何安全 4 北京邮电大学硕上论文 地计算定义在域上的运算就停止了，因为这从理论上讲，所有函数都可以被安全 地计算了。但是这离实际应用还有一步需要跨越，多方计算协议生成器的作用就 是为了弥补这最后一步。而对于计算协议生成器的输入是函数f 和如何计算域上 定义的基本运算的子协议，输出是安全计算f 的协议。许多学者提到了安全多方 计算协议生成器，但是没有对它进行详细的研究。 1 3 本文的主要成果 本文的主要成果如下： 1 、 对s m c 的理论、技术与研究现状进行了系统总结，提出了安全多方多数 据排序问题，并将前面的技术应用解决安全多方多数据排序的问题。为安全多方 多数据排序问题提出了一个模型，该模型涉及到了安全多方多数据排序问题的各 个方面。 2 、 提出了一个用r s a 密码体制和不经意传输来解决安全多方多数据排序问 题的解决方案。该方案与多次使用y a o 的协议相比，在安全性和公平性上都有很 大提高。 3 、提出了一个基于大数分解困难性的解决安全多方多数据问题的解决方 案，该方案可以保证安全性、公平性，同时该方案不需使用任何的加密算法，效 率很高。 1 4 本文的组织结构 本文主要对安全多方计算的一个应用一安全多方多数据排序做了研究。本 文的组织如下：第二章介绍了和安全多方计算相关的技术，包括安全多方计算的 模型和解决安全多方计算的密码学工具；第三章对安全多方数据的比较问题做了 一个阐述，总结了前人在安全两方比较方面做出的贡献，提出了安全多方多数据 比较这个问题，并对这个问题进行了定义。第四章我们提出了一个用r s a 密码体 制来解决安全多方多数据排序的方案，并给出了正确性安全性证明和效率分析， 该方案可以保证公平性。第五章我们给出了一个基于大数分解困难性的解决安全 多方多数据排序的协议，并给出了正确性安全性证明和效率分析，该方法没有使 用任何加密算法，效率上有了很大提高并同时可以保证公平性。第六章进行了总 结。 北京邮电大学硕士论文 第二章安全多方计算技术 2 1安全多方计算问题 安全多方计算问题：有力个参与方，每个参与方拥有一个秘密输入，他们希 望在不泄漏自己的秘密输入的情况下，用这些秘密输入共同计算一个函数。计算 结束后，要求每一方都能接收到正确的输出( 正确性) ，而且每一方只能了解他 们自己的输入和输出( 保密性) 。 其形式化的定义是：假设有力个参与方足，只，每一个参与方拥有一个秘 密输入，设只的秘密输入是镌o = 1 9 0 9 n ) 。这n 方共同计算一个函数 厂( 玛，) = ( 乃，以) ，计算结束以后，每个参与方只只能了解自己的输出y i ， 而不了解其他方的输入、输出信息。 安全多方计算协议：解决安全多方计算问题的协议，称为安全多方计算协议。 安全多方计算协议的研究主要有两个方向：一般安全多方计算协议和特殊安全多 方计算协议。一般安全多方计算协议需要用到电路计算，陷门置换的知识，效率 非常低，不实用。因此，设计特殊的安全多方计算协议是目前安全多方计算协议 研究的主要任务。 2 2 安全多方计算的模型 2 2 1 参与方 参与者即参与协议的各方，参与者提供输入、得到输出并且执行实际计算。 我们用饵，只) 表示参与者集合。安全多方计算协议的参与者的行为，决定 了安全多方计算协议设计的难易程度，根据参与者在协议中的行为，我们将参与 者分为三种类型。 诚实参与者：在协议的执行过程中，诚实参与者完全按照协议的要求完成协 议的各个步骤，同时保密自己的所有输入、输出及中间结果。注意，诚实参与者 可以根据自己的输入、输出及中间结果推导另外的参与者的信息。诚实参与者与 半诚实参与者的区别仅在于：诚实参与者不会被攻击者腐败。 半诚实参与者：在协议的执行过程中，半诚实参与者完全按照协议的要求完 成协议的各个步骤，同时可能将自己的所有输入、输出及中间结果泄露给攻击者。 6 北京邮电大学硕士论文 恶意参与者：在协议过程中，恶意参与者完全按照攻击者的意志执行协议的 各个步骤。他不但将自己的所有输入、输出及中间结果泄露给攻击者，还可以根 据攻击者的意图改变输入信息、中间结果信息，甚至终止协议。 安全多方计算协议，需要保护诚实的参与者的各种安全需求，不保护( 或者 不关心) 半诚实参与者的安全，并且需要及时发现恶意参与者。 2 2 2 攻击者 所谓攻击者( 或称敌手) ，就是在安全多方计算协议中，企图破坏协议安全 性或正确性的人。攻击者可以腐败参与者的一个子集。我们可以将攻击者看成一 个电脑黑客，他可以破坏或控制参与者的计算机。根据攻击者腐败的参与者的不 同类型，攻击者可以分为两类。 被动攻击者：如果腐败者集合中的被腐败者都是半诚实参与者，即攻击者只 能得到被腐败者的所有输入、输出及中间结果，那么称这个攻击者是被动攻击者， 或称攻击者是被动的。被动攻击者不能改变被腐败者的输入及中间结果，也不能 终止协议的运行。 主动攻击者：如果腐败者集合中的被腐败者有恶意参与者，即攻击者不但能 得到被腐败者的所有输入、输出及中间结果，还能指示被腐败者改变输入信息、 中间结果信息，甚至终止协议的运行。那么称这个攻击者是主动攻击者，或称攻 击者是主动的。 2 2 3 通信模型 安全多方计算的通信信道模型分为同步模型( s y n c h r o n o u s mo d e l ) 和异步模 型( a s y n c h r o n o u sm o d e l ) ，主要的安全信道模型是同步的点到点安全信道 ( p r i v a t e c h a n n e l ) 和带广播的安全信道。 同步通信模型：所有参与方共享一个全局时钟，一个时钟周期称为一轮 ( r o u n d ) 。在一个时钟周期开始时，所有成员接收发送给自己的消息，然后执行 本周期内其他操作，计算并发出自己的消息。 异步通信模型：不存在一个全局时钟，一个消息从发送到接收要经过不同的 时钟周期。接收方接收的消息可能是延迟的，也可能是无序的，但最终都可以收 到。异步通信模型更符合实际的i n t e r n e t 环境。 点到点安全信道：假设每对成员间存在可靠的安全信道( p r i v a t ec h a n n e l ) ， 该信道传输的消息不会泄露给其它成员。在实际通信网环境下，通过加密技术可 7 北京邮电大学硕士论文 以在不安全信道上实现安全通信。 广播信道：广播信道( b r o a d c a s tc h a n n e l ) 中每一个成员发送的消息及其身 份标识符都可以被其它所有的成员收到，每一轮只有一个成员发送消息。局域网 中存在天然的广播信道，其它网络可以通过广播协议模拟实现广播信道。 安全广播信道：多方计算的安全广播信道模型中，发送方的身份标识及发出 的消息一定可以被接收方收到。每一轮通信过程中只有一个成员发送消息：任意 两个成员间存在安全的点到点信道。 目前多数安全多方计算都是研究带有安全广播信道的同步通信网。 2 2 4 安全多方计算模型 安全多方计算一般分为两种模型：半诚实模型与恶意模型。 半诚实模型：如果所有参与者都是半诚实或诚实的，称此模型为半诚实模型。 半诚实模型中的攻击者是被动的。 恶意模型：在攻击者的腐败集中，有恶意参与者的模型称为恶意模型。即攻 击者能完全控制腐败方的模型。恶意模型中的攻击者是主动的。 半诚实模型的安全多方计算较恶意模型的安全多方计算要容易得多，大多数 情况下，如果协议中有恶意行为，协议得不到正确结果。要保证在恶意模型的计 算中得到正确结果，需要使用较多的密码学技术。 2 2 5 信息论安全和密码学安全 若s m c 协议能够抵抗具有无限计算能力的攻击者，则称为信息论安全 ( i n f o r m a t i o n - t h e o r e t i c a ll ys e c u r e ) 或者称为无条件安全( u n c o n d i t i o n a l s e c u r e ) 协议若要达到无条件安全，则要求通信信道是安全的。 若s m c 协议只能抵抗具有多项式时间计算能力的攻击者，则称其为密码学安 全( c r y p t o g r a p h i c t h e o r e ti c a ll ys e c u r e ) ，或者称为计算安全。 2 2 6 安全性定义 本节我们介绍一下文献 5 】的安全定义方式。这是一种比较难懂的形式化定 义。虽然我们实际分析协议安全性的时候很少直接运用这个形式化的定义，但是 它仍然是最严格和最完备的一种定义形式，因此我们需要强调一下。该定义的基 本思想是：首先定义一种理想模型，用理想模型模仿真实协议，如果真实协议能 够被理想模型模仿，那么我们说真实模型是安全的。我们只介绍两方计算的安全 北京邮电大学硕士论文 定义，多方计算的安全定义可以类推。 2 2 6 1 相关定义 定义2 - 1 ( 可忽略函数) ：一个函数：n h 0 ，1 】是可忽略的，如果对每一个 正的多项式p ( g ) 和所有充分大的以，有4 n ) l p ( n ) 。 定义2 2 ( 计算上不可区分性) ：令s 0 ，1 ) ，两个族x l ) 。s 和 y 匕 。s 是计算上不可区分的，如果对每一个多项式大小的电路族 见) 。， 存在 一个 可忽略函数 ：nh o ，l 】 ， 使 l e 见( 嵋瓦) = l l - p ， d ( w 匕) = l 卫 ( 1 w 1 ) 成立。记为x - - y 。 命题2 1 ：两个族x l ) 。s 和y 匕) 。5 是计算上不可区分的当且仅当对 每一个多项式大小的电路族 g ) 。和每一个多项式p ( g ) 以及所有充分大的 w e s ，有l e e ( k ) = q - 8 c ( 匕) = 1 】| 1 p ( 1 w 1 ) 成立。 2 2 6 2 半诚实两方计算的安全定义 符号约定：首先我们假设有两个参与方，他们分别为异和罡，要计算的函数 为f ： o ，1 ) o ，1 ) h o ，1 ) o ，1 ) ，函数f ( x ，y ) 的第一个元素记为彳( 工，y ) ，第二 个元素记为l ( x ，y ) 。计算函数，的两方协议为n 。运行协议n 的过程中曰( 昱) 所得的信息记为脚彬n ( x ，y ) = ( x ，m t ) ( 眦时( x ，y ) = ( y ，l i ，m e ) ) ，其 中，表示曰和只两方共同产生的随机数，朋，表示他们接收到的第j 个信息。运 行协议兀后，墨( e ) 的输出结果记为o u t p u t 。兀少) ( o u t p 四( x ，y ) ) 。显 然，o u t p u t i i n ( z ，y ) 含于脚形n j ，) ( o u t p 叼“j ，) 含于脚时k j ，) ) 。 定义2 3 ( 半诚实模型下的理想模型) ：在理想模型中，我们假设存在一个 无条件诚实者凡他能保密所有的参与者发送给他的所有信息，并且所有参与者 可以与r 进行保密通信。攻击者不能得到诚实参与者与无条件诚实者丁之间交换 的任何信息。其中唯一允许的攻击行为是：一个参与方利用他的输入以及他接收 到的输出实施任意一个多项式时间的计算，而其它参与方都只能输出他们接收到 的内容。我们也称之为理想协议模型。 这不同于现实模型，在现实模型中，协议的执行只有两个参与方而不存在诚 实的第三方。两方协议以及攻击者的行为都是半诚实的，也就是说，一个参与方 可能会利用他得到的信息实施任意一个多项式时间的计算。 一个协议在现实模型中针对一定的攻击行为被称为是安全的，如果所有存在 这样一个攻击者的现实执行情况在理想模型中都可以被模仿出来。 定义2 - 4 ( 半诚实模型两方保密计算) ： 9 北京邮电大学硕士论文 确定情况：对于每一个确定的函数，我们称h 保密计算，若存在多项式 时间算法墨和最，使下面两式成立： 墨( x ，z ( 工，少) ) ) ，胆 o ，1 ) 剐j 卅；l ，i 兰 阳e 噬n ( x ，y ) ) ，胙 o ，l ，榭：i 川 ( 1 ) s 2 ( y ，五( z ，y ) ) b e o 1 ) 忡m 耋 m 时( 石，y ) ) o i 油忡 ( 2 ) 一般情况：我们称兀保密计算，若存在多项式时间算法墨和是，使下面两 式成立： 墨( z ，z ( x ，y ) ) ，五( x ，y ) ) 。，肟 。，1 ) 一，j 卅：l j ，i 兰 阿e 形n ( 工，j ，) ，o u t p u t s ( x ，y ) ) 圳。 。，t ，杠l ：i j ，i 石( 工，y ) ，最( y ，五( 五y ) ) ) 。，j ，e 。1 1 捌：i 一兰 d 暇p 【伍n ( x ，y ) ，v e w 2 n ( x ，y ) ) ，班 。，i 芦。捌：i 川 其中，v i e w , n “y ) ，脚时( x ，) ，) ，o u t p u t , n y ) 和o u t p u t 2 n “y ) 都 是相关的随机变量。 在确定性情况的定义中，( 1 ) 式断言：第一个参与方能够得到的信息，仅仅 可以通过他自己的输入和输出信息模拟出来。( ( 2 ) 式也说明同样的问题) 。还注 意到，当输出是一个确定的表达式时，确定情况的定义与一般情况的定义是一致 的，因为，这时有o u t p 叼( 工，) ，) = z ( x ，y ) ，f = l ，2 。 定义2 - 5 ( 半诚实模型下的可接受电路) ： 用弓= ( c l ，c 2 ) 表示理想模型中攻击者的一对多项式电路计算。如果至少有一 个c ：满足c ：( ，d ) = 0 ，即至少有一方可以得到正确输出，那么称弓= ( c l ，c 2 ) 是 可接受的。设合法的输入对为0 ，y ) ，在理想模型下运行否，定义为 ( c ；( x ，z ( x ，y ) ) ，c ：( y ，l ( x ，y ) ) ) ，记为i d e a l , e ( z ，y ) 。 用弓= ( c l ，q ) 表示现实模型中攻击者的一对多项式电路计算，如果至少有一 个q 满足c ：( y ) = 0 ，这里y 就是眦形，0 包含在y 中，那么称c = ( c l ，g ) 是 可接受的。输入对为( x ，y ) ，在现实模型下运行c ， 定义为 ( c l ( 眦彬兀( x ，y ) ) ，c 2 ( 脚时( x ，y ) ) ) ，记为兄，c ( x ，少) 。 定义2 - 6 ( 半诚实模型的两方安全计算) ：设彳= ( 4 ，4 ) 为现实模型中的可 l o 北京邮电大学硕士论文 接受电路，否= ( 墨，最) 为理想模型中的可接受电路。如果存在一对多项式转换计 算电路，使下面的等式成立，那么称协议n 在半诚实模型下安全计算函数 c i d e a l i r 。j ( x ，j ，) ) f 川；i ) ，i - - - r e a l n 。j ( x ，j ，) ) j 啪i t l ，i 命题2 2 ( 两方计算的安全计算定义与保密计算定义的关系) ：设是计算 函数f n 两方协议，那么协议保密计算f n 且仅当协议在半诚实模型中安全 计算f o ( 证明见文献 5 】) 。 2 2 6 3 恶意模型两方计算的安全定义 具体的恶意模型可以分为三类：一是腐败参与方在协议开始时，拒绝参与协 议。二是腐败参与方更换自己的输入。三是腐败参与方中途中止协议的运行。 定义2 7 ( 恶意模型下的理想模型) ：我们允许恶意模型下的理想模型中的 一个恶意参与方可以拒绝参与协议，也可以更换自己的输入，而且这些都不会被 诚实的第三方r 阻止。另外，我们还假定第一个参与方有权选择是否在收到丁 发送给他的输出后马上中止协议，而这时r 还来不及将输出发送给第二个参与 方。这样一个选择的机会第二个参与方是没有的。理想模型的协议执行过程可以 描述如下： 输入：每一方都有一个输入，用z 表示。 将输入发送给诚实的第三方死诚实的参与者总是将输入z 发送给诚实的第 三方r 。恶意参与者有可能根据输入z 决定拒绝发送或将某个z 7 o ，l 产发送给几 诚实的第三方z 回应第一个参与方：如果诚实的第三方收到的是一对输入 ( 工，y ) ，他计算f ( x ，y ) ，并将第一个元素f , c x ，y ) 发回给第一个参与方。否则如果 他只收到了一个输入或遇到其它一些情况，诚实的第三方就向两个参与方都发送 一个终止符上。 诚实的第三方r 回应第二个参与方：如果第一个参与方是恶意的，他有可 能根据自己的输入以及诚实第三方丁的回应，决定是否停止丁的执行。如果他阻 止了丁的执行，丁就将终止符j - 发送给第二个参与方。否则t 将l ( x ，y ) 发送给 第二个参与方。 输出：一个诚实的参与方总是输出他从诚实的第三方t j i j 里得到的信息。一 个恶意的参与方可能会输出任意一个关于他的初始输入以及他从r 那里得到的 信息的多项式函数。 北京邮电大学硕士论文 定义2 8 ( 理想模型f 的司接受电路) ： 设弓= ( g ，c 2 ) 表示理想模型中攻击者的一对多项式电路计算。如果至少有一 个q 满足c ：( ，d ) = 0 ，那么称e = ( q ，c 2 ) 是可接受的。设合法输入对为( x ，j ，) ， 在理想模型下 运行弓，j , e 为i d e a l , e ( 工，j ，) ，定义为： 当是诚实的，即c 2 ( ，) = i r g ( z ，d ) = 0 时， 如果c l ( x ) - 上，那么： i d e a l ：e ( x ，y ) = ( q ( x ，上) ，上) 如果q ( z ) “但q ( x ，石( c l ( x ) ，y ) ) - 上，那么： i d e a l ：e ( x ，y ) = ( c l ( x ，z ( q ( x ) ，y ) ，上) ，上) 其他： i d e a l e ( x ，y ) = ( g ( 五彳( q ( x ) ，y ) ) ，五( q ( x ) ，j ，) ) 当只是诚实的，即q ( o = ，且q ( j ，d ) = 0 时， 如果c 2 ( j ，) _ 上，那么： i d e a l f e ( x ，y ) = ( 上，g ( y ，上) ) 其他： i d e a l f e ( x ，y ) = ( 彳( x ，c 2 ( y ) ) ，g o , ，l ( x ，c 2 ( y ) ) ) 其中i d e a l e ( x ，j ，) = ( c l ( x ，彳( q ( x ) ，夕) ，上) ，上) 表示鼻用一个替代输入g ( 功 发送给诚实参与方，并且在获得输出彳( q ( x ) ，y ) 后中止协议。在这种情况下没 有输出。i d e a l e ( x ，y ) = ( g ( 石，彳( c l ( x ) ，y ) ) ，以( q ( x ) ，y ) ) 式表示墨完成了协议， 并且允许得到输出，但皇在计算过程中更换了输入。 定义2 - 9 ( 现实模型和现实模型恶意两方计算) ： 现实模型下协议的执行：现实模型中，只有两个参与方而没有诚实的第三方。