（管理科学与工程专业论文）基于安全多方计算的协同过滤推荐算法研究.pdf

ad i s s e r t a t i o ns u b m i t t e dt og u a n g d o n gu n i v e r s i t yo ft e t h ed e g r e eo fm a s t e r 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 - b a s e dc o l l a f i l t e r i n gr e c o m m e n d a t i o na l g o r i t h mr e s c a n d i d a t e ：y a oz h i h u i s u p e r v i s o r ：p r o f l i uh o n g w e i a p r i l2 0 1 0 s c h o o lo fm a n a g e m e n t g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g y g u a n g z h o u ，g u a n g d o n g ，p r c h i n a ，5 10 5 2 0 摘要 于两芰 协同过滤是一种常用的减少信息过载的技术，它已经成为了个性化推荐系统 的一种主要工具。随着电子商务的不断发展需要，跨机构的协同计算越来越多， 由此也引出了数据隐私保护这一严峻的问题。而安全多方计算正是解决在多方计 算过程中确保计算结果准确的前提下如何进行隐私保护的一个多方计算协议。如 何将安全多方计算应用到个性化推荐中，特别是协同过滤研究中将非常有现实意 义。 目前，一些常用隐私保护算法或只能保护数据在传输过程的安全性，使之不 泄露出去；或对数据进行扰乱，使其他人无法获得源数据。前者不能保护数据的 隐私，因为数据对于参与计算的多方是完全公开的；后者则使计算的结果产生一 定的偏差，反映并非真实的结果。而安全多方计算是一种多方协同计算协议，他 既可以保护数据的隐私又可以计算出准确的结果，即使是参与协同计算的多方也 仅能知道自己的隐私输入和计算结果。本文详细研究了安全多方计算协议的两个 协议：线性方程组问题协议和线性最小二乘问题协议。安全多方计算协议是有别 于常用数据隐私保护算法的协议，它通过巧妙地运用1 o u t o f - n 协议和矩阵运算 达到既可得到在数据统一服务器计算时的结果，又可避免数据在同一服务器上而 产生的隐私泄露问题。此外本文归纳总结了将不含隐私保护的协同计算转换为有 隐私保护的安全多方计算的两种输入模型转换机制。并归纳整理了安全多方计算 在各种隐私保护现实问题中的应用：如在线性方程组问题、数据查询问题、入侵 检测问题、数据挖掘问题、几何计算问题和数理统计问题中的应用。最后根据协 同过滤算法和安全多方计算协议的结构特征，将两者结合起来，设计出一种基于 安全多方计算协议的协同过滤推荐算法。该算法主要分为四个功能模块( 也叫过 程模块) ：数据预处理、相似性度量、寻找最近邻、评分预测及项目推荐。该算法 的核心部分是对相似性的度量，本文分别运用了矩阵变换和数值扰动两种方法来 设计该功能模块。所运用的这两种方法均能达到既不影响相似度计算的准确性又 实现了计算过程中的隐私保护。最后本文还对所设计算法的安全策略进行分析。 该算法对促进电子商务的发展具有极高现实的意义，也是本为的创新点所在。 关键词：隐私保护；数据扰乱技术；安全多方计算；协议；协同过滤；矩阵变换； q u e r yp r o b l e m ，i n t r u s i o nd e t e c t i o np r o b l e m ，d a t am i n i n g ，g e o m e t r yc a l c u l a t i o na n d a p p l i c a t i o no fm a t h e m a t i c a ls t a t i s t i c s f i n a l l y , c o m b i n i n gt h ec o l l a b o r a t i v ef i l t e r i n g a n ds 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 ，t h i sp a p e rd e s i g n s e c u r e m u l t i p a r t y c o l l a b o r a t i v ef i l t e r i n ga l g o r i t h m t h i sa l g o r i t h mi sd i v i d e di n t of o u rm a i nf u n c t i o n m o d u l e s ( a l s oc a l l e dp r o c e s sm o d u l e ) ：d a t ap r e t r e a t m e n t ，s i m i l a r i t y , l o o k i n gf o rt h e n e a r e s t ，s c o r ep r e d i c t i o na n dr e c o m m e n d e dp r o je c t t h ec o r eo ft h ea l g o r i t h mi st h e i i a b s t r a c t m e a s u r eo fs i m i l a r i t y t h i sp a p e rd e s i g n st h et w om o d u l e sa c c o r d i n gt om a t r i x t r a n s f o r m a t i o na n dn u m e r i c a ld i s t u r b a n c ew h i c hn e i t h e rc a nr e a c ht h es i m i l a r i t y c a l c u l a t i o na c c u r a c yn o rr e a l i z et h ec a l c u l a t i o np r o c e s so fp r i v a c yp r o t e c t i o n m e a n w h i l e ，t h i sp a p e ra l s oa n a l y s e st h es a f e t ys t r a t e g yo ft h ed e s i g n e da l g o r i t h m t h ea l g o r i t h mh a sh i g hp r a c t i c a ls i g n i f i c a n c ef o rp r o m o t i n gt h ed e v e l o p m e n to f e - c o m m e r c e ，b u ta l s of o rt h ei n n o v a t i o no ft h i s k e yw o r d s ：p r i v a c yp r o t e c t i o n ，d a t ad i s r u p tt e c h n o l o g y ，s 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 ，c o l l a b o r a t i v ef i l t e r i n g ，m a t r i xt r a n s f o r m a t i o n i i i 广东工业大学硕士学位论文 日三茸 目水 摘要i a b s t r a c t 目录 c o n t e n t v i i 第一章绪论1 1 1 研究背景1 1 3 相关研究的发展动态及综述3 1 3 1 隐私保护算法3 1 3 2 数据扰乱技术4 1 3 3 安全多方计算5 1 3 研究的目标、内容及组织结构6 第二章常用的隐私保护算法概述8 2 1 各国信息化隐私保护的相关法律8 2 1 1 美国儿童在线隐私保护法案8 2 1 2 澳大利亚隐私法9 2 1 3 美国电子通信隐私法9 2 1 4 加拿大获得信息法9 2 1 5 加拿大个人信息保护和电子文档法1 0 2 1 6 信息公开促进法1 0 2 1 7 其它国家信息化隐私保护的相关法律1 0 2 1 8 中国的相关法律1 1 2 2 数据传输加密算法1 l 2 2 1 数据加密的基本过程1 1 2 2 2 常见的数据传输加密算法1 2 2 3 数据扰乱技术18 目录 2 3 1 概率分布方法1 9 2 3 2 值扰乱方法2 0 第三章安全多方计算隐私保护协议2 4 3 1 研究背景2 4 3 - 2 相关的工作2 7 3 2 1 “1 一o u t o f 二n 不经意传输协议2 7 3 2 2 关于安全的定义2 7 3 3 安全多方计算协议2 8 3 3 1 两种协同模式2 8 3 3 2 隐私保护线性方程组问题协议2 9 3 3 3 隐私保护线性最小二乘问题协议3 6 3 4 协议与一般解决方案效率的比较3 8 第四章安全多方计算的应用4 0 4 1 安全多方计算转换机制一4 l 4 2 具体安全多方计算问题4 5 4 2 1 隐私保护协同科学计算4 5 4 2 2 隐私保护数据库查询4 6 4 2 - 3 隐私保护入侵检测4 7 4 2 4 隐私保护数据挖掘。4 8 4 2 5 隐私保护几何计算4 9 4 2 6 隐私保护的统计分析。5 0 4 2 7 其他具体安全多方计算问题5 l 4 3 几种概要方法5 1 第五章基于安全多方计算的同过滤算法设计5 4 5 1 协同过滤算法原理5 4 5 2 基于安全多方计算协议的协同过滤算法设计原理5 4 5 3 数据预处理5 5 5 4 相似性度量5 6 v 广东工业大学硕士学住论文 5 4 1 选取度量方法5 6 5 4 2 计算相似度5 7 5 5 寻找最近邻6 2 5 6 评分预测及项目推荐6 4 5 7 隐私保护策略分析6 7 5 7 1 矩阵变换策略6 7 5 7 2 数值扰动策略6 8 结论6 9 参考文献7 1 攻读学位期间发表的论文7 6 独创性声明。7 7 致谢7 8 v i a b s t r a c t ( e n g l i s h ) i i c o n t e n t ( c h i n e s e ) c o n t e n t ( e n g l i s h ) v i i c h a p t e r li n t r o d u c t i o n 1 1 1r e s e a r c hb a c k g r o u n da n ds i g n i f i c a n c e 1 1 2r e s e a r c hs t a t u so f p r i v a c yp r o t e c t i o no f d a t am i n i n g 3 1 2 1p r i v a c yp r o t e c t i o na l g o r i t h m 3 1 2 2d a t ad i s r u p tt e c h n o l o g y 4 1 2 2s e c u r em u l t i - p a r t yc o m p u t a t i o n 5 1 3r e s e a r c hc o n t e n ta n dt h e s i ss t r u c t u r e 6 c h a p t e r 2r e l a t e dt h e o r yo fe n c r y p t i o na l g o r i t h m 8 2 1a 1 lr e l e v a n tl a w s 8 2 1 1 a m e r i c a nc h i l d r e n so n l i n ep r i v a c yp r o t e c t i o n a c t 8 2 1 2 a u s t r a l i a np r i v a c ya c t 9 2 1 3a m e r i c a ne l e c t r o n i cc o n u n u n i c a t i o n sp r i v a c ya c t 9 2 1 4 c a n a d i a na c c e s s t i o ni n f o r m a t i o na c t 9 2 1 5c a n a d i a nt h ep e r s o n a li n f o r m a t i o np r o t e c t i o na n de l e c t r o n i cd o c u m e n t sa c t 10 2 i 6t h es o u t ho f a f r i c ap r o m o t i o no f a c c e s st oi n f o r m a t i o n a c t 1 0 2 1 7o t h e ri n f o r m a t i o np r i v a c yp r o t e c t i o nl a w s 1 0 2 1 8c h i n a sr e l e v a n tl a w s 1 1 2 2d a i ae n c r y p t i o na l g o r i t h m l1 2 2 1t h eb a s i cp r o c e s so f d a t ae n c r y p t i o n 11 2 2 2c o m m o ne n c r y p t i o na l g o r i t h m s 1 2 2 3d a t ad i s r u p tt e c h n o l o g y 18 2 3 1p r o b a b i l i t yd i s t r i b u t i o nm e t h o d 1 9 v i i 广东工业大学硕士学位论文 2 3 2v a l u e d i s r u p tm e t h o d 2 0 c h a p t e r 3s 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 2 4 3 1r e s e a r c hb a c k g r o u n d 2 4 3 2r e l a t e dw o r k 2 7 3 2 i “i o u t o f - n o b l i v i o u st r a n s f e rp r o t o c o l 2 7 3 2 2t h ed e f i n i t i o no f s a f e t y 2 7 3 3s 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 2 8 3 3 1t w ok i n d so fc o o p e r a t i v em o d e s 2 8 3 3 2l i n e a re q u a t i o n sp r o b l e m sp r o t o c o l 2 9 3 3 3p p cp r o b l e mo f l i n e a rl e a s ts q u a r e sp r o t o c o l 3 6 3 4p r o t o c o l se f f i c i e n c y 3 8 c h a p t e r 4s m cp r o b l e ma p p l i c a t i o n 4 0 4 1s e c u r em u l t i - p a r t yc o m p u t a t i o nc o n v e r s i o nm e c h a n i s m 4 1 4 2s p e c i f i cs 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 b l e m s 4 5 4 2 1p r i v a c yp r o t e c t i o nc o o r d i n a t i o ns c i e n t i f i cc a l c u l a t i o n s 4 5 4 2 2p r i v a c yp r o t e c t i o nd a t a b a s eq u e r i e s 4 6 4 2 3p r i v a c yp r o t e c t i o ni n t r u s i o nd e t e c t i o n 4 7 4 2 4p r i v a c yp r o t e c t i o ng e o m e t r yc a l c u l a t i o n 4 8 4 2 5p r i v a c yp r o t e c t i o ng e o m e t r yc a l c u l a t i o n 5 0 4 2 6as t a t i s t i c a la n a l y s i so f t h ep r i v a c yp r o t e c t i o n 5 0 4 2 7o t h e rs p e c i f i cs 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 b l e m s 51 4 3s e v e r a ls u m m a r ym e t h o d s 51 c h a p t e r 5s m ci nc o l l a b o r a t i v ef i l t e r i n ga p p l i c a t i o n 5 4 5 1c o l l a b o r a t i v ef i l t e r i n ga l g o r i t h m 5 4 5 2s m cp r o t o c o lb a s e do nt h ed e s i g np r i n c i p l eo ft h ec o o p e r a t i v ef i l t e ra l g o r i t h m 5 4 5 3d a t ap r e p r o c e s s i n g 5 5 5 4s i m i l a r i t ym e a s u r i n g 5 6 5 4 1s e l e c tm e a s u r i n gm e t h o d 5 6 v i i i c o n t e n t s 5 4 2s i m i l a r i t yc a l c u l a t i o n 5 7 5 5s e e k i n gn e a r e s tn e i 曲b o r 6 2 5 6s c o r ep r e d i c t i o na n dp r o j e c tr e c o m m e n d a t i o n 6 4 5 7p r i v a c yp r o t e c t i o ns t r a t e g ya n a l y s i s 6 7 5 7 1m a t r i xt r a n s f o r m a t i o ns t r a t e g y 6 7 5 7 2d a t ad i s t u r b e ds t r a t e 舀e s 6 8 c o n c l u s i o n 6 9 r e f e r e n c e s 7 l p u b l i s h e da r t i c l e sd u r i n gp o s t g r a d u a t es t u d y 7 6 o r i g i n a l i t ys t a t e m e n t 7 7 a c k n o w i e d g e m e n t 7 8 i x 第一章绪论 1 1 研究背景 第一章绪论 近年来，网络技术的不断发展，极大地改变了计算的含义及计算的方式，人 们面临的是以高性能计算机、网格等为代表的日益强大的计算环境，用户可以通 过网络使用这些强大的计算资源完成自己的计算任务。而在这种环境中，保证用 户数据的安全，是计算的基本要求。安全多方计算( s 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 ，s m c ) 正是在这样的背景之下日益引起人们的关注。所谓安全多方 计算问题，就是假设有刀个参与者弓，r ，每个参与者只持有秘密输入x t ， 共同计算函数值厂( 而，t ，) i ( k ，艺，) ，要求即使在某些参与者不诚实的情 况下，这种计算也能保护参与者的输入的秘密性，同时保证计算结果的正确性， 使得第i 个参与者确保能够得到共，除此之外得不到任何其他的信息。例如，在 利用网络进行商务活动时，经常要建立某些网络协议，参与的双方或多方提供自 己的( 一般是秘密的) 输入，在协议被完全诚实地执行时，参与各方获得预期的 ( 一般是秘密的) 输出信息。但是，在现实世界中，参与各方的诚实性往往难以 保证，我们必须要考虑某些参与方企图通过各种欺诈手段( 比如，提供假的输入、 提供假的身份信息、恶意终止协议) 获得利益的情况，当然也要考虑由于无意的 输入错误或网络故障导致协议不能正常完成的情况及来自外部的恶意或无意攻 击，在所有这些情况下，我们必须保证诚实参与者的信息安全，使欺诈者或攻击 者不能获得额外利益。g o l d w a s s e r 曾经预言：“多方计算领域的今天，就像是l o 年前的公钥密码学。它是一个强大的工具且蕴含丰富的理论，其实际应用刚刚开 始，但必将变成计算王国的主干。 这从某种程度上，也反映出安全多方计算研究 的远大前景。 为了保护参与者输入的秘密性，一个最简单的方式就是找到一个可信任的实 体，大家把各自的输入秘密地交给这个可信方，由可信方来计算出函数值，然后 将相应的函数值返回给参与计算的各方。但是现实世界中很难找到这样的可信第 三方，这就导致了安全多方计算问题的研究。 s m c 的含义极为广泛，且具有广泛的应用背景。保密通信、数字签名等都可 视为安全多方计算的特殊情况，典型应用如认证协议、在线支付协议、拍卖协议、 广东工业大学硕士学位论文 选举协议、隐私保护的数据查询数据挖掘等等。甚至从某种意义上讲，任何计算 都可以被看作是安全多方计算的一个实例。 s m c 最早是由a c y a o 1 】于19 8 2 年提出的，即广为人知的百万富翁问题，实 际上是解决两个整数比较大小的s m c 问题。随后，广大的研究工作者对s m c 进 行了广泛的研究，产生了一批代表性的成果。目前所有的工作可以分为两类。第 一类工作致力于在理论上研究任意函数的一般化的安全多方计算方法。作为解决 问题的一般性方法，这类研究在理论上具有很大价值，但是目前得到的结果，都 存在着时间、空间以及通信复杂度的代价太高的问题，还不能应用于解决实际问 题。另外一类工作重点讨论特定函数的多方计算，以期待对于特定的问题找到更 高效的可以实用的解决方案。 1 ) 理论上一般化方法的研究 理论上的一般化方法首先是将任意函数用基本操作表示，然后讨论这些基本 操作的安全多方计算方法。事实上，要计算的函数可视为某空间，上的一个算法 电路c ，而c 可以被分解为一系列依次被处理的基本运算门，因此任意函数的多 方安全计算转化为基本运算门的安全多方计算。现有的c 的分解方式有两种，一 种是将其分解为只有加法门与乘法门构成，这种情况下，任意函数的计算则可以 认为是依次进行一系列，上的函数输入值( 或中间结果) 间的加法与乘法；另外 一种分解方式是将c 分解为基本的比特运算，也就是二元a n d ，x o r 以及一元 n o t 运算。 2 ) 特定的安全多方计算问题 在已有文献【2 巧】中，有几个针对特定安全多方计算应用问题的特定解决方案， 比如私有信息的查询问题( 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 ) ，隐私保护的统计 数据库问题，隐私保护的数据挖掘问题，加密数据计算问题等。 p i r 问题由一个客户端和一个服务器组成，客户端需要从服务器得到二进制 序列的第f 个比特，但是不想让服务器知道f ，同样的服务器不想让客户端得到除 第f 个比特之外的其他信息。这个问题的解决方案并不困难，然而要得到一个高 效的解决方案，特别是一个通信代价较小的解决方案，并非易事。文献【2 巧1 在这方 面作了大量工作，相对于使用一般化的安全多方计算方法，对p i r 问题，得到了 通信复杂度大大降低的专用方案。 加密数据计算( c o m p u t i n gw i t he n c r y p e t e dd a t a ，c e d ) 问题也是s m c 问题的 2 第一章绪论 一个特殊形式，是只有一方存在输入与输出的s m c 。典型的两方c 的是安全地借用对方的计算能力，例如，客户端借用高性能计算中- 算能力，智能卡借用主机计算能力等。目前c e d 问题的主要解决思路是利用同态 加密的思想。同态加密的理论基础是环的同态，设明文空间p 以及密文空间c 都 是环，e 是p 专c 上的加密函数。记明文a , b p 。若存在算法儿u s 及m u l t ，满 足e ( a + b ) = 儿嬲( e ( 口) ，e ( 6 ) ) ，e ( a b ) = 删己丁( e ( 口) ，e ( 6 ) ) ，则我们称加密算法e 满 足加法同态以及乘法同态性。利用加密同态算法，我们就可以在不需要知道明文 a ，b 的情况下，利用a ，b 的密文e ( 口) ，e ( b ) ) 计算出e ( a + b ) 与e ( a b ) 的值，再解 密就可以得到a + 6 及口6 的值。目前典型的c e d 方案是f e i g e n b e u m 的，给出了离 散对数问题的c e d 方法，并指出n p c 问题都是可加密计算的。而在应用中，目 前对于比如公钥运算等具体问题的c e d 协议还没有人涉足。 综上所述，s m c 问题是一个在信息安全领域广泛关注的问题，从s m c 领域 的最初成果出现以来，己经有许多的工作提升了得到的结果，至今还有大量文献 出现，这些文献得到了一些更强或更一般化的敌手攻击下的处理方案，在降低通 信或者交互轮次的复杂性方面也有一些进展。但是目前的成果仍然只停留在理论 研讨的阶段，其效率低下，远远没有达到可以实用化的程度。随着高性能计算、 网格计算环境的发展，s m c 问题具有了很强的实用化需求，需要大力研究可以实 用的方案。 1 3 相关研究的发展动态及综述 1 3 1 隐私保护算法 随着数据挖掘的广泛应用和随之而来的隐私泄露问题，隐私保护成为了一个 重要而富有挑战性的课题。自从隐私保护问题提出之后，产生了很多隐私保护算 法。2 0 0 0 年，文献 6 , 7 1 同时从两个不同的角度提出了两种不同的隐私保护数据挖 掘问题，并分别采用数据扰乱技术和安全多方计算协议加以解决，推动了相关技 术的研究。此外，文献【8 】习还提出了一种基于随机化的方法一随机响应技术，利 用这种源于统计学研究中隐私保护的方法，来实现在不泄露隐私数据的情况下进 行一定精度的建模。文献 9 1 将这种技术与其他数据挖掘算法进行结合，设计了其 他算法框架。当前研究最多的还是关联规则挖掘的隐私保护算法。文献【1o 】讨论了 广东工业大学硕士学住论文 保护私有信息的关联规则挖掘的一般方法。文献】讨论了一个利用不确定性符号 进行数据阻塞并应用于关联规则挖掘的具体例子，这种情况下支持度和置信度分 别用支持度区间和置信度区间代替。在保护隐私的关联规则挖掘中，按照用户的 合作方式可以将共享的数据库分为垂直划分【1 2 】与水平划分【1 3 1 两类，文献【1 2 】提出 一种新的点积协议来求解数据垂直划分问题，文献【”】基于安全求并算法求解数据 水平划分问题。 目前对于分布式数据挖掘隐私保护方法的研究工作绝大部分集中在数据扰乱 ( 例如公布数据之前对数据源使用增加噪音法) 和使用安全多方计算对数据进行 隐私计算上。 1 3 2 数据扰乱技术 数据扰乱方法【1 4 】是一种解决数据挖掘中个人隐私保护难题的常用方法。数据 扰乱技术的主要思想是在保护数据在挖掘和统计中的效用的同时，通过转换改变 数据使得真实的个人数据值不被披露。因为转换后的数据不是反映真实的个人数 据值，所以即使数据项跟某个体相关联，该个体的隐私也不会被侵犯。扰乱技术 的一个主要方法是数据交换，通过数据记录之间交换数据从而保护了可靠的统计 结果，但同时隐藏了真实的数据值。扰乱技术的另一个主要方法是随机化，为数 据增加“噪声”以保护真实数据不被发现。通过对数据的随机化处理，数据不再反 映真实的世界，从而使得数据无法被滥用而侵犯个人的隐私。当然扰乱技术的关 键在于如何从扰乱数据中获得有效的数据挖掘结果。 使用数据扰乱方法的前提假设是数据必须对挖掘算法保密，是与安全相关的 数据挖掘应用中一个常用的方法，所有数据扰乱技术的目标是最大化隐私保护程 度和数据有用性，但隐私保护和数据有用性又是互相矛盾的。数据扰乱技术首先 是由r a g r a w a l 等【l5 】提出，目的是保证在挖掘过程中单个记录的值不会泄露。因 为数据挖掘的任务是从数据集中找到有用的集合模式，那么就有可能在无需获得 单个具体记录值的条件下找到正确的模式。他们的方法是对原始数据加上服从某 种分布( 均值为0 的正态分布或者均匀分布) 的“噪声数据，得到的所谓“扭 曲数据，这些数据可以认为不会泄露原始数据的信息，因此对于数据挖掘算法而 言是安全的。他们利用扭曲数据的值以及噪声数据的分布，通过b a y e s 法则构建 原始数据的近似分布，在这个过程中可以认为不会泄露单个数据的值。利用所得 4 第一章绪论 到的近似分布，对“扭曲数据”进行改进或直接进行挖掘，得到数据挖掘结果的近 似值。这种方法相对于安全多方计算方法效率较高，但存在一个主要问题是需要 在挖掘结果的正确性和隐私性之间做出折衷，很难得到精确的挖掘结果。在保护 隐私的前提下要保持数据的有用性是目前数据扰乱方法面临的一个挑战。目前为 止，己有一些学者提出了一些数据扰乱方法【1 6 】并得到了应用。 a g r a w a l 等【l5 j 提出了一种值扰乱技术来保护隐私，即添加一些服从高斯分布 的噪声到实际数据中。并且表明了这种技术不但伪装了真实数据并且以很好的精 度提取出正确的模型，这一方法也得到了进一步的发展。e v f i m i e v s k i 等针对关联 规则挖掘提出了限制隐私裂口的方法。最近，k a r g u p t a t l 7 】等对添加随机噪声方法 提出了质疑，并指出加法随机噪声可以很容易的被过滤出，在许多情况下会折衷 隐私。由于出现了大量的信号处理文献提出关于过滤随机噪声的方法，使得添加 加法随机噪声的方法对隐私保护的数据挖掘的效果已经不是十分明显了。 1 3 3 安全多方计算 安全多方计算( 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 ) 【l8 】就是拥有秘密输入的多方， 希望用各自的秘密输入共同计算一个函数。计算要求每方都能接收到正确的输m ( 正确性) 。并且每方只能了解他们自己的输出( 保密性) 。安全多方计算的一个 关键就是构造多方安全协议。安全多方协议( s e c u r em u l t i p a t r yp r o t o c 0 1 ) 是一个 为解多方安全计算问题的协议。 s m c 的含义极为广泛，且具有广泛的应用背景。保密通信、数字签名等都可 视为安全多方计算的特殊情况，典型应用如认证协议、在线支付协议、拍卖协议、 选举协议、隐私保护的数据查询数据挖掘等等。甚至从某种意义上讲，任何计算 都可以被看作是安全多方计算的一个实例。 s m c 最早是由a c y a o 1 】于1 9 8 2 年提出的，即广为人知的百万富翁问题，实 际上是解决两个整数比较大小的s m c 问题。随后，广大的研究工作者对s m c 进 行了广泛的研究，产生了一批具有代表性的成果。目前所有的工作可以分为两类。 第一类工作致力于在理论上研究任意函数的一般化的安全多方计算方法。作为解 决问题的一般性方法，这类研究在理论上具有很大价值，但是目前得到的结果， 都存在着时间、空间以及通信复杂度的代价太高的问题，还不能应用于解决实际 问题。另外一类工作重点讨论特定函数的多方计算，以期待对于特定的问题找到 5 广东工业大学硕士学位论文 更高效的可以实用的解决方案。 1 3 研究的目标、内容及组织结构 研究目标：将安全多方计算应用到协同过滤中，设计出一个基于安全多方计 算的协同过滤算法。 研究内容：本文结合前人研究的成果，重点讨论了常用的隐私保护算法以及 安全多方计算协议，还列举了安全多方计算的相关问题及其应用。最后设计出基 于安全多方计算的协同过滤算法。 本文共分为五章，具体安排如下t 第一章为绪论部分，首先提出研究背景及研究意义，其次，简要概括文中相 关研究的发展动态，其中包括安全多方计算的发展概况、各国信息化隐私保护的 相关法律、隐私保护算法综述、数据要乱技术及安全多方计算的相关研究。 第二章首先归纳出在数据隐私保护方面的相关法律，然后归纳总结常用的隐 私保护算法。根据隐私保护在协同计算的不同计算过程将常用的隐私保护算法划 分为数据传输加密算法和数据扰乱技术两类。 数据传输加密算法的基本过程就是对原来为明文的文件或数据按某种算法进 行处理，使其成为不可读的一段代码，通常称为“密文 ，使其只能在输入相应的 密钥之后才能显示出本来内容，通过这样的途径来达到保护数据不被非法人窃取、 阅读的目的。该过程的逆过程为解密，即将该编码信息转化为其原来数据的过程。 加密技术通常分为两大类：“对称式 和“非对称式”。 数据扰乱方法主要分为两类：概率分布方法和值扰乱方法。前者用其它的服 从同样分布的样本代替原始的数据；而值扰乱技术直接添加一些加法或乘法扰乱 噪声扰乱原始的数据元素或属性的值。 第三章我们描述了两个关于安全多方计算的协议，包括用于隐私保护协同线 性系统方程组协议( p p c l s e ) 和隐私保护协同线性最小二乘问题协议( p p c l l s ) 。并就安全多方就算协议与一般解决方案的效率进行比较。 第四章归纳总结了将没有隐私要求的协同计算转换为有隐私保护的安全多方 计算的两种输入模型的转换机制。并归纳整理了安全多方计算在各种隐私保