Collaborative filtering techniques have become popular in the past several years as an effective way to help people deal with information overload. An important security concern in traditional recommendation systems is that users disclose information that

DerivingPrivateInformationfromRandomlyPerturbedRatings

ShengZhang,JamesFord,FilliaMakedon{clap,jford,makedon}@cs.dartmouth.edu

DepartmentofComputerScienceDartmouthCollege,Hanover,NH03755

Abstract

Collaborative lteringtechniqueshavebecomepopularinthepastseveralyearsasane ectivewaytohelppeopledealwithinformationoverload.Animpor-tantsecurityconcernintraditionalrecommendationsystemsisthatusersdiscloseinformationthatmaycompromisetheirindividualprivacywhenprovidingratings.Randomizedperturbationschemeshavebeenproposedtodisguiseuserratingswhilestillproducingaccuraterecommendations.However,recentresearchhassuggestedthatperturbationschemesmightnotbeabletopreserveprivacyasmuchashasbeenbelieved.Weproposetwodatareconstructionmethodsthatderiveoriginalprivateinformationfromdisguiseddatainexistingperturbationcollaborative lteringschemes.Onemethodisbasedonk-meansclusteringandtheotherusessingularvaluedecom-position(SVD).Wehaveconductedtheoreticalandexperimentalanalysisonthedi erencebetweenorig-inaldataandreconstructeddata.Ourexperimentsshowthatbothmethodscanderiveaconsiderableamountoforiginalinformation.Thisstudyhelpstodetermineanempiricaltrade-o betweenrecommenda-tionaccuracyanduserprivacyinperturbationschemes.Keywords:collaborative ltering,privacy,randomizedperturbation,datareconstruction.1

Introduction

informationiftheycanbene tinreturn,asarecentsurvey[9]indicates,asigni cantnumberofpeoplearenotwillingtodothat.Therefore,aresearchchallengeforCFsystemsistoprovideaccuraterecommendationswithoutcompromisingcustomers’privacy.

Tothebestofourknowledge,therearethreemeth-odsofpreservinguserprivacythathavebeenusedinrecommendationsystems.The rstistouseanonymiza-tiontechniquesthatallowuserstoprovidepersonalin-formationwhilekeepingtheiridentitiesprivate[1,19].Themainproblemwiththisapproachisthatthequal-ityofthecollecteddatacannotbeguaranteedbecausetheidentitiesofdatacontributorscannotbeveri ed.Thesecondapproachistodesignsecuremulti-partycomputationprotocolsforCFalgorithmstoensurethatprivacyisnotcompromisedduringcommunicationsbe-tweentheserverandusers[7,8].Ascryptographicop-erationsarefrequentlyusedinthisapproach,compu-tationalcostisaconcern.Thelastmethodusesran-domizedperturbationtechniquestodisguiseuserdatawhilestillallowingtheservertoestimatetheaggregateinformationwithreasonableaccuracy[17,18].

Recently,Karguptaetal.[16]pointedoutthatrandomizationtechniquesmightnotpreserveprivacyasmuchashadbeenbelieved.Theyproposedarandommatrix-basedspectral lteringtechniquetorecovertheoriginaldatafromtheperturbeddata,andtheirresultsshowedthatrecovereddatacanbeclosetotheorigi-naldata.Motivatedbythiswork,Huangetal.[15]proposedusingtwodatareconstructionmethods(prin-cipalcomponentanalysis(PCA)andBayesestimation)thatarebasedondatacorrelationsintheoriginaldata.Theirexperimentsshowedthattheoriginaldatacanbereconstructedmoreaccuratelywhencorrelationsarehigh.

Whilemethodsfromtheabovestudiescanbeusedgenerallyforvariousapplications,thegoalofthispaperistodesignspeci cdatareconstructiontechniquesforrandomizedperturbationCFschemes(inparticular,schemesproposedin[17,18]).Weintendtoanswerthefollowingquestions:Whatistheempiricaltrade-

CollaborativeFiltering(CF)isawaytoserveupproductsorservicestoaparticularuserbasedonwhatotheruserswithsimilartasteshavepreferred.PeopleusesCFsystemstocopewithinformationoverloadbyreducingthenumberofalternativestheyneedtoconsider.However,traditionalCFsystemsareaseriousthreattoindividualprivacybecausedatacollectedfromcustomerscoverspersonalinformationaboutplacesandthingstheydo,watch,andpurchase[7,8,17].Customerdataisvaluable,andsomecompanieshavesoldtheirsuponsu eringbankruptcy.Whilesomepeoplemightbewillingtoselectivelyprovidepersonal