L-Diversity Privacy Beyond K-Anonymityl-多樣性超越K-匿名隱私

L-Diversity:PrivacyBeyondK-AnonymityAshwinMachanavajjhala,JohannesGehrke,DanielKifer,MuthuramakrishnanVenkitasubramaniamCS295Dataprivacyandconfidentiality-ViragKothariOverviewIntroductionAttacksonk-AnonymityBayesOptimalPrivacyl-DiversityPrinciplel-DiversityInstantiationsMultipleSensitiveAttributesMonotonicityPropertyUtilityConclusionCS295DataprivacyandconfidentialityBackgroundLargeamountofperson-specificdatahasbeencollectedinrecentyearsBothbygovernmentsandbyprivateentitiesDataandknowledgeextractedbydataminingtechniquesrepresentakeyassettothesocietyAnalyzingtrendsandpatternsFormulatingpublicpoliciesLawsandregulationsrequirethatsomecollecteddatamustbemadepublicForexample,CensusdataCS295DataprivacyandconfidentialityWhatAboutPrivacy?Firstthought:anonymizethedataHow?Remove“personallyidentifyinginformation”(PII)Name,SocialSecuritynumber,phonenumber,email,address…AnythingthatidentifiesthepersondirectlyIsthisenough?CS295DataprivacyandconfidentialityRe-identificationbyLinkingNameZipcodeAgeSexAlice4767729FBob4798365MCarol4767722FDan4753223MEllen4678943FVoterregistrationdataQIDSAZipcodeAgeSexDisease4767729FOvarianCancer4760222FOvarianCancer4767827MProstateCancer4790543MFlu4790952FHeartDisease4790647MHeartDiseaseIDNameAliceBettyCharlesDavidEmilyFredMicrodataCS295DataprivacyandconfidentialityClassificationofAttributesKeyattributesName,address,phonenumber-uniquelyidentifying!AlwaysremovedbeforereleaseQuasi-identifiers(5-digitZIPcode,birthdate,gender)uniquelyidentify87%ofthepopulationintheU.S.CanbeusedforlinkinganonymizeddatasetwithotherdatasetsCS295DataprivacyandconfidentialitySensitiveattributesMedicalrecords,salaries,etc.Theseattributesiswhattheresearchersneed,sotheyarealwaysreleaseddirectlyNameDOBGenderZipcodeDiseaseAndre1/21/76Male53715HeartDiseaseBeth4/13/86Female53715HepatitisCarol2/28/76Male53703BrochitisDan1/21/76Male53703BrokenArmEllen4/13/86Female53706FluEric2/28/76Female53706HangNailKeyAttributeQuasi-identifierSensitiveattributeCS295DataprivacyandconfidentialityK-AnonymityTheinformationforeachpersoncontainedinthereleasedtablecannotbedistinguishedfromatleastk-1individualswhoseinformationalsoappearsinthereleaseExample:youtrytoidentifyamaninthereleasedtable,buttheonlyinformationyouhaveishisbirthdateandgender.Therearekmeninthetablewiththesamebirthdateandgender.Anyquasi-identifierpresentinthereleasedtablemustappearinatleastkrecordsCS295DataprivacyandconfidentialityAttacksonK-anonymityHomogeneityAttacksBackgroundKnowledgeAttacksCS295DataprivacyandconfidentialityHomogeneityAttacksSinceAliceisBob’sneighbor,sheknowsthatBobisa31-year-oldAmericanmalewholivesinthezipcode13053.Therefore,AliceknowsthatBob’srecordnumberis9,10,11,or12.ShecanalsoseefromthedatathatBobhascancer.CS295DataprivacyandconfidentialityOriginalTable4-anonymousTableBackgroundKnowledgeAttacksAliceknowsthatUmekoisa21year-oldJapanesefemalewhocurrentlylivesinzipcode13068.Basedonthisinformation,AlicelearnsthatUmeko’sinformationiscontainedinrecordnumber1,2,3,or4.Withadditionalinformation,UmekobeingJapaneseandAliceknowingthatJapanesehaveanextremelylowincidenceofheartdisease,AlicecanconcludedwithnearcertaintythatUmekohasaviralinfection.CS295DataprivacyandconfidentialityOriginalTable4-anonymousTableWeaknessesink-anonymoustablesGiventhesetwoweaknessesthereneedstobeastrongermethodtoensureprivacy.Basedonthis,theauthorsbegintobuildtheirsolution.CS295DataprivacyandconfidentialityAdversariesBackgroundKnowledgeTheadversaryhasaccesstoT*andknowsitwasderivedfromtableT.Thedomainofeachattributeisalsoknown.Theadversarymayalsohaveinstancelevelbackgroundknowledge.Theadversarymayalsoknowdemographicbackgrounddatasuchastheprobabilityofaconditiongivenanage.CS295DataprivacyandconfidentialityBayes-OptimalPrivacyModelsbackgroundknowledgeasaprobabilitydistributionovertheattributesandusesBayesianinferencetechniquestoreasonaboutprivacy.However,Bayes-OptimalPrivacyisonlyusedasastartingpointforadefinitionofprivacysothereare2simplifyingassumptionsmade.Tisasimplerandomsampleofalargerpopulation.AssumeasinglesensitivevalueCS295DataprivacyandconfidentialityPriorbeliefisdefinedas:Posteriorbeliefisdefinedas:CS295DataprivacyandconfidentialityPriorbeliefandposteriorbeliefareusedareusedtogaugetheattacker’ssuccess.CalculatingtheposteriorbeliefCS295DataprivacyandconfidentialityPrivacyPrinciplesCS295DataprivacyandconfidentialityPositiveDisclosure:PublishingthetableT?thatwasderivedfromTresultsinapositivedisclosureiftheadversarycancorrectlyidentifythevalueofasensitiveattributewithhighprobability.Negativedisclosure:PublishingthetableT?thatwasderivedfromTresultsinanegativedisclosureiftheadversarycancorrectlyeliminatesomepossiblevaluesofthesensitiveattribute(withhighprobability)CS295DataprivacyandconfidentialityDrawbackstoBayes-OptimalPrivacyInsufficientknowledgebecausethepublisherisunlikelytoknowthefulldistributionofsensitiveandnon-sensitiveattributesoverthefullpopulation.Thedatapublisherdoesnotknowtheknowledgeofawouldbeattacker.Instancelevelknowledgecannotbemodeled.TherearelikelytobemanyadversarieswithvaryinglevelsofknowledgeCS295DataprivacyandconfidentialityL-DiversityPrincipleTheorem3.1definesamethodofcalculatingtheobservedbeliefoftheadversaryInthecaseofpositivedisclosures,AlicewantstodetermineBob’ssensitiveattributewithaveryhighprobability.GivenTheorem3.1thiscanonlyhappenwhen:CS295DataprivacyandconfidentialityTheconditionofequation2canbesatisfiedbyalackofdiversityinthesensitiveattribute(s)and/orstrongbackgroundknowledge.

