（计算机软件与理论专业论文）隐私保护序贯模式挖掘研究.pdf

上海大学硕士学位论文 摘要 分布式或网格环境中隐私保护数据挖掘是近年来的一个热点研究闯题。分布 式环境中，与传统的集中式数据挖掘不同，隐私保护的数据挖掘需要解决如下矛 盾：一方面，各数据持有方都希望保持自己的私有数据不为其他任何一方所知； 另一方面，它们又希望通过合作获得全局数据模型。因此，需要研究新的算法使 得各方在不共享原始数据的情况下进行正确的数据挖掘，称为隐私保护数据挖掘 ( p r i v a c y p r e s e r v i n gd a t am i n i n g ，简称p p d m 。 本文首先结合数据分布方式、数据修改方式、数据挖掘算法、数据或规则保 护和隐私保护技术五个角度，分析了当前流行的隐私保护数据挖掘方法。 然后文章针对数据挖掘中应用较为广泛的序贯模式挖掘问题，提出隐私保护 序贯模式挖掘算法，不同的数据分布方式，需要不同的解决方法。主要工作包括： ( 1 ) 针对数据水平分布的情况，提出了水平分布数据的隐私保护序贯模式挖掘算 法。其中包括全局候选频繁项收集协议以及候选项支持度收集协议。全局候选频 繁项收集协议主要采用了可交换加密方式来最小化信息共享，保护单个站点的局 部频繁候选项集信息，同时在数据挖掘和处理上增加的系统开销非常小；候选项 支持度收集协议主要采用了安全和技术，来保护单个站点上候选项集的支持度信 息。从理论分析上了协议的隐私保护性，通过实验证明协议是高效可行的。 ( 2 ) 针对数据垂直分布的情况，提出了垂直分布数据的隐私保护序贯模式挖掘 算法。其中包括安全两方交易时间比较协议以及安全两方点积协议。安全两方交 易时间比较协议主要采用了同态加密技术，在不泄露数据具体值的情况下。完成 项集发生时间先后的比较；安全两方点积协议同样采用了同态加密技术，在不泄 露各自具体向量值的情况下，完成点积计算。从理论上分析了所提出协议的正确 性和隐私保护性，直接运行点积协议花费的时间比较多，接着提出了几种优化技 术来改进协议的性能，通过实验分析了改进后的点积协议是高效可行的。 关键词：可交换加密，同态加密，序贯模式挖掘，安全多方计算，隐 私保护 上海大学硕士学位论文 a b s t r a c t p r i v a c y p r e s e r v i n gd a t am i n i n gi nd i s t r i b u t e do rg d de n v i r o n m e n ti sa ni m p o r t a n t a n dh o tr e s e a r c hf i e l di nr e c e n ty e a r s d a t am i n i n gi nd i s t r i b u t e de n v i r o n m e n ti s d i f f e r e n tf r o mc e n t r a l i z e de n v i r o n m e n t ，a n do b v i o u s l yas o l u t i o ni sn e e d e dt ob ef o u n d b yp r i v a c y - p r e s e r v i n gd a t am i n i n gt os u c hac o n t r a d i c t i o nt h a tw i t h o u td i s c l o s i n gt h e i r p r i v a t ed a t at oe a c ho t h e r 。e a c hu s e l - h a v i n gap r i v a t ed a t as e t , a n dt h e yj u s t 、析s ht o c o l l a b o r a t i v e l yd i s c o v e rp a t t e r n so nt h eu n i o n c o m b i n eo ft h e i rp r i v a t ed a t as e t s t h e r e f o r e ，w en e e dt op u tf o r w a r dan o v e la p p r o a c ht od i s c o v e rp r i v a c y - p r e s e r v i n g p a t t e r n sw i t h o u ts h a r ed a t a , w h i c h ，c a nb ec a l l e dp r i v a c y - p r e s e r v i n gd a t am i n i n g ( p p d m ) f i r s to fa l l ，t h ep a p e ri n t r o d u c e sa n da n a l y z e st e nt y p i c a lp 哂v a c yp r e s e r v i n g a l g o r i t h m sf r o md a t ad i s t r i b u t i o n ，d a t am o d i f i c a t i o n ，d a t am i n i n ga l g o r i t h m ，h i d i n g o b j e c t sa n dp r i v a c yp r e s e r v i n gt e c h n o l o g yd i m e n s i o n s s e q u e n c ep a t t e r nm i n i n gh a sn u m e r o u sa p p l i c a t i o n s i nt h i sd i s s e r t a t i o nan o v e l p r i v a c y - p r e s e r v i n ga l g o r i t h mi sp r o p o s e dt om i n es e q u e n c ep a t t e r no nh o r i z o n t a l l y d i s t r i b u t e dd a t aa n dv e r t i t a l l yp a r t i t i o n e dd a t a t om a k eu s eo fe f f i c i e n tm e t h o d sf o r p r i v a c y - p r e s e r v i n gc o m p u t a t i o na n do u rm a i nr e s e a r c hd i r e c t i o n sa r e a sf o l l o w ： ( 1 ) t h i st h e s i sp r e s e n t sm e t h o d st om i l l es e q u e n t i a lp a t t e r n so nh o r i z o n t a l l y p a r t i t i o n e dd a t aw i t h o u tv i o l a t i n gp r i v a c y t h em e t h o d si n c o r p o r a t ec o m m u n i c a t i o n e n c r y p t i o nt e c h n i q u et om i n i m i z e 血ei n f o r m a t i o ns h a r e d , w h i l ea d d i n ga sl i r l ea s p o s s i b l eo v e r h e a dt ot h em i n i n ga n dp r o c e s s i n gt a s k i n c l u d i n gt w op r o t o c o l s ，o l l ei s f i n d i n gs e c u f eu n i o no f l a r g ei t e m s e t so f s i z ek ：t h eo t h e ri sf i n d i n gt h eg l o h a ls u p p o a c o u n t ss e c u r e l y w ep r o v e dt h a tp r i v a c y - p r e s e r v i n gd i s t r i b u t e ds e q u e n c ep a r e mm i n i n g , w h i c hr e a l l ym a k e ss e n s e ，c a nb ec a r r i e do u te f f i c i e m l ya n ds e c u r e l yu n d e rr e a s o n a b l e a s s u m p t i o n s ( 2 ) t h i st h e s i sp r e s e n t sm e t h o d s t om i n es e q u e n t i a lp a t t e r n so nv e r t i c a l l yp a r t i t i o n e d d a t aw i t h o u tv i o l a t i n gp r i v a c y t h em e t h o d si n c o r p o r a t eh o m o m o r p h i ce n c r y p t i o na n d s c a l a rp r o d u c tt e c h n i q u e st om i n i m i z et h ei n f o r m a t i o ns h a r e d a n df i n do u tg l o b a l l y f r e q u e n ti t a m s e t st h e ng l o b a ls e q u e n t i a lp a t t e r n sa l em i n e df i n a l l y w h i l ea d d i n ga s l i t t l ea sp o s s i b l eo v e r h e a dt ot h em i n i n ga n dp r o c e s s i n gt a s k t h e r e sn od e n y i n gt h a t o u rp r o d u c t i o np r o v i d e sa l le x p e r i m e n t a le v a l u a t i o no fae r y p t o g r a p h i cs o l u t i o nt ot h e p r o b l e m ，w h i c hi su s e dt oc o m p u t et h es c a l a rp r o d u c to f t w ov e c t o r s i i 上海大学硕士学位论文 k e y w o r d s ：c o m m u n i c a t i o ne n c r y p t i o n , h o m o m o r p h i ce n c r y p t i o n , s e q u e n c ep a t t e r n m 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 ，p r i v y - p r e s e r v i n g i i i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：歪鉴垫e t 期：幽：至竺 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) ， 签名：逊丝 导师签名：琶苤敞期：兰掣 i i i 上海大学硕士学位论文 1 1 课题研究背景 第一章绪论 信息时代给我们带来了数据在数量和复杂性上的爆炸性增长，也催生了富有 挑战性的研究领域一数据挖掘。在很多情况下，数据由不同的组织持有、分布于 不同的地理位置，而且持有者可能出于数据安全性和敏感性等原因不愿意直接共 享他们的数据。怎样跨越数据挖掘和数据机密性之间的这道鸿沟，是当前数据挖 掘的一大研究方向，称为隐私保护的数据挖掘( p r i v a c y p r e s e r v i n gd a t am i n i n g ， 简称p p d m ) 。 根据考虑对象的不同，隐私保护的数据挖掘目前的解决方法主要分为( 1 ) 初 始数据隐私保护，即对初始数据进行扭曲、扰乱、随机化和匿名化。这是因为初 始数据中可能含有不能公开的个人隐私信息，如姓名、身份证号码、年龄、工资 等。( 2 ) 分布式数据隐私保护，即在双方或多方合作进行数据挖掘时，由于某种 原因，参与者往往不愿意将数据与他人共享而只愿共享数据挖掘的结果。这就要 求人们提出隐私保护的数据挖掘算法，对于参与者而言，只能获得最终的挖掘结 果，除此以外，不能获得他人的其他任何信息。 多年来安全多方计算一直是理论密码学的研究热点，并取得了一定的成果。 但将一般的安全多方计算协议直接应用于特殊情形，效果并不理想，因此针对实 际的应用情形，给出有效、安全的特殊安全多方计算协议，并从理论上给出协议 的安全性证明是一项有意义的工作。 1 2 课题研究内容 我们通过收集和整理大量相关资料，结合隐私保护技术和序贯模式挖掘技 术，选取了下面几个问题开展相关工作。 1 2 1 水平分布数据的隐私保护序贯模式发现 该问题描述如下：设有p a r t l 、p a r t 2 ，p a r t n 各自拥有一个包含敏感信息 的数据集d b i 、d b 2 、d b 。，而且d b i 、d b 2 、d b 。是水平数据分布的， 即为同构数据库，所有的站点有相同的模式结构，但是每个站点包含关于不同实 体的记录。各方拟在d b l u d b 2 u u d l 3 上实施某种序贯模式挖掘算法，并且 上海大学硕士学位论文 希望信息泄露受到限制，一个站点不能知道其余站点的内容，比如其余站点支持 什么样的序贯模式以及支持度，除非信息是由站点本身以及全局最终结栗泄露 ( 比如一条规则的支持度是1 0 0 ，则可知每个站点上这条规则的支持度都为 1 0 0 , 4 ) ，在这个过程中不考虑任何第三方( 可信或不可信) 的存在。 1 ) 半诚实模型下，基于计算不可区分概念以及交换加密的语义安全性假设，给 出一个用于计算全局候选项集的特殊安全多方计算协议。 2 ) 给出了利用安全和技术的安全多方计算协议来判断候选项集的支持度。并且 通过实验分析了协议的性能、开销。 1 2 2 垂直分布数据的隐私保护序贯模式发现 该问题描述如下：设有p a r t l 、p a r t 2 、p a r t n 各自拥有一个包含敏感信息 的数据集d b t 、d b 2 、d b 。，而且d b l 、d b 2 、d b 。是垂直数据分布的， 即除了拥有相同的关键字外，其它属性均各不相同。各方拟在d b l u d b 2 u u d b 。上实施某种序贯模式挖掘算法，要求是除了算法的计算结果外，任何一方均 不能获得有关其它方的任何信息。 1 ) 采用基于同态加密技术的安全两方计算协议来判断交易时间比较协议。 2 ) 针对半诚实的安全两方模型，提出基于同态加密技术的点积计算协议，来计 算候选项集的支持度。从理论上分析了协议的计算复杂度和通讯复杂度。并且对 协议进行了优化，通过实验证明协议具有较高的效率。 以上提出的协议在政府文件共享、医疗机构的合作研究、数据挖掘等领域中 有着广阔的应用前景。 1 3 课题研究的意义 序贯模式挖掘是数据挖掘技术的一个重要组成部分。序贯( s e q u e n c e ) 是一列 排好序的项集。序贯模式【4 s l 挖掘是基于时间或者其它序列的经常发生韵模式 1 1 1 4 8 1 。挖掘得到的序贯模式，可，以帮助企业决策者制定商务决策。 近几年，由于社会的发展以及人们对于安全、隐私的重视，客户对于序贯模 式挖掘技术的需求呈现出新的变化，主要表现为以下几点： 企业规模的扩大。使用序贯模式挖掘的企业规模的扩大，它们大都有很多分 支机构，而各个分支机构又自成一体。 安全、隐私变得越来越重要。在市场竞争中，数据的安全和隐私保护对于各 个企业组织越来越重要。 2 上海大学硕士学位论文 数据量越来越大，而企业对于序贯模式挖掘的效率要求越来越高。 鉴于以上几点，传统的基于集中式数据库的序贯模式挖掘技术已经不能满足 需要，逐渐地暴露出它自身的缺陷，主要表现为以下几点： ( 1 ) 对于有很多分支节点的应用，如果把数据都集中在一个中心服务器上进 行挖掘，网络的传输负载会很大。 ( 2 ) 相对于分别在各个分支节点的挖掘来说，集中挖掘的效率显然很低。 ( 3 ) 数据都集中在一地的集中挖掘对于数据的隐私保护很不利。 这样设计出一套分布式隐私保护序贯模式挖掘算法就显得尤为重要。 对于隐私保护的数据挖掘研究成果，国外已经有比较多的文献报道1 2 】【1 9 】，国 内却比较鲜见，但基于双方或多方的安全计算( 算法、协议) 研究偶有报道【3 】【4 】。 本课题的意义具体体现在：在理论上，第一次把安全多方计算理论应用于水 平分布数据、垂直分布数据的隐私保护序贯模式挖掘。在保护各分站点数据隐私 的前提下，为准确地找到候选频繁项集和确定项集的支持度的提供了理论基础； 在技术上，提出了利用安全多方计算理论、可交换加密和同态加密技术的隐私保 护序贯模式新技术和新算法，通过理论和实验分析，证明了多方协议的安全性， 并分析了协议的计算复杂度和通讯复杂度，为基于分布式数据存储的隐私保护序 贯模式挖掘提供了技术支持。同时，发现分布式隐私保护序贯模式挖掘中的新问 题，为本领域进行研究的人员提供了借鉴，也为进一步的深入研究打下了基础。 1 4 论文的组织结构 本文的内容安排如下： 第一章绪论 介绍了本课题的研究背景，提出了论文的要解决的问题和研究意义，同时阐 述了本文的主要研究内容和组织结构。 第二章隐私保护和数据挖掘。 系统介绍了隐私保护和数据挖掘相关背景知识，包括当前流行的隐私保护数 据挖掘算法；数据挖掘方面主要介绍了序贯模式挖掘和隐私保护的数据挖掘。然 后介绍了密码学的基本知识，可交换加密，同态加密和安全多方计算理论。 第三章水平分布数据的隐私保护序贯模式挖掘。 本章是论文的一个重点研究- 内容之一，提出了水平分布数据的隐私保护序贯 模式挖掘算法( p r i v a c y p r e s e r v i n gs e q 嘲c ep a t t e r nm i n i n g o nh o r i z o n t a l l y p a r t i t i o n e dd a t a ，简称p p h s p m ) ，详细阐述了p p h s p m 算法的设计思想，分析 得出了考虑到隐私性以后增加的时间开销。在保护参与序贯模式挖掘各方的数据 上海大学硕士学位论文 隐私的前提下，为快速有效求出水平分布数据的全局频繁序贯模式提供了理论和 技术基础。 第四章垂直分布数据的隐私保护序贯模式挖掘 本章是论文的重点研究内容之一，论述了垂直分布数据的隐私保护序贯模式 挖掘新技术，提出了垂直分布数据的隐私保护序贯模式挖掘算法 ( p d v a c y p r e s e r v i n gs e q u e n c ep a t t e r nm i n i n go nv e r t i c a l l yp a r t i t i o n e dd a t a ，简称 p p v s p m ) ，详细阐述了p p - v s p m 算法的设计思想，并给出了实验结果与分析。 第五章结论与展望 本章总结了论文所做的主要工作，提出了论文中的一些需要改进的地方，对 隐私保护程度的度量以及在水平分布、垂直分布两种数据分布方式上的隐私保护 序贯模式挖掘进一步研究提出了自己的一些看法。 4 上海大学硕士学位论文 第二章隐私保护和数据挖掘 2 1 隐私保护 2 1 1 隐私保护概述 随着信息技术，特别是网络技术、数据存储技术和高性能处理器技术的飞速 发展，海量数据的收集、管理和分析变得越来越方便，知识发现和数据挖掘更是 在一些深层次的应用中发挥了积极的作用。但与此同时，在隐私保护方面也带来 了诸多问题。从应用领域来说，如商业领域，各公司都不愿意向其他公司，特别 是竞争对手公开自己的业务记录数据，以防止泄露商业机密，因此，他们需要有 一个安全的方法来解决联合统计分析问题，同时能保护各自的隐私信息：而从数 据挖掘应用本身的数据分布和系统拓扑上来说，在网络环境或者新兴的网格计算 环境下，大量的数据往往广泛分布于网络网格的各节点上，在跨节点联合数据 挖掘时，无论从网络信息安全角度还是应用数据机密性角度来说，同样存在隐私 保护的问题。所以，如何在数据挖掘过程中解决好隐私保护的问题，目前已经成 为数据挖掘界的一个研究热点嘲o 洲。 2 1 2 隐私的定义 隐私在不同的应用环境下有不同的解释。数据挖掘过程中所涉及的隐私一般 指的是用户的基本信息( 如姓名，年龄，家庭住址) 或用户某些行为产生的信息( 如 购物信息，医疗信息，网页浏览信息等) 这些信息的有意或无意泄露可能会给用 户带来麻烦。例如，医药公司希望客户泄露所患疾病的目的是为了解疾病之间的 相关性，而客户担心自己的隐私( 姓名、病史等) 泄露可能会影响就业。在分布式 数据挖掘中，参于的各方拥有各自的数据，通过合作进行挖掘的过程中，一方数 据相对于其他方是隐私。 2 1 3 隐私保护和信息安全 隐私保护和信息安全是非常相近的概念。但隐私保护与我们平常所说的狭义 的信息安全还是有一些明显的差别的。信息安全考虑的是如何保证数据不被泄 上海大学硕士学位论文 漏、修改和破坏，只有被授权的用户才有权限访问和修改相关的数据。而数据挖 掘系统里的隐私保护考虑的是如何保证挖掘出来的数据即挖掘的结果不涉及到 客户的隐私。需要明确的是，可能泄露隐私的并不是数据挖掘技术本身，而是数 据挖掘方法的特定应用和具体过程。 2 2 数据挖掘技术 2 2 1 数据挖掘概述 数据挖掘。1 旨在从大量的数据中提取隐藏的预测性信息，挖掘数据问潜在的 模式，找出那些常常被忽略的信息，用便于理解和观察的方式反映给用户，作为 决策的依据。 在数据挖掘过程中，如何选择输入数据和对应的挖掘方法，取决于具体的数 据挖掘目标，即期望从数据中发掘出何种类型的“知识”。 2 2 2 数据挖掘知识的分类 数据挖掘所发现的知识最常见的有以下五类： 广义知识( g e n e r a l i z a t i o n ) ：指类别特征的概括性描述知识。根据数据的 微观特性发现其表征的、带有普遍性的、较高层次概念的，中观和宏观的知识， 反映同类事物共同性质，是对数据的概括、精炼和抽象。广义知识的发现方法和 实现技术有很多，如数据立方体、面向属性的归约等。 关联知识( a s s o c i a t i o n ) ：它反映一个事件和其它事件之间依赖或关联的知 识。如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其它 属性值进行预测。最为著名的关联规则发现方法是r h g r a w a l 提出的a p r i o r i 算法。 分类知识( c l a s s i f i c a t i o n c l u s t e r i n g ) ：它反映同类事物共同性质的特征 型知识和不同事物之间的差异型特征知识。最为典型的分类方法是基于决策树的 分类方法。数据分类还有统计、粗糙集( r o u g h s e t ) 等方法。线性回归和线性辨 别分析是典型的统计模型。为降低决策树生成的代价，人们还提出了一种区间分 类器。最近也有人研究使用神经网络方法在数据库中进行分类和规则提取。 预测型知识( p r e d i c t i o n ) ：它根据时间序列型数据，由历史的和当前的数 据去推测未来的数据，也可以认为是以时间为关键属性的关联知识。目前，时间 序列预测方法有经典的统计方法、神经网络和机器学习等。h m a n n i l a “州“1 、 6 上海大学硕士学位论文 r a g r a w a l 等作了很多研究，较为著名的序贯模式挖掘方法是r a g r a w a l 叫”1 提 出的a p r i o r i a l l 、a p r i o r i s o m e 和g s p “”算法。 偏差型知识( d e v i a t i o n ) ：它是对差异和极端特例的描述，揭示事物偏离常 规的异常现象，如标准类外的特例，数据聚类外的离群值等。所有这些知识都可 以在不同的概念层次上被发现，并随着概念层次的提升，从微观到中观、到宏观， 以满足不同用户不同层次决策的需要。 2 2 3 数据挖掘的知识发现 知识 图2 i 数据挖掘流程图 数据挖掘的知识发现过程o 大致如图2 1 所示。 该过程包括了以下的处理步骤： 数据提取：根据要求从数据库中提取相关的数据，数据挖掘主要从这些数据 中进行知识提取，在此过程中，需要利用一些数据库操作对数据进行处理。 数据预处理：对选择的数据进行再加工，检查数据的完整性及一致性，对其 中的噪声数据进行处理，去除冗余数据，填补丢失的数据。 数据选择：从经过预处理的数据集中筛选出与分析目标无关或关系很小的属 性，在此进行特征抽取。 数据变换：将数据变换或统一成适合挖掘的形式，如数据汇总。 数据挖掘：根据应用的要求，选择合适的数据挖掘算法及模型参数，建立数 据挖掘模型，从数据中提取所需的知识，并以一定的形式展现出来。如决策树结 构，关联规则集。 7 上海大学硕士学位论文 解释与评价：将挖掘出的知识以用户可以理解的方式呈现给用户，并对所得 的结果进行解释。包括对知识的一致性检查，模型的验证，识别知识的真正有趣 的模式。 2 3 序贯模式挖掘技术 序贯模式挖掘是r a g r a w a l 与r s r i k a n t 首先提出的。与关联规则发现类 似，都是在交易数据库中试图发现先前未知的有价值的知识。所不同的是，关联 规则是试图发现在同一交易内的顾客购物联系，如“有7 5 的顾客在商场购物时 买了物品a 很可能同时还会买物品b ”；而序贯模式则是设法发现在不同交易阃 的顾客购物联系，如“有7 5 的顾客在商场购物时买物品a 后下次购物会很可能 购买物品b ”。商场可借此类发现结果调整、安排更合理更科学的商品进货、商 品摆放和商品促销等经营工作。 在序贯模式挖掘中，我们给定一个客户交易数据库d 。每笔交易记录由客户 标识符、交易时间和所购物品组成。在同一交易时问，任一顾客不会产生多于一 笔的交易，而且仅考虑在交易中购买那些物品，不考虑所购物品的数量，即在交 易数据库中，物品项是二元属性变量，表示要么购买了，要么就没有购买。 项集为非空的项集合，而序列则是项集的有序列表。顾客序列为某顾客按交 易时间排序的在不同时间购买的项集的有序列表。如果某一序列包含在某顾客序 列中，那么我们称该顾客支持该序列。一个序列的支持度为支持该序列的顾客数 除以顾客总数所得之百分比值。我们称支持度不低于某个用户指定阈值 m i n s u p p o r t 的序列为频繁序列。给定一个顾客交易数据库d 。序贯模式挖掘就 是在该数据库中发现最长的频繁序列。每个这样的最长频繁序列称为序贯模式。 2 4 隐私保护挖掘技术 2 4 。1 当前典型的隐私保护数据挖掘算法 表2 1 是根据数据分布方式、数据修改方法、数据挖掘算法、隐私保护的对 象和隐私保护技术所作的个归类。 8 上海大学硕士学位论文 表2 1 典型隐私保护数据挖掘算法一览表 作者题目数据 数据数据 隐私 隐私 分布 修改 挖掘保护 保护 方式方法方法对象技术 r a k e s ha g r a w a l p r i v a c y - p r e s e r v i n g集中 加随机偏分类数据重建技术 d a t am i n i n g 移量 w e n l i a n gd u u s i n gr a n d o m i z e d集中相关问题分类数据随即响应技术 r 娜n s ct e c h n i q u e s模型 f o rp r i v a c y - p s e r v i n g d a t am i n i n g w e n l i a n gd ub u i l d i n gd e c i s i o nt r e c 垂直 加随机数分类数据安全点积协议 c l a s s i f i e ro i lp r i v a t e分布 d a t a y e h u d al i n d d l p r i v a c y p r e s e r v i n gd a t a 水平依赖一个 分类 数据 不经意求 m i n i n g 分布。半可信”值协议 的第三方 s t a n l e y i 乙m p r i v a c yp r e s e r v i n g 集中过滤掉敏频繁规则启发式技术 o l i v e i r a f r e q u e n tl t e m s e t感数据项集 m i n i n g 一 a l e x a n d r e p r i v a c yp r e s e r v i n g集中随机修改关联数据重建技术 e v f i m i e y s k i m i n i n go f a s s o c i a t i o n 部分数据规则 r u l e s s j 砌z v j m a i n t a i n i n gd a t a 集中 剥用贝努 关联数据 重建技术 p d r a c yi na s s o c i a t i o n 利模型修规则 r u l em i n i n g 改数据 j a i d e e pv a i d y ap r i v a c yp r e s e r v i n g 垂直加随机数关联数据安全点积协议 a s s o c i a t i o nr u l e 分布规则 m i n i n gi nv e r t i c a l l y p a r t i t i o n e dd a t a m k a n t a r c i o g l u p r i v a c y - p r e s e r v i n g 水平数据加密关联数据交换加密技术 d i s u i h n t e dm i n i n go f分布及随机向规则 a s s o c i a t i o nr u l e so n量 h o r i z o n t a l l yp a r t i t i o n e d 。 d a i a s 咖l e y k ma c h i e v i n gp r i v a c y 集中乘以一个聚类数据基于旋转的等 o l i v c i r u p r e s e r v a t i o nw h e n 分布旋转变换s t a n l e y r m s h a r i n gd a t af o r 矩阵o l i v e i m c l u s t e r i n g 距变换技术 9 上海大学硕士学位论文 2 4 2 隐私保护技术概述 1 ) 基于启发式的技术 针对分类、关联规则发现、聚类等数据挖掘技术，已经提出了很多基于选择 性数据更改或清理的技术m 邮。瑚埘1 ，而数据选择更改或清理是n p 难的问题， 因此，启发式的方法可以处理复杂的情况。 2 ) 基于密码学的技术 已有很多基于密码学方法的隐私保护数据挖掘算法，这个领域种有两篇论文 相当具有概括性，第一篇文献。1 提出了一个转换框架，它允许系统地把正常计算 转换成安全多方计算。在其它信息项中，讨论了将各种数据挖掘问题转换成一个 安全多方计算。在该领域描述的数据挖掘应用包括数据分类，数据聚类，关联规 则，数据泛化，数据泛化和数据特征化。第二篇文献1 提出了四种基于安全多方 计算的方法，它们都支持隐私保护数据挖掘。描述的方法包括，安全和，安全集 合并，安全集合交的大小和数量积。下面我们列出在安全多方解决框架下解决问 题的几种方法。显然由于这种解决方法的本质，所有采用这种解决方法的实例中 的数据，其分布在两个或更多的站点中。 1 垂直分布数据的安全关联规则挖掘 从垂直分布数据中挖掘全局关联规则“州矧，可以从发现一个项集的支持度计 数而得到。垂直分布数据中，项是分布式的，每个项集被分开存贮在各站点。如 果这样的项集支持度计数可以安全计算，那么我们可以检查该支持度是否大于阈 值，而决定项集是否是频繁的。项集支持度计数的关键是计算代表各方子项集向 量的点积。因此，如果点积“订可以安全计算的话，支持度计数也可以计算。文献 描述的计算点积的算法，如同通过将它们放置在用随机值伪装的方程式中来隐 藏真实值的代数解决方案。点积协议的安全性是基于任何一方不能从k 个方程 组中解出多于k 的未知数：一些未知数是随机选择的，可以安全地假定为隐私 数据。文献”3 提出了一个相似的方法。文献1 描述了计算支持度计数的另一个方 法，它使用了集合交的安全大小。 2 水平分布式的数据安全关联规则挖掘 在水平分布式数据库中，交易分布在n 个站点。项集的全局支持度计数是所 有局部支持度计数的和。如果项集x 的全局支持度计数大于整个交易数据库大小 的s ，项集x 是全局支持的。如果k 项集是全局支持的，那么它成为全局大k 项 集。文献啪1 利用安全并和安全和的隐私保护安全多方计算安全多方计算( 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 c ) ，操作，实现了隐私保护的分布式关联规则 挖掘算法m 】。 上海大学硕士学位论文 3 垂直分布式数据安全决策树产生器 文献啪3 研究了建立一个适应垂直分布数据的决策树分类器的过程。该研究中 提出的协议是利用第三方服务器建立一个安全点积协议。 4 水平分布数据安全决策数据产生器 文献啪1 针对隐私保护分类问题提出了一个解决方案，它使用安全多方计算方 法，即针对水平分布数据的健忘传递协议。给定一个一般的s m c 解决方法，它不 具有实际值，该作者集中在决策树产生器的问题上，特别是广泛使用的i d 3 产 生器。通过用皿，表示所有可能树的集合，一旦它们在等价类中就选择一个属 性，针对特殊i d 3 。算法的安全计算提出了一个协议。为了秘密计算i d 3 。该协 议由很多更小的私有计算触发。其中最难的计算降低到x l n x 函数的健忘评估。 5 隐私保护聚类 一 文献汹1 提出了使用最大期望算的安全聚类的算法。该算法是一个迭代算法， 它使用了安全和s 眦协议。 ( 3 ) 基于重构的技术 最近提出了很多技术，通过在聚合层次上扰动数据和重构分布律来进行数据 挖掘，以此强调隐私保护的问题。下面我们就有关这方面的一些技术作一下分类。 1 数值型数据的重构技术 文献“”强调了通过个别记录值已经扰乱的训练数据来建立决策树分类器的 问题。从个别数据记录中精确地估计原始值是不可能的，而作者提出了一个重构 过程来精确地估计原始数据的分布律。通过重构分布律而建立的分类器的精确度 与直接用原始数据建立的分类器的精确度相当。对于数据的扭曲，该作者采用一 种离散化的方法和值扭曲的方法。对于重构原始分布律，他们采用贝叶斯方法， 并提出了三种依赖于重构分布律来建立精确决策树的算法。 文献嘲使用e m 分布重构算法来改进贝叶斯重构过程。更确切地说，作者证 明e m 算法收敛于扰动数据初始分布的极大似然估计。当数据很大的情况下，e m 算法对初始分布律提供了健壮的估计。这也说明了，文献。”在从重构聚合分布中 挖掘出额外的知识时隐私估计精确度降低。 2 二值和类别数据的重构技术 文献“聃3 研究了对关联规则挖掘中的二值和类别数据的处理。这些文献中 都考虑了隐私问题的随机化技术，并且维持了数据集的高可用性。 2 5 密码学和安全多方计算理论 首先对于密码学的基本理论进行简单的介绍，然后较为详细地阐述安全多方 计算的理论，最后对于安全多方计算的算法特点进行说明。而本文后面提出算法 上海大学硕士学位论文 中的隐私保护部分的设计就是以安全多方计算理论为基础的。 2 5 1 密码学概述 待加密的消息称作明文( p l a i n t e x t ) ，用某种方法伪装消息并隐藏其内容的 方法称作加密( e n c r y p t i o n ) ，被加密以后的消息称为密文，把密文转变成明文 的过程称为解密。加密体制中的加密运算是由一个算法类组成，这些算法类的不 同运算可用不同的参数表示，不同的参数分别代表不同的算法，被称作密钥，密 钥空间是所有密钥的集合。密码体制一般是指密钥空间与相应的加密运算结构， 同时还包括了明文和密文的结构特征。 密码体制发展到现在，已经有了很多种不同的类型。但是从密码体制所使用 算法的分类上说，一种是利用了对称算法；另一种则是利用了公开密钥算法。对 称算法是指加密密钥和解密密钥能够互相推算出来，公开了一个也就相当于公开 另一方。因此对称算法的密钥只能由发送者和接收者两方知道，它们必须事先商 定好密钥，这一点就涉及了密钥交换协议。公开密钥算法啪1 是指公开了加密算法 b 以后不会泄露解密算法d 。因此和对称算法相比，任何人都可以通过公开渠道 ( 网络或密钥管理中心) 获知他人的加密密钥，把明文加密以后传送给接收者，而 只有拥有解密密钥仉的人才能够对密文解密。这在密钥管理和消息的传送方面更 具有优势。公开密钥算法的加密、解密函数，大都互为反函数，采用计算复杂度 高的单向函数，如模指数运算，其安全性高于短密钥的对称密钥密码，但是加密 解密的速度慢于对称密钥密码。 在目前实际生活中应用比较广泛的公钥加密算法包含有r s a 密码体制和椭 圆曲线密码体制”1 1 9 7 9 年，s h a m i rr i v e s t 和a d e l m a n 提出了第一个也是应用最广的公钥密码 体制，即r s a 体制。经过2 0 多年的密码分析和攻击，迄今为止，r s a 被证明仍 是安全的。设n = p q ，p 和q 是两个大素数，a 和b 是两个整数，定义密钥空间为 ( n ，p ，q a ，b ) ：n = p q ，a b e - 1 ( m o d 妒( n ) ) ) 。把n ，b 作为公开密钥，而p ，q ，a ，妒( h ) ， 作为秘密密钥，整个加密算法就是y = e ( 工) = 矿m o d 一，而解密算法是 b ( ) ，) = ，m o d 再，由e u l e r 定理知道，工= 皿( y ) 成立，上述解密的方法正确。 由于r s a 加密算法是指数运算，因此当密钥越大时，计算速度越慢。r s a 算 法比通常的d e s 算法慢了1 5 0 0 倍。并且r s a 的计算量很大，为了要达到较高的 安全程度，r s a 的密钥位数比其它的密码体制大的多，现在一般需要1 0 2 4 比特 上海大学硕士学位论文 位的密钥。所以一般对速度要求较高的数字签名或智能卡中的身份验证不太使用 r s a 密码体制，而采用其它较快的算法。椭圆曲线密码系统就是其中的一种。 椭圆曲线密码体制和r s a 体制比较起来，所需要的密钥量小，安全程度高， 比如r s a 密码体制需要1 0 2 4 比特位的密钥才能达到的安全程度，利用椭圆曲线 只需要1 6 0 比特位的密钥就能够保证同样的安全，密钥长度的减少同时带来了计 算速度的提高。即使是在剩余类环z 。运用离散对数而构造的加密系统的安全程 度也要低于椭圆曲线，因此椭圆曲线系统不愧为一个性质较好的密码系统。 椭圆曲线第一次运用于公钥密码算法是在1 9 8 5 年，n e a lk o b l i t z 和v s m i l l e r 提出来的他们并没有提出新的算法，只是把椭圆曲线运用到已存在的 公钥密码算法中，比如说e i g a m a l 加密算法。利用e i g a m a l 思想构造的椭圆曲线 密码体制如下显示： 首先是产生密钥阶段。b o b 从乙中随机选取充分大的整数k ，随后计算出 椭圆曲线上的点p = q ( q 是椭圆曲线上的适当的点) ，将保密，作为秘密密 钥，并将p 公开，作为公钥。 加密方法如下：如果r l i c e 想把消息m ( 同样是椭圆曲线上的一点) 发送给 b o b ，就从乙中随机选择整数，e 乙后，计算出s l = i q 和足= m + i p 的值，加密 以后的信息就是椭圆曲线上两点( s ，最) 。 解密：b o b 收到加密信息( s ，是) 后，通过密钥就可以计算m = s 2 一k s 得 到消息m 。 上述两个系统的安全性都依赖于一些数论中的基本困难问题。比如说r s a 体 制利用了把大整数n 分解为两个大素数的难度，而椭圆曲线是利用了求解离散对 数问题的困难程度，即根据p = q 和q 求解乙中整数k 。这些密码体制都是很 成功的，在实际中也有了进一步的应用。 协议( p r o t o c 0 1 ) 是指一系列的步骤，它包括两方或者多方，设计它的目的 是要完成一项任务。密钥交换协议( k e ye x c h a n g ep r o t o c 0 1 ) 是指两人或多人之 问通过一个协议取得密钥并用于进一步的加密算法中的方法。在实际的密码世界 中密钥交换是很重要的一个环节。比如说利用对称加密算法，如果双方没有约定 好密钥，就必须再进行密钥交换。但是如何使得密钥到达接收者和发送者手里是