boundadmit

HALId:hal-01006380https://hal.
inria.
fr/hal-01006380Submittedon16Jun2014HALisamulti-disciplinaryopenaccessarchiveforthedepositanddisseminationofsci-entificresearchdocuments,whethertheyarepub-lishedornot.
ThedocumentsmaycomefromteachingandresearchinstitutionsinFranceorabroad,orfrompublicorprivateresearchcenters.
L'archiveouvertepluridisciplinaireHAL,estdestinéeaudéptetàladiffusiondedocumentsscientifiquesdeniveaurecherche,publiésounon,émanantdesétablissementsd'enseignementetderecherchefranaisouétrangers,deslaboratoirespublicsouprivés.
Generalizeddifferentialprivacy:regionsofpriorsthatadmitrobustoptimalmechanismsEhabElsalamouny,KonstantinosChatzikokolakis,CatusciaPalamidessiTocitethisversion:EhabElsalamouny,KonstantinosChatzikokolakis,CatusciaPalamidessi.
Generalizeddifferentialpri-vacy:regionsofpriorsthatadmitrobustoptimalmechanisms.
vanBreugel,FranckandKashefi,ElhamandPalamidessi,CatusciaandRutten,Jan.
HorizonsoftheMind.
ATributetoPrakashPanangaden,8464,SpringerInternationalPublishing,pp.
292-318,2014,LectureNotesinComputerScience,978-3-319-06879-4.
10.
1007/978-3-319-06880-0_16.
hal-01006380Generalizeddifferentialprivacy:regionsofpriorsthatadmitrobustoptimalmechanismsEhabElSalamouny1,2,KonstantinosChatzikokolakis1,andCatusciaPalamidessi11INRIA,CNRSandLIX,Ecolepolytechnique,France2FacultyofComputersandInformatics,SuezCanalUniversity,EgyptAbstract.
Differentialprivacyisanotionofprivacythatwasinitiallydesignedforstatisticaldatabases,andhasbeenrecentlyextendedtoamoregeneralclassofdomains.
Bothdifferentialprivacyanditsgeneralizedversioncanbeachievedbyaddingrandomnoisetothereporteddata.
Thus,privacyisobtainedatthecostofreducingthedata'saccuracy,andthereforetheirutility.
Inthispaperweconsidertheproblemofidentifyingoptimalmechanismsforgen-eralizeddifferentialprivacy,i.
e.
mechanismsthatmaximizetheutilityforagivenlevelofprivacy.
Theutilityusuallydependsonapriordistributionofthedata,andnaturallyitwouldbedesirabletodesignmechanismsthatareuniversallyoptimal,i.
e.
,optimalforallpriors.
Howeveritisalreadyknownthatsuchmechanismsdonotexistingeneral.
Wethencharacterizemaximalclassesofpriorsforwhichamechanismwhichisoptimalforallthepriorsoftheclassdoesexist.
Weshowthatsuchclassescanbedenedasconvexpolytopesinthepriorsspace.
Asanapplication,weconsidertheproblemofprivacythatariseswhenusing,forinstance,location-basedservices,andweshowhowtodenemechanismsthatmaximizethequalityofservicewhilepreservingthedesiredlevelofgeo-indistinguishability.
1ProloguePrivacyisaninstanceofthegeneralproblemofinformationprotection,whichconsti-tutesoneofthemaintopicsoftheresearchofourteamCométe.
ThehistoryofourinterestforthistopichasanimportantmilestoneinthevisitofPrakashtoCométein2006,inthecontextofouréquipeassociéePrintemps.
Wehadbeenworkingforawhileonaprobabilisticapproachtoanonymity,andwhenPrakasharrived,hesuggestedtoconsideraninformation-theoreticapproachinstead.
ThiswasthebeginningofaveryfruitfulcollaborationbetweenPrakashandourteam,andtwoofthepapersthatorigi-natedfromthiscollaborationbecamethebackboneofthePhDthesisofKonstantinosChatzikokolakis.
Furthermore,thecollaborationwithPrakashinuences,stilltoday,ourresearchoninformationprotection,inthesensethatourresearchischaracterizedbytheparadigmaticviewofasystemasanoisychannel–thecentralconceptofinformationtheory.
Thepresentpaper,whichexploresthepropertiesofthechannelmatrixinthecontextofdifferentialprivacy,isatributetothefundamentalrolethatPrakashhashadinCométe'sscienticlifeandevolution.
ThisworkispartiallyfundedbytheInrialargescaleinitiativeCAPPRIS,theEUFP7grantno.
295261(MEALS),theINRIAEquipeAssociéePRINCESS,andbytheprojectANR-12-IS02-001PACE.
2EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessi2IntroductionItisoftenthecasethataprivacythreatarisesnotbecauseofdirectaccesstosensi-tivedatabyunauthorizedagents,butratherbecauseoftheinformationtheycaninferfromcorrelatedpublicdata.
Thisphenomenon,knownasinformationleakage,isquitegeneralandithasbeenstudiedinseveraldifferentdomains,includingprogramminglanguages,anonymityprotocols,andstatisticaldatabases(see,forinstance,[1–3]).
Nat-urally,thesettingsandtheapproachesvaryfromdomaintodomain,buttheprinciplesarethesame.
Inthecaseofstatisticaldatabases,thepublicinformationistypicallydenedbythekindofqueriesweareallowedtoask,andtheconcernsforprivacyfocusontheconsequencesthattheparticipationinthedatabasesmayhaveforthecondentialdataofasingleindividual.
Differentialprivacy[4,5]wasdesignedtocontroltheseconse-quences.
Sinceithasbeenrecognizedthatthedeterministicmethodsofferlittleresis-tancetocompositionattacks(i.
e.
tothecombinationofinformationinferredfromdif-ferentdatabases,seeforinstance[6,7]),differentialprivacytargetsprobabilisticmech-anisms,i.
e.
mechanismsthatanswerthequeryinaprobabilisticfashion.
Typically,theygeneratetheoutputbyaddingrandomnoisetothetrueanswer,accordingtosomeprobabilisticdistribution.
Theaimofdifferentialprivacyistoguaranteethatthepartic-ipationofasingleindividualinthedatabasewillnotaffecttoomuchtheprobabilityofeachreportedanswer.
Moreprecisely,(thelogof)theratiobetweenthelikelihoodsofobtainingacertainanswer,fromanytwoadjacentdatabases(i.
e.
,differingonlyforthepresenceofanindividual),mustnotexceedagivenparameter.
Therationaleofthisnotioncomesfromthefactthatitisequivalenttothepropertythatthereportedanswerdoesnotchangesignicantlytheprobabilisticknowledgeoftheindividualdata.
Differ-entialprivacyhasbecomeverypopularthankstothefactthatitiseasytoimplement:itissufcienttoaddLaplaciannoisetothetrueanswer.
Furthermore,thenotionandtheimplementationareindependentfromthesideknowledgeoftheadversaryabouttheunderlyingdatabase(representedasapriorprobabilitydistiributionoverpossibledatabases).
Finally,itiscompositional,inthesensethattheprivacylosscausedbythecombinationofattacksisthesumofthesingleprivacylosses.
Therehavebeenseveralstudiesaimedatapplyingdifferentialprivacytootherareas.
Inthiswork,wefocusontheapproachproposedin[8],whichintroducedtheconceptofdX-privacy,suitableforanydomainXequippedwithanotionofdistancedX.
GivenamechanismKfromthesetofsecretsXtodistributionoversomesetofoutputsZ,wesaythatKsatisesdX-privacyifforanytwosecretsx1andx2,andanyoutputz,thelogoftheratiobetweenK(x1)andK(x2)doesnotexceeddX(x1,x2).
NotethatdX-privacyisanextensionofdifferentialprivacy:thelattercanbeobtainedbysettingXtobethesetofdatabases(seenastuplesofindividualrecords)anddXtobetheHammingdistancebetweenthesetuples,scaledby.
Furthermore,itisaconservativeextension,inthesensethatitpreservestheimplementabilitybymeansofLaplaciannoise,theindependencefromthepriorprobability,theinterpretationintermsofprob-abilisticknowledge,andthecompositionalityproperties.
Fromthepracticalpointofview,dX-privacyisparticularlysuitabletoprotecttheaccuracyofthevalues,likeinthecaseofsmart-metersignatures[8]andtheprecisegeographicalpositioninlocation-TitleSuppressedDuetoExcessiveLength3basedservices[9].
Similarextensionsofdifferentialprivacyobtainedbygeneralizingthedistanceortheadjacencyrelationhavebeenconsideredin[10–12].
Besidesguaranteeingprivacy,amechanismshouldofcourseprovideananswerwhichis"useful"enoughfortheserviceithasbeendesigned.
Thissecondgoalismea-suredintermsofutility,whichrepresentstheaveragegainthatarationaluserobtainsfromthereportedanswer.
Moreprecisely,letybethetrueanswerandletzbetheout-putreportedbythemechanism.
Onthebasisofthelatter,theusertriestomakeaguessy′(remapping)aboutthe(hidden)trueanswery.
Hisgaing(y,y′)isdeterminedbyagivenfunctiong.
Theutilityisthendenedastheexpectedgainunderthebestpossibleremapping.
Whilethegainfunctioncantakevariousforms,inthispaperwerestrictouranalysistothebinarygainfunction,whichevaluatesto1whentheuser'sguessisthesameasthequeryresult(y=y′)andevaluatesto0otherwise.
Obviously,thereisatrade-offbetweenprivacyandutility,andweareinterestedinmechanismsthatoffermaximalutilityforthedesiredlevelofdX-privacy.
Suchmecha-nismsarecalledoptimal.
Naturally,wearealsointerestedinmechanismsthatareuni-versallyoptimal,i.
e.
,optimalunderanyprior1,aswedon'twanttodesignadifferentmechanismforeachuser2.
AfamousresultbyGoshetal.
[13]statesthatthisispossi-bleforthecountingqueries,namelythequeriesoftheform"howmanyrecordsinthedatabasehavethepropertyp",forsomep.
UnfortunatelyBrennerandNissimshowedthatindifferentialprivacyuniversallyoptimalmechanismsdonotexistforanyotherkindofquery[14].
However,onecanstillhopethatitispossibletodesignmechanismsthatareoptimalforasignicantclassofusers.
Theseareexactlythemainobjectivesofthispaper:identifyregionsofpriorswhichadmitarobustoptimalmechanism,i.
e.
amechanismwhoseoptimalityisnotaffectedbychangesintheprior(withintheregion),andprovideamethodtoconstructsuchmechanism.
Arelatedissuethatweconsiderinthispaperistheamountofinformationleakedbyamechanism,acentralconceptintheareaofquantitativeinformationow.
Therehavebeenvariousproposalsforquantifyingtheinformationleakage,weconsiderhereaninformation-theoreticapproachbasedonRényimin-entropy[15,16],whichissuitableforone-tryattacks.
Amaindifferencebetweenthemin-entropyleakageanddX-privacyisthattheformermeasurestheexpectedriskofdisclosureofsensitiveinformation,whilethelatterfocusesontheworstcase,i.
e.
,itconsiderscatastrophicanysuchdisclo-sure,nomatterhowunlikelyitis.
Recently,researchershaveinvestigatedtherelationbetweendifferentialprivacyandmin-entropyleakage[17–19],andinparticularithasbeenprovedin[18]thatdifferen-tialprivacyinducesaboundonthemin-entropyleakage,whichismetbyacertainmechanismfortheuniformprior(forwhichmin-entropyleakageisalwaysmaximum).
Inthispaper,weextendtheaboveresulttoprovideamoreaccurateboundforanypriorinthespecialregionsdescribedabove.
Moreprecisely,weprovideaboundtotheleak-agespecictothepriorandthatcanbemet,underacertaincondition,byasuitablemechanism.
Contributions1Notethat,incontrasttodX-privacy,utilitydoesdependontheprior.
2Werecallthatthepriorrepresentsthesideknowledgeoftheuser.
4EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessi–Weidentify,foranarbitrarymetricspace(Y,dY),theclassofthedY-regulardistri-butionsofY.
TheinterestofthisclassisthatforeachpriordistributioninitweareabletoprovideaspecicupperboundtotheutilityofanydY-privatemechanism.
Wecharacterizethisclassasageometricregion,andwestudyitsproperties.
–WedescribeadY-privatemechanism,called"tight-constraintsmechanism",whichmeetstheupperboundforeverydY-regularprior,andisthereforerobustlyoptimalinthatregion.
Weprovidenecessaryandsufcientconditionsfortheexistenceofsuchmechanism,andaneffectivemethodtotesttheconditionsandtoconstructthemechanism.
–Weconsiderthedomainofdatabases(X,dX),wheredXistheHammingdistance,andwerecasttheabovedenitionsandresultsintermsofmin-entropyleakage.
Weareabletoimprovearesultfromtheliteraturewhichsaysthatdifferentialprivacyinducesaboundonthemin-entropyleakagefortheuniformprior:Weprovidemoreaccuratebounds,andshowthattheseboundsarevalidforallthedX-regularpriors(notjustfortheuniformone).
Aconstructionsimilartotheoneinthepreviouspointyieldsthetight-constraintsmechanismwhichreachesthoseupperbounds.
Apreliminaryversionofthispaper,restrictedtostandarddifferentialprivacy,andwithoutproofs,appearedinPOST2013.
PlanofthepaperInthenextsectionwerecallthebasicdenitionsofgeneralizeddifferentialprivacy,utility,andmin-entropymutualinformation.
Section3introducesthenotionofdY-regularprior,investigatesthepropertiesofthesepriors,andgivesageometriccharacterizationoftheirregion.
Section4showsthatforalldY-regularpriorsonthetrueanswers(resp.
databases),dY-privacyinducesanupperboundontheutility(resp.
onthemin-entropyleakage).
Section5identiesamechanismwhichreachestheaboveboundsforeverydY-regularprior,andthatisthereforetheuniversallyoptimalmechanism(resp.
themaximallyleakingmechanism)intheregion.
Section6illustratesourmethodologyandresultsusingtheexampleofthesumqueriesandlocationprivacy.
Section7concludesandproposessomedirectionsforfutureresearch.
3PreliminariesInthissectionwerecallthegeneralizedvariantofdifferentialprivacyfrom[8],con-sideringanarbitrarysetofsecretsX,equippedwithametricdX.
Wethendiscusstwoinstantiationsofthegeneraldenition:rst,standarddifferentialprivacyisdenedondatabasesundertheHammingdistance.
Second,geo-indistinguishability[9],anotionoflocationprivacy,isobtainedbyusinggeographicallocationsassecrets,undertheEuclideandistance.
Finally,werecallastandardwayformeasuringtheutilityofamechanism,andthenotionofmin-mutualinformation.
3.
1GeneralizedprivacyAsdiscussedintheintroduction,ageneralizedvariantofdifferentialprivacycanbedenedonanarbitrarysetofsecretsX,equippedwithametricdX.
Intuitively,dX(x,x′)TitleSuppressedDuetoExcessiveLength5givesthe"distinguishabilitylevel"betweensecretsx,x′,basedontheprivacysemanticsthatwewishtoobtain.
Thesmallerthedistinguishabilitylevelis,theharderitshouldbefortheadversarytodistinguishthetwosecrets,henceofferingprivacy,whilesecretsatgreatdistanceareallowedtobedistinguished,givingthepossibilitytoobtainsomecontrolledknowledgeaboutthesecret.
AmechanismfromXtoZisafunctionK:X→P(Z),whereP(Z)denotesthesetofprobabilitydistributionsoversomesetofoutputsZ.
InthispaperweconsiderX,Ztobenite,hencetheinvolveddistributionstobediscrete.
Themechanism'soutcomeK(x)isthenaprobabilitydistribution,andK(x)(z)istheprobabilityofanoutputz∈Zwhenrunningthemechanismonx∈X.
ForsimplicitywewriteK:X→ZtodenoteamachanismfromXtoZ(omittingP).
ThemultiplicativedistancedPbetweenprobabilitydistributions1,2∈P(Z)isdenedasdP(1,2)=supz∈Z|ln1(z)2(z)|withtheconventionthat|ln1(z)2(z)|=0ifboth1(z),2(z)arezeroand∞ifonlyoneofthemiszero.
WearenowreadytogivethedenitionofdX-privacy:Denition1.
AmechanismK:X→ZsatisesdX-privacy,iffx,x′∈X:dP(K(x),K(x′))≤dX(x,x′)orequivalently:K(x)(z)≤edX(x,x′)K(x′)(z)z∈ZTheintuitionbehindthisdenitionisthattheattacker'sabilitytodistinguishtwosecretsshoulddependontheirdistinguishabilityleveldX(x,x′).
Theclosertwosecretsare,themoresimilarthemechanism'soutputonthosesecretsshouldbe,makingitharderfortheadversarytodistinguishthem.
DependingonthechoiceofdX,thedenitioncanbeadaptedtotheapplicationathand,givingrisetodifferentnotionsofprivacy.
In[8],twoalternativecharacterizationsofdX-privacyarealsogiven,inwhichtheattacker'sknowledgeisexplicitlyquantied,whichmakesiteasiertounderstandtheprivacyguaranteesobtainedbyaparticularchoiceofdX.
Answeringqueries.
Inpractice,weoftenwanttolearnsomeinformationaboutoursecret,thatiswewanttoobtaintheanswertoaqueryf:X→Y.
Todosoprivately,wecancomposefwitha"noise"mechanismH:Y→Z,thusobtainingan"oblivious"mechanismHf:X→Z,calledoblivioussincetheanswerdependsonlyonf(x)andnotonxitself.
TheroleofHistoaddrandomnoisetothetruequeryresultf(x)andproducea"noisy"reportedoutputz∈Z.
Sinceweassumeallsetstobenite,themechanismHcanbedescribedbyastochasticmatrixH=(hyz),calledthenoisematrix,whoserowsareindexedbytheelementsofYandwhosecolumnsareindexedbytheelementsofZ.
Hence,hyzistheprobabilityofreportingzwhenthetruequeryresultisy.
GivenametricdYonY,thegeneralizeddenitionofprivacyallowsustodirectlytalkabouttheprivacyofH,withoutinvolvingfatall.
Usingmatrixnotation,dY-privacyforH(Denition1)canbewrittenashyz≤edY(y,y′)hy′zy,y′∈Y,z∈Z(1)6EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessiAnaturalquestion,then,ishowdX-privacyofthecomposedmechanismHfrelatestodY-privacyofH.
Theconnectionbetweenthetwocomesfromtheconceptofuniform-sensitivity.
Denition2.
Asequencey1,yniscalledachainfromy1toyn.
WesaythatsuchchainistightifdY(y1,yn)=idY(yi,yi+1).
Twoelementsy,y′∈Yarecalled-expansiveiffdY(y,y′)=dX(x,x′)forsomex∈f1(y),x′∈f1(y′).
Achainis-expansiveiffallstepsyi,yi+1are-expansive.
Finally,fisuniformly-sensitivewrtdX,dYiff:–forallx,x′∈X:dY(f(x),f(x′))≤dX(x,x′),and–forally,y′∈Y:thereexistsatightand-expansivechainfromytoy′.
Theintuitionbehindthisdenitionisthatfexpandsdistancesbyatmost,andtherearenoanswersthatarealwaystheresultsofasmallerexpansion:ally,y′∈Ycanbelinkedbyachaininwhichtheexpansionisexactly.
Underthiscondition,ithasbeenshownin[8]thattheprivacyofHcharacterizesthatofHf.
Theorem1([8]).
Assumethatfisuniformly-sensitivewrtdX,dY.
ThenHsatisesdY-privacyifandonlyifHfsatisesdX-privacy.
Intheremainingofthepaper,wegiveresultsaboutdY-privacyforH,foranar-bitrarymetricdY,independentlyfromanyfunctionf.
TheresultscanbeusedeithertotalkabouttheprivacyofHitself,or–giventheabovetheorem–abouttheprivacyofobliviousmechanismsoftheformHf,forsomefunctionfforwhichuniformsensitivitycanbeestablished.
AtypicalcaseofuniformsensitivityarisesinstandarddifferentialprivacywhendYisthemetricobtainedfromtheinducedgraphoff,asdiscussedinthenextsection.
Butuniformsensitivitycanbeestablishedforothertypesofmetrics;someexamplesaregivenin[8].
3.
2DifferentialprivacyThenotionofdifferentialprivacy,introducedbyDworkin[4],imposesconstraintsondatareportingmechanismssothattheoutputsproducedbytwodatabasesdifferingonlyforonerecordarealmostindistinguishable.
LetVbeauniverseofvaluesanduthenumberofindividuals.
Thesetofallpossibledatabases(u-tuplesofvaluesfromV)isV=Vu.
Twodatabasesx,x′∈Varecalledadjacent,writtenxx′,ifftheydifferinthevalueofexactlyoneindividual.
Theadjacencyrelationdenesagraph,andthelengthoftheshortestpathbetweentwodatabasesx,x′inthegraph,writtendh(x,x′),denesametriccalledtheHammingdistance.
Inotherwords,dh(x,x′)isthenumberofindividualsinwhichxandx′differ.
Thepropertyof-differentialprivacyrequiresthat,foranytwoadjacentdatabases,theratiooftheprobabilitiesofproducingacertainoutputisboundbye.
Itiseasytoseethatthispropertyisequivalenttodh-privacy,undertheHammingdistancedh.
Givenaqueryf:V→Y,theadjacencyrelationcanbeextendedtoY,givingrisetotheinducedgraphfoff[14,19],denedas:yfy′iffxx′forsomex∈f1(y),x′∈f1(y′)TitleSuppressedDuetoExcessiveLength7012nAcountqueryf1(x)=count(x,p)01234nQueryf2(x)=count(x,p)mod(n+1)(0,n)(1,n)(2,n)(n,n)(0,2)(1,2)(2,2)(n,2)(0,1)(1,1)(2,1)(n,1)(0,0)(1,0)(2,0)(n,0)A2-countqueryf3(x)=(count(x,p1),count(x,p2))Fig.
1.
TheinducedgraphofdifferentqueriesFigure1showstheinducedgraphofthreedifferentqueries.
Intheseexamplescount(x,p)referstoacountingquerywhichreturnsthenumberofrecordsinthedatabasexwhichsatisfyacertainpropertyp.
Otherqueriesinthegureareexpressedusingthecountfunction.
Furthermore,letdf(y,y′)bethemetriconYdenedastheshortestf-pathfromytoy′.
Ithasthenbeenshownin[8]thatanyfunctionfisuniformly1-sensitivewrtdh,df.
Asaconsequenceofthis,andofTheorem1,-differentialprivacyofanobliv-iousmechanismHfcanbecharacterizedbythedf-privacyprivacyofH.
Corollary1.
Foranyqueryf:V→Y,Hsatisesdf-privacyifandonlyifHfsatisesdh-privacy.
3.
3Geo-indistinguishabilityAnadvantageofthegeneralizeddenitionofprivacyisthatitcanbeappliedincaseswhenthereisasingleindividualinvolved–hencethenotionofadjacencyisinadequate–byusingametricthatgivesameaningfulnotionofprivacyfortheapplicationathand.
Anexampleofsuchanotionisgeo-indistinguishability[9],proposedasaformalnotionoflocationprivacyinthecontextofLocationBasedServices(LBSs).
Consideramobileuser,typicallyusingaGPS-enabledhand-helddevice,whowishestoobtaininformationrelatedtohiscurrentlocation,forinstancerestaurantsclosetohim.
Todoso,hecanqueryanLBSprovider,providinghisactuallocationxaspartofthequery.
However,locationinformationisnotonlyinherentlysensitiveitself,butalsocorrelatedtoavarietyofothersensitiveinformation,suchaspoliticalandreli-giousbeliefs,medicalinformation,etc.
Hence,theuserwouldliketoperformtheLBSqueryprivately,thatiswithoutdisclosinghisexactlocationtotheprovider.
Notethatprotectingtheuser'sidentityisnotthegoalhere;infact,theusermightwishtobeauthenticatedtotheserviceproviderinordertoobtainpersonalizedrecommendations.
Whatheisinterestedin,instead,ishidinghislocation.
Apossiblesolutionistousealocationobfuscationmechanism[20],producinganoisylocationzwhichisreportedtotheserviceprovider.
Anaturalgoalthenisto8EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessiformalizetheprivacyguaranteesprovidedbysuchamechanism,forwhichvariousapproacheshavebeenproposedintheliterature[21].
Geo-indistinguishabilityprovidessuchaformaldenitionoflocationprivacy,andcanbeexpressedasaninstanceofdX-privacy.
SecretsXarenowlocations(asubsetofR2),and-geo-indistinguishabilityisd2-privacy,whered2istheEuclideandistancebetweenlocations.
3Intuitively,dP(K(x),K(x′))≤d2(x,x′)requiresthatthecloser(geographically)twolocationsx,x′are,themorelikelytoproducethesamereportedlocationztheyshouldbe.
Thisallowstheprovidertogetsomeapproximateinforma-tionnecessarytoprovidetheservice(e.
g.
distinguishlocationsinParisfromthoseinLondon),butpreventshimfromlearningxwithhighaccuracy(sincelocationsx′closetoxproducethesamezwithsimilarprobabilities).
Theresultsofthispaperrefertoanarbitrarymetricbetweensecrets,hencetheyaredirectlyapplicabletogeo-indistinguishability.
Acase-studyinthecontextoflocationprivacyisgiveninSection6.
2.
3.
4UtilitymodelThemainroleofanoisemechanismH:Y→ZistoguaranteedY-privacywhilepro-vidingusefulinformationaboutthetruequeryresult,i.
e.
tosatisfyatrade-offbetweentheprivacyandutility.
ForquantifyingtheutilityofHwefollowastandardmodelfrom[13].
Lety∈Ybetheresultofexecutingaqueryf.
ThemechanismH:Y→Zpro-cessesyandproducesanoutputzinsomedomainZtotheuser.
Basedonthereportedoutputzandpriorknowledgeaboutthelikelyresultsoff,sheappliesaremappingfunctionR:Z→Ytoztoproduceaguessy′∈Yfortherealqueryresult.
NotethatthecompositemechanismRH:Y→YisamechanismwhoseoutputdomainisthequeryresultsdomainY.
WesaythatHisremappedtoRHbytheremapR.
Now,withtheuser'sguessedvaluey′,areal-valuedgainfunctiong:Y*Y→Rquantieshowinformativey′iscomparedtotherealqueryresulty.
Inthispaperwerestrictouranalysistothebinarygainfunctiongbwhichisdenedasgb(y,y′)=1iffy′=yand0otherwise.
Thechoiceofthisgaincorrespondstothepreferenceofausertoguessthetruequeryresult.
Inpractice,theuserusuallybasesherguessy′abouttherealqueryresultonpriorknowledgeabouttheunderlyingsecretandtheunderlyingquery.
Thisknowledgeismodeledbyaprobabilitydistributionπ(calledprior)overthedomainYofqueryresults.
NowtheutilityofamechanismH:Y→ZwithrespecttoapriorπandaremapR:Z→Yistheexpectedvalueoftheunderlyinggainfunctiongb,andisthereforeexpressedasU(H,π,R)=y,y′πy(HR)yy′gb(y,y′).
(2)Usingthedenitionofgb,theaboveexpressionreducestoaconvexcombinationofthediagonalelementsofHRasfollows.
U(H,π,R)=yπy(HR)yy.
(3)3Notethatanyothermeaningfulgeographicaldistancecouldalsobeused,suchastheManhat-tanoramap-baseddistance.
TitleSuppressedDuetoExcessiveLength9Accordingly,wesaythatadY-privatemechanismHisdY-optimalforapriorπifthereisaremapRsuchthatU(H,π,R)ismaximalforalldY-privatemechanismsandallremaps.
4Ingeneraltheoptimalityofamechanismdependsontheprior(relatedtotheuser).
Thatisamechanismthatisoptimalforapriormaynotbeoptimalforanotherone.
Inthesettingofdifferentialprivacy,ithasbeenproven[14]thatforanyquery,otherthanasinglecountingone,thereisnomechanismthatisoptimalforallpriorssimultaneously.
Nevertheless,weidentifyinSection3aregionofpriors,whereitispossibletondasinglemechanismwhichisoptimaltoallofthem.
3.
5Min-mutualinformationInthissectionwerecalltheuseofaninformation-theoreticnotion,namelymutualinformation,toquantifytheamountofinformationconveyedbyamechanismH:Y→Zasaninformationtheoreticchannel.
Followingrecentworksintheareaofquantitativeinformationow([15–17]),weadoptRényi'smin-entropy([22])asourmeasureofuncertainly.
Themin-entropyH∞(π)ofapriorπ,denedasH∞(π)=log2maxiπi,measurestheuser'suncertaintyaboutthequeryresult.
Then,thecorrespondingnotionofconditionalmin-entropy,de-nedasH∞(H,π)=log2z∈Zmaxyπyhyz,measurestheuncertaintyaboutthequeryresultafterobservinganoutputz∈Z.
Finally,subtractingthelatterfromtheformerbringsustothenotionofmin-mutualinformation:L(H,π)=H∞(π)H∞(H,π)whichmeasurestheamountofinformationaboutthequeryresultconveyedbythemechanismH.
Intheareaofquantitativeinformationowthisquantityisknownasmin-entropyleakage;thereaderisreferredto[15]formoredetailsaboutthisnotion.
4RegularpriorsInthissectionwedescribearegionofpriors,called'dY-regular'.
Thesepriorsarede-terminedbythemetricdYonthedomainY.
RecallthatthedY-privacyconstraintsforHcanbewrittenashyz/hy′z≥edY(y,y′)forally,y′∈Y.
SinceeverylowerboundedY(y,y′)dependsonlyony,y′,theconstraintscanbedescribedaltogetherbyasquarematrixΦformedbysuchlowerbounds.
Werefertothismatrixastheprivacy-constraintsmatrix.
Denition3(privacy-constraintsmatrix).
Theprivacy-constraintsmatrixΦofamet-ricdYisasquarematrix,indexedbyY*Y,whereφyy′=edY(y,y′)forally,y′∈Y.
NotethatΦissymmetric(φyy′=φy′y)duetothesymmetryofdY.
RecallthatdYdescribestheprivacyrestrictionsimposedonthedomainY.
Inparticulartheserestric-tionsbecomevacuousifdY(y,y′)→∞forally,y′:y=y′.
Inthisextremecasetheprivacy-constraintsmatrixΦconvergestotheidentitymatrixwhereeachdiagonal4Notethattheremayexistmanyoptimalmechanismsforagivenprior.
10EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessientryis1andallotherentriesare0.
WenowdenethedY-regularpriors,intermsoftheprivacy-constraintsmatrixofdY.
Foravectorhavingcardinality|Y|,weuse≥0todenotey:y≥0.
Denition4(dY-regularprior).
ApriorπiscalleddY-regulariffthereexistsarowvector≥0suchthatπ=Φ.
Inthefollowingwedescribethecommonpropertiesofthesepriorsandalsogiveageometriccharacterizationfortheirregioncomparingittothewholepriorspace.
Asarstobservation,thisregionconvergestotheentirepriorspacewhentheprivacyconstraintsonYbecomevacuous.
Thisisbecause,asdescribedabove,Φapproachestheidentitymatrixwherethevectorexistsforeachpriorπ(justdene=π).
AnimportantpropertyofanydY-regularprioristhattheratiobetweenanytwoofitsentriesπy,πy′isalwaysboundbyedY(y,y′).
Becauseofthisproperty,suchaprioriscalleddY-regular.
Proposition1.
ForeverydY-regularpriorπandforally,y′∈Ywehavethatπyπy′≤edY(y,y′).
Proof.
ByDenition4,theratioπy/πy′isgivenbyπyπy′=y′′y′′φy′′yy′′y′′φy′′y′.
(4)Bythedenitionsofφy′′y′,φy′′ywealsohavethatφy′′y′=edY(y′′,y′)≥e(dY(y′′,y)+dY(y,y′))=edY(y,y′)φy′′y.
Theaboveinequalityisimpliedbythetriangleinequality,dY(y′′,y′)≤dY(y′′,y)+dY(y,y′)andthefactthate10forally∈Y.
InthefollowingwedescribethesetofdY-regularpriorsasaregioninthepriorspace.
Fordoingso,werstdeneinthefollowingsetofpriorswhichwerefertoasthecornerpriors.
Denition5(cornerpriors).
Foreveryy∈Y,acorrespondingcornerprior,denotedbycy,isdenedascyy′=φyy′y′′∈Yφyy′′y′∈Y.
Notethattheabovedenitionissound,i.
e.
cyisaprobabilitydistributionforally∈Y.
Notealsothatthereare|Y|cornerpriors;eachonecorrespondstoanelementy∈Y.
Byinspectingtheentriesofcy,observethatcyyhasthemaximumvaluecomparedtootherentries,andmoreoverthisvalueisexactlytheupperboundspeciedbyProposition2.
Wecanthereforeinterpretthisobservationinformallyascyis'maximallybiased'toy.
ItcanbealsoseenthateachcornerpriorisdY-regular.
Infactforanycornercy,thereisarowvectorthatsatisestheconditioninDef.
4;thisvectorisobtainedbysettingy=1/y′∈Yφyy′andy′=0forally′=y.
Hereitiseasytoverifythatcy=Φ.
NowwecandescribetheregionofthedY-regularpriorsusingthecornerpriors.
Precisely,thisregionconsistsofallconvexcombinationsofthecornerpriors.
Proposition3(convexity).
ApriorπisdY-regulariffitisaconvexcombinationofthecornerpriors,i.
e.
thereexistrealnumbersγy≥0,y∈Ysuchthatπ=y∈Yγycyandy∈Yγy=1.
Proof.
ByDenition4,apriorπisdY-regulariffthereexistsvector≥0suchthatπ=Φ;thatisifftherearerealsy≥0forally∈Y,suchthatπcanbewrittenasalinearcombinationofΦ'srowsasfollows.
π=y∈YyΦy,whereΦyistherowofΦcorrespondingtotheelementy∈Y.
FromDef.
5,observethateachrowΦyisequaltoy′∈Yφyy′cy.
Bysubstitutionintheaboveequationforπ,wegetthatπisdY-regulariffπ=γyΦywhereγy=yy′∈Yφyy′.
Notethattheexistenceofthevector≥0isequivalenttotheexistenceofthecoefcientsγy≥0.
Observealsothaty∈Yγy=Φ=1.
Theseobservationscompletetheproof.
12EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessi(1,0,0)(0,1,0)(0,0,1)c1c2c3=0.
7=1.
6=∞Yconnectedinacir-cle(1,0,0)(0,1,0)(0,0,1)c1c2c3YconnectedinalineFig.
2.
RegionsofdY-regularpriorsforExample1FromProposition3theregionofdY-regularpriorsisaconvexset,whereeachpoint(prior)inthisregionisaconvexcombinationofthecornerpriors.
Thisregionisthere-foregeometricallyregardedasaconvexpolytopeinthepriorspace.
Sincethecornerpointsalwaysexists,thisregionisneverempty.
Forapriorπinthisregion,thecoef-cientsγymodelthe'proximity'ofπtoeachcornerpriorcy.
Inparticular,notethat0≤γy≤1,andγy=1iffπ=cy.
Wedemonstratethisgeometricinterpretationusingthefollowingexamples.
Example1.
ConsiderasimpledomainYconsistingof3elementsorganizedinagraphstructurewheredg(y,y′)isthegraphdistancebetweeny,y′.
Nowforanarbitraryscal-ingnumber>0,wecandenethemetricdYasdY(y,y′)=dg(y,y′).
Sinceev-eryprioronYhas3entries(specifyingtheprobabilityofeveryelementy∈Y),thepriorspaceforYcanberepresentedbythe3-dimensionalEuclideanspace.
Figure2visualizestheregionofdY-regularpriorsintwocases:whenthegraphstructureofYisaline,andwhenitisacircle.
Notethatinbothcases,wehave3cornerpriorsc1,c2,c3.
Ineachcase,theregionisdepictedfor=0.
7and=1.
6.
NoteinthisexamplethatcontrolstheprivacyconstraintsimposedbydY-privacy,whichinturndeterminethesizeoftheregionofdY-regularpriors.
Inparticularwith=1.
6(lessprivacy),theregionislargerthantheonewith=0.
7.
Ingeneraltheregionexpandsasincreasesandconvergestotheentireregionofpriorsdenedbythecornerpoints{(0,0,1),(0,1,0),(0,0,1)}when→∞.
Example2.
SupposethatYcontains4elements,anddYisdenedasdY(y,y′)=Dforally,y′:y=y′.
Inthiscaseeverypriorcontains4entriesandthereforeisnotpossibletobeplottedinthe3-dimensionalspace.
However,usingthefactthatthefourthcomponentisredundant(iπi=1),everypriorisfullydescribedbyits'projection'ontothe3-dimensionalsubspace.
Figure3showstheprojectionofthedY-regularpriorregionfordifferentvaluesofD.
AgaintheprivacyconstraintsenforcedbydY-privacyaredeterminedbyD.
ThelessrestrictedisD(i.
e.
havingahighervalue),thebiggertheregionis;andeventuallycoincideswiththeentirespacewhenD→∞.
TitleSuppressedDuetoExcessiveLength13(1,0,0)(0,1,0)(0,0,1)(.
7,.
1,.
1)(.
1,.
7,.
1)(.
1,.
1,.
7)(.
5,.
17,.
17)(.
17,.
5,.
17)(.
17,.
17,.
5)D=1D=2D=∞Fig.
3.
RegionsofdY-regularpriorsforExample25Upperboundsforutilityandmin-mutualinformationInthissection,wefurtherdescribethedY-regularpriorsonthedomainYintermsoftheutilitythatcanbeachievedforthesepriorsbyamechanismH:Y→ZsatisfyingdY-privacy.
WealsodescribetheamountofinformationthatcanbeconveyedbyHtouserswithsuchpriors.
Moreprecisely,weidentifyforanydY-regularpriorπupperboundsfortheutilityandmin-mutualinformation,consideringalldY-privatemechanismsandallpossibleremaps.
TheseboundsareindeedinducedbytheprivacyconstraintsdenedbythemetricdY.
5.
1UtilityForagivendomainYequippedwiththemetricdY,consideradY-privatemechanismH:Y→ZproducingobservablesinsomedomainZ.
InthefollowinganalysiswederivealinearalgebraicexpressionforU(H,π,R),theutilityofHforapriorπusingtheremapR:Z→Y.
Suchanexpressionwillplaythemainroleinthesubsequentresults.
WestartbyobservingthatthematrixproductofHandtheremapRdescribesandY-privatemechanismHR:Y→Y.
ThereforetheentriesofHRsatisfythefollowingsubsetofconstraints.
edY(y,y′)(HR)y′y′≤(HR)yy′forally,y′∈Y.
UsingDenition3oftheprivacy-constraintsmatrixΦ,andtakingintoaccountthaty′∈Y(HR)yy′=1forally(asbothHandRarestochastic),wegetthefollowinginequalities.
y′∈Yφyy′(HR)y′y′≤1,y∈Y.
Theinequalityoperatorscanbereplacedbyequalitieswhileintroducingslackvariablessy:0≤sy≤1forally∈Y.
Theaboveinequalitiescanthereforebewrittenasfollows.
y′∈Yφyy′(HR)y′y′+sy=1,y∈Y.
14EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessiLettheslackvariablessyformacolumnvectorsindexedbyY.
Letalso1denoteacolumnvectorofthesamesizeandhavingallentriesequalto1.
Usingthesevectorsandtheprivacy-constraintsmatrixΦ(forthegivenmetricdY),theaboveequationscanberewritteninthefollowingmatrixform.
Φdiag(HR)+s=1,(5)wherediag(HR)isthecolumnvectorconsistingofthediagonalentriesofHR.
Now,foranymechanismH:Y→ZandaremapR:Z→YsatisfyingEq.
(4),andforapriorπ,wewanttorenethegenericexpression(3)oftheutilitybytakingEq.
(4)intoaccount.
WestartbyrewritingEq.
(3)inthefollowingmatrixform.
U(H,π,R)=πdiag(HR).
(6)Now,letbearowvectorsuchthatπ=Φ.
(7)Notethat,theabovematrixequationisinfactasystemof|Y|linearequations.
TheythequationinthissystemisformedbytheythcolumnofΦ,andtheythentryofπasfollows.
Φy=πyy∈Y.
Solvingthissystemofequationsfortherowvectorhasthefollowingpossibleout-comes:IfthematrixΦisinvertible,then,foranypriorπ,Eq.
(6)hasexactlyonesolution.
IfΦisnotinvertible(i.
e.
itcontainslinearlydependentcolumns),thenthereareeither0oraninnitenumberofsolutions,dependingonthepriorπ:Iftheentriesofπrespectthelineardependencerelationthenthereareinnitelymanysolutions.
Otherwise,theequationsare'inconsistent',inwhichcasetherearenosolutions.
WhetherΦisinvertibleornot,weconsiderhereonlythepriorswherethematrixequation(6)hasatleastonesolution.
Notethat,bydenition,allthedY-regularpriorshavethisproperty,buttherecanbeothersforwhichthesolutionhassomenegativecomponents.
Insomeoftheresultsbelow(inparticularinLemma1)weconsiderthislargerclassofpriorsforthesakeofgenerality.
MultiplyingEquation(4)byyieldsΦdiag(HR)+s=1.
(8)SubstitutingEquations(6)and(5)intheaboveequationconsecutivelyprovidestherequiredexpressionfortheutilityandthereforeprovesthefollowinglemma.
Lemma1.
Forametricspace(Y,dY)letπbeanyprioronY.
Thenforeveryrowvectorsatisfyingπ=Φ,theutilityofanydY-privatemechanismHforπusingaremapRisgivenbyU(H,π,R)=1s,(9)foravectorssatisfying0≤sy≤1forally∈Y.
TitleSuppressedDuetoExcessiveLength15Lemma1expressestheutilityfunctionforanydY-privatemechanismH,forapriorπsatisfyingπ=Φ,andusingaremapR.
Thisutilityisexpressedasafunctionofthevectorandtheslackvectors.
AlthoughthematrixHandtheremapRdonotexplicitlyappearontherightsideofEquation(8),theutilitystilldependsonthemindirectlythroughthevectors.
Namely,accordingtoEquation(4),thechoiceofHandRdeterminestheslackvectors.
Theutilityfunctiondependsalsoonthepriorπ,becausethechoiceofπdeterminesthesetofvectorssatisfyingEq.
(6).
SubstitutinganyofthesevectorsinEq.
(8)yieldsthesamevalueforU(H,π,R).
NowrecallfromDenition4thatforeverydY-regularpriorπthereissatisfyingπ=Φand≥0.
ThischaracteristictogetherwithLemma1impliesanupperboundontheutilityofanydY-privatemechanismHforπ.
Theorem2(utilityupperbound).
LetπbeadY-regularpriorandH:Y→ZbeadY-privatemechanism.
Thenforallrowvectors≥0satisfyingΦ=π,andanyremapR,itholdsthatU(H,π,R)≤y∈Yy.
(10)FurthermorethemechanismHandremapRsatisfytheequalityin(9)foreverydY-regularprioriffΦdiag(HR)=1.
Proof.
SinceπisdY-regular,wehaveπ=Φforavector≥0.
ApplyingLemma1andnotingthatsy≥0forally∈Y,weobservethats≥0andhencetheutilityisupper-boundedby1=y∈Yy.
ItremainstoshowthatthisboundisattainedforeverydY-regularpriorifandonlyifΦdiag(HR)=1,whichisequivalent(accordingtoEq.
(4))tos=0:Clearly,ifs=0,thenapplyingLemma1yieldstheequalityin(9)foreverydY-regularprior.
Forthe'onlyif'direction,itissufcienttondaregularpriorforwhichs=0mustholdtosatisfytheequalityin(9).
ForthispurposewerecallthateverycornerpriorcysatisesyΦ=cywhereyy>0.
Nowconsiderthepriorπ=(1/|Y|)y∈Ycy,whichisdY-regularbyProposition3.
ItiseasytoseethatitholdsΦ=πwhere=(1/|Y|)y∈Yy.
Observeherethaty>0forally∈Y.
Supposenowthattheequalityin(9)holdsfor.
Thereforeitmusthold,byLemma1,thats=0.
Sincey>0forally∈Y,itmustholdthats=0.
Thiscompletestheproof.
Theaboveresultcanbealsoseenfromthegeometricperspective.
AsshownbyPropo-sition3,eachmemberintheregionofdY-regularpriorsisdescribedasaconvexcombinationofthecornerpriors.
Thatistherearecoefcientsγy≥0fory∈Ywhichformthiscombination.
Itcanbeshown(asintheproofofProposition3)thatγy=yy′∈Yφyy′.
Hence,theupperboundgivenbyTheorem2canbewrittenasfollowsusingthecoefcientsγy.
U(H,π,R)≤y∈Yγyy′∈Yφyy′.
Inspectingtheaboveresultforcornerpriors,recallthatforacornercy,γy′is1fory′=yandis0otherwise;thus,theutilityupperboundforcyistherefore1/y′φyy′.
Moreover,theupperboundforeachdY-regularpriorπcanberegarded(accordingto16EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessitheaboveequation)asaconvexcombinationoftheupperboundsforthecornerpriors.
Thatis,fromthegeometricperspective,theutilityupperboundforπlinearlydependsonitsproximitytothecornerpriors.
5.
2Min-mutualinformationInthispaperweusetheinformation-theoreticnotionofmin-mutualinformationintwodistinctways:rst,weuseittomeasuretheinformationconveyedabouttheresultofaspecicquery,similarlytotheuseof"utility"intheprevioussection.
Mutualinformationandutilityareindeedcloselyrelated,whichallowsustotransfertheboundobtainedintheprevioussectiontotheinformation-theoreticsetting.
Second,weuseittoquantifytheinformationaboutthesecretitself,thusobtainingwhatisknownintheareaofquantitativeinformationowasmin-entropyleakage[15].
Theaboveboundcanthereforebeinterpretedasaboundontheinformationleakedbyanymechanism,evennon-obliviousones,independentlyfromtheactualquery.
Forarbitrarypriors,weobtaininamorenaturalwaytheboundconjecturedin[17]andprovenin[19].
Moreover,ifwerestricttospecic(dY-regular)priors,thenweareabletoprovidemoreaccuratebounds.
Thefollowingresultfrom[19]showsthatmin-mutualinformationcorrespondstothenotionofutilityunderthebinarygainfunctionandusinganoptimalremap,i.
e.
,aremapthatgivesthebestutilityamongallpossibleremaps,forthegivenprior.
Proposition4([19]).
GivenamechanismH:Y→Zandapriorπ,letRbeanoptimalremapforπ,H.
Then,wehaveL(H,π)=log2U(H,π,R)maxyπyThisconnectionallowsustotransfertheupper-boundgivenbyTheorem2tomin-mutualinformation.
Proposition5(min-mutualinformationupperbound).
LetπbeadY-regularpriorandH:Y→ZbeadY-privatemechanism.
Thenforallrowvectors≥0satisfyingΦ=π,wehave:L(H,π)≤log2y∈Yymaxyπy.
(11)Furthermore,HsatisestheequalityforeverydY-regularprioriffthereisaremapRsuchthatΦdiag(HR)=1.
Proof.
ByProposition4,theleakageL(H,π)ismonotonicallyincreasingwiththeutil-ityU(H,π,R).
ByTheorem2,thisutilityisupper-boundedbyy∈Yy.
SubstitutingthisupperboundinProposition4yieldstheinequality(10)wheretheequalityholdsiffitholdsinTheorem2forHandandanoptimalremapR.
ThatisiffΦdiag(HR)=1.
ThisconditionisequivalenttotheconditionofequalityinProposition5,becauseifaremapRsatisesthislatterconditionthenitmustbeoptimalbecausetheutilitywithR(byTheorem2)isgloballymaximum,thatisnootherremapcanachievehigherutility.
TitleSuppressedDuetoExcessiveLength17TheaboveboundholdsonlyfordY-regularpriors.
However,itiswell-known([16])thatmin-mutualinformationismaximizedbytheuniformprioru,i.
e.
L(H,π)≤L(H,u)forallH,π.
Thus,incaseswhenuisdY-regular,wecanextendtheaboveboundtoanyprior.
Corollary2.
SupposethattheuniformprioruisdY-regular,andletH:Y→ZbeanydY-privatemechanism.
Thenforallrowvectors≥0satisfyingΦ=u,andforallpriorsπ,wehavethatL(H,π)≤log2(|Y|y∈Yy)5.
3QuantifyingtheleakageaboutthedatabaseIntheprevioussectionweconsideredtheinformationaboutthequeryresultthatisrevealedbyamechanismH.
Thisinformationwasmeasuredbythemin-mutualinfor-mationL(H,π).
Wenowturnourattentiontothecaseofstandarddifferentialprivacy,withthegoalofquantifyingtheinformationaboutthedatabasethatisconveyedbyadifferentiallyprivatemechanismK(notnecessarilyoblivious).
Intuitively,wewishtominimizethisinformationtoprotecttheprivacyoftheusers,contrarytotheutilitywhichweaimatmaximizing.
WecanapplytheresultsoftheprevioussectionbyconsideringthefullmechanismK,mappingdatabasesV=Vutooutputs(recallthatuisthenumberofindividualsinthedatabaseandVtheuniverseofvalues).
Differentialprivacycorre-spondstodh-privacy,wheredhistheHammingdistanceonthedomainVofdatabases.
Correspondinglydh-regularitywillconcernpriorsπondatabasesV.
Inthiscase,L(K,π)measurestheinformationaboutthedatabaseconveyedbythemechanism,whichwerefertoas"min-entropyleakage",andtheboundsfromtheprevioussectioncanbedirectlyapplied.
However,sincewenowworkonaspecicmetricspace(V,dh),wecanobtainaclosedexpressionfortheboundofCorollary2.
Westartbyobservingthatduetothesymmetryofthegraph,theuniformprioruisdh-regularforall>0.
Moreprecisely,wecanshowthatthevectorofsizeVhavingallelementsequaltoe|V|(|V|1+e)usatisesΦ=uand≥0.
Thus,applyingCorollary2wegetthefollowingresult.
Theorem3(min-entropyleakageupperbound).
LetV=Vubeasetofdatabases,let>0,andletKbean-differentiallyprivatemechanism.
ThenforallpriorsπonV,wehave:L(K,π)≤ulog2|V|e|V|1+eThisbounddeterminesthemaximumamountofinformationthatany-differentiallyprivacymechanismcanleakaboutthedatabase(independentlyfromtheunderlyingquery).
Theboundwasrstconjecturedin[17]andindependentlyprovenin[19];ourtechniquegivesanalternativeandarguablymoreintuitiveproofofthisresult.
18EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessi11.
522.
533.
544.
550.
50.
60.
70.
80.
91Leakagebound(bits)BoundforallpriorsBoundforπFig.
4.
LeakageboundsforvariousvaluesofNotethattheaboveboundholdsforallpriors.
Ifwerestricttoaspecicdh-regularpriorπ,thenwecangetbetterresultsbyusingtheboundofProposition5whichdependsontheactualprior.
Thisisdemonstratedinthefollowingexample.
Example3.
Consideradatabaseof5individuals,eachhavingoneof4possiblevalues,i.
e.
V=VuwithV={1,2,3,4}andu=5.
Assumethateachindividualselectsavalueindependentlyfromtheothers,butnotallvaluesareequallyprobable;inpartic-ulartheprobabilitiesofvalues1,2,3,4are0.
3,0.
27,0.
23,0.
2respectively.
LetπbethecorrespondingprioronVthatmodelsthisinformation.
Wehavenumericallyver-iedthatforall0.
48≤≤1(withstep0.
01)πisdh-regular.
ThuswecanapplyProposition5togetanupperboundofL(K,π)forthisprior.
Theresultingbound,togetherwiththegeneralboundforallpriorsfromTheorem3,areshowninFigure4.
Weseethatrestrictingtoaspecicpriorprovidesasignicantlybetterboundforallvaluesof.
Forinstance,for=0.
5wegetthatL(K,π)≤1.
2forthisπ,whileL(K,π)≤2.
5forallpriorsπ.
6Tight-constraintsmechanismsIngeneral,theboundsfortheutility(Theorem2)andthemin-mutualinformation(Proposition5)arenottight.
ThatisforagivenmetricdYonadomainY,theremaybenodY-privatemechanismHthatmeetsthesebounds.
Nevertheless,theypro-videultimatelimits,inducedbythedY-privacyconstraints,foralldY-privatemech-anismsanddY-regularpriors.
TheseboundsaresimultaneouslytightiftheconditionΦdiag(HR)=1issatised(notethatthisconditionisindependentoftheunderlyingprior).
Inthissectionweexploitthis'tightness'conditionandinvestigatethemecha-nismsthat,wheneverexist,satisfythisconditionandarethereforeoptimalfortheentireregionofdY-regularpriors.
Wecallthesemechanismstight-constraintsmechanisms.
Denition6(Atight-constraintsmechanism).
ForametricdY,amechanismH:Y→Yiscalledatight-constraintsmechanismiffitsatisesthefollowingconditionsforally,y′∈Y.
edY(y,y′)hy′y′=hyy′.
(12)TitleSuppressedDuetoExcessiveLength19Itisimportanttonotethat,ingeneral,theremayexistzero,oneormoretight-constraintsmechanismsforagivenmetricdY.
Theabovedenitionenforces|Y|(|Y|1)linearlyindependentequations,referredtoasthe'tightconstraints'.
Additionallyitmustalsoholdthaty′∈Yhyy′=1forally∈Y.
Thuswehave,intotal,|Y||Y|equations.
Iftheseequationsarelinearlyindependent,thentheysolvetouniquevalues.
Iftheseval-uesarenon-negative,thentheydetermineauniquetight-constraintsmechanism.
Ontheotherhand,iftheseequationsarenotlinearlyindependent,thentheremaybemultiplesolutionswithnon-negativeentries,inwhichcasewehavemultipletight-constraintsmechanismsfordY.
6.
1PropertiesTherstfeaturethatfollowsimmediatelyfromthedenitionoftight-constraintsmech-anisms,forametricdY,isthattheysatisfydY-privacy:Proposition6(dY-privacy).
ForagivenmetricdY,everytight-constraintsmechanismisdY-private.
Proof.
Foratight-constraintsmechanismH,wewanttoshowthatforeverypairofqueryresultsy,y′andeveryoutputz,wehavehyz≤edY(y,y′)·hy′z.
(13)ByDenition6,foreverypairofelementsy,y′andeveryoutputz,wehavehy′z=edY(y′,z)·hzzandhyz=edY(y,z)·hzz.
(14)Ifhzz=0thenhy′z=hyz=0.
Inthiscase,Condition(14)issatised.
Otherwise(i.
e.
ifhzz=0),bothhy′zandhyzarenon-zero,anditfollowsfromEquations(15)that,forallinputsyandy′,andeveryoutputz,hy′zhyz=e(dY(y′,z)dY(y,z)).
Bythetriangleinequality,wehavethatdY(y′,z)dY(y,z)≤dY(y,y′).
Knowingalsothate1edY(y,y′)hy′y′.
Theny′∈Yhyy′>y′∈YedY(y,y′)hy′y′=1,wherethelastequalityholdsbyEq.
().
Thatis,thesumoftheentriesofarowinHisstrictlygreaterthan1whichviolatesthevalidityofH.
Theabovepropositionprovidesawaytochecktheexistenceof,andalsocompute,thetight-constraintsmechanismsforagivenmetricdY.
SinceCondition(12)issatisedonlybythesemechanisms,thereisatleastonetight-constraintsmechanismifthereisavectorz,withnon-negativeentries,thatsatisestheequationΦz=1.
Inthiscaseatight-constraintsmechanismisobtainedbysettingitsdiagonaltoz,andevaluatingthenon-diagonalentriesfromthediagonalusingEqs.
(11).
NowweturnourattentiontotheregionofdY-regularpriorsandidentifythemech-anismsthatareoptimalwithrespecttobothutilityandmin-mutualinformationinthisregion.
Precisely,weshowthatthesetoftheseoptimalmechanismconsistsexactlyofallmechanismsthatcanbemappedtoatight-constraintsoneusingsomeremapR.
Theorem4(Optimality).
LetdYbeametricforwhichatleastonetight-constraintsmechanismexists.
ThenadY-privatemechanismH:Y→ZisdY-optimal(wrtbothutilityandmin-mutualinformation)foreverydY-regularpriorπiffthereisaremapR:Z→YsuchthatHRisatight-constraintsmechanismfordY.
Proof.
Ifthereexistsatight-constraintsmechanismH′foragivenmetricdY,thenH′mustsatisfyEq.
(12).
Thisimpliesthattheupper-boundinTheorem2isreachablebyH′andtheidentityremap.
Thustheupper-bound,inthiscase,istight.
NowconsideradY-privatemechanismH:Y→Z.
ByTheorem2,Hmeetsthatupperboundfortheutility(andthereforeisdY-optimal)iffitsatisestheconditionΦdiag(HR)=1,withsomeremapR.
SinceHisdY-private,HRisalsodY-private.
NowbyProposition7,satisfyingtheconditionΦdiag(HR)=1(meaningthatHisoptimal)isequivalenttothatHRisatight-constraintsmechanism(fordY).
Usingtherelation,givenbyPropo-sition4,betweenutilityandmin-mutualinformation,thesameargumentholdsforthelatter.
Observethattight-constraintsmechanismsareoptimalbecausetheyaremappedtothemselvesbytheidentityremap.
InthelightofTheorem4,weconsiderthespecialcaseoftheuniformprior,denotedbyu,whereallresultsinYareequallylikely.
Notethatthispriorcorrespondstousershavingunbiasedknowledgeaboutthequeryresults,TitleSuppressedDuetoExcessiveLength21i.
e.
theyassumethatallthetrueresultsYareyielded,byexecutingthequery,withthesameprobability.
Firstly,thefollowinglemmaprovesanequivalencebetweentheexistenceofatleastonetight-constraintsmechanismononehandandtheuniformpriorubeingdY-regularontheotherhand.
Proposition8.
ForagivenmetricdY,thereexistsatleastonetight-constraintsmech-anismifftheuniformprioruisdY-regular.
Proof.
ByProposition7,ifthereisatleastatight-constraintsmechanismH,thenEq.
(12)mustholdforthismechanism.
Takingthetransposeofbothsidesinthisequation,andnotingthatΦt=Φ(becauseΦissymmetric),thenwegetthat(diag(H))t·Φ=1t.
Scalingtheaboveequationby1/|Y|yieldstherowvectoru,theuniformprior,ontherighthandside.
Thusifatight-constraintsmechanismH,existsthen(1/|Y|)(diag(H))t·Φ=u.
whichmeans(ByDef.
4)thatuisdY-regular,becausetherowvector(diag(H))thasonlynon-negativeentries.
Fortheoppositeimplication,assumethatuisdY-regular.
Thenbythedenitionthereisarowvectorwithnon-negativeentriessuchthatΦ=u.
Takingthetransposeofbothsides,andmultiplyingby|Y|,yieldsthatEq.
(12)issatisedforH,whosediagonalisgivenbydiag(H)=|Y|·t(non-negative).
Thusthereexistsatight-constraintsmechanismfordY.
ItisworthnoticingthatingeneraltheregionofdY-regularpriorsmayormaynotincludetheuniformprior.
However,asshownearlierinSection3,thisregionisenlargedandconvergestotheentirepriorspaceasthedistancesdY(y,y′)→∞forally=y′.
InparticularthedY-regularpriorsaccommodatetheuniformprioruifdYisscaledupbyanappropriatefactor.
Inthecaseof-differentialprivacyitholdsthatdY=dhwheredhistheHammingdistanceondatabases.
Thusthereisalwaysathreshold,abovewhichtheuniformprioruisdh-regular.
Thiscanprovideadesigncriteriatoselectasettingforsuchthat,accordingtoProposition8,thereisatight-constraintsmechanismthatisoptimalforalldh-regularpriors.
UsingProposition8,wecandescribetheoptimalmechanismsfortheuniformpriorasacorollaryofTheorem4.
Corollary3.
LetdYbeametricforwhichthereexistsatleastonetight-constraintsmechanism.
ThenamechanismHisdY-optimalfortheuniformprioronYiffHRisatight-constraintsmechanismforsomeremapR:Z→Y.
Insummary,theexistenceoftight-constraintsmechanismsandtheirstructuresde-pendonthegivenmetric.
Thechoiceofsuchmetriccorrespondstotherequiredpri-vacyguarantee.
Considerinparticulartheconventional-differentialprivacy,whereanytwoadjacentelementsinadomainYarerequiredtobeindistinguishablerelativeto.
Inthiscase,thedomainYanditsadjacencyrelationfaremodeledbythegraph22EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessiG=(Y,f);andtherequirementofsatisfying-differentialprivacyforYtranslatesinourgeneralmodeltothemetricdY(y,y′)=df(y,y′),wheredf(y,y′)isthegraphdistancebetweeny,y′.
Withthismetric,wendthattight-constraintsmechanismscap-tureotherknowndifferentially-privatemechanisms.
Forexample,ifwesetYtobetheoutputdomainofacountingqueryexecutedonadatabase,wendthatthetight-constraintsmechanismforYisexactlythetruncated-geometricmechanism,whichwasshownby[13]tobeoptimalforeveryprior.
Also,weinstantiate,inthefollowing,thetight-constraintsmechanismwhenthemetricspace(Y,dY)satisesacertainsymme-try.
Thissymmetrycaptures,inparticular,thegraphsforwhichanoptimalmechanismisconstructedin[19]fortheuniformprioru.
Onceagainthismechanismispreciselyatight-constraintsone.
NotethatanadditionalconclusionwhichweaddhereisthatthismechanismisoptimalnotonlyforubutalsoforalldY-regularpriors.
6.
2Tight-constraintsmechanismforsymmetricmetricspacesWeconsiderthemechanismsthatsatisfydY-privacyforagivendomainY.
Wefocushereonthemetricspaces(Y,dY)thatsatisfyacertainsymmetrywhichwecallball-sizesymmetry.
Todescribethisproperty,werecallthestandardnotionofballsinmetricspaces:aballofradiusraroundapointy∈YisthesetBdYr(y)={y′∈Y:dY(y,y′)≤r}.
Nowwedenetheball-sizesymmetryasfollows.
Denition7(ball-sizesymmetry).
Ametricspace(Y,dY)issaidtobeball-sizesym-metricifforally,y′∈Y,andallradiir,wehave|BdYr(y)|=|BdYr(y′)|.
Notethattheaboveconditionisequivalenttosayingthatforanyy∈Y,thenumberofelementsthatareatdistancerfromydependsonlyonr,allowingustowritethisnumberasnr.
Inspectingtheprivacy-constraintsmatrixΦinthiscase,weobservethattherowsumy′φyy′foreveryy∈Yisthesameandequaltornrer.
Thismeansthatthecolumnvectorz,ofwhicheveryelementisequalto1/rnrer,satisesΦz=1andthereforeyields(byProposition7)thediagonalofatight-constraintsmechanismH.
Theother(non-diagonal)entriesofHfollowfromthediagonalasinDenition6.
Thusweconcludethefollowingresult.
Proposition9(tight-constraintsmechanismforsymmetricmetricspaces).
Foranymetricspace(Y,dY)satisfyingball-sizesymmetrythereisatight-constraintsmecha-nismH:Y→Ywhichisgivenashyy′=edY(y,y′)rnrer.
ThemainconsequenceoftheabovepropositionisthatthemechanismHisoptimalforeverydY-regularpriorincludingtheuniformprioru.
Theaboveresultgeneralizesandextendsaresultby[19]inthecontextofdifferen-tialprivacy.
Theauthorsof[19]consideredtwotypesofgraphs:distance-regularandvertex-transitivegraphs.
Theyconstructedforthesegraphsan-differentiallyprivatemechanismoptimalfortheuniformprior.
Asshownearlier-differentialprivacyforagraph(Y,f)translatesinoursettingtothemetricspace(Y,df).
Itcanbeeas-ilyseenthatif(Y,f)iseitherdistance-regularorvertex-transitive,thecorrespond-ingmetricspace(Y,df)isball-sizesymmetric.
Therefore,wecaninstantiatethetight-constraintsmechanismofProposition9todf,whichgivesexactlytheoptimalTitleSuppressedDuetoExcessiveLength2301234vu(a)Sumquery(0,u)(1,u)(2,u)(u,u)(0,2)(1,2)(2,2)(u,2)(0,1)(1,1)(2,1)(u,1)(0,0)(1,0)(2,0)(u,0)(b)2-countqueryFig.
5.
Adjacencygraphsmechanismconstructedin[19].
Hence,wedirectlyobtainthesameoptimalityresults,andmoreoverouranalysisshowsthatthismechanismisoptimalontheentireregionofdf-regularpriors,insteadofonlytheuniformone.
7Case-studiesInthissectionweshowtheusefulnessofthetight-constraintsmechanismbyapplyingittotwocontexts:standarddifferentialprivacyandgeo-indistinguishability.
7.
1Differentialprivacy:sumand2-countqueriesWeevaluatethetightconstraintsmechanismfortwofamiliesofqueries,namelysumand2-countqueries.
Foreachfamily,weapplythemechanismondatabasesconsistingofuindividualseachhavinganintegervaluebetween0andv,andwecompareitsutilitytothegeometricmechanism.
Itiswell-knownthatnouniversallyoptimalmechanismexistsforthesefamilies;inparticular,thegeometricmechanism,knowntobeoptimalforasinglecountingquery,isnotguaranteedtobeoptimalforsumqueriesormultiplecountingqueries.
Ontheotherhand,asdiscussedintheprevioussection,tight-constraintsmechanisms,whenevertheyexist,areguaranteedtobeoptimalwithintheregionofregularpriors.
Thecomparisonismadeasfollows:foreachquery,wenumericallycomputethesmallest(usingastepof0.
01)forwhichatight-constraintsmechanismexists(i.
e.
forwhichtheuniformprioruisdf-regular,seeProposition8).
Thenwecomputetheutility(usinganoptimalremap)ofboththetightconstraintsandthegeometricmech-anisms,forarangeofstartingfromtheminimumone.
Notethatthetightconstraintmechanismexistsforanygreaterthantheminimumone.
SumqueryLetfbethequeryreturningthesumofthevaluesforallindividuals,thusithasrangeY={0,vu}.
Bymodifyingthevalueofasingleindividual,theoutcomeofthequerycanbealteredbyatmostv(whenchangingthevaluefrom0tov),thustwoelementsi,j∈Yareadjacentiff|ij|≤v.
TheinducedgraphstructureonYisshowninFigure5(a)(forthecasev=3).
24EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessi0.
080.
10.
120.
140.
160.
180.
20.
220.
80.
911.
11.
21.
3UtilityTight-constraintsGeometric(a)Sumquery0.
060.
080.
10.
120.
140.
160.
180.
20.
220.
911.
11.
21.
3UtilityTight-constraintsGeometric(b)2-countqueryFig.
6.
UtilityforvariousvaluesofForourcase-studywenumericallyevaluatethisqueryforu=150,v=5andfortheuniformprior.
Wefoundthattheminimumforwhichatight-constraintsmecha-nismexists(andisinfactuniquesinceΦisinvertible)is0.
8.
Figure6(a)showstheutilityofthetight-constraintmechanism,aswellasthatofthegeometricmechanism,forvaluesofbetween0.
8and1.
3,theuniformpriorandusingandoptimalremap.
Weseethatthetight-constraintsmechanismprovidessignicantlyhigherutilitythanthegeometricmechanisminthiscase.
2-countqueryConsidernowthequeryfconsistingof2countingqueries(i.
e.
reportingthenumberofuserssatisfyingpropertiesp1andp2),thusithasrangeY={0,u}*{0,u}.
Bymodifyingthevalueofasingleindividual,theoutcomeofeachcountingquerycanbealteredbyatmost1,thustwoanswers(i1,i2),(j1,j2)∈Yareadjacentiff|i1j1|≤1and|i2j2|≤1.
TheinducedgraphstructureonYisshowninFigure5(b).
Weevaluatethisqueryforu=30andfortheuniformprior.
Wefoundthattheminimumforwhichatight-constraintsmechanismexistsis0.
9.
Figure6(b)showstheutilityofthetwomechanisms(withthegeometricbeingappliedindependentlytoeachcountingquery)forvaluesofbetween0.
9and1.
3andtheuniformprior.
Similarlytothesumquery,weseethatthetight-constraintsmechanismprovidessignicantlyhigherutilitythanthegeometricmechanisminthiscase.
7.
2Geo-indistinguishabilityAsdiscussedinSection2.
3,geo-indistinguishabilityisanotionoflocationprivacyobtainedbytakingdX=d2,whered2istheEuclideandistancebetweenlocations.
In[9]itisshownthataplanarversionoftheLaplacemechanismsatises-geo-indistinguishability.
ThePlanarLaplacemechanismiscontinuous,havingasinputandoutputthefullR2,butinthecaseofanitenumberoflocationsitcanbediscretizedandtruncatedwhilestillsatisfyinggeo-indistinguishability(foraslightlyadjusted).
AlthoughthePlanarLaplacemechanismissimple,efcientandeasytoimplement,itprovidesnooptimalityguarantees.
Ontheotherhand,foranynitenumberofloca-TitleSuppressedDuetoExcessiveLength2500.
050.
10.
150.
20.
250.
40.
60.
811.
2UtilityTight-constraintsPlannarLaplaceFig.
7.
Utilityoflocationprivacymechanismsforvariousvaluesoftions,thetight-constraintsmechanism,ifitexists,isguaranteedtobeoptimalford2-regularpriors.
Inthissectionwecomparethetwomechanismsonagridof100*100locations,withstepsize1km.
Notethatconstructingthetight-constraintsmechanisminvolvesinvertingthematrixΦ,whichcanbedoneintimeO(|X|2.
376)usingtheCoppersmith-Winogradalgorithm.
Thiscomplexityismuchlowerthanthatofrecentmethodsforcomputingoptimalloca-tionobfuscationmechanisms.
Forinstance,thewell-knownmethodofShokrietal.
[23]–whichusestheadversary'sexpectederrorasthemetricofprivacy–involvessolvinglargelinearoptimizationproblemsandwasevaluatedtoagridofonly30locations(comparedtothe10,000locationsinourgrid).
Figure7showstheutilityofthetwomechanismsforrangingfrom0.
4to1.
3andforauniformprior.
Asexpected,thetight-constraintsmechanismofferssignicantlyhigherutilitythanthePlanarLaplacemechanismforthesame.
Itshouldbeemphasized,however,thatouroptimalityresultsholdforthebinarygainfunction,whichcorrespondstoanattackertryingtoguessthetruelocationoftheuser(theutilitybeingtheprobabilityofacorrectguess).
Thismightoftenbemeaning-ful,especiallywhenthegridsizeisbig:guessinganyincorrectcellcouldbeconsideredequallybad.
Butitisalsocommontoconsidergainfunctionstakingthedistancebe-tweenlocationsintoaccount,withrespecttowhichthetight-constraintsmechanismisnotguaranteedtobeoptimal.
8ConclusionandfutureworkInthispaperwehavecontinuedthelineofresearchinitiatedby[13,14]abouttheex-istenceofdifferentially-privatemechanismsthatareuniversallyoptimal,i.
e.
,optimalforallpriors.
Whilethepositiveresultof[13](forcountingqueries)andthenegativeoneof[14](foressentiallyallotherqueries)answerthequestioncompletely,thelattersetsaratherdissatisfactoryscenario,sincecountingqueriesareaveryspecickindofqueries,andingeneraluserscanbeinterestedinverydifferentqueries.
Wehavethenconsideredthequestionwhetherwecanachieveoptimalitywiththesamemechanismforarestrictedclassofpriors.
Fortunatelytheanswerispositive:wehaveidentiedaregionofpriors,calleddY-regular,andamechanism,calledtight-constraints,whichis26EhabElSalamouny,KonstantinosChatzikokolakis,andCatusciaPalamidessioptimalforallthepriorsinthisregion.
Wehavealsoprovidedacompleteandeffec-tivelycheckablecharacterizationoftheconditionsunderwhichsuchmechanismexists,andaneffectivemethodtoconstructit.
Asasideresult,wehaveimprovedontheexist-ingboundsforthemin-entropyleakageinducedbydifferentialprivacy.
Moreprecisely,wehavebeenabletogivespecicandtightboundsforeachdY-regularprior,ingeneralsmallerthantheboundexistingintheliteraturefortheworst-caseleakage(achievedbytheuniformprior[18]).
Sofarwehavebeenstudyingonlythecaseofutilityforbinarygainfunctions.
Inthefutureweaimatliftingthislimitation,i.
e.
wewouldliketoconsideralsootherkindsofgain.
Furthermore,weintendtostudyhowtheutilitydecreaseswhenweuseatight-constraintsmechanismoutsidetheclassofdY-regularpriors.
Inparticular,weaimatidentifyingaclassofpriors,largerthanthedY-regularones,forwhichthetight-constraintsmechanismisclosetobeoptimal.
References1.
Sabelfeld,A.
,Myers,A.
C.
:Language-basedinformation-owsecurity.
IEEEJournalonSelectedAreasinCommunications21(1)(2003)5–192.
Chatzikokolakis,K.
,Palamidessi,C.
,Panangaden,P.
:Anonymityprotocolsasnoisychan-nels.
Inf.
andComp.
206(2–4)(2008)378–4013.
Dwork,C.
:Armfoundationforprivatedataanalysis.
CommunicationsoftheACM54(1)(2011)86–964.
Dwork,C.
:Differentialprivacy.
In:Proc.
ofICALP.
Volume4052ofLNCS.
,Springer(2006)1–125.
Dwork,C.
,Mcsherry,F.
,Nissim,K.
,Smith,A.
:Calibratingnoisetosensitivityinprivatedataanalysis.
In:Proc.
ofTCC.
Volume3876ofLNCS.
,Springer(2006)265–2846.
Narayanan,A.
,Shmatikov,V.
:Robustde-anonymizationoflargesparsedatasets.
In:Proc.
ofS&P.
(2008)111–1257.
Narayanan,A.
,Shmatikov,V.
:De-anonymizingsocialnetworks.
In:Proc.
ofS&P,IEEE(2009)173–1878.
Chatzikokolakis,K.
,Andrés,M.
E.
,Bordenabe,N.
E.
,Palamidessi,C.
:BroadeningthescopeofDifferentialPrivacyusingmetrics.
In:Proc.
ofPETS.
Volume7981ofLNCS.
,Springer(2013)82–1029.
Andrés,M.
E.
,Bordenabe,N.
E.
,Chatzikokolakis,K.
,Palamidessi,C.
:Geo-indistinguishability:differentialprivacyforlocation-basedsystems.
In:Proc.
ofCCS,ACM(2013)901–91410.
Gaboardi,M.
,Haeberlen,A.
,Hsu,J.
,Narayan,A.
R.
,Pierce,B.
C.
:Lineardependenttypesfordifferentialprivacy.
In:ProceedingsofPOPL2013.
Toappear.
11.
Barthe,G.
,Olmedo,F.
:Beyonddifferentialprivacy:Compositiontheoremsandrelationallogicforf-divergencesbetweenprobabilisticprograms.
In:Automata,Languages,andPro-gramming-40thInt.
Colloquium,ICALP2013,Riga,Latvia,July8-12,2013,Proceedings,PartII.
Volume7966ofLNCS.
,Springer(2013)49–6012.
Barthe,G.
,Kpf,B.
,Olmedo,F.
,Béguelin,S.
Z.
:Probabilisticrelationalreasoningfordif-ferentialprivacy.
ACMTrans.
Program.
Lang.
Syst35(3)(2013)913.
Ghosh,A.
,Roughgarden,T.
,Sundararajan,M.
:Universallyutility-maximizingprivacymechanisms.
In:Proc.
ofSTOC,ACM(2009)351–36014.
Brenner,H.
,Nissim,K.
:Impossibilityofdifferentiallyprivateuniversallyoptimalmecha-nisms.
In:Proc.
ofFOCS,IEEE(2010)71–80TitleSuppressedDuetoExcessiveLength2715.
Smith,G.
:Onthefoundationsofquantitativeinformationow.
In:Proc.
ofFOSSACS.
Volume5504ofLNCS.
,Springer(2009)288–30216.
Braun,C.
,Chatzikokolakis,K.
,Palamidessi,C.
:Quantitativenotionsofleakageforone-tryattacks.
In:Proc.
ofMFPS.
Volume249ofENTCS.
,Elsevier(2009)75–9117.
Barthe,G.
,Kpf,B.
:Information-theoreticboundsfordifferentiallyprivatemechanisms.
In:Proc.
ofCSF,IEEE(2011)191–20418.
Alvim,M.
S.
,Andrés,M.
E.
,Chatzikokolakis,K.
,Degano,P.
,Palamidessi,C.
:DifferentialPrivacy:onthetrade-offbetweenUtilityandInformationLeakage.
In:Postproceedingsofthe8thInt.
WorshoponFormalAspectsinSecurityandTrust(FAST).
Volume7140ofLNCS.
,Springer(2011)39–5419.
Alvim,M.
S.
,Andrés,M.
E.
,Chatzikokolakis,K.
,Palamidessi,C.
:OntherelationbetweenDifferentialPrivacyandQuantitativeInformationFlow.
In:Proc.
ofICALP.
Volume6756ofLNCS.
,Springer(2011)60–7620.
Ardagna,C.
A.
,Cremonini,M.
,Damiani,E.
,diVimercati,S.
D.
C.
,Samarati,P.
:Locationprivacyprotectionthroughobfuscation-basedtechniques.
In:Proc.
ofDAS.
Volume4602ofLNCS.
,Springer(2007)47–6021.
Shokri,R.
,Theodorakopoulos,G.
,Boudec,J.
Y.
L.
,Hubaux,J.
P.
:Quantifyinglocationpri-vacy.
In:Proc.
ofS&P,IEEE(2011)247–26222.
Rényi,A.
:OnMeasuresofEntropyandInformation.
In:Proceedingsofthe4thBerkeleySymposiumonMathematics,Statistics,andProbability.
(1961)547–56123.
Shokri,R.
,Theodorakopoulos,G.
,Troncoso,C.
,Hubaux,J.
P.
,Boudec,J.
Y.
L.
:Protectinglocationprivacy:optimalstrategyagainstlocalizationattacks.
In:Proc.
ofCCS,ACM(2012)617–62724.
Kifer,D.
,Lin,B.
R.
:Towardsanaxiomatizationofstatisticalprivacyandutility.
In:Proc.
ofPODS,ACM(2010)147–15825.
Kifer,D.
,Lin,B.
R.
:Anaxiomaticviewofstatisticalprivacyandutility.
JournalofPrivacyandCondentiality4(1)(2012)5–49