Vi introducerar koncentrerad differential integritet, en avkoppling av differential integritet åtnjuter bättre noggrannhet än både ren differential integritet och dess populära "(ε, δ)" avkoppling utan att kompromissa på kumulativ integritet förlust över flera beräkningar. I den grundläggande lagen om informationsåtervinning anges informellt att "mycket korrekta" uppskattningar av "för många" statistik helt förstör integriteten ([DN03] et sequelae). Differentiell integritet är en matematiskt strikt definition av integritet skräddarsydd för analys av stora datamängder och utrustad med ett formellt mått på integritet förlust [DMNS06, Dwo06]. Dessutom tar olika privata algoritmer som indata en parameter, vanligtvis kallad ε, som täcker den tillåtna integritetsförlusten i varje utförande av algoritmen och erbjuder en konkret integritet / användbarhet kompromiss. En av de starka sidorna av differential integritet är förmågan att resonera om kumulativ integritet förlust över flera analyser, med tanke på de värden för ε som används i varje enskild analys. Genom lämpligt val av ε är det möjligt att hålla sig inom ramen för grundlagen samtidigt släppa ett visst antal uppskattad statistik, men innan detta arbete var gränserna inte snäva. Ungefär, differential integritet säkerställer att resultatet av en analys på en databas x distribueras mycket på samma sätt som resultatet på varje angränsande databas y som skiljer sig från x i bara en rad (Definition 2.3). Det vill säga, differentialt privata algoritmer är randomiserade, och i synnerhet den maximala skillnaden mellan dessa två fördelningar (en sort maximal log odds ratio för alla händelser, se definition 2.2 nedan) begränsas av sekretessparametern ε. Denna absoluta garanti på maximal integritet förlust kallas nu ibland "ren" differential integritet. En populär avkoppling, (ε, ε)-differentiell integritet (Definition 2.4) [DKM + 06], garanterar att med sannolikhet högst 1 − δ integritetsförlusten inte överstiger ε. 1 Vanligtvis δ anses vara "kryptografiskt" liten, det vill säga mindre än inversen av någon polynom i storleken på datasetet, och ren differential integritet är helt enkelt det speciella fall där δ = 0. Avkopplingen tillåter ofta asymptotiskt bättre noggrannhet än ren differential integritet för samma värde av ε, även när δ är mycket liten. Vad händer i fallet med flera analyser? Även om sammansättningen av k (ε, 0)-differentiellt integritetsalgoritmer är som värst (kε, 0)-differentiellt privat, är den också samtidigt ( 2k ln(1/ε)ε+ kε(e ε − 1), δ)-differentiellt privat för varje δ [DRV10]. Låt oss dekonstruera uttalandet om detta resultat. För det första är integritetsförlust en slumpmässig variabel som fångar upp skillnader i sannolikhetsfördelningar som erhålls när en randomiserad algoritm M körs på x i motsats till angränsande databas y (se avsnitt 2.1). I allmänhet, om den maximala skillnaden mellan två fördelningar begränsas av ε 1 Observera att sannolikheten är över mynten i den algoritm som utför analysen. Ovanstående formulering är inte omedelbar från definitionen av (ε, ε)-differentiell integritet, detta bevisades i den fullständiga versionen av [DRV10]. 1 sedan deras KL-divergens (Definition 2.1) begränsas av ε(e ε − 1). Detta innebär att den förväntade integritetsförlusten för en enskild (ε, 0)-differentierad privat beräkning begränsas av ε(e ε − 1). Genom linjäritet i förväntan begränsas den förväntade förlusten över k (ε, 0)-differentiellt privata algoritmer av kε(e ε − 1). Påståendet säger därför att den kumulativa integritetsförlusten slumpmässiga variabeln över k beräkningar är starkt koncentrerad om dess medelvärde: sannolikheten för integritetsförlust som överstiger dess förväntningar genom t ε kε faller exponentiellt i t 2 /2 för alla t ≥ 0. Vi kommer att återkomma till denna formulering för närvarande. Mer allmänt visar vi följande avancerade sammansättning teorem, som förbättrar sammansättningen teorem av Dwork, Rothblum, och Vadhan [DRV10] genom att exakt halvera gränsen för förväntad integritet förlust av (ε, 0)-differentiellt integritetsmekanismer (beviset är annars identisk). Närmare uppgifter om den skarpare gränsen finns i avsnitt 3.2. Teorin 1.1. För alla ε, ε, ε′ ≥ 0, uppfyller klassen (ε, ε′)-differentiellt privata mekanismer (2k ln(1/δ)ε + kε(e ε − 1)/2, kδ ′ + δ)-differentiell integritet under k-faldig adaptiv sammansättning. Som theorem visar (återkalla att δ ′ vanligtvis anses vara "sub-polynomiellt liten"), de rena och avslappnade former av differential integritet beter sig ganska på samma sätt under sammansättning. För den mycket viktiga klassen att räkna frågor ("Hur många människor i datauppsättningen uppfyller egenskapen P?") Teorem 1.1 leder till noggrannhetsgränser som skiljer sig från de gränser som införs av (en omedelbar ändring av) grundlagen av en faktor på ungefär 2 log(1/δ). 2 Nyligen, snäva gränser för sammansättningen av (ε, δ)-differentiellt privata algoritmer har getts i [KOV15, MV16] (se nedan). En ny avkoppling. I detta arbete introducerar vi en annan avkoppling, Koncentrerad differentiell integritet (CDP), ojämförlig med (ε, δ)-differentiell integritet men återigen har samma beteende under sammansättning. Koncentrerad differential integritet är närmare "varje δ" egenskap i uttalandet av Theorem 1.1: En algoritm erbjuder (μ, τ)-koncentrerad differential integritet om integritetsförlust slumpmässiga variabeln har medel μ och om, efter att ha subtraherat av detta medelvärde, den resulterande (centrerad) slumpmässig variabeln är subgaussian med standard τ. 3 Till följd av detta (se t.ex., [BK00] Lemma 1.3), x > 0: Således säkerställer koncentrerad differential integritet att den förväntade integritetsförlusten är μ och sannolikheten för förlust som överstiger dess medelvärde med x = tτ begränsas av e −t 2/2, ekar formen av den garanti som erbjuds av Advanced Composition Theorem (Theorem 1.1). Tänk på i vilket fall τ = ε. Å ena sidan är (μ, ε)-koncentrerad differentiell integritet klart svagare än (ε, ε)-differentiell integritet, eftersom även om den förväntade förlusten μ är mycket liten, sannolikheten för integritetsförlust som överstiger ε i den förra kan vara konstant i den förra men är bara δ, som är liten, i den senare. Å andra sidan, i (ε, ε)-differentiell integritet finns det ingen bunden på den förväntade integritetsförlusten, eftersom med sannolikhet alla satsningar är avstängda och förlusten kan vara oändlig. Koncentrerad differentiell integritet har två fördelar jämfört med (ε, ε)-differentiell integritet.  • Förbättrad noggrannhet. Koncentrerad differential integritet är skräddarsydd för (realistiska!) fallet med ett stort antal beräkningar. Traditionellt sett, för att säkerställa liten kumulativ förlust med hög sannolikhet, är den tillåtna förlusten för varje enskild fråga satt mycket låg, säger ε ′ = ε (log 1/δ) / k, även om en integritetsförlust av, låt oss säga, ε/10 eller ens ε sig själv kanske inte är av stor betydelse för någon enskild fråga. Detta är just den flexibilitet som vi ger i den koncentrerade differentiella integriteten: mycket mindre oro för förlust av en enda fordran, men med stor sannolikhet gräns för kumulativ förlust. Sammansättningen av k (μ, τ )-koncentrerade differential integritetsmekanismer är (kμ, ε kτ )-koncentrerad differential integritet (Theorem 3.4). Ställa in τ = ε får vi en förväntad integritetsförlust av kμ och, för alla t samtidigt, sannolikheten för integritetsförlust som överstiger dess espektation av t ε kε faller exponentiellt i t 2 / 2, precis som vi fick i sammansättningen för de andra varianterna av differential integritet i Theorem 1.1 ovan. Men vi får bättre exakthet. Till exempel, för att hantera n räkna frågor med hjälp av Gaussian mekanismen, kan vi lägga till oberoende slumpmässigt buller från N (0, n/ε 2 ) till varje fråga, uppnå (ε(e ε − 1)/2, ε)-koncentrerad differential integritet (Theorem 3.2) 4. När ε =  och 1) buller skalas till O ( ε n); enligt grundlagen är buller o ( ε n) katastrofalt. • Gruppintegritetsgruppens integritet begränsar integritetsförlusten även för ett par databaser som skiljer sig åt i data från en liten grupp av individer; till exempel kan man i en hälsoundersökning inte bara vilja veta att ens egen hälsoinformation förblir privat utan också att informationen om ens familj som helhet är starkt skyddad. Varje (ε, 0)-differentiellt privat algoritm säkerställer automatiskt (sε, 0)-differentiell integritet för alla grupper av storlek s [DMNS06], med den förväntade integritetsförlusten växer med en faktor på omkring s 2. Situationen för (ε, ε)-differentiell integritet är inte riktigt så elegant: litteraturen visar (sε, se-1 δ)-differentiell integritet för grupper av storlek s, en oroande exponentiell ökning av sannolikheten för misslyckande (se-1 δ term). Situationen för koncentrerad differential integritet är mycket bättre: för alla kända naturliga mekanismer med koncentrerad differential integritet får vi snäva gränser. För (hypotetiska) godtyckliga algoritmer som erbjuder subgaussian integritet förlust, visar Theorem 4.1 gränser som är asymptotiskt nästan-tät (tät upp till låg-order termer). Vi misstänker att de snäva gränserna bör hålla för godtyckliga mekanismer, och det skulle vara intressant att överbrygga klyftan. 1. Vad är det för fel på dig? Under vissa villkor, nöjda med alla rena differential integritetsmekanismer 5, och tillägg av Gaussian buller, alla (μ, τ )-koncentrerad differential integritet mekanism uppfyller (s 2 ·μ, s·τ )-koncentrerad differential integritet för grupper av storlek s, vilket är optimalt. 2. Utgångspunkten är följande: Varje ( (1))-koncentrerad differential integritet för grupper av storlek s. Den bundna håller så länge s · τ är tillräckligt liten (ungefär, (1/τ ) bör förbli kvasi-linjär i s). Se Theorem 4.1 för det formella uttalandet. Vi antar också här att μ ≤ τ 2 2. 6 Anmärkning 1.2. Överväga varje mekanism som byggs genom att komponera en samling av "goda" mekanismer som var och en uppfyller villkoren i punkt 1 ovan. För att bevisa att den sammansatta mekanismen har de bra gruppintegritetsgränserna kan vi först tillämpa gruppintegritetsgränserna för de underliggande "bra" mekanismerna, och sedan tillämpa sammansättningen. Det är intressant att dessa två operationer pendlar. 4 För att uppnå (ε, ε)-differentiell integritet lägger man till buller från N (0, 2 ln(1/δ)), vilket ökar den typiska snedvridningen med en faktor av ln(1/δ). 5 Varje (ε, 0)-differentiellt privat mekanism avkastning (ε(e ε −1)/2, ε)-koncentrerad differentiell integritet (Theorem 3.5). 6 Upp till låg-order villkor, denna relation innehar för alla mekanismer vi känner. För andra mekanismer är det möjligt att härleda en mindre elegant allmän bundet, eller τ kan "artificiellt uppblåst" tills detta villkor håller. Täta gränser på förväntade förluster. Som nämnts ovan förbättrar vi med en faktor av två den kända övre gränsen för förväntad integritetsförlust av någon (ε, 0)-differentiellt privat mekanism, vilket avslutar ett gap som öppnats sedan 2010 [DRV10]. Detta översätts omedelbart till en förbättring med en faktor på 2 på nytta / privacy kompromiss i någon tillämpning av Advanced Composition Theorem. Den nya gränsen, som är tight, erhålls genom att först bevisa resultatet för speciella par av probablit fördelningar som vi kallar antipodal (privacy förlust för alla resultat är i {−ε, 0, ε}), och sedan visar en minskning, där ett godtyckligt par distributioner med maximal divergens begränsas av ε -såsom fördelningen på resultaten av en differentialt privat mekanism när körs på databaser x och y skiljer sig i en enda rad - kan "ersätts" av en antipodal par utan ändring i max divergens och ingen minskning i KL-divergens. Anmärkning 1.3. Om alla (ε, 0)-differentiellt privata algoritmer åtnjuter koncentrerad differential integritet, liksom Gaussian-mekanismen, vilka (ε, ε)-differentiellt privata algoritmer utesluts? Alla (ε, ε)-differentiellt privata algoritmer där det finns en viss sannolikhet δ ′ ≤ δ för oändlig integritet förlust. Detta inkluderar många (men inte alla!) algoritmer i ramverket "Propose-Test-Release" [DL09], där ett differentialt privat test först utförs för att kontrollera att datauppsättningen uppfyller vissa "säkerhetsvillkor" och i så fall utförs en operation som endast garanterar integritet om villkoren är uppfyllda. Det kan finnas en liten sannolikhet för misslyckande i det första steget, vilket innebär att testrapporterna om att säkerhetsvillkoren är uppfyllda, men i själva verket inte, i vilket fall integritet kan äventyras i det andra steget. Hårdhet. Optimalitet i integritetsförlust är en överskuggande subtil och svår fråga under sammansättning. Resultat av Kairouz, Oh och Viswanath [KOV15] få snäva gränser under sammansättningen av godtyckliga (en, en)-mekaniker, när alla mekanismer delar samma värden av  till och en. Det är, de finner den optimala  till ′, δ ′ sådan att sammansättningen av k mekanismer, som var och en är ( till 0, δ 0 )-differentiellt privat, är ( till ′, δ ′ )-differentiellt privat. Det icke-homogena fallet, där ith-mekanismen är i, i )-differentiellt privat, har analyserats av Murtagh och Vadhan [MV16], där det visas att bestämma gränserna för den optimala sammansättningen är svårt för #P. Båda dessa papper använder en analys liknande den som finns i vår Lemma 3.8, som vi fick innan publiceringen av dessa verk. Optimala gränser för sammansättningen av godtyckliga mekanismer är mycket intressanta, men vi är också intresserade av gränser för de specifika mekanismer som vi har i handen och vill använda och analysera. I detta syfte får vi en fullständig karakterisering av integritetsförlusten av Gaussian mekanismen. Vi visar att integritet förlust av sammansättningen av flera tillämpning av Gaussian mekanismen, eventuellt med olika individuella parametrar, är sig en Gaussian slumpmässig variabel, och vi ger exakta gränser för dess medelvärde och varians. Denna karakterisering är inte möjlig med hjälp av ramen för (en, en)-differentiell integritet, den tidigare rådande synen på den Gaussiska mekanismen. Efterföljande arbete. Motiverad av vårt arbete, Bun och Steinke [BS15] föreslår en avslappning av koncentrerad differential integritet. Istället för att sätta in integritetsförlusten som en subgaussisk slumpmässig variabel som vi gör här, de istället rama in frågan i termer av Renyi entropy, få en avslappning av koncentrerad differential integritet som också stöder en liknande komposition teorem. Deras begrepp ger också integritetsgarantier för grupper. Gränserna vi får med hjälp av koncentrerad 4 differential integritet (Theorem 4.1) är hårdare; vi vet inte om detta är inneboende i definitionerna. Avvikelse. Vi kommer att behöva flera olika begrepp om skillnader mellan distributionerna. Vi kommer också att införa ett nytt begrepp, subgaussisk skillnad i avsnitt 3. Definition 2.1 (KL-divergens). KL-divergensen, eller relativ entropi, mellan två slumpmässiga variablerna Y och Z definieras som: där om stödet för Y inte är lika med stödet för Z, då D KL (Y  för Z) inte definieras. Definition 2.2 (största avvikelse). Max Divergensen mellan två slumpvariabler Y och Z definieras som: där om stödet för Y inte är lika med stödet för Z, då D ∞ (Y  och Z) inte definieras. Den ungefärliga skillnaden mellan Y och Z definieras som: För en given databas d, en (randomized) icke-interaktiv databasåtkomstmekanism M beräknar en utgång M (x) som senare kan användas för att rekonstruera information om d. Vi kommer att ägna oss åt mekanismer M som är privata enligt olika sekretessbegrepp som beskrivs nedan. Vi tänker på en databas x som en multiuppsättning av rader, var och en från ett datauniversum U. Intuitivt innehåller varje rad uppgifter om en enskild individ. Vi kommer ofta att visa en databas av storlek n som en tuple x  på U n för några n  på N (antalet individer vars data finns i databasen). Vi behandlar n som offentlig information hela tiden. Vi säger databaser x, y är intilliggande om de bara skiljer sig i en rad, vilket innebär att vi kan få en från den andra genom att ta bort en rad och lägga till en annan. Det vill säga. databaser är intilliggande om de är av samma storlek och deras redigeringsavstånd är 1. För att hantera värsta fall par av databaser, våra sannolikheter kommer att vara över de slumpmässiga val som görs av integritetsmekanismen.  där sannolikheterna är över algoritm M mynt. Eller alternativt: En randomiserad algoritm M ger (ε, δ)-differentiell integritet om för alla par av angränsande databaser x och y och alla S  på Range(M) där sannolikheterna är över myntflips av algoritmen M. Eller alternativt: Privacy Loss som en slumpmässig variabel. Överväg att köra en algoritm M på ett par databaser x, y. För ett resultat o är integritetsförlusten på o den log-ratio av dess sannolikhet när M körs på varje databas: Koncentrerad differential integritet delar mer djupt in i integritetsförlusten slumpmässig variabel: denna real-värderade slumpmässig variabel mäter integritetsförlusten som följer när algoritm M körs på x (i motsats till y). Det provtas genom att ta y  på M (x) och ta ut L (o) (M (x) och M (y). Denna slumpmässiga variabel kan ta positiva eller negativa värden. För (ε, 0)-differentiellt privata algoritmer begränsas dess storlek alltid av ε. För (ε, ε)-differentiellt privata algoritmer, med all sannolikhet är magnituden begränsad av ε. Subgaussiska slumpmässiga variabler infördes av Kahane [Kah60]. En subgaussisk slumpmässig variabel är en för vilken det finns ett positivt reellt tal τ > 0 s.t. momentgeneratorfunktionen är alltid mindre än momentgeneratorfunktionen hos en Gaussian med standardavvikelsen τ och förväntan 0. I detta avsnitt går vi kort igenom definitionen och grundläggande lemmata ur litteraturen.  Vi säger att X är subgaussian om det finns τ ≥ 0 s.t. X är τ - subgaussian. För en subgaussisk slumpmässig variabel X är den subgaussiska standarden X: Anmärkningar. En omedelbar konsekvens av definition 2.5 är att en τ - subgaussisk slumpmässig variabel har förväntningar 0, och variansen begränsas av τ 2 (se fakta 2.1). Observera också att den gaussianska fördelningen med förväntan 0 och standardavvikelsen σ är σ-subgaussian. Det finns också kända gränser för de högre ögonblicken av subgaussiska slumpmässiga variabler (se fakta 2.2). Se [BK00] och [Riv12] för vidare diskussion. Lemma 2.1 (subgaussisk koncentration). Om X är τ - subgaussian för τ > 0, då: Bevis. För varje λ > 0 och t > 0: där den första jämlikheten uppnås genom att en exponentiell av alla argument, den andra (i)jämlikhet är av Markov, och detta är genom egenskaperna hos subgaussiska slumpmässiga variabeln X. Höger sida minimeras när λ = t/τ, och därmed får vi det: Beviset att Pr[X ≤ −t · τ ] ≤ e −t 2 /2 är liknande.  För alla τ - subgaussian random variabel Y, och heltal k, k-th ögonblick begränsas av: Lemma 2.2 (summan av subgaussians). Låt X 1,. ., X k vara (gemensamt fördelade) real-värderade slumpvariabler sådan att för varje i K, och för varje (x 1,. .., x i-1) Supp(X 1,........................................................................................... .., X k-1 ), det håller att den slumpmässiga variabeln ( Bevis. Beviset är genom induktion över k. Basfallet k = 1 är omedelbart. För k > 1, för alla λ  på R, har vi: där den sista ojämlikheten är genom induktionshypotesen. Följande tekniska Lemma om produkter av (gemensamt fördelade) slumpvariabler, av vilka en är exponentiell i en subgaussian, kommer att användas i stor utsträckning för att bevisa gruppintegritet: 7 Lemma 2.3 (Förväntad produkt med Exponential i Subgaussian). Låt X och Y fördelas gemensamt slumpvariabler, där Y är τ - Subgaussian för τ ≤ 1/3. Sedan: Bevis. Tar Taylor expansion av e Y vi har: Av Cauchy-Schwartz ojämlikhet: där den sista ojämlikheten använder det faktum att för en τ -subgaussian RV Y, Var (Y ) ≤ τ 2 (Fact 2.1), och att för att binda den sista summan i Ojämlikhet 2, vi använder linjäritet av förväntan och Cauchy-Schwartz: Använda det faktum att för alla τ -subgaussian distribution Y, det 2k-et moment E [Y 2k ] begränsas av 2), Vi drar slutsatsen från det ovan att för τ < 1: Att sätta ihop ojämlikheter (2) (3), (4), drar vi slutsatsen att för τ ≤ 1/2: där nästa till sista ojämlikhet innehar när τ ≤ 1/3, och den sista ojämlikheten beror på 3 Koncentrerad Olika sekretess: Definition och egenskaper Om stöden för Y och Z inte är lika, då integritetsförlust slumpmässiga variabeln inte definieras. Vi studerar integritetsförlusten slumpmässig variabel, med fokus på fallet där denna slumpmässiga variabel är tätt koncentrerad kring sin förväntan. I synnerhet kommer vi att vara intresserade av det fall där integritetsförlusten (förändrad av dess förväntningar) är subgaussian. ) definieras och subgaussian, och dess subgaussian parameter är som mest τ. Om vi har både D subG (Y  på Z) (μ, τ ) och D subG (Z på Y ) (μ, τ ), då säger vi att paret slumpmässiga variabler X och Y är (μ, τ )-subgaussian-oskiljbara.  Bevis. Följer av definition 3.3 och koncentrationsegenskaperna hos subgaussiska slumpvariabler (Lemma 2.1). Guassian Mechanism återuppväcktes. Vi ser över Gaussian buller mekanism [DMNS06], vilket ger en snäv karakterisering av integritet förlust slumpmässig variabel. Därefter Gaussian mekanism med brus magnitud σ är (τ 2 /2, τ )-CDP, där τ =  och (f )/σ. Senare kommer vi att bevisa (Theorem 3.5) att varje ren differentierad privat mekanism också åtnjuter koncentrerad differentiell integritet. Den Gaussiska mekanismen är annorlunda, eftersom den endast garanterar (ε, ε)-differentierad integritet för δ > 0. av Theorem 3.2. Låt M vara Gaussian mekanism med buller magnitud σ. Låt d, d ′ vara angränsande databaser, och anta w.l.o.g att f (d) = f (d ′ ) +  tillf. Vi undersöker integritetsförlust slumpmässiga variabel som erhållits genom att dra en brus magnitud x  på N (0, σ 2 ) och utdata: Eftersom x  på N (0, σ 2 ), drar vi slutsatsen att fördelningen av integritetsförlust slumpmässiga variabeln L (U  och V ) är också Gaussian, med förväntan 2 / 2, och standardavvikelsen. Att ta τ =  skaf /σ, Som noterats i inledningen, är det en följd av Theorem 3.2 att vi kan uppnå (ε(e ε − 1)/2, ε)-koncentrerad differentiell integritet genom att lägga till oberoende slumpmässiga buller dras från N (0, n/ε 2 ) till varje fråga. Om vi ytterligare koppla av till (ε, ε)-cdp, kan vi lägga till ännu mindre buller, magnitud ( 1/ε). Detta skulle vara meningsfullt i miljöer där vi förväntar oss ytterligare sammansättning, och så att vi kan fokusera på den förväntade integritetsförlusten (begränsa den med ε) och tillåta mer slapphet i standardavvikelsen. För små ε ger detta ytterligare en storleksordningsförbättring av den snedvridning som införts för att skydda privatlivet. Slutligen observerar vi att gränserna för grupp koncentrerad differential integritet Gaussian mekanismen följer omedelbart från Theorem 3.2, notera att för en grupp av storlek s gruppen känslighet för en funktion f är som mest s · f. Samband 3.3 (grupp CDP för Gaussian Mechanism). Den Gaussiska mekanismen med buller magnitud σ uppfyller ((s)f /σ) 2 /2, s tillf )-koncentrerad differential integritet. Koncentrerad differential integritet komponerar "samt" standard differential integritet. En av CDP:s främsta fördelar är att det möjliggör större noggrannhet och mindre buller, vilket i huvudsak inte innebär någon förlust av privatlivet under sammansättningen. I detta avsnitt bevisar vi dessa kompositionsegenskaper. Vi följer formaliseringen i [DRV10] i modellering sammansättning. Sammansättning omfattar både upprepad användning av (olika) CDP-algoritmer på samma databas, vilket möjliggör moduluppbyggnad av CDP-algoritmer, och upprepad användning av (olika) CDP-algoritmer på olika databaser som kan innehålla information om samma individ. I båda dessa scenarier kan förbättrad noggrannhet hos CDP algoritmer ge större nytta för samma "privacy budget". Sammansättning av k CDP mekanismer (över samma databas, eller olika databaser) formaliseras av en sekvens av par slumpmässiga variabler (U, V ) = ((U (1), V (1) ),. .., (U (k), V (k) ) ). De slumpmässiga variablerna är resultaten av kontradiktoriskt och adaptivt valda CDP mekanismer M 1,. .., M k. I U-sekvensen (verklighet) provtas den slumpmässiga variabeln U (i) genom att köra mekanismen M i på en databas (enligt motståndarens val) som innehåller en individs, säger Bobs, data. I V-sekvensen (alternativ verklighet) provtas den slumpmässiga variabeln V (i) med hjälp av körmekanism M i på samma databas, men där Bobs data ersätts med (motsvarariskt valda) data som tillhör en annan individ, Alice. Kravet är att även för adaptivt och kontradiktoriskt valda mekanismer och databas-par, resultatet av U (Bob-reality) och V (Alice-reality) är "mycket nära", och i synnerhet integritetsförlusten L (U  och V ) är subgaussian. I mer detalj, och följande [DRV10], definierar vi ett spel där en återförsäljare vänder ett rättvist mynt att välja mellan symboler U och V, och en motståndare adaptivt väljer en sekvens av par av intilliggande databaser (x U i, x V i ) och en mekanism M i njuta (μ i, τ i )-CDP och som kommer att fungera på antingen vänster element (om dealern valde U ) eller rätt element (om dealern valde V ) av paret, och returnera utdata, för 1 ≤ i ≤ k. Motståndarens val är helt adaptiva och därför kan bero inte bara på godtycklig extern kunskap men också på vad som har observerats i steg 1,.., i − 1. Målet för motståndaren är att maximera integritetsförlusten. Det är inramat som ett spel eftersom stor integritet förlust är förknippad med en ökad förmåga att avgöra vilken av (U, V ) valdes av dealern, och vi föreställer oss att detta är motivation av motståndaren. Teorem 3.4 (Sammanställning av CDP). För varje heltal k  på N, varje μ 1,. .., μ k, τ 1........................................................... .., τ k ≥ 0, och konstruerad som i det spel som beskrivs ovan, Vi har att Betrakta de slumpmässiga variabler U och V definieras ovan, och integritet förlust slumpmässig variabel L (U  på V ). Denna slumpmässiga variabel erhålls genom att plocka y  på U och mata ut ln Mekanismen och datauppsättningar som valts av motståndaren i steg jag beror på motståndarens syn på den tiden. Motståndarens uppfattning omfattar dess slumpmässighet och de resultat som den hittills har observerat. Låta R U och R V betecknar slumpmässigheten i U -världen respektive V - världen, vi har, för alla y = (y 1,. .., y k ) Supp (U) och slumpmässiga sträng r c i (r, y 1,. ......................................................... Nu för varje prefix (r, y 1,. .., y i-1) vi villkor på R U = r, U 1 = y 1,. .., U i‐1 = y i‐1, och analysera den slumpmässiga variabeln c i (R U, U 1,. .., U i ) = c i (r, y 1,. ..,...................................................... När prefixet är fast, nästa par av databaser x U i och x V i och mekanismen M i utdata av advesary bestäms också. Således är U i distribueras enligt M i (x U i ) och för alla värde y i, Vi har är (μ i, τ i ) subgaussian. Genom subgaussiska egenskaper hos de slumpmässiga variablerna C i = c i (r, U (1),. .., U (i) ), har vi att L (U) (U) = i) [k] C i, d.v.s. Den slumpmässiga integritetsförlustvariabeln motsvarar summan av C i:s slumpmässiga variabler. Genom linjäritet i förväntningarna drar vi slutsatsen att: och genom Lemma 2.2 har vi den slumpmässiga variabeln: I detta avsnitt utforskar vi relationen mellan differentiell integritet och koncentrerad differential. Vi visar att alla differentialt privata algoritmer också är koncentrerade differentialt privat. Vårt huvudsakliga bidrag här är en förfinad övre gräns på den förväntade integritetsförlusten av differentialt privata algoritmer: vi visar att om M är ε-DP, då dess förväntade integritetsförlust är endast (i stort sett) ε 2 /2 (för liten nog ε). Vi visar också att integritetsförlusten slumpmässiga variabeln för någon ε-DP algoritm är subgaussian, med parameter τ = O(ε): Theorem 3.5 (DP  på CDP). Låt M vara någon ε-DP algoritm. Därefter är M (ε · (e ε − 1)/2, ε)-CDP. Bevis. Eftersom M är (ε, 0)-differentiellt privat, vet vi att integritetsförlust slumpmässig variabel alltid begränsas i magnitud av ε. Den slumpmässiga variabeln som erhålls genom att subtrahera den förväntade integritetsförlusten, kalla den μ, har därför ett medelvärde på noll och ligger i intervallet [−ε − μ, ε − μ]. Det framgår av Hoeffdings Lemma att en sådan avgränsad, centrerad, slumpmässig variabel är (ε − μ − (−ε − μ))/2 = ε-subgaussian. Lemma 3.6 (Hoeffdings Lemma). Låt X vara en noll-medel slumpmässig variabel sådan att Den största utmaningen är därför att begränsa förväntan, nämligen kvantiteten D KL (D-D ′ ), där D är fördelningen av M(x) och D ′ är fördelningen av M(y), och x, y är angränsande databaser. I [DRV10] visades det att: Vi förbättrar denna gräns, erhålla följande förfining: Beviset för Theorem 3.5 följer från Lemma 3.8. För att bevisa Lemma 3.8 introducerar vi begreppet antipodal distribution: Vi använder sedan följande två lemmas om maximalt divergerande distributioner (de bevis som följer nedan) för att bevisa Lemma 3.8: Bevis på Lemma 3.9. Låta ε =  påse (D, D ′ ). Vi konstruerar M och M ′ iterativt från D och D ′ genom att räkna över varje x X. För varje sådant x lägger vi till ett nytt element s x till stödet. Tanken är att massan av x i D och D ′ kommer att vara "split" mellan x och s x i M och M ′ (respektive). Denna uppdelning kommer att säkerställa att sannolikheterna för s x i M och i M ′ är identiska, och sannolikheten för x i M och M ′ är "maximalt olika". Vi kommer att visa att "bidrag" av x och s x till KL skillnaden från M till M ′ är minst lika stor som bidraget av x till KL skillnaden från D till D ′. Lemman följer sedan. Vi fortsätter med den fullständiga specifikationen av denna "split" och formaliserar sedan ovanstående intuition. För x X, ta p x = D ′ [x]. Eftersom (D, D ) = e ε, måste det finnas α  på [-1, 1] s.t. D[x] = e α·ε · p x. Vi inför en ny punkt s x i stödet och anger vikten av M och M ′ på x och s x enligt följande: = e tecken(α)·ε · p x · e α·ε − 1 e tecken(α)·ε − 1 = p x · (1 - e α·ε − 1 e tecken(α)·ε − 1 ) = p x · (e α·ε − 1 + 1) · e α·ε − 1 e tecken(α)·ε − 1 e tecken(α)·ε − 1 ) = p x · (e α·ε − 1) · e tecken(α)·ε − 1 e tecken(α) · 1 + 1) · e α·ε − 1 e tecken(α)·ε − 1 e tecken (α)·ε − 1 ) = p x · (e α·ε − (e tecken(α)·ε − 1) · e α·ε − 1 e tecken(α) · 1 e tecken(α) · 1 e) Dessutom är M och M ′ antipodal (M, M ′ ) = ε = (D, D ′ ). Distributionerna M och M ′ uppfyller således villkoren för lemma. Slutligen betonar vi att genom ovanstående har vi  på x X, M [Vi jämför nu KL divergensen från D till D ′ med divergensen från M till M ′.
Dwork har föreslagit begreppet differentiell integritet för integritetsbevarande i statistiska datauppsättningar REF.
Concentrated Differential Privacy
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}