Lackofdiversityinthesensitiveattributecanbedescribedasfollows:

Equation3indicatesthatalmostalltupleshavethesamevalueasthesensitivevalueandthereforetheposteriorbeliefisalmost1.ToensurediversityandtoguardagainstEquation3istorequirethataq?-blockhasatleastl≥2differentsensitivevaluessuchthatthelmostfrequentvalues(intheq?-block)haveroughlythesamefrequency.Wesaythatsuchaq?-blockiswell-representedbylsensitivevalues.CS295DataprivacyandconfidentialityThisequationstatesthatBobwithquasi-identifiert[Q]=qismuchlesslikelytohavesensitivevalues′thananyotherindividualintheq?-block.CS295DataprivacyandconfidentialityAnattackermaystillbeabletousebackgroundknowledgewhenthefollowingistrueCS295DataprivacyandconfidentialitySupposeweconsideranequivalenceclassfortheexampleofbackgroundknowledgeattackshownearlier.HereAlicehasbackgroundknowledgethatJapanesepeoplearelesspronetoheartdisease.∴f(s′|q)=0(∵TheprobabilitythatUmekohasheartdiseasegivenhernonsensitiveattributeas‘Japanese’is0).Also,f(s′|q*)=2/4∴f(s′|q)/f(s′|q*)=0.

