（计算机软件与理论专业论文）保护隐私的分布式数据挖掘研究.pdf

摘要 摘要 数据挖掘，作为一种能够帮助人们从大量数据中提取或“挖掘”有用信息的 强有力的技术，已经被应用到众多的领域，如金融、电信、零售业、科技，甚至 国家安全领域等。然而，在得益于数据挖掘技术提供的服务的同时，用户的隐私 和数据安全正在受到威胁。特别是，随着经济全球化的发展，数据越来越多地分 布存储在多个地方，而且数据挖掘任务也越来越需要有着竞争关系的多个参与方 之间通过合作去完成。当然，在这合作的过程中，任何参与挖掘任务的一方都不 想泄露自己的隐私或敏感信息。因此，在分布式合作环境下保护隐私的数据挖掘 的实现就显得尤为重要。 1 9 8 2 年由姚期智提出的安全多方计算技术能够保证参与合作计算的各个参 与方在不泄露各自隐私的情况下，获得正确的计算结果，而这一点恰恰满足了分 布式数据挖掘中隐私保护的要求，所以本文将结合安全多方计算的技术来探讨保 护隐私的数据挖掘的实现，主要的研究成果包括： 1 在聚类分析应用方面，细致分析了一种基于密度分布函数的d e n c l u e 聚类算法中涉及隐私保护的各个部分的安全性计算，在这基础上给出了数据在水 平划分下和垂直划分下的保护隐私的d e n c l u e 协议的实现，其中针对垂直划分 下两方和多方的不同情形给予了不同的实现。 2 在离群点检测应用方面，讨论了两种不同类别的离群点检测算法的隐私 保护的实现。一种是基于偏差的离群点检测，介绍了能在线性时间内完成的顺序 异常检测技术，并给出了其在数据水平划分下隐私保护的实现；另一种是基于距 离的离群点检测，实现了其在数据垂直划分下两方和多方情况下的隐私保护。 3 在数据挖掘预处理应用方面，探讨了保护隐私的基于粗糙集的属性约简 问题的求解，给出了其在数据水平划分下和垂直划分下的解决方案。 本文对实现的各种保护隐私的数据挖掘协议的安全性、时间复杂度和通讯复 杂度都给予了详细的分析。 关键词：保护隐私；数据挖掘；安全多方计算；聚类分析；离群点检测；属性约 简 a b s t r a c t a b s t r a c t d a t am i n i n g ，a sas t r o n gt e c h n o l o g yw h i c hh e l p su st oe x t r a c to rm i n eu s e f u l i n f o r m a t i o no ri n t e r e s t i n gk n o w l e d g ef r o ml a r g ea m o u n t so fd a t a ，h a sb e e nu s e d a c r o s sm a n ya r e a ss u c ha sf i n a n c e ，t e l e c o m m u n i c a t i o n ，r e t a i l ，s c i e n c e ，e v e nn a t i o n a l s e c u r i t yf i e l da n ds oo n h o w e v e lw h i l eb e n e f i t i n gf r o mt h es e r v i c ep r o v i d e db yd a t a m i n i n gt e c h n o l o g y , o u rp r i v a c ya n dd a t as e c u r i t yi st h r e a t e n e d p a r t i c u l a r l y , w i t ht h e d e v e l o p m e n to fe c o n o m i cg l o b a l i z a t i o n ，m o r ea n dm o r ed a t aa r ed i s t r i b u t e da t m u l t i p l ed i f f e r e n ts i t e s ，h e n c e ，i nt h ed i s t r i b u t e ds c e n a r i o ，i t n e e d s m u l t i p l e c o m p e t i t i v ep a r t i c i p a n t sc o o p e r a t ew i t he a c ho t h e rt oc o n d u c td a t am i n i n g o fc o u r s e ， d u r i n gt h ec o o p e r a t i o n ，a n yp a r t i c i p a n tt a k e sp a r ti nd a t am i n i n gd o e sn o tw a n tt o d i s c l o s et h ep r i v a c yo rs e n s i t i v ei n f o r m a t i o no w n e db yh i m s e l f s o ，i ti sv e r y i m p o r t a n tt oi m p l e m e n tp r i v a c yp r e s e r v i n gd a t am i m n gi nt h ed i s t r i b u t e dc o o p e r a t i o n s c e n a r i 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 n ，p r o p o s e db ya c y a oi n19 8 2 ，e n s u r e se a c h p a r t i c i p a n tt a k i n gp a r ti nt h ec o o p e r a t i v ec o m p u t i n ga c q u i r e st h er i g h tr e s u l tw i t h o u t d i s c l o s i n gt h e i rp r i v a c y t h i sj u s tm e e t st h er e q u i r e m e n t so fp r i v a c yp r o t e c t i o nf o r d i s t r i b u t e dd a t am i n i n g t h u s ，t h i sa r t i c l ew i l ld i s c u s st h ei m p l e m e n t a t i o no fp r i v a c y p r e s e r v i n gd a t am i n i n gw 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 na n dt h em a i nr e s e a r c h a c h i e v e m e n t sc o n s i s to f 1 a b o u tt h ec l u s t e r i n ga n a l y s i s ，t h es e c u r ec o m p u t a t i o n so fa l lp a r t si n v o l v e di n p r i v a c yp r o t e c t i o n i nt h ed e n c l u ec l u s t e r i n ga l g o r i t h mb a s e do n d e n s i t y d i s t r i b u t i o nf u n c t i o na r ea n a l y z e da tg r e a tl e n g t h o nt h eb a s i so ft h ea n a l y s i s ， p r o t o c o l so fp r i v a c yp r e s e r v i n gd e n c l u eo v e rh o r i z o n t a l l yp a r t i t i o n e dd a t aa n d o v e rv e r t i c a l l yp a r t i t i o n e dd a t aa r ep r e s e n t e d w h a t sm o r e ，o nv e r t i c a l l yp a r t i t i o n e d d a t a ，t w od i f f e r e n ti m p l e m e n t a t i o n sa r eg i v e nf o rt w o p a r t ya n dm u l t i p a r t ys i t u a t i o n s 2 a b o u tt h eo u t l i e rd e t e c t i o n ，t h ei m p l e m e n t a t i o n so fp r i v a c yp r o t e c t i o nf o rt w o d i f f e r e n t t y p e so fo u t l i e rd e t e c t i o na l g o r i t h m s a r ed i s c u s s e d o n ei su n d e rt h e d e v i a t i o n - b a s e do u t l i e rd e t e c t i o n s e q u e n t i a le x c e p t i o nt e c h n i q u ec o m p l e t e di nl i n e a r t i m ei si n t r o d u c e d p r o t o c o lf o rp r i v a c yp r e s e r v i n go u t l i e rd e t e c t i o no v e rh o r i z o n t a l l y p a r t i t i o n e dd a t ai sp r e s e n t e df o rs e q u e n t i a le x c e p t i o nt e c h n i q u e t h eo t h e ri su n d e r t h e d i s t a n c e - b a s e do u t l i e rd e t e c t i o n p r o t o c o l so f p r i v a c yp r e s e r v i n go u t l i e rd e t e c t i o no v e r v e r t i c a l l yp a r t i t i o n e dd a t aa r ea l s og i v e nf o rt h ed i s t a n c e b a s e do u t l i e rd e t e c t i o n i i a b s t r a c t 3 a b o u tt h ep r e p r o c e s s i n gf o rd a t am i n i n g ，t h es o l u t i o n sf o rp r i v a c yp r e s e r v i n g a t t r i b u t er e d u c t i o nb a s e do nr o u g hs e ta r ed i s c u s s e da n dp r o t o c o l so v e rv e r t i c a l l y p a r t i t i o n e dd a t aa n do v e rh o r i z o n t a l l yp a r t i t i o n e dd a t af o ri ta r ep r e s e n t e d t h es e c u r i t y , t i m ec o m p l e x i t ya n dc o m m u n i c a t i o nc o m p l e x i t ya r ea n a l y z e df o r a ut h ep r o t o c o l si m p l e m e n t e da b o v ef o rp r i v a c yp r e s e r v i n gd a t am i n i n g k e yw o r d s ：p r i v a c yp r e s e r v i n g ；d a t am i n 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 ( s m c ) ； c l u s t e r i n ga n a l y s i s ；o u t l i e rd e t e c t i o n ；a t t r i b u t er e d u c t i o n i i i 目录 图表目录 图1 1 分布式数据挖掘与整体隐私2 图1 2 基于重构的保护隐私的数据挖掘3 图1 3 基于安全多方计算的保护隐私的数据挖掘3 图1 4 水平划分( 左) 和垂直划分( 右) 4 图4 1 离群点2 7 表4 1 基于偏差的离群点检测( 顺序异常检测) 一3 0 表5 1 决策表4 l 表5 2 决策表的区分矩阵4 2 v i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：骀 签字日期： 加，。j - 专 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 欧开口保密( 年) 作者签名： ) 鸷至垄 签字日期： 垆lo j 、弓) 。 新虢颦 签字日轫：2 生! ! ：垒z 第一章绪论 第一章绪论 在分布式环境下，数据挖掘任务的执行经常发生在互不完全信任的多方之 间，这就涉及到隐私保护的问题，即各方都希望不泄露各自的隐私数据而通过合 作获取数据挖掘的正确结果，保护隐私的分布式数据挖掘所要解决的就是这个方 面的问题。 1 1研究背景及意义 随着数据库技术的发展，各行各业利用数据库存储技术积累了越来越多的数 据。尤其是，伴随着互联网的兴盛，w e b 数据更是呈现爆炸式增长。面对快速增 长的海量数据，人们往往会不知所措，因为理解它们己经远远超出了人的能力。 但是，如果用户不能充分利用这些数据，从数据中得到有用的信息，那么数据就 会成为负担，因为存储这些数据需要付出高昂的费用。既然人们仅凭自己的经验 或直觉无法从大量数据中提取有价值的信息，那么对于帮助用户发现有价值信息 的工具的需求就显得愈加迫切。幸运的是，数据挖掘这种技术满足了要求，使得 人们能够从海量数据中解脱出来。 那么，什么是数据挖掘呢? 简单地说，数据挖掘是指从大量数据中提取或者 “挖掘”有用的知识( h a nj ，2 0 0 7 ) 。随着数据挖掘技术的发展，数据挖掘已经可 以帮助人们发现很多感兴趣的模式，如频繁模式、关联规则、分类、预测、聚类 分析、离群点分析和演变分析等。现在这些模式分析技术已被应用到各个行业和 领域，如商业领域、国家安全领域等。在商业领域，可以利用数据挖掘去发现消 费者的消费行为规则以便更好地调整产品的价格和布局以及向消费者进行产品 的交叉推荐等。还可以将消费者进行分类和聚类，以便识别顾客群，为不同类的 顾客提供更加个性化的服务。类似的商业应用还有很多，如金融业中顾客信用评 估分析、金融犯罪预测等，电信业中用户使用行为分析，电子商务中欺诈行为分 析，互联网行业中搜索习惯分析等。此外，近年来数据挖掘也被应用到国家安全 领域，如恐怖主义活动挖掘等。因此，数据挖掘成为人们从大量数据中获取知识 的强有力的工具。 然而，在数据挖掘给用户带来好处的同时，数据挖掘操作的数据中所包含的 隐私或敏感信息的保护成为人们越来越关心的问题。只有数据中包含的隐私得到 有效的保护，数据挖掘才能被合法的使用和推广。 那么数据挖掘过程中哪些私有信息称为隐私而需要得到保护呢? 总的来说， 第一章绪论 主要有两类：个体隐私( i n d i v i d u a lp d v a c y ) $ 1 整体隐私( c o r p o r a t ep r i v a c y ) ( c l i f t o n c ，2 0 0 2 b ) 。个体隐私主要是指个人的敏感信息，如信用卡号，身份标识信息等， 这些敏感信息可以在数据挖掘之前将其删除或修改而得到保护。整体隐私则是一 些信息的集合，不涉及个体隐私，但能从信息的集合中推断出一些隐私。由于随 着经济的发展，数据挖掘任务经常需要在多方之间通过合作来完成，传统的集中 式数据挖掘就无法胜任，因为不可能将所有存储在各个地方的数据放到一个中心 去进行挖掘，而且各个地方存在竞争关系时还涉及数据隐私保护的问题。这样， 分布式数据挖掘就应运而生。分布式数据挖掘就是各方在本地先利用集中式数据 挖掘方法产生本地局部结果，然后再将各个本地局部结果结合起来生成全局结 果，如图1 1 所示： 图1 - 1 分布式数据挖掘与整体隐私 虽然分布式数据挖掘不存在个体隐私保护问题，但本地局部结果会存在整体 隐私泄露的问题，因此需要新的技术解决分布式环境下数据挖掘过程中隐私泄露 的问题。 保护隐私的数据挖掘( p r i v a c yp r e s e r v i n gd a t am i n i n g ，简称p p d m ) 在各种 隐私保护的需求下应运而生，它一经提出迅速成为研究的热点。当前，研究保护 隐私的数据挖掘的方法主要有：基于随机重构技术和基于安全多方计算技术。基 于随机重构技术的保护隐私的数据挖掘是将各个站点的本地数据利用随机化技 术进行重构，重构后的数据和原始数据具有相同的分布，然后各个站点将重构后 的数据集中在一起，最后利用集中式算法在重构后的全局数据上进行数据挖掘 ( a g r a w a lr 2 0 0 0 ；e v f i m i e v s k ia ，2 0 0 2 ) ，如图1 2 所示。 2 第一章绪论 图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 ，简称s m c ) 和数据挖掘结合 在一起来达到保护隐私的目的。安全多方计算最初是由姚期智针对百万富翁问题 提出来的( y a oa c ，1 9 8 2 ) ，它能够保证参与计算的多方在各自的输入信息不泄露 前提下获得合作计算的结果，这正好符合分布式数据挖掘中隐私保护的要求。 1 2 研究现状 l i n d e l l 和p i n k a s 于2 0 0 0 年首次在保护隐私的数据挖掘中引入了安全多方计 算技术。基于安全多方计算技术的保护隐私的数据挖掘的主要思想是：将数据挖 掘算法看做一个计算函数，各个参与方的数据看做输入参数，这样保护隐私的数 据挖掘就可以看做将该函数归约为对应的安全多方计算协议，只要设计足够安全 的安全多方计算协议就能够确保各方数据的隐私或敏感信息不被泄露给其他任 何一方，从而达到保护隐私的目的，如图1 3 所示： 厂：d 伤d _ ，哟 厘 靠1 图1 3 基于安全多方计算的保护隐私的数据挖掘 第一章绪论 这里的d 等是各方的输入数据，是归约的安全多方计算协议，- 等为输出结 果，在具体协议中输出结果可以是偏一方的或多方共享的。对于各方的输入数据 分布，本文只考虑两种最常见的形式：水平划分和垂直划分。如图1 4 所示，水 平划分情况下，每一方拥有一部分记录，每条记录包含所有属性，所有的记录的 并集是全局记录集合；垂直划分情况下，每一方拥有每条记录的一部分属性集合， 这些部分属性集合的连接是全局属性集合。 r i da 1 a 2a 3 0 1 r i da 1 a 2 a 3 0 x lr l da 1 a 2 0 1 图1 4 水平划分( 左) 和垂直划分( 右) l r i d a 3a 4 1 0 1 近年来，安全多方计算技术已经被应用到分布式数据挖掘的各类任务分析 中，具体表现在： 1 关联规则挖掘：已有的成果很多，如采用可交换加密实现了水平划分下 的保护隐私的关联规则挖掘( k a n t a r c i o g l um ，2 0 0 4 ) ，采用安全点积协议实现 了垂直划分下和水平划分下的保护隐私的关联规则挖掘( v a i d y aj ，2 0 0 2 ；z h a n j ，2 0 0 6 ) ，采用安全求和协议实现保护隐私的布尔关联规则挖掘( y a n gz q ， 2 0 0 5 ) ，等等。此外，量化关联规则挖掘、统计量化规则挖掘等都有相关采用 安全多方计算技术来确保隐私保护的成果( j i n gw w ，2 0 0 6 ，2 0 0 7 ) ； 2 分类挖掘：基于安全多方计算的保护隐私分类挖掘已经被广泛的研究i 如保护隐私的决策树分类( x i a om j ，2 0 0 5 ) 、保护隐私的贝叶斯分类 ( k a n t a r c o g l um ，2 0 0 3 ；v a i d y aj ，2 0 0 4 a ；w r i g h tr ，2 0 0 4 ) 、保护隐私的k - n n 分类 ( z h a nj ，2 0 0 5 ；x i o n gl ，2 0 0 7 ) 、保护隐私的支持向量机分类( v uh ，2 0 0 6 a b ) ， 等等。但还有一些非主流的但对于一些特殊数据很有效的分类算法还没有被 研究，如基于粗糙集的分类、基于案例的分类等； 3 聚类分析：聚类分析算法非常多，主要分为：基于划分的方法、基于层 次的方法、基于密度的方法、基于网格的方法和基于模型的方法，当前对于 保护隐私的聚类分析研究主要是基于划分的方法( v a i d y aj ，2 0 0 4 ；j a g a n n a t h a n 1 3 i2 0 0 5 ) 。然而，基于划分方法以外的聚类算法在实际的应用中具有更强的 实用性和可扩展性，所以保护隐私的聚类分析成为当前保护隐私的数据挖掘 4 第一章绪论 领域中一个很重要的研究热点： 4 离群点检测：保护隐私的离群点检测相关成果非常少，目前仅有少量论 文涉及，主要集中在基于距离的保护隐私的离群点检钡o ( v a i d y aj ，2 0 0 4 ； h u a n gy q ，2 0 0 6 ) 和保护隐私的局部离群点检钡f j ( s h a n e c km ，2 0 0 6 ；x u ea ， 2 0 0 8 ) 。由于离群点检测广泛地被应用在入侵检测、反恐活动预测中，而且这 些应用对于隐私保护的要求非常高，因此保护隐私的离群点检测还有很多工 作值得研究； 5 特定的复杂数据类型挖掘：目前对于特定的复杂数据类型挖掘的隐私保 护研究的很少，如流数据挖掘，图数据挖掘，时间序列挖掘等这些具有广泛 应用的类型需要予以更多的关注。 1 3 本文工作 从上节介绍可以看出，只有实现保护隐私的数据挖掘，才能真正将数据挖掘 的应用推广开来，让人们不再担忧隐私泄露的问题。然而，保护隐私的数据挖掘 是个新兴领域，目前还有很多方向有待去研究，如聚类分析、离群点检测等。因 此本文将基于安全多方计算技术对保护隐私的数据挖掘进行以下几个方面的探 讨和研究： 1 保护隐私的聚类分析：聚类分析有着很丰富的内容，而且应用甚广，但 是在隐私保护领域产其成果相对于被广泛研究的关联规则和分类还不是很多，因 此本文对其给予了重点关注，研究了一种基于密度分布函数的d e n c l u e 算法， 详细分析了算法中涉及到的密度函数、密度函数梯度向量和密度函数梯度向量的 安全性计算，分别给出了d e n c l u e 在数据水平划分下和垂直划分下的隐私保护 实现，特别的是，对于数据垂直划分下，针对参与者为两方和多方两种情形提出 了不同的解决方案。对于所有的实现都进行了安全性和性能方面的详细分析。 2 保护隐私的离群点检测：基于偏差的离群点检测在隐私保护的领域至今 没有被人研究，然而它具有很好的统计特性，所以本文在细致分析了其中一种很 好体现这种性质的顺序异常检测技术，调用安全多方计算的基础协议，实现了其 在水平划分下的隐私保护协议。此外，本文还实现了一种基于距离的保护隐私的 离群点检测，主要考虑了其在垂直划分下的两方和多方的两种情形。同时，对所 有的协在安全性和性能上都给予了详细分析。 3 保护隐私的属性约简：当前数据挖掘的隐私保护研究主要集中在数据挖 掘算法本身，很少涉及到数据挖掘预处理，但是它是完整的数据挖掘系统所不可 缺少的一部分，而且很多预处理对于数据挖掘能够有效完成起着举足轻重的作 第一章绪论 用，如属性约简。因此，本文将就基于粗糙集的属性约简这种重要的预处理在分 布式环境下的隐私保护展开研究，利用安全多方计算技术实现了其在数据垂直划 分下和水平划分下隐私保护的实现，并对其安全性和性能都进行了详细地分析。 1 4 本文结构 本文第一章介绍保护隐私的数据挖掘的研究背景和研究意义，着重介绍了基 于安全多方计算技术的保护隐私的数据挖掘的研究现状，同时介绍了本文的工作 和本文的内容安排结构。 第二章介绍安全多方计算技术的基础概念、基本工具和基础协议，为保护隐 私的数据挖掘的研究提供理论基础。 第三章探讨了聚类分析中的隐私保护的实现。介绍了聚类分析的基础知识和 保护隐私的聚类分析的现有研究成果，实现了在水平划分下保护隐私的 d e n c l u e 协议、在垂直划分下的两方的保护隐私的d e n c l u e 协议和在垂直划 分下的多方的保护隐私的d e n c l u e 协议，并对这些协议的安全性、时间复杂度 和通讯复杂度进行了详细地分析。 第四章探讨了离群点检测中的隐私保护的实现。介绍了离群点检测的基本概 念和保护隐私的离群点检测的研究现状。给出了基于偏差的和基于距离的两种类 型的离群点检测的隐私保护的实现，其中基于偏差的实现了在数据水平划分下的 隐私保护，基于距离的实现了在垂直划分下两方和多方的隐私保护，并对这些协 议的安全性、时间复杂度和通讯复杂度进行了详细地分析。 第五章解决了基于粗糙集的属性约简的隐私保护问题。介绍了粗糙集和基于 粗糙集的属性约简的基础知识，给出了垂直划分下和水平划分下保护隐私的属性 约简的实现，并对这些协议的安全性、时间复杂度和通讯复杂度进行了详细地分 析。 第六章总结了全文的工作并对保护隐私的数据挖掘的未来进一步的研究方 向进行了展望。 1 5 本章小结 本章介绍了保护隐私的数据挖掘的研究背景和研究意义，着重介绍了基于安 全多方计算技术的保护隐私的数据挖掘的研究现状，同时介绍了本文的工作和本 文的内容安排结构。 第二章安全多方计算技术概述 第二章安全多方计算技术概述 本章首先介绍安全多方计算的基础概念，如安全多方计算的定义、主要模型、 组合定理等，然后对一些安全多方计算基本工具，如同态加密、可交换加密、茫 然传送和数据扰乱等给予阐明，最后对安全求和、秘密比较、安全距离、点积协 议、安全求并集、安全求交集和安全乘法等基础协议进行简单的介绍和总结， 为后文的研究工作提供必要的预备知识。 2 1 安全多方计算基本概念 安全多方计算是由姚期智在1 9 8 2 年解决著名的百万富翁问题时提出来的。 安全多方计算能够保证参与比较的两方在不泄露自己的数据的前提下而获知谁 更富有，此后g o l d r e i c h 等对安全多方计算做了大量的研究工作，大大推动了安 全多方计算的发展和应用。那么，什么是安全多方计算呢? 下面就对它的定义、 安全计算模型、安全性定理等给予简单的介绍。 2 1 1安全多方计算定义及模型 定义2 1 安全多方计算( s e c u r em u l i t p a r t yc o m p u t a t i o n ，简称s m c ) ( g l o d r e i c ho ，1 9 9 8 ) ：安全多方计算是指在分布式计算环境下，参与合作计算某 个函数的各方，在不泄露各自私有数据的前提下获得各自期望的计算结果。 安全多方计算主要有三种模型：可信第三方模型、半诚实模型和恶意模型。 可信第三方模型中所有计算由一个可信的第三方代劳，各个参与方只需将数据发 给这个第三方即可，最终结果由第三方广播给各方。但是，可信任的第三方是理 想的，在现实中很难找到。在半诚实模型下各方严格执行协议，但允许各方对其 他方的数据充满好奇，可以利用中间结果来推测别人的隐私信息。在恶意模型下， 恶意参与方不需要严格执行协议，这样不能保证数据输入是准确的或协议能正常 执行完毕而不被中途中止。 本文主要考虑基于半诚实模型来实现各种保护隐私的数据挖掘算法，因为任 意一个半诚实模型下的安全计算协议都可以“编译”为等价的恶意模型下的安全 计算协议( g l o d r e i c ho ，l9 9 8 ) 。 第二章安全多方计算技术概述 2 1 2 安全性定理 首先介绍半诚实模型下的两方安全性定义，然后介绍安全多方多方计算的一 个很重要的定理即组合定理。 定义2 2 半诚实模型下的安全性定义( g l o d r e i c ho ，1 9 9 8 ) ：该定义使用模拟 器方法定义计算的安全性，设f ( x ，y ) = ( f l ( x ，y ) ，f 2 ( x ，y ) ) 是一个概率的多项式时 间函数，厂，( x ，y ) 和厂z ( x ，y ) 分别表示f ( x ，y ) 的第一个元素和第二个元素，n 表 示计算函数的两方协议。v i e w l 兀( x ，y ) 表示第一方执行协议时作用在( x ，y ) 上的 视图，v i e w 2 n ( 墨y ) 表示第二方执行协议时作用在( 墨y ) 上的视图，o u t p u t l 兀( x ，y ) 表 示第一方执行协议时作用在( x ，y ) 上的输出结果，o u t p u t s 兀( x ，y ) 表示第二方执行 协议时作用在( x ，y ) 上的输出结果，如果协议兀能够安全地计算厂当且仅当存在 多项式时间的算法s t 和s z ，使得 s l ( x ，f l ( x ，y ) ，f ( x ，y ) ) ) ze o 1 ) 兰c v i e w l 儿( x ，j ，) ，o u t p u t ( x ，y ) ) xe o ，l ( 2 1 ) s 2 ( y ，f 2 ( x ，y ) ，f ( x ，y ) ) ) y el o 。1 ) 三c v i e w s 儿( x ，y ) ，o u t p u t ( x ，y ) ) ye o ，l ( 2 2 ) o u t p u t 儿( x ，y ) = o u t p u t l 儿( x ，y ) ，o u t p u t s 儿( x ，y ) ) ( 2 3 ) 这里的兰c 表示计算不可区分，所谓计算不可区分指的是对于任何两个序列，没 有任何有效的程序即多项式时间的程序能够区分它们，那么这两个序列就是计算 不可区分的。运用该安全性定义可以对半诚实模型下的协议模拟视图，即模拟各 方接收的数据分布，如果存在一个模拟器，它的输出和参与方的视图是计算不可 区分的，那么多方协议就被视为安全的。 另一个对安全性说明很重要的定理就是组合定理。组合定理能够说明一个复 杂问题被分解为多个子问题处理时的安全性，只要能够证明各个子问题的安全 性，那么就可以利用组合定理说明全局问题的安全性。半诚实模型下组合定理的 定义是： 定理2 1 组合定理：如果函数g 可安全地归约为函数厂，而且存在一个能 够安全计算函数厂的协议，那么就存在能够安全计算函数g 的协议。这里函数譬 可以安全地归约为函数厂指的是文献( g l o d r e i c ho ，1 9 9 8 ) 中定义的预言机协助协 议在所访问的预言机实现的函数为厂的情况下能安全地计算函数g ，则该预言机 协助协议能安全地将函数g 归约为函数f ( g l o d r e i c ho ，1 9 9 8 ) 。 2 2 安全多方计算基本工具 本节介绍设计安全多方计算协议时经常用到的基本工具，正是有了这些工 具，各种安全的协议才能够比较容易地实现。 第二章安全多方计算技术概述 在介绍同态加密方案之前，先简短介绍一下公钥密码体制，因为它是很多工 具实现的基础。公钥密码体制，它的加密密钥和解密密钥是独立的，其中加密密 钥称为公钥，解密密钥称为私钥。利用公私钥独立的特性，可以用来设计一系列 的安全协议，在这里介绍的同态加密就是典型的例子。 同态加密：设k 口为公钥，k ，为私钥，ml 和朋2 为明文，如果 风( 聊) 凰( 朋：) = 风( 聊+ m 2 ) 成立，那么这个公钥加密系统就是同态的，这里的 脚( 坍) 表示明文m 用公钥岛加密后的密文。p a i l l i e r 加密系统就满足同态性质， 它是最广泛使用的安全同态加密系统之一( p a i l l i e rp ，1 9 9 9 ) 。 可交换加密：一个加密算法是可交换的，如果它对任意，z 个公钥 k t ，k 2 ，i g k ，明文域m 中的任意明文聊，任意的置换f ，满足下面两个 等式： e x n ( 如 ) ) = e 妁- ( e x j ( m ) ) ( 2 4 ) 对于任意的v m l ，m 2 m ，m l m s ，任意给定的七，占 有 p r ( 眈一( e x r ( m 0 ) = 鼬( e x j ( m 2 ) ) ) 占 ( 2 5 ) 可交换加密使用所有的参与者提供的密钥来进行加密，这样能更好地抵御恶意参 与者的攻击( k a n t a r c o g l um ，2 0 0 4 ) 。 茫然传送：又称不经意传输，是构造安全多方计算协议的一个强有力的基本 工具，最初是由r a b i n 提出来0 0 ( 1 9 8 1 ) ，百万富翁问题的解决方法中就用到了茫 然传送。茫然传送的主要形式有两种：卜o u t o f - 2 茫然传送和卜o u t o f - n ，其中 卜o u t _ o f - 甩是比较实用的。通常一个o t 协议有两个参与者，称为发送方和接收 方。发送方拥有玎个秘密m l ，优z ，朋。，接收方拥有一个整数f 1 ，门】，代表他 的选择，一个o t 协议要满足下面的要求：( 1 ) 如果发送方和接收方严格地执行 协议，那么最后接收方得到秘密m i ，而对其他秘密一无所知；( 2 ) 协议执行完 后，发送方对于接收方的选择f 也一无所知，他不知道接收方到底选择了哪一个 秘密。茫然传送已经有很多实现，如基于离散对数、大数分解等( n a o rm ，1 9 9 1 ， 2 0 0 1 ) 。 数据扰乱：以上介绍了几种基于公钥加密的工具，由于加密运算的复杂度很 高，所以就出现了数据扰乱技术。数据扰乱通过对原始数据进行简单的算术变换 达到保护数据隐私的目的，它的最大特点就是复杂度低，因为它只利用了算术变 换，而没有复杂的加密运算。典型的例子加随机数和乘随机数等，其中加随机数 就是在原始数据上加上一个服从某种随机分布的随机数，同理，乘随机数就是在 原始数据上乘上一个随机数，有关它们的隐私泄露问题在许多文献中都有讨论， 这里就不再论述。作为数据扰乱技术的推广，后来又出现了线性隐藏和z + v 隐 藏等扰乱技术。线性隐藏是数据向量的隐藏，将向量乘上一个可逆矩阵，利用可 9 第二章安全多方计算技术概述 逆矩阵的性质，还原数据的时候只需要乘上可逆矩阵的逆即可( d uw l ，2 0 0 2 b ) 。 2 3 安全多方计算的基础协议 本节将描述安全多方计算中的一些基础协议，这些基础协议中已经有很多被 应用在保护隐私的分布式数据挖掘中。 安全求和协议：设有n 方尸，尸：，r ，每一方尸j 拥有自己的数据船，他们 想通过合作计算获得罗? 。船，而任一方又不愿意向其他方泄露自己的隐私数据 勋。当玎3 时，为了计算y 7 x ，存在一个效率很高的协议，那就是：尸产生 一个随机数，然后将x l + ，发送给尸2 ，尸2 将x l + x 2 + r 发送给尸3 ，依次类推， 最后 将y ? 。船+ 厂发送给p l ，尸。知道，的具体值，只要计算( y ：知+ ，) 一，就可 以获得y ? ，勋的值，然后将y ”骱的值广播给其他各方( c l i f t o nc ，2 0 0 2 a ) 。这个 协议不能抵御相邻的串谋获取隐私，为此罗永龙博士基于秘密共享技术对此协议 进行了改进，改进后的协议可以防止串谋获取隐私，具体的协议这里不再详述 ( 2 0 0 5 ) 。 秘密比较协议：该协议就是为了解决如何安全地比较两个数的大小或相等， 但是不能泄露这两个数。百万富翁问题实质上就是秘密比较问题。秘密比较问题 可以描述为：a l i c e 有一个隐私数据x ，b o b 有一个隐私数据y ，他们想知道x 与 y 的大小关系而不泄露x 和y 的值。对于x 与y 的大小比较，姚期智在解决百万 富翁问题时已经给出了秘密比较方案( 1 9 8 2 ) 。而对于x 与y 是否相等，一种简单 的方案是利用可交换加密来实现。假设a l i c e 和b o b 的密钥分别为乜和b ，根据 可交换加密的性质，只需比较眈( 如( y ) ) 和风( 眈( x ) ) 是否相等，如果相等则 x = y ，否则x y 。此外，对于大字符串的比较，一种解决方案是使用单向散列 函数。设两个要比较的信息为m l ，m 2 ，单向散列函数为厂，如果厂( 聊，) = f ( m o ， 那么所l = m 2 ，否则m l m 2 ( 李顺东，2 0 0 9 ) 。 安全点积协议：该协议可以描述为a l i c e 有一个向量x = x l ，x 2 ，勋) ，b o b 有一个向量y = y l ，y 2 ，弘) ，a l i c e 和b o b 分别得到“和v 满足u + ，= x y 。安 全点积协议已经有很多种实现，有基于同态加密( d uw l ，2 0 0 1 b ) 、基于茫然传送 ( d uw l ，2 0 0 1 b ) 和利用可逆矩阵( d uw l ，2 0 0 2 b ) 等。 安全距离协议：该协议可以描述为a l i c e 有一个点x = ( x t ，x 2 ，x n ) ，b o b 有 一个点】，= ( y l ，y 2 i i o - l l 弦) ，a l i c e 和b o b 合作计算x 和l ，之间的距离d 而不泄露各 自的数据。在本文中，为简单起见，这里和后面的研究中只考虑欧几里德距离， 且用距离的平方来代替距离。对于欧几里德距离，d 2 = 罗：( 鼢一弘) 2 = ：。x i 2 + ：。弘2 - 2 z ：。砂，：。知2 和：。少2 可以由a l i c e 和b o b 各自计算， l o 第二章安全多方计算技术概述 记函= ：。崩2 和d s = ：。弦2 ，：。砂的计算可以调用安全点积协议，从而获 得“+ v = ：l 砂，因此d 2 = ( 砒+ “) + ( 出+ v ) ，其中a l i c e 拥有( 以+ 甜) ，b o b 拥 有( r i b + v ) 。 安全求并集协议：该协议用来安全地计算来自多方的集合的并集，由于并集 运算只需要比较集合中两个元素是否相等，因此可以利用可交换加密来实现。假 设a l i c e 有集合 x l ，x 2 ，x m ，b o b 有集合 y l ，y 2 ，弘) ，a l i c e 用乜加密自己的数 据获得 眈( 朋) ，眈( x ：) ，眈( 渤) ) ，b o b 用b 加密自己的数据获得 e 幻( y o ，e b ( y o ，眈( 弦) ) ，a l i c e 和b o b 各自向对方发送自己加密后的集合，然 后a l i c e 和b o b 再用各自的密钥对接收到的集合进行加密，a l i c e 和b o b 分别持 有集合厶和厶，其中： 厶= 眈( 眈( y ) ) ，e a ( e k a ( y 2 ) ) ，眈( 眈( 弘) ) ) ( 2 6 ) i s = e 妇( e a ( x o ) ，凰( 眈( x 2 ) ) ，如( 如( 渤) ) ) ( 2 7 ) 根据可交换加密的性质，如果船= y j ，那么眈( 眈( 勋) ) = e h ( e 妇( 弦) ) ，所以 x l ，x 2 ，x m ) u 抄- ，y 2 ，弘) 和厶u 厶解密后的结果相等，这样就获得了并集 ( c l i f t o nc ，2 0 0 2 a ) 。 安全求交集协议：该协议可以描述为a l i c e 拥有集合x = x l ，x 2 ，x n ) ，b o b 拥有集合y = y l ，y 2 9o ，p ) ，a l i c e 和b o b 合作计算获得x n 】，协议执行结束后， a