RevisitingtheexampleInspiteofsuchbackgroundknowledge,iftherearel“wellrepresented”sensitivevaluesinaq?-block,thenAliceneedsl?1damagingpiecesofbackgroundknowledgetoeliminatel?1possiblesensitivevaluesandinferapositivedisclosure!CS295DataprivacyandconfidentialityL-DiversityPrincipleGiventhepreviousdiscussions,wearriveatthel-Diversityprinciple:CS295DataprivacyandconfidentialityRevisitingtheexampleUsinga3-diversetable,wenolongerareabletotellifBob(a31yearoldAmericanfromzipcode13053)hascancer.WealsocannottellifUmeko(a21yearoldJapanesefromzipcode13068)hasaviralinfectionorcancer.CS295Dataprivacyandconfidentiality4-anonymoustable3diversetableDistinctl-DiversityEachequivalenceclasshasatleastlwell-representedsensitivevaluesDoesn’tpreventprobabilisticinferenceattacks10records8recordshaveHIV2recordshaveothervaluesCS295DataprivacyandconfidentialityL-DiversityInstantiationsEntropyl-DiversityRecursive(c,l)DiversityPositiveDisclosure-Recursive(c,l)-DiversityNegative/PositiveDisclosure-Recursive(c1,c2,l)-DiversityCS295DataprivacyandconfidentialityEntropyl-DiversityHereeveryq?-blockhasatleastldistinctvaluesforthesensitiveattributeThisimpliesthatforatabletobeentropyl-Diverse,theentropyoftheentiretablemustbeatleastlog(l).Therefore,entropyl-Diversitymaybetoorestrictivetobepractical.CS295DataprivacyandconfidentialityRecursive(c,l)DiversityLessrestrictivethanentropyl-diversityLets1,…,smbethepossiblevaluesofsensitiveattributeSinaq*-blockAssume,wesortthecountsn(q*,s1),...,n(q*,sm)indescendingorderwiththeresultingsequencer1,…,rm.Wecansayaq*-blockisrecursive(c,l)-diverseifr1<c(r2+….+rm)foraspecifiedconstantc.CS295DataprivacyandconfidentialityPositiveDisclosure-Recursive(c,l)-DiversitySomecasesofpositivedisclosuremaybeacceptablesuchaswhenmedicalconditionis“healthy”.Toallowthesevaluestheauthorsdefinepd-recursive(c,l)-diversity

CS295DataprivacyandconfidentialityNegative/PositiveDisclosure-Recursive(c1,c2,l)-DiversityNpd-recursive(c1,c2,l)-diversitypreventsnegativedisclosurebyrequiringattributesforwhichnegativedisclosureisnotallowedtooccur.MultipleSensitiveAttributesPreviousdiscussionsonlyaddressedsinglesensitiveattributes.SupposeSandVaretwosensitiveattributes,andconsidertheq*-blockwiththefollowingtuples:

{(q,s1,v1),(q,s1,v2),(q,s2,v3),(q,s3,v3)}.Thisq*-blockis3-diverse(actuallyrecursive(2,3)-diverse)withrespecttoS(ignoringV)and3-diversewithrespecttoV(ignoringS).However,ifweknowthatBobisinthisblockandhisvalueforSisnots1thenhisvalueforattributeVcannotbev1orv2,andthereforemustbev3.Toaddressthisproblemwecanaddtheadditionalsensitiveattributestothequasi-identifier.CS295DataprivacyandconfidentialityImplementingPrivacyPreservingDataPublishingDomaingeneralizationisusedtodefineageneralizationlattice.Fordiscussion,allnon-sensitiveattributesarecombinedintoamulti-dimensionalattribute(Q)wherethebottomelementonthelatticeisthedomainofQandthetopofthelatticeisthedomainwhereeachdimensionofQisgeneralizedtoasinglevalue.CS295DataprivacyandconfidentialityImplementingPrivacyDataPublishing(cont.)ThealgorithmforpublishingshouldfindthepointonthelatticewherethetableT*preservesprivacyandisusefulaspossible.Theusefulness(utility)oftableT*isdiminishedasthedatabecomesmoregeneralized,sothemostutilityisatthebottomofthelattice.CS295DataprivacyandconfidentialityMonotonicityPropertyMonotonicitypropertyisdescribedasastoppingpointinthelatticesearch